规则评估方法与数据质量挖掘系统的研究 刘波

规则评估方法与数据质量挖掘系统的研究刘波1，潘久辉1，刘佩珊2(1.暨南大学计算机科学系，广东广州，510632；2.广东拓思软件科学园有限公司，广东广州，510663）摘要:为了从数据挖掘结果中获得真正有用的规则，探讨了评估规则的度量，提出了度量关系的新概念，并应用于发现与评估有用规则集的算法中。经过度量函数之间的相关分析，确定适合的度量，并据此对规则进行兴趣度评估，指导用户对有用规则的选择。此外，为了解决数据集成系统中存在“垃圾”数据的问题，提出了数据质量挖掘与控制系统框架，将数据挖掘规则应用到了数据质量管理中。使用经过评估筛选得到的规则，能够检测数据库中异常、不完整等数据，解决数据集成过程中部分数据质量问题。通过企业信息集成实例，说明了规则评估及应用方法的有效性。关键词：规则评估；度量函数；数据质量挖掘；集成系统中图分类号：TP302文献标识码：AStudyofruleevaluationmethodanddataqualityminingsystemLIUBo1,PANJiu-hui1,LIUPei-shan2(1.DepartmentofComputerScience,JinanUniversity,Guangzhou,Guangdong,510632,China;2.GuangdongTopsSoftwareScienceParkCo.Ltd.,Guangzhou,Guangdong,510663,China)Abstract：Inordertogetactuallyusefulrulesfromdataminingresults,itstudiedmeasuresforevaluatingrules,anddefinedthenewconceptofmeasurerelationship,whichwasappliedinthealgorithmfordiscoveringandevaluatingusefulrules.Bycorrelativeanalysisofmeasurefunctions,thesuitablemeasuresforruleinterestingnessevaluationcanbedetermined,soastoguideuserstochooseusefulrules.Inaddition,forsolvingtheproblemof“garbage”datainintegrationsystems,theframeofdataqualityminingandcontrolsystemwaspresented,whichapplieddataminingrulesindataqualitymanagement.Usingtheevaluatedandselectedrules,theabnormal,incompletedatacanbedetected,soastosolvesomedataqualityproblemsindataintegration.Theexampleofanenterpriseinformationintegrationshowstheeffectivenessoftherules’evaluationandtheapplicationmethod.Keywords：ruleevaluation;measurefunction;dataqualitymining;integrationsystem基金项目：国家863计划项目(2006AA01Z190),广东省教育部产学研结合项目(2007B090400095)。FoundationItem:ProjectsupportedbytheNationalHigh-Tech.R&DProgram,China(No.2006AA01Z190),andtheProductionandResearchProgramofMinistryofEducation,GuangdongProvince(No.2007B090400095)。作者简介：刘波(1965-)，女，湖南人，暨南大学计算机科学系副教授，主要从事数据库与信息集成、数据挖掘、软件工程等研究。E-mail:[e-mail]；潘久辉(1956-)，男，湖南人，教授，硕士研究生学历，主要研究方向为数据库、数据流处理、信息集成与网格计算等，Email:[e-mail]。0引言在大型数据库中，存在许多潜在的知识或模式，可以用规则这种典型的形式表达。许多数据挖掘算法通常利用一些统计度量，获取需要的规则或加快规则的挖掘。同样，在规则使用时，也必须考虑评估规则的度量，因为挖掘得到的规则往往仅一小部分是有用的。规则评估方法是比较与选择规则的基础，目前涉及这方面的研究尚不完善。已有一些关于规则度量的研究工作[1][2][3]提出了许多度量，用于评估所发现规则的兴趣或效用性，如：支持度、置信度、准确率、灵敏性、特效性、新颖度等。这些度量从不同角度反映规则的性质，通过统计满足不同特性的数据集得到。由于评估度量较多，选择不同度量可能得到不同评估结果，需要一套规范化的规则选择机制与用户的主观选择相结合，才能获得真正适用的规则。数据质量挖掘（DataQualityMining，DQM）[4]以度量及改善数据质量为目标，应用数据挖掘技术监测、量化、解释、纠正数据库中的错误。显然，要完整、准确地解决数据质量问题，缺少不了特定应用领域知识支持，需要人工参与分析，但采用自动分析的数据挖掘方法可以为减少人工分析、提高分析的准确度提供有效支持,是数据清洗工具扩充与发展方向。已有一些工作采用数据挖掘的方法解决部分数据质量问题[4-6]，如：发现与纠正错误数据[4]、填充空值[4]等。但这些工作没有强调规则评估问题，缺乏对模型或规则的评估度量研究，没有考虑对挖掘结果进行有效地过滤与选择。本文从规则度量关系及其之间相关分析的角度出发，探究了挖掘规则的度量评估方法，并应用到数据集成过程的数据质量管理中。通过规则评估系统过滤掉无用规则，得到真正有用的规则，以解决单关系或多关系数据集中存在的部分数据质量问题。1规则与评估度量的定义数据挖掘可以发现大量新颖的、有趣的、潜在的规则，包括预测型规则和描述型规则等。存在许多评估规则的度量，分为客观度量和主观度量；统计、结构度量和语义度量[2]。下面基于关系型数据表，参考文献[3]和文献[7]，给出了本文拟研究的规则形式和常用的统计度量定义。定义1规则r的形式为B→H，B称作规则的前件或前提，H是规则的结论。对于预测型的分类规则，B是一些属性-值对的连接，H为一个类型属性-值对。对于描述型的关联规则（或相关规则），B和H均可为一些属性-值对的连接。按照文献[8]的观点，一个数据集中的概念是形式如(Φ，m(Φ))的对，其中Φ是概念的内涵，m(Φ)是概念的外延，即：Φ是m(Φ)的一个描述，m(Φ)是满足Φ的实例集。为简单表示起见，在下面的度量定义中，规则R=B→H中的B与H即表示一个或一组概念的描述，又表示满足B或H描述的数据子集（或实例集）。对于规则r=B→H，假设：B表示B为真的实例集，B是B的补集（即B为假的实例集）；同样，H表示H为真的实例集，H是H的补集。HB表示H∩B，HB表示H∩B，P(HB)表示数据集实例中H和B同时为真的概率，P(H|B)表示B为真的实例集中H为真的概率等。这里，概率表示集合的频度，如NnP)()(φφ=，其中：N为所有实例数目，n(Φ)为满足Φ为真的实例数目。定义2规则r的支持度(support)是：Sup(r)=P(HB)(1)定义3规则r的准确率(Accuracy)或置信度(confidence)是：Acc(r)=Conf(r)=P(H|B)＝P(HB)/P(B)(2)定义4规则r的负可靠度(Negativereliability)是：NegRel(r)=P(H|B)=P(HB)/P(B)(3)定义5规则r的灵敏性(Sensitivity)是：Sens(r)=P(B|H)=P(HB)/P(H)(4)定义6规则r的特效性(Specificity)是：Spec(r)=P(B|H)=P(HB)/P(H)(5)定义7规则r的新颖度(Novelty)是：Nov(r)=P(HB)-P(H)P(B)(6)上述定义将预测型规则和描述型规则采用统一的方式表示；规则的支持度来源于关联规则的度量，也称为频度(frequency)；分类规则的准确率与关联规则的置信度的定义一致；灵敏度也称真正率；特效性也称真负率；新颖度表示H和B的相关程度。2规则评估系统给定一个数据库，往往隐藏着大量规则，其中仅一部分对应用或决策起指导作用，这一部分规则的筛选取决于一个或一组规则评估度量值。理论上讲，如果不结合用途去评价哪种度量好坏是没有意义的[2]。但是，有必要建立一个通用的评估规则系统，用于解释、比较不同的规则。2.1度量关系的基本概念定义8多值依赖关系D是序偶r,m的集合，其中r∈R，m∈M，R是符合定义2.1所规定形式的规则集，M为某种特定度量-值对集合，记为：D:R→M，也称为度量关系。例如：(r1,(Sup,0.02))、(r1，(Conf,0.98))、(r1，(Nov,0.01))均为关系D中的实例，表示规则r1的支持度为0.02、置信度为0.98、新颖度为0.01。定义9给定挖掘发现的规则集R和度量函数f，θ为依据度量值确定的规则之间的比较关系。假定度量函数f取值越大，规则质量或兴趣度越高，则规则之间存在以下三种比较关系：（1）“大于”或“优于”关系f：如果f(r1)f(r2)，则r1fr2；（2）“小于”或“劣于”关系p：如果f(r1)f(r2)，则r1pr2；（3）“等于”或“相等”关系＝：如果f(r1)＝f(r2)，则r1＝r2。例如：给定两个规则r1,r2∈R和置信度函数Conf，如果Conf(r1)Conf(r2)，则r1fr2，表示r1优于r2。同一种比较关系θ具有传递性：r1θr2，r2θr3⇒r1θr3值得注意的是：如果某度量函数f取值越小，规则质量越高，则为了统一描述比较关系，将度量函数f进行适当的变换（如：求倒数等），使得变换后的函数f’满足：取值越大，规则质量越高的要求。定义10给定挖掘发现的规则集R、度量函数集F，比较关系符集S，（R，F，S）的组合称为规则评估系统。假设在一个规则评估系统中，R＝{r1,r2,r3,r4,r5}，F＝{Sup，Conf，Nov}，S＝{f，p，＝}，可能存在以下情况：(R，Sup，r1fr2fr3fr4fr5)(R，Conf，r1fr2fr4fr3=r5)(R，Nov，r1pr2pr3＝r4pr5)也就是说，在同一个规则评估系统中，采用不同的评估度量可能得到截然不同的规则质量或兴趣序列。因此，需要一种度量函数分析机制，结合应用领域或用户的规则评判准则，才能得到有实际意义的规则序列。2.2规则度量函数之间的相关性分析定义11给定规则集，ri、rj为规则集中任意两条规则，满足以下条件之一，则度量函数f1与f2正相关。f1(ri)f1(rj)⇔f2(ri)f2(rj)f1(ri)f1(rj)⇔f2(ri)f2(rj)f1(ri)＝f1(rj)⇔f2(ri)＝f2(rj)定义12给定规则集，ri、rj为规则集中任意两条规则，满足以下条件之一，度量函数f1与f2负相关。f1(ri)f1(rj)⇔f2(ri)f2(rj)f1(ri)f1(rj)⇔f2(ri)f2(rj)若度量函数f1与f2不满足定义10和定义11，则它们无关。定理1如果f1与f2正相关及f2与f3正相关，则f1与f3正相关。证明因为f1与f2正相关，f2与f3正相关，存在以下推导：由f1(ri)f1(rj)⇒f2(ri)f2(rj)f2(ri)f2(rj)⇒f3(ri)f3(rj)可得f1(ri)f1(rj)⇒f3(ri)f3(rj)反之，由f3(ri)f3(