（计算机软件与理论专业论文）基于粗糙集理论的数据挖掘方法研究.pdf

摘要 随着数据库技术和i n t e m e t 的发展，数据挖掘引起了信息产业界的极大关注， 其主要原因是存在大量可供使用的数据，并且迫切需要将这些数据转换成有用的 信息。传统的信息处理技术已经不能很好地满足实际应用的需求，人们迫切需要 具有更强能力和更高效率的信息处理技术。波兰数学家z p a w l a k 于1 9 8 2 年提出的 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。粗糙集在数据挖掘 过程中，可用于数据挖掘的数据预处理部分。本文以此为出发点，以粗糙集理论 用于数据挖掘过程的相关步骤为线索，对下列几个问题进行了研究。 ( 1 ) 连续属性的离散化问题 粗糙集能很好的处理离散属性，但不能直接处理连续属性，在数据挖掘应用 中，经常需要进行连续属性离散化处理。本文提出了基于遗传算法的连续属性离 散化方法。该算法克服了基于支持度和基于重要性等离散化算法容易得到局部最 优解的缺点，实验证明文中的算法兼顾了属性离散化的全局性和准确性。 ( 2 ) 属性约简 通过比较现有约简算法的不足进行分析，提出了基于信息熵核子集应用遗传 算法的属性约简算法。引入信息熵的概念进行约简数据预处理，在约简过程中不 用求核，大大提高了算法收敛速度和约简效率。实验证明它是求取信息系统最小 约简较好的算法。 ( 3 ) 规则获取 在实际应用中，数据库中的数据往往是动态变化的，因此，对规则获取的增 量式算法的研究是知识发现领域所急需解决的问题之一。文章给出了一种基于粗 糙集和决策树的增量式规则获取算法，并与基于静态的知识系统的规则获取算法 和r r i a 算法进行了比较，实验结果表明该算法具有的更好的性能。 关键词：数据挖掘；粗糙集；连续属性离散化：属性约简；规则获取 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ed a t a b a s et e c h n o l o g ya n di n t e r n e t ，d a t am i n i n g a t t r a c t sg r e a ta t t e n t i o ni ni n f o r m a t i o ni n d u s t r y t h em a j o rr e a s o ni st h a tl a r g ea m o u n t o fe x i s t i n gd a t am a yb eu s e dw i d e l y , a n di ti su r g e n t l yn e c e s s a r yt oc o n v e r tt h e s ed a t a i n t od a t ai n t ou s e f u li n f o r m a t i o na n dk n o w l e d g e t r a d i t i o n a li n f o r m a t i o np r o c e s s i n g t e c h n i q u e sa r en o wn o ta d a p t i v et op r a c t i c a la p p l i c a t i o n s p e o p l en e e dm o r ep o w e r f u l a n dm o r ee f f i c i e n ti n f o r m a t i o np r o c e s s i n gt e c h n i q u e s ，w h i c hc a nd i s c o v e ri n t e r e s t i n g k n o w l e d g ef r o mm a s s i v ei n f o r m a t i o n ，t og u i d et om a k i n gd e c i s i o n s t h et h e o r yo f r o u g h s e t st h a tw a sp u tf o r w a r db yap o l i s hm a t h e m a t i c i a nn a m e dz p a w l a ki n1 9 8 2i s an e wt o o lf o rp r o c e s s i n gv a g u ea n du n d e r l i n e dk n o w l e d g e i nt h ew h o l ep r o c e s so f d a t am i n i n g ，r o u g hs e t si sa p p l i e di nt h ea s p e c to fp r e p r o c e s s i n go fd a t am i n i n g f r o mt h i sp o i n ta n dw i t ht h et h e o r i e so fr o u g hs e t si nd a t am i n i n gt op r e p a r et h e p r o c e s so fs t e pf o rc l u e s ，t h i st h e s i ss t u d i e saf e wp r o b l e m so ft h et h e o r y t h ef o l l o w i n ga r es o m em a i np o i n t sd i s c u s s e db yt h et h e s i s ： ( 1 ) t h ep r o b l e mo fc o n t i n u o u sa r r t i b u t e sd i s c r e t i z a t i o n r o u g hs e t sc a nd e a lw i t ht h ed i s c r e t ea t t r i b u t e so u t s t a n d i n g l y ；h o w e v e r , i tc a n t p r o c e s st h ec o n t i n u o u sa t t r i b u t e s t h u sw en e e dt oc h a n g et h ec o n t i n u i t yi n t o t h e d i s c r e t i z a t i o ni nt h ep r a c t i c a la p p l i c a t i o ni nd a t am i n i n g t h i st h e s i sa p p r o a c h e sa d i s c r e t i z a t i o nm e t h o do fc o n t i n u o u sa t t r i b u t e sb a s e do ng a a n dt h i sm e t h o dc a na v o i d o b t a i n i n gl o c a l l yo p t i m i z e dr e s u l t sw h e nu s i n gd i s c r e t i z a t i o nm e t h o db a s e do ns u p p o r t a n di m p o r t t h ee x p e r i m e n tp r o v e st h a t t h i sa l g o r i t h m sl o o k sa f t e rb o t ht h eo v e r a l l s i t u a t i o na n da c c u r a c yi nd i s c r e t i z a t i o na t t r i b u t e s ( 2 ) a t t r i b u t e sr e d u c t i o n a n a l y s i st h es h o r t a g eo ft h ec u r r e n tr e d u c t i o na l g o r i t h m ，t h i st h e s i sa p p r o a c h e s b a s e do ni n f o r m a t i o ne n t r o p yc o r es e t sg e n e t i ca t t r i b u t e sr e d u c t i o na l g o r i t h m i n t r o d u c i n gi n f o r m a t i o ne n t r o p yt h e o r yt op r e p r o c e s st h er e d u c t i o nd a t a ，i nt h ep r o c e s s o fr e d u c t i o n ，i tc a ne n h a n c et h ec o n v e r g e n c es p e e do fa l g o r i t h ma n da d v a n c et h e r e d u c t i o ne f f i c i e n c y t h ee x p e r i m e n tp r o v e st h a ti ti st h eg o o da l g o r i t h m s ，w h i c hc a n g e tt h eb e s tr e d u c t i o ni ni n f o r m a t i o ns y s t e m ( 3 ) r u l e sp i c k - u p i nt h ec u r r e n t u t i l i t y ，t h e d a t ai nd a t a b a s ei s a l w a y s i n c r e m e n t a l t h e r e f o r e i n c r e m e n t a lr e d u c t i o no fr u l e si sat o p i co fg e n e r a li n t e r e s ti nt h ef i e l do fk n o w l e d g e d i s c o v e r y i nt h i st h e s i s ，a ni n c r e m e n t a ll e a r n i n gm e t h o db a s e do nr o u g hs e tt h e o r ya n d d e c i s i o nt r e e st e c h n i q u e si sp r o p o s e d t h e ni ti sc o m p a r e dw i t hc l a s s i c a la n dr r i a a l g o r i t h m t h er e s u l t ss h o wt h em e t h o da n de f f e c to ft h ea l g o r i t h ma r eb e t t e r k e yw o r d s ：d a t am i n i n g ；r o u g hs e t ；d i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e s ； a t t r i b u t er e d u c t i o n ；r u l e sp i c k - u p 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名： 稽平日期：2 0 0 8 鹎月侣日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密e z l 。 ( 请在以上相应方框内打“4 ”) 作者签名： 1 学平 导师签名： 罗歹 日期：2 0 0 8 年占月f g 日 日期：2 0 0 8 年亏月i g 日 1 1 研究目的和意义 第一章绪论 当今，社会已经进入了网络信息时代，计算机技术在这十几年来得到了迅猛 的发展，特别是存储技术、数据库技术和网络技术。存储设备单位价格的不断下 跌、容量的急剧扩大，关系数据库、对象数据库、多媒体数据库、地理信息数据 库和空间数据库的不断成熟并得到广泛的应用，数据库管理系统的日益普及，自 动数据采集系统的引入以及互联网络在全球的不断深入应用，这些都使得人们轻 而易举地就可以获得容量达g b 甚至t b 的数据，并且这些数据每天还在不断地 增长。因此，如何从大量的、杂乱无章的、强干扰的数据中挖掘出潜在的、有利 用价值的信息，便成为人类智能信息处理中面临的前所未有的挑战。由此产生了 人工智能研究的一个崭新领域一一数据挖掘( d a t am i n i n g ，简称d m ) p , 2 】。 数据挖掘是一个多学科领域，它从多个学科吸取营养。这些学科包括数据库 技术、人工智能、机器学习、模式识别、统计学、高性能计算和可视化技术等。 数据挖掘是一个新兴的具有广泛应用前景的研究领域。 有效可行的数据挖掘对于人们了解、掌握信息具有极其重要的意义。目前， 数据挖掘中常用到的方法有：统计分析方法、决策树、神经网络、遗传算法、模 糊集方法、粗糙集理论、可视化技术等等。在这些方法中，粗糙集理论与方法对 于处理复杂系统不失为一种较为有效的方法。因此研究基于粗糙集理论的数据挖 掘方法有着极其重要的理论意义和现实意义。 1 2 数据挖掘综述 1 2 1 数据挖掘定义 数据挖掘1 2 j ( d m ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是有用的潜在信息 和知识的过程。也有一些文献把数据挖掘称为知识抽取( k n o w l e d g ee x t r a c t i o n ) 、 数据考古( d a t aa r c h a e o l o g y ) 、数据捕捞( d a t ad r e d g i n g ) 等等。国内学者也把d a t a m i n i n g 译为数据采掘或数据开采。通过数据挖掘，把有价值的知识、规则从数据 库的相关数据集合中抽取出来，为决策提供依据。 1 2 2 数据挖掘的结构和过程 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 s ，简称k d d ) 过程中的关键步骤，一般也把数据挖掘称为 知识发现。知识发现是指从数据中发现有用知识的整个过程，数据挖掘是这一过 程中的一个特定步骤。知识发现包括数据选择、数据预处理、数据转换、数据挖 掘、模式解释和知识评价等多个步骤，是应用特定数据挖掘算法和评价解释模式 的一个循环反复过程，并要对发现的知识不断求精深化，使其易于理解；数据挖 掘是知识发现过程中的一个关键步骤，它利用特定的数据挖掘算法从数据中抽取 模式，数据挖掘算法是数据挖掘与知识发现整个过程的核心。知识发现强调知识 是数据挖掘的最终产品，利用相应的数据挖掘算法，按指定方式和阈值提取有价 值的知识，因此，知识发现包括数据挖掘前对数据的预处理、抽样及转换和数据 挖掘后对知识的评价解释等方面，而数据挖掘是知识发现整个过程中的一个步骤。 图1 1 p j 是一个知识发现的处理过程示意图 知识 图1 1 知识发现的处理过程 2 ) 知识发现的过程 知识发现1 4 j 的过程分为三个阶段：数据准备( d a t ap r e p a r a t i o n ) ，数据挖掘及 结果解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 。 ( 1 )数据准备：它包括，选择数据一一根据用户需要从原始数据库和数据 仓库中提取数据挖掘的目标数据集；数据预处理一一进行数据再加工，包括检查 数据的完整性及数据的一致性、去噪声、填补丢失的值、删除无效的数据等；数 据变换一一从初始特征中找出真正有用的特征以减少数据挖掘时要考虑的特征变 量的个数，以便达到消减数据维数或降维的目的。 ( 2 )数据挖掘：数据挖掘阶段首先要确定挖掘的任务或目的，如数据分类 聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什 么样的挖掘算法。选择算法有两个考虑因素：一是不同的数据有不同的特点，因 此需要用与之相关的算法来挖掘；二是要根据用户或实际运行系统的要求，有的 用户可能希望获取描述型的，容易理解的知识，而有的用户只是希望获取预测准 确度尽可能高的预测型知识。选择了挖掘算法后，就可以实施数据挖掘操作，获 取有用的模式。 ( 3 )结果解释和评估：数据挖掘阶段发现出来的模式，经过评估可能存在 冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则 需要回退到发现过程的前面阶段，如重新选取数据，采用新的数据变换方法，设 定新的参数值，甚至换一种挖掘算法等。另外，由于最终是面向用户的，因此可 能要对发现的模式进行可视化，或者把结果转换为用户易懂的另一种表示形式， 如把分类决策树转换成为“l f t h e n 规则。 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个影响要 素：一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数量。 1 2 3 数据挖掘的任务 按照数据挖掘技术所能够发现的知识，将常见的数据挖掘任务分为关联分析、 分类、聚类、偏差检测、序列模式和预测等类型。 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) ：它所要做的是从客户指令的数据库中挖掘 出满足一定条件的依赖关系。若两个或多个数据项的取值之间重复出现且概率很 高时，就存在某种规律性，则可以建立起它们的关联规则。 2 ) 分类( c l a s s i f i c a t i o n ) ：分类是数据挖掘中应用得最多的任务。它所做的是 已知训练信息的特征和分类结果的基础上，为每一个类别找到一个合理的描述或 模型，然后再用这些分类的描述或模型来对未知的新数据进行分类。其中比较典 型的分类模型是线性回归模型、决策树模型、神经网络模型等。 3 ) 聚类( c l u s t e r i n g ) ：是根据一定的规则，合理地划分记录集合，并用显示或 隐性的方法描述不同的类别。而所依据的这些规则是聚类分析工具自己定义的。 许多在分类分析法中适用的算法同样适用于聚类分析法。聚类有时直接满足用户 的要求，有时是其他发现过程的“预处理 。例如，由聚类所产生的类可以作为决 策树生成算法的目标概念，也可作为偏差分析的基础。 4 ) 偏差检测( d e v i a t i o nd e t e c t i o n ) ：指通过数据分析，发现异常情况的过程。 其基本方法就是寻找观察结果与参照物之间的差别。偏差包括很多有用的规则和 知识，如分类中的反常实例、观察结果对模型预测的偏差，量值随时间的变化等 等。偏差检测的数据模型有极值点、断点、拐点、和边界等不同的偏差对象。 5 ) 序列模式( s e q u e n c ep a t t e r n ) ：是指从业务数据中的所有细节数据和事务的 历史数据中搜索出重复发生且概率较高的模式。它与关联分析有点相似，都是要 找出数据之间的互相联系，但序列分析更侧重于研究数据间的前后因果关系，有 个时间上的概念。 3 6 ) 预测( p r e d i c t i o n ) ：当分类的工作偏向于插入漏掉的数据、预测数据分类或 发展的趋势，此时的工作即为预测分析。即指从现有的数据中找出规律性，建立 模型，并用此模型预测未知事例的种类、特性等。 1 2 4 数据挖掘常用的技术分类 数据挖掘中采用的方法综合了数据库、人工智能、统计学、模式识别、机器 学习、数据分析等领域的研究成果【5 1 。现有的数据挖掘方法主要有以下几种： 1 ) 决策树方法 利用信息论中的信息增益寻找出数据集中具有最大信息的字段，建立决策树中 的每一个结点，再根据字段的不同取值建立树的分支的过程，就是建立决策树过 程。国际上最有影响的决策方法是q u i n l a n 研究的i d 3 方法。 2 ) 神经网络方法 它模拟人脑神经元结构，以m p 模型规则为基础，建立了三大类神经网络模 型【6 1 。 ( 1 ) 前馈式网络，以反向传播模型，函数型网络为代表，用于预测、模式识另i 上 等方面。 ( 2 ) 反馈式网络，以h o p f i e l d 离散模型和连续模型为代表，分别用于联想记忆 和优化计算。 ( 3 ) 自组织网络，以a p t 模型，k o h o l o n 模型为代表，用于聚类。 3 ) 模糊论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策，模糊模式识别和模糊 聚类分析。模糊性是客观存在的，系统的复杂性越高，模糊性越强，这是z a d e h 总结出的互克性原理。 4 ) 遗传算法 这是模拟生物进化过程的算法，由三个基本算子组成： ( 1 ) 选择，是指从一个旧种群( 父代) 中选出生命力强的个体，产生新种群( 后 代) 的过程。 ( 2 ) 交叉，是选择两个不同个体的部分进行交换，形成新的个体。 ( 3 ) 变异，对某些个体的某些基因进行变异。 遗传算法已在优化计算和分类机器学习等方面发挥了显著的作用。 5 ) 统计分析方法 在数据库字段项之间存在两种关系1 7 ，：第一，函数关系( 能用函数公式表示的 确定性关系) ；第二，相关关系( 不能用函数公式表示，但仍是相关确定关系) 。 对它们的分析采用如下方法：回归分析、相关分析、主成分分析等。 6 ) 贝叶斯网络 贝叶斯网络基于后验概率的贝叶斯定理l8 1 ，是建立在对数据进行统计处理基础 上的方法。将不确定事件通过网络连接起来，可以对与其他事件相关的事件结果 进行预测，其网络变量可以是可见的，也可以隐藏在训练样本中。贝叶斯网络具 有分类、聚类、预测和因果关系分析的功能。其优点是易于理解，预测效果好， 4 缺点是对发生频率很低的事件预测效果不好。在医学和制造业等领域的应用具有 较好的效果。 7 ) 粗糙集方法 粗糙集理论是上世纪8 0 初z p a w l a k 针对g f i r e g e 的边界域思想提出的， 基于给定训练数据内部的等价类的建立，用上下近似集合来逼近数据库中的不精 确概念。用于分类，可以发现不准确数据或噪声数据内在的结构联系；用于特征 归约，可以识别和删除无助于给定训练数据分类的属性；用于相关分析，可以根 据分类任务评估每个属性的贡献或意义。其主要思想是在保持分类能力不变的前 提下，通过知识约简，导出问题的决策树或分类规则。 1 2 5 数据挖掘的展望 数据挖掘今后可能的研究方向是： 1 ) 加强应用研究，设计针对不同数据挖掘任务的专用数据挖掘系统。不同的 应用领域可能使用多种类型数据和数据库；知识发现系统应当能够对不同类型的 数据和数据库进行有效的数据挖掘。虽然大多数数据库是关系型的，但许多实际 应用的关系数据库还可能含有复杂的数据类型，如结构数据和复杂数据对象，文 本和多媒体数据、空间和时态数据，事务数据以及历史数据等，因此，一个功能 很强的数据挖掘系统应能对各种复杂数据类型进行挖掘，鉴于数据类型的差异和 不同的数据挖掘目的，要求一个数据挖掘系统能够处理各种类型数据是不现实的， 应当根据特定类型数据的挖掘任务构造专用的数据挖掘系统，如关系数据挖掘、 空间数据挖掘等。 “ 2 ) 高效率挖掘算法。为能从海量数据( 特别是大型数据库) 中有效地抽取信 息，数据挖掘算法必须是高效的，即算法的运行时间必须是可预测的和可接受的， 带有指数级的算法，没有实际使用价值。 3 ) 提高数据挖掘结果的有效性，确定性和表达性。已发现的知识应能准确地 描述数据库中的内容，并能用于实际领域。对有缺陷的数据应当根据不确定性度 量，近似规则或定量规则形式表示出来。数据挖掘系统还应能很好地处理和抑制 噪声数据和不希望的数据。所以要研究度量知识质量的方法，包括模型和工具的 实用性和可靠性。 4 ) 数据挖掘结果的可视化。数据挖掘的最后阶段是分析已发现的知识，有多 种不同的分析观点和表示形式，要求用高级语言( 最好是自然语言) 或图形界面 表示数据挖掘需求和已发现的知识，并采用合适的知识表示技术。这样，数据挖 掘任务就可由非领域专家指定，也便于用户理解和直接应用已发现的知识。 5 ) 多抽象层上的交互式数据挖掘。要预测从数据库中实际上能够发现什么是 很困难的，所以要采用高级数据查询去调查和揭示某些可进一步探索的踪迹。交 互式数据挖掘允许用户交互地精练数据挖掘需求，动态改变数据焦点，逐步深化 数据挖掘过程，从不同角度不同抽象层次上灵活地观察数据和挖掘结果。 6 ) 多源数据挖掘pj 。计算机网络( 包括局域网和广域网，特别是i n t e r n e t ) 把 许多数据源联接在一起，形成巨大的分布式异构数据库。不同来源数据的格式和 5 语义可能不统一，数据挖掘系统应当能够帮助用户揭示异构数据库中的高级数据 规律。数据库规模的扩大，数据分布的广泛性，以及分布式数据挖掘的复杂性， 促进了并行和分布式数据挖掘算法的研究。在分布式数据挖掘研究方面，今后应 特别重视把数据挖掘技术与i n t e r n e t 技术及w e b 技术紧密结合起来，开发出基于 i n t e r n e t 和w e b 的数据挖掘软件工具。同时，加强对分布式软代理( a g e n t ) 技术 的研究和应用。 7 ) 数据挖掘的安全性和保密性。当从不同角度和不同抽象层次观察数据的时 候，就要考虑数据的安全性和保密性，防止侵犯别人的隐私和泄露敏感信息。 8 ) 实现与现有数据库系统或数据仓库的无缝集成，进一步扩大数据挖掘工具 的应用范围和提高现有数据的利用率。 1 3 本文的组织 本文章节及内容的安排如下： 第一章绪论。概述数据挖掘研究的目的和意义、数据挖掘定义等基本知识。 第二章粗糙集理论。介绍粗糙集的基本知识，为后续章节做理论基础。 第三章连续属性的离散化。提出了基于遗传算法的连续属性离散化方法，在 遗传算法中利用属性的支持度为控制条件，合理的控制了遗传进化的代数，从而 提高了算法的效率得到较好的离散化结果，提高了离散化值的准确性，为后面的 属性约简操作提供了方便。 第四章属性约简。提出了基于信息熵核子集应用遗传算法的属性约简算法， 引入信息熵的概念进行属性约简，在约简过程中不用求核，大大提高了算法收敛 速度和约简效率。 第五章规则获取。以粗糙集理论为基础，根据新增数据集与已有规则集的关 系，提出了一种基于粗糙集和决策树的增量式规则获取算法，通过与基于静态的 知识系统的规则获取算法和r r i a 算法进行了对比分析，表明该算法性能更好。 第六章结论与展望。总结了本文的研究工作，提出进一步研究的方向。 6 第二章粗糙集理论 2 1 粗糙集理论的研究背景 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种数据分析理论1 1 0 j 。 它是一种处理含糊( v a g u e n e s s ) 和不确定( u n c e r t a i n t y ) 信息的新型数学工具。 p a w l a k 针对模糊逻辑的创始人f r e g e 的“边界线区域”( b o u n d a r yr e g i o n ) 思想， 提出了粗糙集，它把无法确定的个体都归属于边界线区域，而这种边界线区域被 定义为上近似集和下近似集的差集【l 。粗糙集体现了集合中对象的不可区分性， 即由于知识的粒度而导致的粗糙性。自从粗糙集理论诞生以来，它不仅为信息科 学和认知科学提供了新的科学逻辑和研究方法，而且为智能信息处理提供了有效 的处理技术。由于它的这些固有优点，人们对它的研究日益深入。 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 l a s p e c t so fr e a s o n i n ga b o u td a t a ”l lz j 和1 9 9 2 年s l o w i n s k ir 主编的”i n t e l l i g e n t d e c i s i o ns u p p o r t ：h a n d b o o ko fa p p l i c a t i o n sa n da d v a n c e so fr o u g hs e t st h e o r y ，【1 3 l 的出版，奠定了粗糙集理论的基础，并推动了粗糙集理论与应用的深入研究。 1 9 9 2 年在波兰k i e k r z 召开了关于粗糙集理论的第1 届国际学术会议，这次 会议讨论了集合近似定义的基本思想及其应用，其中粗糙集环境下机器学习的基 础研究是这次会议的四个专题之一。以后每年都召开一次以粗糙集理论为主题的 国际研讨会1 1 4 j 。 1 9 9 3 年在加拿大b a n f f 召开了第2 届国际粗糙集与知识发现研讨会，其主题 是粗糙集、模糊集与知识发现。这次会议介绍了许多基于扩展的粗糙集理论的知 识发现方法与系统。 1 9 9 4 年在美国s a nj o s e 召开了第3 届国际粗糙集与软计算研讨会，这次会 议广泛地探讨了粗糙集与模糊逻辑、神经网络、进化计算等的融合问题。 1 9 9 5 年粗糙集的主要倡导者在第1 1 期a c m 通讯上撰文，概括地介绍了粗 糙集基本概念及其在知识获取、机器学习、决策分析、知识发现等领域的具体研 究项目和进展。特别在1 9 9 5 年召开的第4 届模糊理论与技术国际会议上对模糊集 和粗糙集的相互关系展开了讨论，极大地促进了粗糙集的发展。 2 0 0 0 年，在加拿大b a n f f 召开了粗糙集与计算趋势国际会议。这次会议极大 地推动了粗糙集理论在软计算数据库，人工智能和近似推理等方面的发展。 随着发展许多重要的国际学术会议都把粗糙集理论的研究列入主要内容之 2 2 粗糙集理论的研究现状 将粗糙集理论应用于数据挖掘具有明显的优越性一一它无需提供所需处理的 7 数据集合之外的任何先验信息，利用数据集上的等价关系对知识的不确定程度进 行度量，从而避免了对知识的主观评价( 如证据理论中的信念函数，模糊理论中 的隶属度函数) 所带来的误差。恰恰是这一点，使得粗糙集理论在数据挖掘中具 有更强的生命力。 近几年来，粗糙集理论已应用于机器学习、决策支持、知识发现、专家系统、 模式识别等领域。目前对粗糙集理论的研究主要集中在求解属性的最小约简、较 小约简和最简规则集等方面【”】。粗糙集有效算法方面的研究包括如何求等价类、 上近似、下近似、正区域、约简和核等等。 我国对粗糙集理论的研究，主要集中在对它的数学性质，有效算法的研究， 如粗糙集理论的知识表示、知识约简算法、粗糙逻辑等。 随着粗糙集理论在我国的逐步普及，现在国内研究粗糙集的人越来越多。为 了促进这一理论在中国的发展，中国计算机协会人工智能与模式识别专业委员会 于2 0 0 1 年5 月在重庆邮电学院召开了第一届粗糙集与软计算学术研讨会，以共同 探讨粗糙集理论及其应用研究的新内容和新方法【1 6 j 。 已经开发的基于粗糙集理论的知识发现系统主要有1 1 7 j ： l e r s ( 1 e a r n i n gf r o me x a m p l e sb a s e do nr s ) 系统是美国k a n s a s 大学开发的基于 粗糙集的实例学习系统，该系统是用c o m m o nl i s p 在v a x 9 0 0 0 上实现的，主要 用于环境保护、气候研究和医疗研究等。 r o s e 系统是波兰p a z n a n 工业大学计算科学研究所智能决策支持系统实验室 研制的。该系统实现了p a w l a k 的基本粗糙集模型和可变精度粗糙集模型，并成功 应用于医学、药剂学，技术诊断、金融和管理科学、图像与信号处理、软件工程 评估等。 k d d r 系统是由加拿大r e g i n a 大学研制的，它基于可变精度粗糙集模型，采 用知识发现的决策矩阵方法。该系统具有w i n d o w s x 的菜单驱动界面，用于医学 数据分析和电信市场的决策分析等。 r o u g he n o u g h 是挪威t r o l ld a t al n c 公司开发的，包括数据输入，预处理、编 辑、生成可辩识矩阵、集合近似，约简、生成规则、预测和分析。 除了以上几种系统外，还有国内研究出的一些系统，如中科院计算技术研究所 开发的k d t ，南京大学研制的k n i g h t 等。 2 3 粗糙集概念 2 3 1 信息系统 粗糙集方法属于数学方法，但又不同于数学中一般的集合概念。它从“知识” 的角度处理客观事物的不确定性，认为知识是一种将现实或抽象的对象进行分类 的能力，即将分类与知识联系在一起；并且用一个术语“等价关系”r 来形式化 地表示分类，这样知识就可以理解为等价关系r 对论域( 由所感兴趣对象组成的 非空有限集合) u 的划分所得的u 中的子集称作基本概念或范畴。它们的关系如 8 图2 1 所示： 图2 1知识与分类示意 粗糙集理论对一个集合的描述只取决于一致的关于论域的“知识”，无须任何 先验信息，避免了主观因素的影响，区别于概率、模糊集和证明理论等方法。 为了便于机器处理，粗糙集理论将知识表示为信息系统的形式。p a w l a k 详细 论述了信息系统【1 8 】( i n f o r m a t i o ns y s t e m ) 的概念，用不分明关系定义粗糙集，这 是粗糙集的早期方法；近期已扩展到在一个信息系统中用属性集来定义r o u g h 集。 信息系统的定义如下： 定义2 1 ：四元组【1 9 i s = 是一个知识表达系统，其中u 表示对象的 非空有限集合，u = u l , u 2 ，u n 即为论域咆表示数据库中的一条记录； a=cu d 是属性( a t t r i b u t e ) 集合，子集c = a 1 ，a 2 a 称为条件属性集，d = d ) 称为决 策属性集；v 是属性值组成的集合；f 是信息函数( i n f o r m a t i o nf u n c t i o n ) ，用于 将记录u 转换为在属性a 上的取值： 厂：u x a _ v ，即，0 ，口) = v ( u c u ，a c a ，v c v ) 信息系统可以很方便地用数据表表示，表的行代表对象h c u ，列代表属性 a c a ，表中的数值代表对象u 对应属性a 的属性值，记为a ( u ) 。上面所定义的信 息系统s ，若 d 不存在，就是一般意义上的信息表达系统；若 d 存在，一般称为 决策信息系统。实际上，决策表系统是一般信息系统的特例。例如表2 1 是一个信 息系统。 表2 1 一个信息系统 1 1 1a l ( u 0 a j ( u 1 )a m ( u 1 ) a l ( u i ) a j ( u i ) a m ( u i ) 表2 2 是一个基于小汽车性能的决策表系统，其中u = 1 ，2 ，8 】，在这8 中情 9 况下，类型有大，中，小取值；机型有柴油，汽油取值等；加速有差，好，极好 三种取值情况。c = 类型，机型，颜色 ；d = 加速) 。对于任意对象咋，“，我们 关心在这种信息系统s 中，什么样的小汽车条件适宜加速。粗糙集理论，恰恰是 直接从给定问题的描述集合出发，通过不可分辩关系和等价类确定给定问题的近 似解。 表2 2 一个基于小汽车性能的决策表系统 2 3 2 不可分辨关系与上下近似集 粗糙集理论延伸扩展了经典的集合论，把用于分类的知识嵌入集合内，作为 集合组成的一部分。一个对象n 是否属于集合x 需根据现有的知识来判断，可分 为三种情况1 2 0 l ： 1 ) 对象n 肯定属于集合x ； 2 ) 对象n 肯定不属于集合x ； 3 ) 对象u 可能属于也可能不属于集合x 。 集合的划分密切依赖于我们所掌握的关于论域的知识，是相对的而不是绝对 的。 定义2 2 ： 不可分辨关系【2 1 1 ( 1 n d i s c e r n i b i l i t yr e l a t i o n ) 在信息系统s 中，对任意a e a ，对象e u ，有属性值a ( u i ) 存在且不为空。在该 假设下，p a w l a k 的粗糙集方法是基于不可分辨关系( 或称等价关系) ，记为i n d ) ： i n d ( a ) = 【 f ，u ，) u ul v a e a ，口 f ) = a ( u ) 】 对s 的处理为：将对象集【厂按不可分辨关系进行划分，记为u i n d ( a ) ( 有时也 简记为u 彳，下同) ，表明在u i n d ( a ) 的一个划分中任意两个对象，在属性集a 下 它们的取值相同。 1 0 定义2 3 ： 等价类【2 1 】( e q u i v a l e n c ec l a s s e s ) 在s 中，如果b _ c a ，则对任意x u ，等价类，记y g i x i b 【石】口= ) ，【，io ，y ) ( b ) ) = ye viy i n d ( b ) x ) 显然，在属性集b 的描述下，i x 】b 中的任意元素之问包含x 对应属性值相同， 因此它们之间不可区分。所有i n d ( b ) 得到的等价类便构成了论域u 上的划分： u i n d ( b ) 。 下面举例说明： 在表2 2 实例中，假设b 一扣，c 】；则i n d p ) 构成的等价类： 【1 】b = 1 ，5 ) 【2 】b = 2 ，8 ) 【3 1 b = 3 ，6 【4 】b = 4 【7 】b = 7 u i n d ( b ) = 【1 】b ，【2 b ， 3 i b ，【4 b ，【7 】b ) 性质2 1 1 2 2 l ：在s 中，如果b 月，则对任意x e u ， x l 口。2 吼。 在表2 2 实例中，1 1 口，- l 4 , 5 1 ，【1 】 。 一仉毋， 1 1 一仉5 = 【1 】 。 同样可以验证 其它项。 定义2 4 ：集合的近似( s e ta p p r o x i m a t i o n s ) 在掌握了不可分辨关系( 等价关系) 的概念后，我们引入粗糙集中另两个非常 重要的概念：上近似集与下近似集【2 3 1 。 令x u ，r 为u 上的一个等价关系。当x 能够表达成某些r 基本范畴时， 则称x 是r 可精确定义的，称作r 精确集；否则x 为r 不可精确定义的，称作r 非精确集或r 粗糙集。 r 可定义集是论域的子集，它可在知识库k 中精确地定义，而r 不可定义集 不能在这个知识库中定义。r 可定义集也称作r 精确集，而r 不可定义集也称为 r 非精确集或r 粗糙集。 对粗糙集的近似定义，可以使用两个精确集，即上近似( u p p e r a p p r o x i m a t i o n ) 和下近似( t o w e r a p p r o x i m a t i o n ) 来描述。 假设给定s ，对于每个子集x u 和一个等价关系r ，记不分明关系 h z d 俾) = ，以 ，由其得出的x 的下近似集和上近似集，边界分别可以用r 的基 本集依次定义如下： 冠( x ) = 0 0 4 , l ye u i n d ( r ) 且y x r ( x ) = u iye u i n d ( r ) 且vnx 一妒 b n r ( x ) = r ( 彳) 一足( x ) 兄( x ) 是由那些根据已有知识r 判断肯定属于x 的对象所组成的最大的集合， 即所有包含于x 的基本集y i 的并，有时也称为x 的正域( p o s i t i v er e g i o n ) 记作 p o s ( r ，x ) ，而把u r ( x ) 称为负域，记为n e g r ( x ) 。r ( x ) 是那些可能属于x 的对象组成的最小集合，即所有与集合x 交不为空的基本集y i 的并。b n r ( x ) 是那 些根据知识r 不能判断是否属于x 的对象组成的集合。显然： 尺( x ) = p o s ( r ，x ) u 剧僻) 。它们正好代表了上面提到的三种情况。 性质2 2 1 2 4 l ：( 1 ) x 为r 可定义集( 精确集) 当且仅当r ( x ) = 兄( x ) ； ( 2 ) x 为r 粗糙集当且仅当尺似) 乒兄( j ) 。 例2 1假设b = 【c ；x = 1 ，2 ，5 ，6 ，7 ，8 ) ，则【l l b = 1 ，5 ) ；【2 1 b = 2 ，7 ，8 ) ；【3 】b = 3 ， 4 ， 6 ) ； u i n d ( b ) = 【1 2 3 】口 由【1 k x ，【2 l x ，所以b ( x ) = 【1 ku 1 2 口； 由xn 【1 k ，xn 【2 l 一且xn 3 1 口譬驴，所以及( x ) = 【1 ku 【2 】口u 【3 l - u ；