（计算机应用技术专业论文）基于粗糙集理论的知识发现方法研究.pdf

摘要 随着信息技术的飞速发展，数据库的存储量变得越来越大，以至于产生了“数据爆 炸但知识贫乏”的情形，所以对知识发现技术的研究具有非常重要的实际意义。目前知 识发现面临不能有效地处理不完备、不确定性数据以及知识的可解释性比较差的问题， 而粗糙集理论是一种处理模糊的、不确定性知识的数学工具，不需要先验知谚 和外界参 数。因此，采用粗糙集进行知识发现方法研究具有十分重要的意义。 属性约简和规则获取是粗糙集理论中两个重要的方面。本课题根据胡可云属性频率 的思想，提出属性加权频率算子( a t t r i b u t ew e i g h tf r e q u e n c yf u n c t i o n ，a w f f ) ，将其作为 启发式信息；针对目前属性约简算法效率比较低的情况，将a w f f 应用到属性约简中， 同时结合近似精度和强等价集，提出基于属性加权频率算子的属性约简算法( a t t r i b u t e w e i g h tf r e q u e n c yf u n c t i o u t t r i b u t er e d u c t i o n ，a w f fa r ) ，在保证得到一个属性约简集 的同时，提高算法的效率，并解决算子值相等的情况下不能区分哪个属性更为重要的问 题；针对规则获取效率不高和产生的规则存在冗余性的问题，提出基于属性加权频率算 子的值约简算法( a t t r i b u t ew e i g h tf r e q u e n c yf u n c t i o n - v a l u er e d u c t i o n ，a w f f _ v r ) ，从 值核入手，以a w f f 作为启发式信息进行规则提取，采用支持度和置信度去除冗余规 则，不仅提高算法的效率，而且获得长度比较短、覆盖度比较高的规则。 通过理论分析和在u c i 数据集上的实验验证证明，本课题提出的a w f fa r 属性 约简算法和a w f fv r 启发式值约简算法都达到了预期效果，减少了算法运行的时间， 最终获得了有效的知识规则，对今后进一步的研究和实际应用具有重要的意义。 关键词：知识发现，粗糙集，属性约简，值约简，规则获取 r e s e a r c ho fk n o w l e d g ed i s c o v e r ym e t h o d b a s e do i lr o u g hs e tt h e o r y n i uq i u l i ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rd u a ny o u x i a n g a n da s s o c i a t ep r o f e s s o rg o n ga n a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , d a t a b a s es t o r a g ei se x p a n d i n g l a r g e ra n dl a r g e r , t h u sd e v e l o p i n gt h ep h e n o m e n o no f “d a t ae x p l o s i o nb u tl a c ko fk n o w l e d g e ” t h e r e f o r er e s e a r c ho nt h et e c h n o l o g yo fk n o w l e d g ed i s c o v e r yi nd a t a b a s ei sv e r yi m p o r t a n t n o wk n o w l e d g ed i s c o v e r yi nd a t a b a s ef a c e sd e a l i n gw i t hi n c o m p l e t ea n du n c e r t a i nd a t a u n e f f i c i e n t l ya n dt h ep o o re x p l a n a t i o no fk n o w l e d g e r o u g hs e tt h e o r yi sam a t h e m a t i c a lt o o l w h i c hd e a l sw i t hv a g u ea n du n c e r t a i nk n o w l e d g e i td o e sn o td e e dp r i o rk n o w l e d g ea n d e x t e r n a lp a r a m e t e r s s oa p p l y i n gr o u g hs e tt h e o r yt ok n o w l e d g ed i s c o v e r yi nd a t a b a s eh a s v e r yi m p o r t a n ts i g n i f i c a n c e a t t r i b u t er e d u c t i o na n dr u l ee x t r a c t i o na let w oi m p o r t a n ts t a g e si nr o u g hs e tt h e o r y t h i s p a p e rb a s e do nt h et h o u g h to fh uk e y u n sa t t r i b u t ef r e q u e n c y , p r o p o s e sa t t r i b u t ew e i g h t f r e q u e n c yf u n c t i o n ( a w f f ) a sh e u r i s t i ci n f o r m a t i o n ；a g a i n s t t h ep r o b l e mo ft h el o w e f f i c i e n c y o fa t t r i b u t e r e d u c t i o n ，t h i sp a p e rp r o p o s e sa t t r i b u t ew e i g h tf r e q u e n c y f u n c t i o n a t t r i b u t e r e d u c t i o na l g o r i t h m ( a w f f _ a r ) w h i c ha p p l i e sa w f ft oa t t r i b u t e r e d u c t i o nw i t ha p p r o x i m a t ea c c u r a c ya n ds t r o n ge q u i v a l e n ts e t t h ea l g o r i t h mc a ng e ta n a t t r i b u t er e d u c t i o ns e t ，i m p r o v et h ea l g o r i t h m se f f i c i e n c ya n ds o l v e st h ep r o b l e mt h a tc a nn o t d i s t i n g u i s hw h i c ha t t r i b u t ei sm o r ei m p o r t a n tw h e n t h ev a l u e so fa w f fa r ee q u a l ；a g a i n s tt h e p r o b l e mt h a tt h ee f f i c i e n c yo ft h er u l ee x t r a c t i o ni s n o th i g ha n dt h eg e n e r a t e dr u l e sa l e r e d u n d a n t ，t h ep a p e rp r o p o s e sa t t r i b u t ew e i g h tf r e q u e n c yf u n c t i o n v a l u er e d u c t i o na l g o r i t h m ( a w f f - - v r ) t h ea l g o r i t h ms t a r t sa tv a l u ec o r e ，m a k e sa w f f a sh e u r i s t i ci n f o r m a t i o na n d u s e ss u p p o r ta n dc o n f i d e n c et or e m o v et h er e d u n d a n tr u l e s t h ea l g o r i t h mn o to n l yi m p r o v e s t h ee f f i c i e n c yb u tg e t st h er u l e sw h i c hh a v et h es h o r tl e n g t ha n dt h eh i g hc o v e r a g e t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t so nu c id a t as e tp r o v et h a ta w f f - a ra n d a w f f v ra l g o r i t h m sc a na c h i e v et h ee x p e c t e dr e s u l t s ，r e d u c et h ea l g o r i t h m so p e r a t i n gt i m e ， a n dg e te f f e c t i v ek n o w l e d g er u l e s t h ea l g o r i t h m sh a v ei m p o r t a n ts i g n i f i c a n c ef o rf u t u r e s t u d i e sa n dp r a c t i c a la p p li c a t i o n s k e yw o r d s ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，r o u g hs e t ，a t t r i b u t er e d u c t i o n ，v a l u er e d u c t i o n ， r u l ee x t r a c t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究二 作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对 研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：乒币0 阳同期：y 圩年j 月彤f l 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和 电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学 位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印， 将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手 段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：盐趣缝 指导教师签名： 闩期：矽蜉年j - 月名同 同期：护p 年，月多6 同 中罔彳i 汕人学【华东) f - 贝l ：学位论义 1 1 引言 第一章绪论 随着信息技术的高速发展，数据库的存储量越来越大，并且数据与信息系统中的不 确定性也更加显著。但由于一直缺乏挖掘隐减知识的有效手段，最终形成了“数据爆炸 但知识贫乏”的现象。人们迫切希望从这些海量杂乱的数据背后挖掘出隐藏着的信息和 数据之间的联系，提取有效的规则，做出正确的决策。因此，知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) 技术也就应运而生。 目前，知识发现的方法很多，较常采用的是贝叶斯网络、证掘理论、模糊集、粗糙 集( r o u g hs e t ，r s ) 。前三种方法都要依靠领域专家的知以，而且个人偏好也会直接影响 所发现的规则。而粗糙集理论不仅能够解决一些模糊的、不确定的粗糙数据，得到有效 的知识规则，同时能发现属性问的依赖关系并对所得的结果进行简明易懂的解释，算法 简单、易于操作。这就使得粗糙集理论成为当今的研究热点，并且被广泛地应用于数据 挖掘、人工智能、模式识别、故障诊断和专家系统等领域。 应用粗糙集获取知识一般经过两个过程，即属性约简和规则获取。首先对决策表中 的条件属性进行约简，然后调整决策表，对决策表中的属性值进行约简，得到最简决策 表，最后把决策表中的实例对象转换为相应的舰则。 1 2 课题的提出及意义 一个决策表的知识约简一般不是唯一的，人们期望找到具有最小属性个数的约简， 即最小约简。然而w o n gs k m 和z i a r k ow 已经证明找出一个决策表的所有约简和最 小约简是n p h a r d 问题1 。目前，在令人可接受的时间内获得约简的通常做法是基于启 发式知识的约简方法。比如基于属性重要性的i 羽、基于信息熵的3 1 、基于属性频率1 4 】的 等启发式约简算法。国内外学者在这方面做了大量的研究，但是仍然没有一种非常有效 的方法，因此寻找快速有效的约简算法及其增量版本具有重要的意义。 从决策表中提取出有用的规则可以方便人们快速、准确地做出决策。目前，一般的 规则获取算法大都对决策表进行值约简，然后根据约简后的决策表提取出相应的规则。 其中，启发式值约简算法提供了一般值约简的思想，能够获取有效的规则，但在算法效 率方面还有待提高。胡玉荣掣5 j 对启发式值约简算法进行了改进，但是算法的时间复杂 第一帝绪论 度比较大，为o l c l 2 i u i2 ) ，当条件属性和实例对象数目都比较大的时候，计算量会明显 增大。 综上，本课题在比较分析各种算法的基础上，针对目自玎属性约简算法效率比较低的 情况，提出基于属性加权频率算子的属性约简算法，在保证得到一个属性约简集的同时， 提高算法的效率；针对规则获取效率不高和产生的规则存在冗余性的问题，提出基于属 性加权频率算子的值约简算法，从大量的数据中提取出有效的、分类精度较高的知识规 则提高知识发现的整体效率，为知识发现技术的研究和应用提供一定的帮助。 1 3 国内外研究现状 1 3 1 知识发现研究现状 知识发现是从数据集中抽取和精化新的模式【6 】。知识发现的范围涉及到很多方面， 如经济、工业、农业、军事、社会、商业、科学的数据或卫星观测到的数掘。知识发现 的结果可以表示为法则、规则、科学舰律、方程和概念网等。 1 9 8 9 年，f a y y a d 首先提出 k d d ，他把k d d 定义为“k d d 足从数据集中识别出有 效的、新颖的、潜在可用的，以及最终可以理解的模式的非平凡过程” r l 。k d d 主要采 用机器学习算法或统计方法进行知识学习，一般将k d d 中进行知识学习的阶段称为数据 挖掘( d a t am i n i n g ) 。数据挖掘足k d d 中的一个非常重要的处理步骤，人们往往不加区分 地使用两者。一般地，工程应用领域中多称数据挖掘，而研究领域中人们则多称为数据 库中的知识发现。数据挖掘经常被置于更广阔的k d d 的大背景下。 k d d 是数据库与人工智能相结合的产物。有关k d d 的问题和术语是1 9 8 9 年在底特 律召开的第十一届国际人工智能联合学术会议( i j c a i ) 上首次提出的，在这届学术会议上 举行了以k d d 为主题的学术研究会。在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年相继举行了k d d 专题 研究会，集中讨论数据统计、海量数据分析算法、知识表示以及知识运用等问题。随着 k d d 在学术界和工业界的影响越来越大，k d d 组委会于1 9 9 5 年把专题讨论会更名为国 际会议，并在加拿大蒙特利尔召丌了第一届知识发现和数据挖掘r 嗣际学术会议，此后每 年召开一次。1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议不仅进 行了学术讨论，并且有3 0 多家软件公司展示了不同的数据挖掘软件产品，并且大多都已 经得到相应的应用。 美国人工智能协会主办的k d d 国际研讨会己召丌了7 次，人数由- - e 十人发展到七 2 中国油人学( 1 仁东) 硕l ：学位论义 八百人，论文收录比例从2 ：1 至l j 6 ：l ，研究重点也逐渐从发现方法转向系统应用，并且注 重多种发现策略和技术的集成，以及多种学科之| 白j 的相互渗透。其他内容的专题会议也 将数据挖掘和k d d 列为议题之一。目前，k d d 不仅被许多研究人员霜作足数据库系统 和机器学习方面一个重要的研究课题，而且被许多工商界人士看作是一个能带来巨大回 报的重要领域。 虽然k d d 发展比较迅速，并且在决策支持等业务中获得较多成功的应用，但是目 前还存在许多困难以待解决。 1 大数据集问题：现实中的数据库已经越来越大，如何降低算法的执行效率和复杂 度，从众多数据中寻找最有用的数据一直是困扰k d d 的一个问题。 2 噪音数据与不完备数据的问题：在较大规模的数据集中，由于主观或客观的原因 ( 比如数据采集或录入的错误) ，不可避免地会出现一些噪音问题。噪音数据会直接影响 最后的决策效果。同时，数据的不确定性和模糊性也给知彭 发现带来了很大的困难。 3 知识发现的可解释性：k d d 的过程中往往需要用户的参与，并且要求最终的结果 或者规则易于理解，所以决策结果的可理解性也会影响到用户对k d d 技术的评价。 由以上可以看出，k d d 技术是数据库技术方面一个重要的、热门的研究问题。如何 从数据库中发现有用的知识，就变得尤为重要。羊f l 糙集能够处理不确定性、不精确性知 识，进而获取到有效的、符合人们推理习惯的知识规则。所以，本文将采用粗糙集作为 知识发现的方法来获取有效的知识规则。 1 3 2 粗糙集理论研究现状 粗糙集理论及其在k d d 中的应用是一个较新的研究领域，它提供了丰富的处理不 确定性和模糊性数据的方法与工具，对k d d 过程具有较强的支持。1 9 8 2 年，z p a w l a k 发表了经典论文r o u g hs e t s ，宣告了粗糙集理论的诞生。1 9 9 0 年前后，粗糙集理论在机 器学习与知识发现、数据挖掘、决策支持与分析等方面被广泛应用，逐渐引起了世界各 国学者的广泛关注。1 9 9 1 年，p a w l a k 教授出版的第一本关于粗糙集的专著( ( r o u g hs e t s ： t h e o r e t i c a la s p e c t so fr e a s o n i n ga b o u td a t a ) ) 1 8j 和1 9 9 2 年s l o w i n s k ir 主编的关于粗糙集应 用及其相关方法比较研究的沦文集【9 】的日j 版，推动了困际上对粗糙集理论与应用的深入 研究。 1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召开，以后每隔一年召开一 次粗糙集与软计算的国际研讨会；1 9 9 8 年在波兰召丌了第一届粗糙集与当前的计算发展 3 第一章绪论 ( t h elt hi n t e r n a t i o n a lc o n f e r e n c eo nr o u g hs e t s a n dc u r r e n tt r e n d si n c o m p u t i n g ， r s c t c 9 8 ) 国际正式会议，山此每两年举行一次，第五届( r s c t c 2 0 0 6 ) 已了：2 0 0 6 年在同 本举行【l o 】。 目前国际上研究粗糙集的一些高校和研究机构丌发了一些粗糙集的模型系统和实 用系统【1 。波兰华沙大学和挪威科技大学联合丌发了一个基于粗糙集理论框架的数据分 析工具包r o s e t t a t l 2 1 3 1 ，包括了计算核和图形用户界面。r o s e t t a 实现了对数据挖掘和知识 获取的支持，包括数据的预处理、属性约简和规则产生以及对得到规则的验证和分析。 r o s e t t a 设计的目的是要作为基于不可辨识关系模型的通用工具，而不是为某个特点的应 用领域设计的专用系统。美国肯萨斯大学开发的一套基于粗糙集的经验学习系统l e r s ， 能从大量经验数据中抽取规则。l e r s t 已被美国国家航空航天管理局( n a s a ) 的j o h n s o n 空间中心采用，作为专家系统丌发工具，为f r e e d o m 号空间站上的医疗决策服务。美国 环境保护署资助的一个项目中也采用了l e r s 。除上述经典系统外，粗糙集研究人员还 开发了很多其他粗糙集系统，如波兰工业大学的r o s e t ，挪威t r o l ld a t ai n c 的r o u g h e n o u 曲和加拿大r e 百n a 大学的k d d r 【1 4 】等。 在粗糙集领域产生了许多有效的算法。粗糙集的创始人z p a w l a k 提出的简单数据分 析法，就是利用人工进行分析信息系统的决策表，依次进行属性和属性值进行约简。但 是这种方法是一个典型的非形式化的算法，不容易机械化，在实际中很难应用1 3 j 。 s k o w r o n i m 】提出的可辨识矩阵方法，通过引入代数知识，把决策表转换为可辨识矩 阵，从而在可辨识矩阵上进行操作。同时，s k o w r o n 严格证明，可辨识矩阵原理与p a w l a k 的粗糙集理论是等价的【l7 1 。该算法的特点就是简单、容易理解，在实际中容易实现，但 是在生成可辨识矩阵的中问环节，时间和空问的浪费比较严重。 在可辨识矩阵的基础上，文献【1 8 】对可辨识矩阵算法进行了改进，将可辨识矩阵的元 素按包含属性的个数分类，个数小的元素所含属性的分类能力不容易被其他属性代替。 由于求取决策表的所有约简和最小约简是n p h a r d 问题，所以考虑采用启发式的方 法进行数据约简。j e l o n e k i 旧j 提出了基于属性重要性的算法，可以获得最小或次小约简， 但是当数据量比较大时，就会增加算法的计算复杂度，降低算法的效率。苗夺谦等【2 0 】 提出的基于互信息的知识相对约简，多数情况下能够得到决策表的最小约简，但在决定 如何扩展候选属性约简集时，必须对条件属性进行多次组合，需要很大的计算量。 h o r a f a ( h e u r i s t i co p t i m a lr e d u c tf i n d i n ga l g o r i t h mb a s e do nf r e q u e n c i e so fa t t r i b u t e s ) 算法【4 l 利用反映可辨识矩阵特性的属性频率函数来进行计算。大多数情况下，能够在多项 4 冈t i 油人学( 。仁东) 顺i j 学位论文 式复杂度下得到决策表的最小约简，但是当数据集比较大的时候也不能达到有效的约简 集。r a y m o n d t 2 i 】介绍了粗糙集与生命周期法的结合在规则获取方面的应用，在环境诊断 及决策制定中有一定的应用前景，但是有一定的应用局限性。王清毅等【2 2 j 提出知识库中 面向规则的约简算法，先找到各条规则的核值，对核值规则进行检验，若该核值规则协 调一致，则其为约简规则，否则，对核值外的条件属性依次加入，直到找到所有约简规 则。但是其计算量比较大，算法的效率不高。 1 4 研究目标和主要研究内容 针对目前数据的特点和数据库技术发展的需求，对基于粗糙集理论的知识发现方法 进行研究。结合粗糙集理论本身的特性，提出一种有效的属性约简算法和值约简算法， 最后得到符合人们需求和推理习惯的知识规则，提高算法的效率。 本课题的主要研究内窬包括以下几个方面： ( 1 ) 研究和分析知识发现以及粗糙集理论的研究现状，针对知识发现面临的问题提 出基于粗糙集理论的知识发现方法，并对主要过程提出相应的解决方法。 ( 2 ) 深入分析各种启发式属性约简算法，并对其进行比较，得出各种算法的优缺点。 ( 3 ) 在理论分析的基础上，根据胡可云属性频率的思想，提出属性加权频率算子 ( a t t r i b u t ew e i g h tf r e q u e n c yf u n c t i o n ，a w f f ) ，以作为启发式信息来提高算法的效率。 ( 4 ) 针对目前属性约简算法效率比较低的情况，将a w f f 应用到属性约简中，同时 结合近似精度和强等价集，提出基于属性加权频率算子的属性约简算法( a t t r i b u t ew e i g h t f r e q u e n c yf u n c t i o na t t r i b u t er e d u c t i o n ，a w f fa r ) ，在保证得到一个属性约简集的同 时，提高算法的效率，解决算子值相等时候的不能区分哪个属性更为重要的问题，同时 在u c i 数据集上进行实验验证，达到预期效果。 ( 5 ) 比较各种值约简算法的优缺点，对启发式值约简算法进行改进，提出基于属性加 权频率算子的值约简算法( a t t r i b u t ew e i g h tf r e q u e n c yf u n c t i o n v a l u er e d u c t i o n ， a w f f _ _ v r ) ，对冗余规则进行约简。通过实验验证和结果比较，证明所提算法的高效性 和准确性，能满足人们对知识获取的要求。 1 5 论文的组织结构 本文围绕知识发现和基于粗糙集理论的相关理论算法展开论述，在算法研究的基础 上进行实例验证，组织结构如下： 5 第帝绪沦 第一章绪论。 主要介绍本课题的提出、目的及意义，对当前知谚 发现和料糙集理论的国内外研究 现状进行研究，并提出基于粗糙集理论研究的知识发现方法的内容与思路，阐明了本文 的研究意义和学术价值。 第二章知识发现与粗糙集理论。 系统分析知识发现的定义、过程、方法和现在所面临的困难。同时，重点研究粗糙 集理论产生的背景、概念和特点等相关理论知识。 第三章属性约简算法。 本章对目前比较重要的启发式属性约简算法进行研究分析，并对这几个启发式约简 算法的优缺点进行比较。 第四章基于a w f f 的属性约简算法。 基于属性频率的思想提出a w f f 算予，以此作为启发式信息；针对目前属性约简算 法效率不高的问题，提出a w f fa r 算法，在保持分类能力不变的前提下，得到属性的 一个约简，通过对时间复杂度进行分析，能够减少运行时间，有效地提高算法效率。同 时，通过将此算法在u c i 数据集上进行十交叉验证验证，证明此算法能够保证得到属性 约简集，并且有效地提高运行效率。 第五章基于a w f fv r 的规则获取方法。 深入研究分析现有值约简算法，比较现有算法的优缺点，在一般启发式值约简的基 础上提出相应的a w f fv r 启发式值约简算法，提高算法的效率，获取有效的知识规则。 通过实验验证和结果比较，证明所提算法具有一定的高效性和准确性，能够满足人们对 知识获取的要求。 结论 总结本文的工作和创新点，对于提山的属性约简算法和值约简算法进行归纳、总结， 针对本课题中未完成的问题做下一步的规划。 6 巾圈油人学( 1 扛东) 硕一l j 学化论义 第二章知识发现与粗糙集理论 本章主要研究了知识发现以及粗糙集理论的有关概念和特点，依据知识发现技术所 面临的困难提出基于粗糙集理论的方法研究，并对粗糙集理论的应用和前景进行概括和 分析。 2 1 知识发现概述 2 1 1 知识发现的定义 知识发现是从数据集中抽耿和精化新的模式。知识发现的范围非常广泛，涵盖经济、 工业、农业、科技、教育、商业、军事等诸多领域。数据的形态有数字、符号、声音、 图像等，数据的组织方式也各不相同，有结构的，半结构的，无结构的。知识发现的结 果可以表示成多种形式，包括规则、法则、科学规律或概念网。 定义1 ：知识发现是识别出存在于数据库中的有效的、新颖的、具有潜在价值乃至最 终可理解的模式的非平凡过程【6 1 0 定义2 ：数据挖掘是指从数据库中大量的数据中揭示出隐含的、先前未知的并有潜在 价值的信息的非平凡过程【6 1 。 从上面的定义可以看出，知识发现是从数据库中发现知彭 的全部过程，而数据挖掘 是全部过程的一个特定的、关键的步骤，是指应用特定算法从数据中提取模式。知识发 现中的其它步骤则是用来保证从数据中挖掘得到的知识是有用的知识，否则，盲目挖掘 容易导致所发现的模式是无意义的。事实上，在现今文献中的大多数场合，这两个术语 的使用是不加区别的。 2 1 2 知识发现的过程 知识发现既包括对数据、模式、方法等的研究，也包括处理过程、知识的有效性、 可信度研究。知识发现的研究对象包括：数据、模式、处理过程、可信度、新颖、潜在 作用等等。具体过程见图2 1 7 第二帝知识发现相【糙! l 三理论 匝园厂l j 歹7 多八。螽犷i 。 、，_ ! i - 剧! l 固 ? ，夕i 、 一7 转化教据 辨，据 卜= = 二二1 ：。7 目标致据 l j 图2 - 1k d d 过程 f i 9 2 1 t h ep r o c e s so fk d d f a y y a d 等人给出的k d d 全过程的五个步骤为f 7 】= 1 、数据选择：确定发现任务的操作对象，即目标数据，它是根据用户的需要从原 始数据库中抽取的一组数据； 2 、数据预处理：一般包括消除噪声、推导计算确值数掘、消除重复记录、完成数 据类型转换等； 3 、数据转换：其主要目的是消减数据维数或降维，即从初始特征中找出真正有用 的特征以减少数据开采时要考虑的特征或变量个数； 4 、数据挖掘：这一阶段包括确定挖掘任务、目的、选择挖掘方法和实施数据挖掘； 5 、模式解释、评价：数捌挖掘阶段发现出来的模式，经过用户或机器的评价，可 能存在冗余或无关的模式，需要剔除；也有可能模式不满足用户的要求，需要重新进行 k d d 过程。 2 1 3 知识发现的方法 在l d 的数据挖掘子步骤中，常用的方法有7 1 ： 1 、关联规贝l j ( a s s o c i a t i o nr u l e ) 挖掘：关联规则挖掘发现大量数据中项集之间“有趣 的 关联或相关联系。大量数据中多个项集频繁关联或同时出现的模式可以用关联规则 的形式表示；规则的支持度和置信度是两个规则兴趣度度量，分别反映发现规则的有用 性和确定性。关联规则如果满足最小支持度阈值和最小置信度阂值，则认为该规则是“有 趣的 模式。 r 中罔“油人学( 牛东) 坝i j 学位论义 2 、决策树( d e c i s i o nt r e e ) 方法：决策树是通过一系列规则对数据进行分类的过程。 它以信息论中的互信息( 信息增益) 原理为基础寻找数据库中具有最大信息量的字段，创 建决策树的一个结点，再根据字段的不同取值建立树的分枝；在每个分枝中继续重复创 建决策树的下层结点和分枝的过程，即可建立决策树。采用决策树，可以将数据规则可 视化，其输出结果也容易理解。典型的决策树算法女h i d 3 t 2 3 l 、c 4 5 5 0 t 2 4 1 ，该类方法的实 用效果好，影响较大。 3 、统计( s t a t i s t i c s ) 方法：统计方法是从事物的外在数量上的表现去推断该事物可能 的规律性，即利用统计学原理对数据库中的信息进行分析。可进行常用统计( 求大量数 据中的最大值、最小值、总和、平均值等) 、回归分析( 求p i 归方程来表示变量间的数量 关系) 、相关分析( 求相关系数来度量变量问的相关程度) 、差异分析( 从样本统计量的值 得出差异来确定总体参数之间是否存在差异) 等。 4 、粗糙集方法：粗糙集是一种刻画具有信息不完整、不确定系统的数学工具，能 有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识， 揭示潜在的规律。在数据库中，将行元素( 即一条记录数据) 看成对象，列元素作为属性( 分 为条件属性和决策属性) ，通过等价类划分寻找核属性集和约简集，然后从约简后的数 据库中导出分类决策规则。 5 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) ：人工神经网络模拟人脑神经元 方法，以m p 模型和h e b b 学习规则为基础，建立了三大类多种神经网络模型：前馈式网 络、反馈式网络、自组织网络。神经网络的处理过程主要是通过网络的学习功能找到一 个恰当的连接加权值来得到最佳结果。通过训练学习，神经网络可以完成分类、聚类、 特征挖掘等多种数据挖掘任务。 6 、遗传算法( g e n e t i ca l g o r i t h m ) ：是模拟生物进化过程的算法，由三个基本算子组 成：a 繁殖，即从一个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) ；b 交叉， 即选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个体；c 变异，即对某些 个体的某些基因进行变异( 1 变0 、0 变1 ) 。遗传算法可起到产生优良后代的作用。这些 后代需满足适应值，经过若干代的遗传，将得到满足要求的后代，即问题的解。 2 2 粗糙集理论 2 2 1 粗糙集理论的基本概念 粗糙集并没有确切、统一的定义，目前基本上采用p a w l a k 教授于1 9 9 5 年最早提出 9 第二章知识发现1 羽l 糙集理论 的相关定义 1 1 , 1 5 , 2 5 】。为了使以后章节的内容更加容易了解，下面就将j h 糙集针对集合论 的一些概念进行一下分析。 1 知识库 给定一个论域u ，子集x u 表示( ，中的一个概念，u 中的知识即表现为概念的 簇集。一个论域u 上的分类族定义为u 上的知识库，它构成了一个特定的分类。在u 与 r 的定义下，知识库可定义为属于r 中的关系对u 中元素的划分，记为k = ( u ，r ) 。其 中u o 是一个被称为全域或论域( u n i v e r s e ) 的所有要讨论的个体的集合，尺是u 上等价 关系的一个族集。 2 粗糙集的定义 设x 为，的一个子集，当x 为某些尺的等价类的并时，称x 是r 可定义的，否则x 为r 不可定义的。r 可定义集是论域的子集，它可在k 中被精确地定义，而尺不可定义 集不能在k 中被定义。r 可定义集也称为r 精确集，尺不可定义集也称为非精确集或r 粗糙集。 3 不可分辨关系( i n d i s c e m b i l i t yr e l a t i o n ) 粗糙集理论中一个关键的概念就是不可分辨关系。设psr ，且p o ，p 中所有 等价关系的交集称为尸上的一种不可分辨关系( 或称不可区分关系，不分明关系) ，记作 i n d ( p ) ，具体公式为： i x m 。，= ill 。 r ep 4 上近似和下近似 对于一个样例集，也称为一个概念。根据一个条件属性子集所确定的不可分辨关系， 有可能准确地判定一些样例是否属于该概念，也有可能不能判定某些样例是否属于该概 念。为了描述这个问题，粗糙集采用了上近似和下近似的概念。 x 的上近似：尺一( x ) = xo u ) a ( 【x 】i ix 中) x 的下近似：r 一( x ) = xi ( x u ) a ( 【x 】门x ) ) x 的边界区域：b n ，f ( x ) = r 一( x ) 一r 一( x ) 若b n r ( x ) o ，则集合x 就是一个丰f l 糙概念。下近似包含了所有使用知识r 可确 切分类到x 的元素，上近似则包含了所有那些可能足属于x 的元素。概念的边界区域 1 0 中目石油大学 # 东1 颂i 学位论盘 b n 。( x ) 是根据知识r ，u 中既不能肯定归入集合，又不能肯定归入集合x 的元素构 成的集合。p o s 。( j ) = r ( x ) 称为集合的月正域- n e g f ( x ) = u r - ( x ) 称为集合x 的r 负域。对于j 的上近似和下近似可形象的表示为图2 - 2 。 一x 的下近似( 正域 圃边界域 口x 的上近似( 负倒 o x 图2 - 2x 的上近似、下近似 f i 9 2 - 2t h e u p p e ra p p r o x i m a t i o na n d l o w e r a p p r o x i m a t i o no f x 5 粗糙集的另一种定义形式 当且仅当r ( x ) = r - ( 工) ，j 为霄的可定义集： 当且仅当月一( x ) r - ( 肖) ，对于r ，x 即为撩糙集。 6 决策表 决策表是一类特殊而重要的信息表达系统，它反映了当满足某些条件时，决策( 行 为) 应当怎样进行。决策表可以有效直观地表示大多数的决策问题，因此这一工具在决 策应用中起着重要的作用。 决策表可以定义如下：s = ( u ，r ，v ，p 为一信息系统，其中u = 扛，吐，a 是一个 非空有限集( 即记录集) 。r = ，日2 ，a ，口。 是一非空有限集，称为属性集，且c ，d c r 是 两个属性子集，分别称为条件属性和决策属性，且c y d = r ，c 【d = 0 ，则该信息系 统称为决策表。关系肋( c ) 和关系1 n d ( d ) 的等价类分别称为条件类和决策类。 矿= y 砌匕，k 是属性的值域。f ：v 0 一r 被称为信息函数( 满足关系：，k 口) ， v 4 e a ) 7 可辨识矩阵 可辨识矩阵( d i s c c m b i l 埘m a t r i x ) i 6 1 是由波兰华沙大学的著名数学家s k o w m n 提出 来的，利用这个工具可以将存在于复杂的信息系统中的全部不可辨识关系表达出来。令 第_ 二章知识发现i j ：i ：1 1 糙集理论 s = ( u ，r ，v ，是一个知识表达系统，u 为论域且u = b 。，x ：，人，x 。 ，r ；cyd 是属性集 合，子集c 和d 分别是条件属性集和决策属性集。0 4 x ) 是对象x 在属性口上的值，d ( x ) 是记录x 在d 上的值，则可辨识矩阵m 中的每个元素朋，定义为 f 矗c ：口g ，) 口g ，) )d g ，) d g ，) m = 0d ( x ，) = d b ，) i ，- = 1 ，2 ，八，” l 一1 v 口，口g ，) = 口g ，ld g ，) d g ，) 如果决策表中决策属性值不同并且条件属性值也不同，则矩阵中的元素值为不同的 属性组合；如果决策属性值不同但是条件属性相同，则元素值为1 ；如果决策属性值相 同，则元素值为0 。同时，从上述定义中可知可辨谚 矩阵是一对称矩阵。 2 2 2 粗糙集理论的特点 粗糙集理论自提出以来，许多计算机科学家和数学家对其理论及应用进行了孥持不 懈的研究，使之在理论上同趋完善，特别是由于2 0 世纪8 0 年代术和9 0 年代初在知识 发现等领域得到了成功的应用而越来越受到国际上的广泛关注，这也与粗糙集理论自身 的特点是分不开的： ( 1 ) 粗糙集理论不需要数据的任何先验知识或额外的有关数据信息。模糊集和概率 统计方法是处理不确定信息的常用方法，但这些方法需要些如模糊隶属函数和概率分 布等的数据附加信息或先验信息，这些信息并不容易得到。；l f l 糙集理论方法只是利用数 据本身提供的信息，不需要任何先验知识。 ( 2 ) 粗糙集理论具有很强的数据分析能力。它能在不影响分类的日仃提下对数据趟亍 化简并求得知识的最小表达式；能识别数据之f b j 的依赖关系，揭示出概念简单的模式； 能从经验数据中获取有效的规则知识。并且能够从不同的层次柬对数据进行建模、分析， 以更好地揭示数据间的依赖关系，发现数据问的规律。 ( 3 ) 粗糙集能表达和处理不完备信1 y 6 l ：米只糙集以不可分辨关系为基础，侧重分类， 粗糙集合虽然不能清晰定义，但可以用上下近似集合逼近。模糊集基于元素对集合隶属 程度的不同，强调集合本身的含混性。虽然粗糙集和模糊集特点不同，但它们之间有着 密切的关系，有很强的互补性【2 7 , 2 8 , 2 9 】；粗糙集和证据理论也有一些相互交叠之处【3 0 1 ，在 实际应用中可以相互补充。 ( 4 ) 粗糙集理论可以产生简洁准确、易于验证的舰则知识。粗糙集理论产生的规则 符合人们的推理习惯，能够清晰地表明决策表中数抓之i h j 的关系。 1 2 中闯油人学( 华东) 颀i j 学位论文 2 2 3 粗糙集理论的应用及前景 由于粗糙集理论能解决不确定性、不完备性问题，所以从产生丌始就被应用于各个 领域，并取得了巨大的成绩。主要体现在以下几个方面： ( 1 ) 数据库知识发现3 1 】：知识发现是当前人工智z 月- 匕e , 和数据库技术交叉学科的研究热 点之一。粗糙集方法已成为k d d 的一种重要方法，其导出的知谚 精练且更便于存储和使 用。