（管理科学与工程专业论文）粗糙集扩展模型及其在数据挖掘中的应用研究.pdf

国防科学技术大学研究生院学位论文 摘要 数据挖掘和知识发现是从数据中获取知识的一种新技术。粗糙集作为一种处理不完 全、不精确及不确定信息的有效方法，在数据挖掘和知识发现领域大有用武之地。粗糙 集方法的成功应用很大程度上依赖于其理论的完善，只有深入地研究粗糙集的理论体系， 才能将之更有效地应用到实际领域。本文以国家自然科学基金项目“管理决策中数据仓 库与数据挖掘新技术研究”为背景，从理论和应用两个方面较全面和系统地阐述了这一 理论的研究内容和方法。完成的工作和取得的创新性成果在于： 经过对粗糙集理论的深入研究，作者找到了粗糙集与模态逻辑、模糊集、代数系统 和区间集代数等抽象理论之问的关系，一是粗糙集可以为抽象理论提供语义解释，从而 使我们能更好地理解掌握这些抽象理论；二是粗糙集建立了各个独立的抽象理论之间的 内在关系，使彼此独立的抽象理论联系在了一起。 作者研究了粗糙集扩展理论，提出了一种多层粗糙集模型c b m r s 。该模型是一种 基于覆盖的扩展的多层粗糙集模型。经过验证，二元自反关系序列下的多层粗糙集模型 堤c b m r s 模型的特例。c b m r s 模型突破了局限在二元关系之上的多层粗糙集模型的 研究。另外，作者提出了基于分类正确度的粗糙集模型，该模型已用于作者研制的数据 挖掘方法m i e r s 上。 作者提出了从不一致决策表中挖掘最简规则的粗糙集方法m r s 。通过分类正确度 有效处理了决策表的不一致性，采用启发式算法，挖掘出满足给定精确度的最简产生式 规则知识。作者构造了h a s h 函数来实现算法，有效降低了算法的时间复杂度。并用多个 u c i 数据集进行了测试，与著名的r o s e r a 软件进行了实验对比，结果说明m i e - r s 可以大 大提高总的数据约简量，有效地简化最终得到的规则知识。 作者提出了有序信息表上的数据分析与数据挖掘模型0 i t m 。从数据挖掘的角度考虑 对象排序问题，通过引进属性值上的有序关系，作者扩充了常见的属性值方法，提出了 有序信息表的形式化概念，进而提出了一个有序信息表上的数据分析方法，通过分析有 序信息表中的属性依赖，定义了有序信息表的约简集和核的概念；作者还提出和形式化 了有序信息表中挖掘有序规则的问题，设计了有序决策逻辑语言( 0 d l ) ，并给出了一个挖 掘有序规则的方法。基于有序关系来挖掘有序规则可看作是粗糙集模型的非等价关系扩 展的一个具体应用实例。 本文的研究成果，对于拓宽粗糙集的理论及粗糙集在数据挖掘中的应用，有一定的 理论和实践意义。 关键词：租糙集，数据挖掘，租糙集扩展模型，有序规则，排序 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t d a t am i n i n ga n dk n o w l e d g ed i s c o v e r yi nd a t a b a s e si san e wt e c h n o l o g yf o rd r a w i n g k n o w l e d g ef r o m d a t a a sa ne f f e c t i v ea p p r o a c ht o p r o c e s s i n gi n c o m p l e t e ，i m p r e c i s eo r u n c e r t a i ni n f o r m a t i o n , r o u g hs e th a sb e e n p l a y i n ga ni m p o r t a n tr o l ei nt h ea r e ao f d a t am i n i n g a n dk n o w l e d g ed i s c o v e r y t h es u c c e s s f u la p p l i c a t i o n so f r o u g hs e ta p p r o a c hd e p e n dl a r g e l y o nt h ec o m p l e t e n e s so fi t st h e o r y o n l ya f t e rt h et h e o r yi ss y s t e m a t i c a l l ya n dd e e p l ys t u d i e d ， c a l lr o u g hs e tb ea p p l i e dt op r a c t i c a ld o m a i n s ：t a k i n ga sab a c k g r o u n dt h ep r o j e c to ft h e r e s e a r c ho fn e w t e c h n o l o g yf o rd a t aw a r e h o u s ea n dd a t am i n i n gi nt h ea r e ao fm a n a g e m e n t d e c i s i o ns u p p o r t ，w h i c hi s g r a n t e db yt h en a t i o n a ln a t u r es c i e n c ef o u n d a f i o n t h i st h e s i s a d d r e s s b sc o m p l e t e l ya n ds y s t e m a t i c a l l y t h em a i nr e s e a r c hc o n t e n t sa n dm e t h o d s o f r o u g h s e t f r o mt h ea s p e c t so fb o t ht h e o r ya n d 印p l i c a t i o n t h ep r i m a r yc o n t r i b u t i o n so ft h i st h e s i s i n c l u d e ： h a v i n gs t u d i e dt h er o u g hs e tt h e o r yc a r e f u l l y , t h et h e s i sf i n d st h er e l a t i o n s h i pb e t w e e n r o u g h s e ta n ds u c ha b s t r a c tt h e o r i e sa sm o d a ll o g i c ，f u z z ys e t , a l g e b r as y s t e ma n di n t e r v a l - s e t a l g e b r a , i e ，r o u g h s e t p r o v i d e saw e l ld e f i n e d s e m a n t i c a li n t e r p r e t a t i o nt ot h e s ea b s t r a c t t h e o r i e s ，w h i c h e n a b l e su st ob e t t e ru n d e r s t a n d t h e m s e c o n d l y , r o u g h s e tb u i l d sa n i n t e r - r e l a t i o n s h i pa m o n g t h e s ed e p e n d e n tt h e o r i e sa n dc o n n e c t st h e m t o g e t h e r t h et h e s i ss t u d i e st h eg e n e r a l i z e dr o u g hs e tm o d e l sa n dp r o p o s e sam u l t i - l e v e lr o u g hs e t a p p r o x i m a t i o nm o d e lc b m - r sb a s e do nac o v e r i n go f t h eu n i v e r s e w ev a l i d a t et h a tt h e m u l t i - l e v e lr o u g hs e ta p p r o x i m a t i o ni n d u c e db yas e q u e n c eo fr e f l e x i v er e l a t i o n si sas p e c i a l e a s eo fc b m - r s c b m - r sm o d e lb r e a k st h r o u g ht h el i m i to ft h em u l t i - l e v e lr o u g hs e t m o d e l si n d u c e do n l yb yb i n a r yr e l a t i o n s t h et h e s i sa l s oe x a m i n e st h er o u g hs e tm o d e lb a s e d o nc l a s s i f i c a t i o na c c o r a c y t h em m - r sd a t am i n i n ga p p r o a c hg i v e nl a t e ri sb a s e do nt h e m o d e l t h et h e s i s p r o p o s e sar o u g hs e ta p p r o a c ht om i n i n g m i n i m a lr u l e si ni n c o n s i s t e n t d e c i s i o nt a b l e sm i e - r s w ed e a lw i t ht h ei n c o n s i s t e n c yt h r o u g hc l a s s i f i c a t i o na c c u r a c y , u s i n g h e u r i s t i c a l g o r i t h m sw ec a ng e t as e to fm i n i m a lp r o d u c t i v er u l e s s a t i s f y i n g t h eg i v e n c l a s s i f i c a t i o na c c u r a c y w i t hr e s p e c tt ot h ei m p l e m e n to fo u ra l g o r i t h m , w ec o n s t r u c tt w o h a s hf u n c t i o n st or e d u c et h et i m ec o m p l e x i t y s e v e r a lu c ld a t as e t sa r eu s e dt ot e s tt h e a p p r o a c h c o m p a r e d w i t hr o s e t t a t o o l k i lo u rm e t h o di n c r e a s e st h ed a t ar e d u c t i o n r a t eg r e a t l y a n d s i m p l i f i e st h e r e s u l tr o l e se f f e c t i v e l y t h et h e s i sp r o p o s e sad a t aa n a l y s i sa n dd a t am i n i n gm o d e li no r d e r e di n f o r m a t i o nt a b l e s o i t mo r d e r i n go f o b j e c t si s af u n d a m e n t a li s s u ei nh u m a nd e c i s i o nm a k i n ga n dm a y p l a ya s i g n i f i c a n tr o l ei nt h ed e s i g no fi n t e l l i g e n ti n f o r m a t i o ns y s t e m s t l l i sp r o b l e mi sc o n s i d e r e d 国防科学技术大学研究生院学位论文 f r o mt h ep e r s p e c t i v eo fd a t am i n i n gt h ec o m m o n l yu s e da t t r i b u t ev a l u ea p p r o a c h e sa r e e x t e n d e db yi n t r o d u c i n go r d e rr e l a t i o n so na t t r i b u t ev a l u e s w eg e n e r a l i z et h en o t i o no f i n f o r m a t i o nt a b l e st oo r d e r e di n f o r m a t i o nt a b l e sb ya d d i n go r d e rr e l a t i o n so na t t r i b u t ev a l u e s ad a t aa n a l y s i sm e t h o di st h u sp r o p o s e dt od e s c r i b ep r o p e r t i e so fo r d e r e di n f o r m a t i o nt a b l e s w ed e f i n et h ec o n c e p t so fr e d u c ta n dc o r ee t c b ya n a l y z i n gt h ea t t r i b u t ed e p e n d e n c yi n o r d e r e di n f o r m a t i o nt a b l e s ；t h et h e s i sa l s op r o p o s e sa n df o r m a l i z e st h ep r o b l e mo fm i n i n g o r d e r i n gr u l e s ，d e s i g n s t h eo r d e r e dd e c i s i o nl o g i cl a n g u a g e ( o d l - l a n g u a g e ) ，a n dg i v e sa s o l u t i o nf o rm i n i n go r d e r i n gr u l e s m i n i n go r d e r i n gr u l e sb a s e do no r d e r e dr e l a t i o n si s a c o n c r e t ee x a m p l eo fa p p l i c a t i o no fg e n e r a l i z a t i o n so fr o u g h s e tm o d e lw i t hn o n e q u i v a l e n c e r e l a t i o n s ，t h ea c h i e v e m e n t so ft h i st h e s i sh a v eg r e a tt h e o r e t i ca n dr e a l i s t i c s i g n i f i c a n c e i n e x p a n d i n g t h er o u g hs e tt h e o r ya n di t sa p p l i c a t i o ni nd a t am i n i n g k e y w o r d s ：r o u g hs e t ，d a t am i n i n g ，g e n e r a l i z e dr o u g h s e t a p p r o x i m a t i o nm o d e l ， o r d e r i n gr u l e ，r a n k i n g 第页 。； 国防科学技术大学研究生院学位论文 第一章绪论 在当前的知识经济时代，随着计算机科学和技术，特别是数据库技术的不断发展和广 泛应用，数据库中存储的数据量急剧增大。人类面对着数据的海洋，可是用于对这些数据 进行分析处理的工具却很少。目前大部分数据库系统所能做到的只是对数据库中已有的数 据进行存取，人们通过这些数据所获得的信息量仅仅是整个数据库所包含的信息量的一部 分，隐藏在这些数据之后的更重要的信息是关于这些数据的整体特征的描述及对其发展趋 势的预测，这些信息在决策生成的过程中具有重要的参考价值。为了能有效地从数据库中 挖掘出这些具有潜在价值的信息和知识，数据库中的知识发现( k n o w l e d g ed i s c o v e r y i n d a t a b a s e s ，k d d ) 技术逐渐发展起来。 知识发现方法的研究是k d d 研究领域的热点和主要内容。知识发现的方法和技术有很 多，粗糙集方法是其中比较有影响的方法之一，近年来它在k d d 中得到了成功的应用， 受到国际上广泛关注。本文将对粗糙集方法的理论和应用进行深入的研究，探讨粗糙集扩 展模型及其在数据挖掘方面的应用。 1 本章首先介绍数据库知识发现的研究背景和研究现状：1 2 节解释了知识发现和数据挖 掘这两个术语之间的联系与区别，以及知识发现的一般过程；1 3 节讨论了数据挖掘与其它 学科，特别是与数据库、数据仓库、人工智能及统计分析的关系；1 4 节对数据挖掘的任务 作了一个分类：1 5 节介绍了目前数据挖掘采用的方法：1 6 节讨论了数据挖掘当前与未来 的研究方向和研究内容；粗糙集作为数据挖掘中的一个方法，是本文的主要研究内容，1 7 节介绍了粗糙集理论的兴起：1 8 节对粗糙集理论的特点作了一个分析；1 9 节介绍了粗糙 集理论的研究领域；1 1 0 节总结了目前粗糙集静应用情况r 最后，1 1 l 节初步介绍了本文 的工作和内容安排。 、 1 1数据库知识发现的研究背景与现状 在知识经济时代，人类知识总量每五年增加一倍，知识对经济增长的贡献率将可能从本 世纪初的5 2 0 上升虱j 9 0 t 8 1 ，人类对知识的渴望从来没有象现在这样强烈。数据库和因特 网技术的飞速发展和广泛应用使人类所面对的数据呈几何级数增长，人类迫切需要有效地利 用这些数据和信息，从中挖掘出有价值的信息，即知识。数据库知识发现便顺应实践的这种 迫切需求产生并发展起来。事实上，知识发现给企业带来的潜在的投资回报几乎是无止境的。 世界范围内具有创新性的公司都开始采用知识发现技术来判断哪些是他们最有价值的客户、 重新制定产品的推销战略，以最小的花费得到最大的商业利润。 知识发现，具体为数据库中的知识发现( 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 s ，k d d ) 这 个术语最早出现在1 9 8 9 年8 月在美国底特律召开的第十一界国际人工智能联合会议 ( i j c a i ) 的k d d 专题讨论会上【8 8 】，到目前为止，由美国人工智能协会主办的k d d 国际研 第1 页 国防科学技术大学研究生院学位论文 讨会已经召丌了8 次，规模出原来的专题讨论会发展到国际学术大会，研究重点也逐渐从 发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。 1 9 9 9 年，亚太地区在北京召丌的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的 k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、 计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和 专刊讨论，甚至到了脍炙人口的程度。 从1 9 9 7 年开始，k d d 拥有了自己的专门杂志d a t am i n i n g a n d k n o w l e d g e d i s c o v e r y ) ) ，不仅如此，在i n t e m e t 上还有不少电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威。 与国外相比，国内对k d d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科学基 金首次支持我们对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知 识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空军 第三研究所、海军装备论证中心等。北京系统工程研究所对模糊方法在知识发现中的应用 进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦 大学j 浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则 开采算法的优化和改造：南京大学、四川联合大学和上海交通大学等单位探讨、研究了非 结构化数据的知识发现以及w e b 数据挖掘。 目前k d d 不仅成为一个十分活跃的研究领域，也出现了相当数量的k d d 产品和应用 系统，广泛应用于天文、生物医学、通讯业、风险评估和销售分析等领域，带来巨大收益。 如i b m 公司a l m a d e n 研究中心开发的q u e s t ，其目的是为新一代决策支持系统的应用开 发提供高效的数据挖掘基本构件；s g i 公司和美国s t a n d f o r d 大学联合开发的m i n e s e t 集成 了多种数据挖掘算法和可视化工具，帮助用户直观的、实时地发掘、理解大量数据背后的 知识：加拿大s i m o nf r a s e r 大学开发的d b m i n e r ，其系统设计的目的是把关系数据库和数 据挖掘集成在一起，以面向属性的多级概念为基础发现各种知识。 1 2知识发现和数据挖掘 关于知识发现，目前比较公认的一个定义是知识发现领域知名学者f a y y a d 和 p i a t e s k y s h a p i r o 【3 1 1 1 9 9 6 年给出的，即知识发现是从大量数据中识别出有效的、新颖的、潜 在有用乃至最终可理解的模式的非平凡的过程。 在以上定义中，数据是指有关事实的集合，记录和事物有关的原始信息。模式是对数据 特征的描述。识别出模式则意味着为数据建立一个模型，发现数据的内在结构，产生数据 集的高级描述。过程表明知识发现是一个包括数据准备、模式搜索、知识评价，以及反复 修改求精的多步骤的处理过程。非平凡意味着要要有一定程度的智能性、自动性( 仅仅给出 所有数据的总和不能算作是一个发现过程) 。有效性要求所发现的模式在一定程度上适用于 新的数据。新颖性要求发现的模式应该是新的。潜在有用性是指发现的知识将来有实际效 国防科学技术大学研究生院学位论文 用，如用j 二决策支持提高经济效益。最终可理解性要求发现的模式能被用户理解，目前它 主要是体现在简洁性上。 f a y y a d 等人给出了如图1 1 所示的知识发现的一般过程，从图叶 可见，知识发现过程 是多个步骤相衔接，反复进行人机交互的过程。具体说明如下： ( 1 ) 数据选择。熟悉有关的背景知识，弄清楚用户的要求，根据用户需求从数据库中提 取与知识发现相关的数据，k d d 将主要从这些数据中进行知识提取，在此过程中，会利用 一些数据库操作对数据进行处理。 ( 2 ) 数据清洁。主要是对阶段( 1 ) 产生的数据进行再加工，检查数据的完整性及数据的一 致性，对其中的噪音数据进行处理，对丢失的数据可以利用统计方法进行填补。 f 4 ) 数据变换。根据知识发现的任务，进行数据变换，确定数据的适当表示。包括离散 值数据与连续值数据之间的相互转换，数据值的分组分类，数据项之间的计算组合，以及 寻求数据的有用特征，利用属性约简和数据库投影减少要搜索的参数。 ( 5 ) 数据挖掘( d a am i n i n g ) 。根据用户的要求，选择合适的算法，以特定的算法搜索 感兴趣的模式，如分类规则，关联规则，聚类模型等。 一伯) 模式评价与解释。对所发现模式的一致性、正确性和有效性进行评价。对发现的模 式利用可视化技术进行解释，将发现的知识以用户能了解的方式呈现给用户。 在上述的每个步骤k d d 系统会提供处理工具完成相应的工作。该过程不是单向的，在 过程的任意步骤都可以返回以前的阶段进行再处理，直到得到满意的结果。 预 目 转 处 换 t d 1 垮 标 垫塑煎鼙 理 墼塑壅辇 数 数 数 据 下 据 据 1 图1 1 知识发现的一般过程 知识发现也有人称之为数据挖掘( d a t am i n i n g ) ，在许多文献中，研究者们往往不加区 别地使用这两个术语。由上看出两者实际是有区别的，即知识发现是指从数据库中发现知 识的整个过程，数据挖掘是指整个过程中一个特定的步骤。数据挖掘是知识发现过程中一 个非常重要的步骤，该步骤运用计算技术，在可接受的计算成本下，从数据中提取特定的 模式。 数据中的模式常常是无限多个，特定的搜索算法可以获得特定的模式。一般说来，不 存在一个普遍适用的算法。个算法在某个领域非常有效，但在另一个领域却可能不太合 适。在实际应用中，应该针对具体的问题领域，精心选择有效的数据挖掘算法。因此，实 第3 页 国防科学技术大学研究生院学位论文 际的数始挖= f 1 7 | i 作就转变成了对领域问题、领域知识和发现任务的形式化，而不是对所选 用的数抛挖掘算法进行细节上的优化。 1 3数据挖掘与其它学科的关系 数据挖掘( 知识发现) 是- - f l 交叉性学科，涉及到人工智能、机器学习、数据库、统计 学、可视化技术等众多学科。 数据挖掘与数据库、数据仓库 传统的数据库技术对于一般的事务处理要求可以得到令人满意的结果，但却不能有效地 完成预测、分类、聚类等决策支持任务。最近几年兴起的数据仓库( d a t aw a r e h o u s e ) 4 5 1 4 6 】 技术集成了大量的分散的数据源，采用数据清洁技术保证了数据的一致性与正确性，比起数 据库可以为数据挖掘提供更丰富、更可靠的数据来源。 大部分情况下，数据挖掘都要先把数据从数据仓库中拿到数据挖掘库或数据集市中( 见 图1 2 ) 。 图1 2 数据挖掘库从数据仓库中得出 不同于传统数据库上的在线事务处理( o l t p ) ，数据仓库上的在线分析处理( o l a p o n l i n ea n a l y t i c a lp r o c e s s i n g ) 可以对数据进行多维分析，完成传统数据库难以完成的决策分析 任务。那么同样用以数据分析的数据挖掘与o l a p 有什么区别呢? o l a p 是由用户驱动的， 一般是由分析人员预先设定一些假设，然后使用o l a p 去验证这些假设，它在本质上是一个 演绎推理的过程；数据挖掘不是用于验证某个假定的模式的正确性，而是在数据库中自己寻 找模式，它在本质上是一个归纳的过程。比如，在进行信用风险调查时，如果使用o l a p ， 分析人员可能先做一些假定，如高负债、低收入的人有信用风险，他可以利用o l a p ，通过 对有关数据进行分析来验证或推翻这个假设：而如果使用数据挖掘，数据挖掘工具可能帮他 找到高负债和低收入是对信用风险有影响的因素，甚至还可能发现一些分析人员从来没有想 过或试过的其它因素，如年龄、地区等。 数据挖掘 u o l a p 具有一定的互补性。在利用数据挖掘出来的结论采取行动之前，你也 国防科学技术大学研究生院学位论文 许需要验证一下如果采取这样的行动会给公司带来什么样的影响，o l a p i 具能网答你的这 些问题。而且在知识发现的早期阶段，o i 。a p 工具可以帮助你更好地理解数据，找到对问题 比较重要的变量，发现异常数据和相互影响的变量，从而加快知识发现的过程。 数据挖掘与人工智能 人工智能的理论和技术为数据挖掘的研究和应用提供了强有力的支持。人工智能领域的 一个分支机器学习( m a c h i n el e a r n i n g ) 的各种方法丰富了数据挖掘的算法，例如在数据挖 掘中可以采用决策树方法、贝叶斯理论、神经网络、遗传算法等机器学习方法进行数据的分 类、预测、归纳、约简等以发现新的知识：处于研究发展中的有关知识的表示、存储和存 取的新的理论和方法不断为数据挖掘的研究提供着有力的支持：另外，目前运用人工智能中 的智能主体技术在因特网上进行数据挖掘的研究和应用也成为一个热门的研究课题【3 0 】。 数据挖掘与统计分析 统计分析和数据挖掘有许多共同之处【2 9 j 【3 2 】，它们有着共同的目标：发现数据中的结构。 统计分析为数据挖掘的研究和应用提供了有力的支持。大多数的统计分析都基于完善的数 学理论，发现结果具有很高的准确度。另外，统计分析对于结构搜索过程的假设验证、发 现结果的评价以及恰当地运用发现结果等方面都发挥着很重要的作用。可以用于数据挖掘 的统计分析技术包括：概率分布、估计、假设验证、g i b b s 采样、预测、回归分析、相关 一分析和马尔科夫链等。 1 4数据挖掘任务的类型 目前常见的数据挖掘任务可以分为以下几类： 分类( c l a s s i f i c a t i o n ) 分类是知识发现的一个基本任务，它是要对输入的数据进行分析并且利用数据中出现 的特征为每一个类别构造一个较为精确的描述或模型( t g 常常称作分类器) ，然后按分类器 再对新的数据集进行分类预测。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一定数量的例子( 如 一组数据库记录) 组成，每个例子具有多个属性或特征。此外，每个例子还有一个特定的 类标号。一个具体例子的形式可为：( v - ，v 2 ，v 。；c ) ；其中v ，表示特征值，c 表示类标号。 例如，考虑一个银行的客户数据库，假定根据各自的信用历史记录客户已被分为“信 用好的”和“信用坏的”两类，银行很想对这两个客户类分别给出一个描述，以便月这两 个类描述去决定是接受还是拒绝新的客户贷款申请。首先输入一些已带有类标号的客户的 资料集，按某种分类方法构造分类器，即每个类( 好类或坏类) 的类描述，该分类器可以根 据将来申请的客户资料把客户映射到某一个类，银行可据此进行相应的决策。 第5 页一 国防科学技术大学研究生院学位论文 分类器的构造方法有决策树方法、粗糙集方法、统计方法、神经网络方法等等，卜 1 ，将详细介绍。分类器的表示形式有决策树、决策表、产生式规则、判别函数、原型事例、 以及仪值矩阵( 神经网络) 。 4 i 同的分类器有不同的特点。有三种分类器评价或比较尺度：预测准确度：计算 复杂度；模型描述的简洁度。预测准确度是用得最多的一种比较尺度，特别是对于预测 型分类任务，目前公认的计算方法是1 0 番分层交叉验证法( 1 0 一f o l ds t r a t i f i e d c r o s s v a l i d a t i o n ) 。计算复杂度依赖于具体的实现细节和硬件环境，由于数据挖掘的操作对象是巨 量的数据库，因此空| 1 自_ j 和时间的复杂度问题将是非常重要的一环节。对于描述型的分类任 务，模型描述越简洁越受欢迎，例如，采用规则表示的分类器构造法就更有用，而神经网 络方法产生的结果就难以理解。 另外要注意的是，分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺值， 柯的分布稀疏，有的字段或属性问相关性强，有的属性是离散的而有的是连续值或混合式 n 0 。目前普遍认为不存在某种方法能适合于各种特点的数据。 ；聚类( c l u s t e r i n g ) ： 聚类的目标是要根据数据的属性对数据进行分组，使得一个分组由类似的数据组成。 聚类的结果应陔使得一类中的数据相似性最大，而类与类之间的相似性最小。与分类不同 聚类的输入数据没有类别的标号，在开始聚类之前也不知道依照哪些属性进行分组。因此 从学习的角度来看，聚类是一种无导师指导的学习过程。 关联规贝1 ( a s s o c i a t i o nr u l e s ) 我们以一个超级市场的顾客数据库为例来讨论，给定一个交易的集合，每项交易是一 个文字( 项) 的集合。一条关联规则是形式为x j y 的表达式，其中x 、y 是项的集合，这 样一条关联规则的直观意义就是数据库中含有x 的交易也含有y 。例如，数据库中全部交 易的2 含有啤酒和面包：对于含有啤酒的交易，其中有3 0 的交易含有面包等等。这里， 称2 为关联规则的支持度，3 0 为关联规则可信度。当用户给定了最小支持度和最小可 信度闽值以后，问题就变成要从数据库中挖掘出不小于最小支持度和最小可信度阈值的关 联规则。目前关联规则的发现除上述类型的关联规则外，还有涉及事物的分类层次的广义 关联规则和涉及事物定量信息的定量关联规则。 j1 义关联规贝1 ( g e n e r a l i z e da s s o c i a t i o nr u l e s ) ：在许多情形下，所研究的事物对象存在 ? j ：个分类层次，而用户需要发现这些不同层次上事物之间的关联。例如，考虑这样一个 。_ | 】= 物分类层次即：央克是一件外套，外套是一件上衣。考察三条关联规则：购买央克 的坝锌也会购买鞋子：购头外套的顾客也会购买鞋子；购买上衣的顾客也会购买鞋子。 j 以祈出，这三条规则涉及到了三个层次上的事物，它们彼此独立，分别应用于不同的环 ” 国防科学技术大学研究生院学位论文 定量型关联规爨l j ( q u a n t i t a t i v ea s s o c i a t i o nr u l e s ) ：定量关联规则的一个例子是：1 0 的 已婚、年龄在5 0 岁至6 0 岁的人至少有2 部汽车。这里处理数量信息的办法是首先对属性 的取值范围进行恰当的划分，然后再视需要合并相邻的划分。 序列模式( s e q u e n t i a lp a t t e r n s ) 一个序列是一组按照交易时间排列的交易，每项交易是一个项的集合，问题是要发现 不小于最小支持度闽值的序列模式。这里支持度是指含有某个序列模式的序列的个数。例 如，在一项交易中购买了电视机的顾客有6 0 在随后的交易中会购买影碟机。序列模式的 发现方法与关联规则的发现方法类似。但要注意，关联规则描述的是交易内部 ( i n t m t r a n s a c t i o n ) 项集之间的关联，序列模式则是交易之n 0 n t e r - t r a n s a c t i o n ) 的关联。 时间序列( t i m es e q u e n c e s ) 时间序列是用数据过去的值来预测未来的值。时间序列采用的方法一般是在连续的时 间流中截取一个时间窗口( 一个时间段) ，窗口内的数据作为一个数据单元，然后让这个时 间窗口在时间流上滑动，以获得建立模型所需要的训练集。比如可以用前六天的数据来预 测第七天的值，这样就建立了一个区间大小为7 的窗口。 数据总结( d a t as u m m a r i z a t i o n ) 数据总结的目标是浓缩数据库中的元组，找出能描述数据的较少量的元组，得到高度 概括的知识基表。具体说来就是利用属性取值的分类层次概括元组，除去冗余。 偏差分析( d e v i a t i o nd e t e c t i o n ) 数据的偏差含有很大一类潜在有用的知识，如分类中的异常实例，模式的例外，观测 结果对期望的偏差，量值随时间的变化等。 区分( d i s c r i m i n a t i o n ) 区分出目标类与对照类之间性质和特征上的不同，从而可以发现一系列的区分规则。 例如，为了将某种疾病与其他种类的疾病区分开，区分规则应能概括该疾病的不同于其他 疾病的症状。 1 5数据挖掘的方法 为了完成上述数据挖掘任务，人们从统计学、人工智能和数据库等领域借用基础研究成 果和工具，提出了多种方法。这里我们讨论具有代表性的几类： 统计分析方法 第7 页 国防科学技术大学研究生院学位论文 主要用于完成关联知识挖掘。对关系表中各属性进行统计分析，找到它们之间存在的关 系。在关系表的属性之间一般存在两种关系：函数关系( 能用函数公式表示的确定性关系) ； 相关关系( 不能用函数公式表示的关系) 。对它们可采用回归分析、相关分析、主成分分 析等统计分析方法。 决策树 用于分类。利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的 一个结点，再根据字段的不同取值建立树的分支；在每个分支子集中重复建立下层结点和分 支，这样便生成一棵决策树。接下来还要对决策树进行剪枝处理，然后把决策树转化为规则， 利用这些规则可以对新事例进行分类。典型的决策树方法有分类回归树( c a r t ) 、1 d 3 、c 4 5 等。 神经网络 用于分类、聚类等。神经网络模仿生物神经网络，本质上是一个分布式矩阵结构，它通 过对训练数据的学习逐步计算网络连接的权值。神经网络可分为以下三种： 前馈式网络：它以感知机、反向传播模型、函数型网络为代表，可用于预测、模式识别 等方面。 反馈式网络：它v a h o p f i e l d 的离散模型和连续模型为代表，分别用于联想记忆和优化计 算。 自组织网络：它以a r t 模型、k o h o l o n 漠型为代表，用于聚类。 人工神经网络具有分布式存储信息、并行地处理信息和进行推理、以及自组织自学习等 特点，解决了众多用以往方法很难解决的大复杂度问题。 在使用神经网络时有几点需要注意：一是神经网络很难解释，二是神经网络会学习过度， 记住太多细节而掩盖了规律性，三是训练一个神经网络可能需要相当可观的时间才能完成， 四是建立神经网络需要做的数据准备工作量很大，要想得到准确度高的模型必须认真地进行 数据清洗、整理和转换工作。 遗传算法 用于分类，关联规则挖掘等。遗传算法模拟了自然选择和遗传中发生的繁殖、交配和突 变现象，从任意一初始种群出发，通过随机选择、交叉和变异操作，产生一群新的更适应环 境的个体，使种群进化到搜索空间中越来越好的区域。这样一代代不断繁殖、进化，最后收 敛到一群最适应环境的个体上，求得优化的知识集。 粗糙集 用于数据约简，数据意义的评估，对象相似或差异性分析，分类等。粗糙集理论由 第8 页 国防科学技术大学研究生院学位论文 zp a w l a k 在8 0 年代提出，用于处理不确定性。进行规则挖掘的主要思想如下：把对象的属性 分为条件属性和决策属性。按各属性值相同分等价类。条件属性上的等价类e 与决策属性上 的等价类y 之间有三种情况：下近似：y 包含e 上近似：y 和e 的交非空：无关：y 和e 的 交为空。对下近似建立确定性规则，对上近似建立不确定性规则( 含可信度) ，对无关情况不 存在规则。 可视化技术 可视化技术使用户能交互式地、直观地分析数据，并用直观图形将信息模式、数据的关 联或趋势呈现给决策者，可视化技术将人的观察力和智能融合入挖掘系统，极大地改善了系 统挖掘速度和深度。 1 。6数据挖掘未来研究方向 当前，数据挖掘和知识发现研究方兴未艾，预计在本世纪还会形成更大的高潮，研究 焦点可能会集中到以下几个方面： ，智能的、有效的、可扩充的数据挖掘方法的研究仍是研究的热点： 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化； 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也便于在 知识发现的过程中进行人机交互： 研究在网络环境下的数据挖掘技术( w e b m i n i n g ) ： 加强对各种非结构化数据的开采，如对文本数据、图形数据、视频图像数据、声音 数据乃至综合多媒体数据的开采。 本文将主要研究数据挖掘的一个有效方法粗糙集方法，着重于粗糙集理论的研究及其 在数据挖掘中的应用两个方面。 1 7粗糙集研究的兴起 粗糙集理论是一种处理含糊、不精确性问题的新型数学工具，由波兰数学家zp a w l a k 在1 9 8 2 年首先提出i _ ”】的。在知识工程研究中，一直存在着信息的含糊性( v a g u e n e s s ) 等 问题，含糊性有三种，术语的模糊性，如高矮；数据的不确定性，如噪声引起的；知识自 身的不确定性，如规则的前后件间的依赖关系并不是完全可靠的。人工智能的基础理论之 一的经典逻辑不足以解决这些不确定性问题。为此，人们提出了一些解决方法，包括统计 方法、模糊集理论，以及d e m p s t e r - s h a f f e r 证据理论，但这些方法都有一些内在缺陷或限 定范围，例如模糊集方法存在一个本质问题即如何确定成员隶属度。相比之下，粗糙集方 法具有很人的优点，即不需要预先知道额外信息，如统计方法中要求的先验概率和模糊集 第9 页 国防科学技术大学研究生院学位论文 中要求的隶属度。 粗糙集理论自问世以来，无论是在理论或应用上都是一种新的、最重要的并且迅速发 展的研究领域。它在知识发现、机器学习、知识获取、决策分析、专家系统、决策支持系 统、归纳推理、矛盾归结、模式识别、模糊控制等方面的成功应用，引起了各国学者的广 泛关注。1 9 9 1 年p a w l a kz 出版了专著 7 9 1 ，系统全面地阐述了粗糙集理论，奠定了严密的 数学基础。该书与1 9 9 2 年出版的粗糙集理论应用专集【1 0 6 1 较好地总结了这一时期粗糙集理 论与实践的研究成果，