（农业机械化工程专业论文）基于粗糙集理论的数据挖掘研究.pdf

摘要 随着计算机、网络和通讯等信息技术的高速发展，信息的增长呈现超指数 上升。信息量的急剧增长，使传统数据库的检索查询机制和统计分析方法已远 远不能满足现实的需要，许多数据来不及分析就过时了；也有许多数据因其数 据量极大而难以分析数据间的关系。如何从大规模的数据中挖掘深层次的知识 和詹息，而不仅仅是数据表面的信息，已经成为众多领域的研究热点。在这样 的背景下，新的数据处理技术知识发现便应运而生。 知识发现是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可 理解的模式的非平凡过程。数据挖捉是知识发现过程中蛉核心步骤，是昼箭辊 当活跃的研究领域。 粗糙集理论是波兰数学家p a w l a k z 于1 9 8 2 年提出的一种分析模糊和不确定 知识的强有力的数学工具。粗糙集理论作为人工智能领域的一个新韵研究热点 它能够有效地处理不完整、不确定知识的表达和推理。这个特点使得粗糙集理 论非常适合应用于数据挖掘。目前，基于粗糙集理论的数据挖掘方法已经成为 主要的数据挖掘方法之一。研究基于粗箍集理论的数据挖掘具有极大的理论意 义和现实意义。 介绍了粗糙集和数据挖掘的相关理论。在深入研究经典粗糙集理论的一些 不足后，我们提出了一种粗糙集的拓广模型，即带隶属度及权重的粗糙集模型。 在这种模型中，我们给出了带隶属度及权重的信息系统，进行了噪音的处理、 近似空间的划分、决策属性对条件属性的依赖度的计算、属性的约简、关联规 则挖掘步骤的建立等方面的研究，并用算例验证了该模型是可行的。这种粗糙 集的拓广模型克服了经典粗糙集分类过于严格、对噪音过于敏感、某些隐藏在 边界中的规则丢失等缺陷。它完全继承了粗糙集的性质，拥有粗糙集的所有优 点。该模型提供了一种数理统计中常用的在一个给定错误率的条件下将尽可能 多的对象进行分类的方法。该模型将在信息系统分析、人工智能及应用、决策 支持系统、知识发现、模式识别、分类以及故障诊断等方面取得较好的应用。 今后的工作是开发基于这种粗糙集模型的实用软件系统和理论上的深入研 究。 关键词；数据挖掘：知识发现；粗糙集：约简：分明矩阵 r e s e a r c h0 1 1r o u g hs e t st h e o r yb a s e dd a t am i n i n g w a n gs h u q i n g a g r i c u l t u r a lm e c h a n i z a t i o ne n g i n e e r i n g d i r e c t e db yp r o f e s s o rj i a n gw e n k e a b s t r a c t w i 恤t h er a p i d d 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 s u c ha s c o m p u t e r n e t w o r k c o m m u n i c a t i o na n ds oo n ，t h ei n c r e a s eo fi n f o r m a t i o nt a k e so ng o i n gu p b e y o n dt h ee x p o n e n t i a ls p e e d t h em e c h a n i s mo fs e a r c h e sa n dq u e r yo f t r a d i t i o n a l d a t a b a s e sa n dt h em e t h o do fs t a t i s t i c a la n a l y s i sg r e a t l yc a n n o tm e e tt h er e a l i s t i c d e m a n dw i t ht h ei n f o r m a t i o ns h a r pi n c r e a s i n g l o t so fd a t ai so u t d a t e db e f o r ei t s a n a l y s i s a n di t i st o od i f f i c u l tt oa n a l y z et h er e l a t i o n sa m o n gag r e a td e a lo fd a t a b e c a u s et h ed a t ai st o om u c h i th a sb e c o m er e s e a r c hh o t s p o ti nm a n yf i e l d st h a th o w n o to n l yo s t e n s i b l eb u ta l s oe m b e d d e dk n o w l e d g ea n di n f o r m a t i o na r em i n e df r o ma g r e a td e a lo f d a t a i nt h eb a c k g r o u n d ，t h en e w t e c h n o l o g yo fd a t ap r o c e s s i n g ，t h a ti s k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，i sp r o d u c e d 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 si st h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ， n o v e l ，p o t e n t i a l l yu s e f u la n du l d m a t e l yu n d e r s t a n d a b l ep a t t e r n si n d a t a b a s e s d a t a m i n i n gi s t h ec o r es t e pd u r i n gt h ec o u r s eo fk n o w l e d g ed i s c o v e r yi nd a t a b a s e a t p r e s e n t i ti saq u i t ea c t i v er e s e a r c hf i e l d t h et h e o r yo fr o u g h s e t s p r e s e n t e di n 19 8 2 b yp o l i s hm a t h e m a t i c i a np a w l a kz i sap o w e r f u lm a t h e m a t i c a lt o o lf o ra n a l y z i n g , u n c e r t a i n ，f u z z yk n o w l e d g e r o u g h s e t s ，a san e w h o t s p o ti nt h ef i e l do f a r t i f i c i a li n t e l l i g e n c e ，c a ne f f e c t i v e l yd e a lw i t h t h ee x p r e s s i o na n dd e d u c t i o no fi n c o m p l e t e u n c e r t a i nk n o w l e d g e n l et h e o r yo f r o u g h s e t si ss p e c i a l l yf i tf o rt h ea p p l i c a t i o nt od a t a - m i n i n gb e c a u s eo fi t sf e a t u r e s n o wt h em e t h o do fd a t a - m i n i n gb a s e do nr o u g hs e t sh a sb e c o m eo n eo ft h em a i n m e t h o d so fd a t a - m i n i n g t h e , s t u d yo nr o u g hs e t sb a s e dd a t am i n i n gh a sg r e a t l y t h e o r e t i c a la n dr e a l i s t i cm e a n i n g ， t h ec o r r e l a t i v et h e o r yo fr o u g hs e t sa n dd a t am i n i n gw a sd e l i v e r e di n t h i s d i s s e r t a t i o n ，w ep r e s e n t e dak i n do fe x p a n d i n gm o d e lo fr o u g hs e t s ，t h a ti st h e m o d e lo fr o u g hs e t sw i t ht h eg r a d eo f m e m b e r s h i pa n dw e i g h t a f t e rl u c u b r a t i n gt h e d e f i c i e n c i e so ft h et h e o r yo ft r a d i t i o n a lr o u g hs e t s i nt h i sm o d e l ，w ed i s s e r t a t e dt h e i n f o r m a t i o ns y s t e mw i t ht h eg r a d eo fm e m b e r s h i pa n dw e i g h t ，a n dr e s e a r c h e di n t o t h ep r o c e s so fn o i s e ，t h ep a r t i t i o no fa p p r o x i m a t es p a c e ，t h ec a l c u l a t i o no ft h e d e p e n d e n tg r a d e o fd e c i s i o n m a k i n ga t t r i b u t et oc o n d i t i o n a lo n e s t h ea t t r i b u t e s r e d u c t i o n t h ec o n s t r u c t i o no fe x c a v a t i n gs t e po f c o r r e l a t i v er u l e se t c a u dt h em o d e i i sf e a s i b l et h r o u g ht h ev a l i d a t i o no fa l le x a m p l e t h i se x p a n d i n gm o d e lo fr o u g h s e t so v e r c o m e st h ed e f i c i e n c i e st h a ti t sc l a s s i f i c a t i o ni st o os t r i c ta n di ti s e x c e s s i v e l ys e n s i t i v e t ot h en o i s ea n ds o m er u l e sk e p ti nb o u n d a r ya r el o s te t c a sf a r a st r a d i t i o n a lr o u g hs e t si sc o n c e r n e d t h i sm o d e lc o m p l e t e l ys u c c e e d st h ec h a r a c t e r so f r o u g h s e t sa n dh o l d si t sa l ls t r o n g p o i n t s i tp r o v i d e sam e t h o dt h a ti sc o m m o n l yu s e di ns t a t i s t i c a n da p p l i e dt om o r eo b j e c t sb e i n gc l a s s i f i e do nt h ec o n d i t i o no fag i v e ne r r o rr a t i o i tw i l l o b t a i nb e t t e ra p p l i c a t i o ni ns o m ea s p e c t ss u c ha sa n a l y s i so fi n f o r m a t i o ns y s t e m ， a r t i f i c i a l i n t e l l i g e n c e a n di t s a p p l i c a t i o n ，d e c i s i o ns u p p o r ts y s t e m ，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 ，p a t t e r nr e c o g n i t i o n ，c l a s s i f i c a t i o na n d f a u l td i a g n o s i se t c f o rt h ef u t r i t e ，r e a l i s t i cs o f ts y s t e mb a s e do nt h i sm o d e lo f r o u g h s e t sw i l lb e t h e o r e t i c a l l yl u e u b r a t e da n de x p l o i t e d k e y w o r d ：d a t am i n i n g ；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 ( k d d ) ；r o u g hs e t s ； r e d u c t i o n ；d i s c e r n i b i l i t ym a t r i x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得鲤i t 壅蚣堂或其它 教育枫构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 粼一虢砂书费蝴钟年饥j 日 关于论文使用授权的说明 本学位论文作者完全了解擅j t 壅堑太兰有关保留及使用学位论文的规定，有 权保留并向国家有关部门( 机构) 送交论文的复印件和磁盘，允许论文被查( 借) 阅。本人授权塑j 壅些太堂可以将论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等方法加以保存或编成学位论文。 ( 保密的学位论文在解密后应遵守此协议) 学位论文作者签名- 飞# 摩 签字白期：) 。印年月r 拍 导师签名： 匈圳 签字日期：幺v 年二月日 一一生主塑婪塞呈堡塑塑堡篓塑里垄 1 引言 我们先看一个例子【l l ，英国s a t b w a y 公司用一种数据挖掘( d a t am i n i n g ) 软件i n t e l l i g e n tm i n e r 发现某种乳酪产品虽然销售排名第2 0 9 位，可是消费额最高的客户中有2 5 都常买这种奶酪，这 些客户s a f e w a y 公司可不想得罪。若使用常用的方法这种产品早就不卖了。可是，事实上这种 产品是非常重要的。这就是数据挖掘的强大功能。同样。如果有一个记录了历史上实际发生的边 境冲突情况的数据库，可不可以对当前发生的冲突提出处理建议? 如果有一个股市数据库可不可 以对各种股票投资风险作出评估口1 7 诸如此类的问题，方面，随着计算机技术和网络技术的飞 速发展，计算和存储设备不断更新，存储在计算机中的数据呈海量增加；另一方面，我们却难以 用生前的数据库技术直接从孛发现所焉要的信息。对这些数据进雩亍分析以便发现踌藏在数据中的 有用模式，这类问题都可以通过数据挖掘技术得到较好的解答。 随着计算机、网络和通讯等信息技术的高速发展，信息的增长呈现超指数上升。商务贸易电 子化、企业和政府事务电子化的迅速普及都产生了大规横的数据源，同时日盏增长的科学计算和 丈规模的工业生产过程也提供了海量数据。信息量的急剧增长，使传统数据库的检索查询机制和 统计分析方法已远远不能满足现实的需要，许多数据来不及分析就过时了，也有许多数据因其数 据量极大而建戳分析数据闽赍q 关系。在这样的背景下，薮豹数据弛理技术数强挖据便应运两 生。面对海量的存储数据，如何从中发现有价值的信息或知识，成为一项非常艰巨的任务。数据 挖掘就是为迎合这种要求而产生并迅速发展起来的。数据挖掘是数据库技术与人工智能技术相结 合的产物，是目前雷际上数据库和信息决策领域的最前捂的研究方向之一。已g 起了学术界和工 业界的广泛关注。 许多产业界人士认为此领域是一项能增加企业潜能的重要途径。这一领域蓬勃发展的原因是 因为现在的企业已搜集了大量的资科包括市场、客户、供货商、竞争对以及未来趋势等重要信 息。但是海量与无结构化使得企业决策部门无法利用这些资料，甚至会使决策行为产生混乱与误 用。如果能通过数据挖掘技术从海量的数据中挖掘出不同的信息与知识来，作为决策支持之用， 就能成为企业竞争的优势。另一方面数据挖掘技术也是从海麓的观测或实验数据中发现客观规 律的一种方法。因此，数据挖掘被美国麻省理工学院评为在未来发展中最有前途的十大技术之一。 粗糙集( r o u g hs e t , r s ) 理论p 4 s l 是一种处理不确定和模糊闯题的数学工具，粗糙集理论具 有一些独特的观点，这些观点使得租糙集特别适合于进行致据分析，如知识的粒度性。粗糙集理 论认为知识的粒度性是造成使用已有知识不能精确表示某些概念的原因。通过引人不可分辨关系 作为粗糙集理论的基础- 并在此基础上定义了上下近似粲台等概念，租糙集理论能够有效地逼近 这些概念。租糙集理论有如下优点：不需要提供待解问题之外的任何先验信息科，如统计中要求 的先验概率、d e m p s t e r - s h a f e r 理论中的基本概率赋值和模糊集中要求的隶属函数，并且算法相对 简单。易于操： # 。摺对其它处理不确定帮模糊性阚题的理论悉言，租撵复理论有许多不可替代触 优越性a 租糙集理论这种“让数据自己说话【7 i ”的思想极大地方便了其在各个领域的应用。随着 河北农业大学硕士学位论文 该理论在数据的决策与分析、模式识别、智能控制、故障检测、机器学习利知识发现 等方面的成功应用，基于不可分辨关系和完备信息系统的经典粗糙集理论得到了不断的扩 充【8 ，9 2 o 。 粗糙集理论为数据挖掘技术提供了一种新的较优的数学方法。首先，数据挖掘研究的 对象多为关系型数据库，而关系型数据库的关系表可以被看作是粗糙集理论中的决策表； 第二，现实世界中的规则有确定性也有不确定性的，数据库中包含有确定的也包含有不确 定的潜在规则，从数据库中发现不确定性的知识，这就为粗糙集方法提供了用武之地。第 三，数据库中的数据可能含有噪声，而排除数据处理过程中的噪声也是粗糙集理论的特长 之一。第四，在数据挖掘领域，其它处理工具如神经网络方法不能自动地选择合适的属性 集，利用粗糙集理论方法进行数据预处理去掉多余的属性，这样可以提高数据处理的效率i 第五，由于粗糙集理论自身的优点，使得经过粗糙集方法处理得到的决策规则和推理过程 较神经网络等理论工具更易于被证实和检测。采用粗糙集作为研究数据挖掘的工具还具有 如下优点：粗糙集理论将知识定义为不可分辨关系的一个族集，这使得知识具有了一种清 晰的数学意义，并可使用数学方法进行处理。 经典粗糙集理论和其他处理不精确与不确定性的方法相比具有独特之处然而仍然存 在着某些不足之处。由于完全抛弃了可能客观存在的先验知识，使基于不可区分关系的经 典粗糙集理论面l 临某些无法克服的难题1 1 2 ”1 ，如缺乏对原始数据模糊性的处理手段，对于 模糊概念的刻画过于简单：对于粗糙集的边界区域的刻画过于简单；不便处理具有各种数 据域的原始数据集：难以避免生成偶然性规则【1 4 】：粗糙集理论的方法在可用信息不完全的 情况下将对象归类于某一具体的类，通常分类是确定的但并未提供数理统计中所常用的 在一个给定错误率的条件下将尽可能多的对象进行分类的方法等。因此，如果能对经典粗 糙集的这些不足进行改进，发现更优的租糙集的拓广模型，将这种模型应用于数据挖掘， 可能产生更好的数据挖掘方法。目前，大多数成功的应用都从不同的侧面对经典粗糙集理 论进行了拓广。 针对上述这些问题，我们提出了一种粗糙集的拓广模型，即带隶属度及权重的粗糙集 模型。在这种模型中，我们进行了噪音的处理、近似空间的划分、决策属性对条件属性的 依赖度的计算、属性的约简、关联规则挖掘步骤的建立等方露的研究。用这种模型进行数 据挖掘可以将原来由于嗓音的影响被划到边界的部分等价类重新划回到正区( 此时的正 区称准正区) 或负区( 此时的负区称准负区) 。这种粗糙集的拓广模型克服了经典框糙集分 类过于严格、对噪音太敏感、某些隐藏在边界中的规则丢失等缺陷。它完全继承了粗糙集 的性质，拥有粗糙集的所有优点。该模型提供了一种数理统计中常用的在一个给定错误率 的条件f 将尽可能多的对象进行分类的方法该模型将在信息系统分析、人工智能及应用、 决策支持系统、知识发现、模式识别、分类以及故障诊断等方面取得较好的应用。 甚于粗糙集理论的数据挖掘研究 2 粗糙集理论及其应用 2 ，1 粗糙集理论的产生和发展 2 0 世纪7 0 年代，波兰学者p a w l a k z 和一些波兰科学院、波兰华沙大学的逻辑学家们 一起从事有关信息系统逻辑特性的研究。粗糙集理论就是在这些研究的基础上产生的。2 0 世纪8 0 年代，许多波兰学者对租裢集理论及其应用迸行了坚持不懈的深入研究对该理论的 数学性质与逻辑系统进行了广泛分析，取得了许多研究成果。1 9 8 2 年，p a w l a kz 发表了经 典论文r o u g hs e t s l 5 1 , 宣告了粗糙集理论的诞生。由于当初的研究大多数是用波兰文发表的， 因此，这项研究当时并来引起国际计算机学界的重视，研究区域仅局限于东欧各国。随后 很多学者对粗糙集理论及其应用进行了不懈的深入研究，其中主要对粗糙集理论的数学性 质与逻辑系统进行了广泛的分析【l ”。大多数研究成果发表在“b u l l e t i no f t h ep o l i s ha c a d e m y o f s c i e n c e ：m s t h e m a t i e s ”或“b u l l e t i no f t h ep o l i s h a c a d e m yo f s c i e n c e ：t e c h n i c a ls c i e n c e s ” 上，同时他们也开发了一些应用系统。 1 9 9 1 年，p a w l a k z 的第一本关于粗糙集理论的专著“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 s o f r e a s o n i n ga b o u td a t a ”和1 9 9 2 年，s l o w i n s k ir 主编的“i n t e l l i g e n td e c i s i o n s 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 f r o u g hs e t st h e o r y ”1 的出版，奠定了粗糙集理 论的基础，井推动了国际粗糙集理论与应用的深入研究。 1 9 9 2 年在波兰k i e l 【r z 召开了第l 届国际粗糙集讨论会议。这次会议着重讨论了集合近 似定义的基本思想及其应用，其中粗糙集环境下机器学习的基础研究是这次会议的四个专 题之一。从此以后，每年都召开一次毁粗糙集理论为主题鹩国际研讨会。 1 9 9 3 年在加拿大b a n f f 召开了第2 届国际租糙集与知识发现研讨会，其主题是粗糙集、 模糊集与知识发现。这次会议介绍了许多基于扩展的粗糙集理论的知识发现方法与系统， 1 9 9 4 年在美鬟的s a nj 笛e 召开了第3 屠衽糙集与软计算研讨会广泛讨论了楹糙集与 模糊逻辑、神经网络、进化理论等的融合问题。 1 9 9 5 年粗糙集的主要倡导者在第l l 期a c m 通讯上撰文，概括地介绍了粗糙集的基本 概念及其在知识获取、机器学习、决策分析、知识发现等领域的具体研究项目和进展。特 别在1 9 9 5 年召开的第四届模糊理论与技术国际会议上对模糊集和租糙集的相互关系展开 了讨论，极大地促进了粗糙集的发展。 1 9 9 6 年，在日本东京召开了第四届图际租糙集、模糊集与机器学习国际研讨会。 1 9 9 7 年，在美国n o r t hc a r o l i n a 召开了第五屑粗糙集与软计算国际研讨会。 1 9 9 8 年，1 0 月第六届粗糙集、数据挖掘及粒度计算团际研讨会在美国n o r t hc a r o l i n a 召开。1 9 9 8 年6 月，在渡兰召开了第l 届粗植集和计算的当前趋势学术会议， 河北农业大学硕士学位论文 1 9 9 9 年1 1 爿，在日本y a m a g u c h i 召开了第七届粗糙集、模糊集、数据挖掘和粒度软 计算国际研讨会。这次研讨会的重要特点是强调智能技术的集成，也就是，促进人工智能、 软计算和数据库等技术的高度融合，以便解决实际中具有不确定性与模糊性的大而复杂的 问题。 2 0 0 0 年l o 月，在加拿大b a n f f 召开了第二届粗糙集与计算趋势国际会议。这次会议 极大地推动了粗糙集理论在软计算、数据库、人工智能和近似推理等方面的发展。 我国从9 0 年代开始了对粗糙集理论的研究，主要集中在对它的数学性质、有效算法的 研究，如粗糙集理论的知识表示、知识约简算法、租糙逻辑等，并出版了一本租糙集理论 的中文专著【i 。 随着粗糙集理论在我国的逐步普及。现在国内研究粗糙集的人越来越多。为了促进这 一理论在中国的发展，中国计算机协会人工智能与模式识别专业委员会于2 0 0 1 年5 月在重 庆邮电学院召开了第一届粗糙集与软计算学术研讨会以共同理解和探讨粗糙集理论及其 应用研究的新内容和新方法。 现在，粗糙集理论在国内外有了更大的发展取得了很多可喜的成绩。粗糙集理论已 经广泛应用于医疗分析诊断、经济、金融、商业、环保、工程设计、信息科学、决策分析、 社会、分子生物学和材料科学等诸多领域。 已经开发的基于粗糙集理论的知识发现系统主要有l ”1 ：l e r s ( 1 e a r n i n gf r o me x a m f l e s b a s e do nr s ) 系统是美国k a n s a s 大学开发的基于粗糙集的实例学习系统，该系统是用 c o m m o n l 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 ai n e 公司开发的，包括数据输入、预处理、编辑、生 成可辨识矩阵、集合近似、约简、生成规则、预测和分析。 除以上系统外，还有一些其他系统，如加拿大r e d u c t s y s t e m i n c 公司开发的d a t a l o g i c r 、中国科学院计算技术研究所开发的k d t 和南京大学研制的k n i g h t 等。 2 2 粗糙集理论概述 2 2 1 知识的分类观点 在信息系统中一般认为，知识【”1 是人类实践经验的总结和提炼具有抽象和普遍的 特征，是属于认识范畴的概念，任何知识都是对事物运动状态及变化规律的抽象性描述。 基于粗糙集理论的数据挖掘研究 包括这种状态和规律的形式( 形态性知识) 、含义( 内容性知识) 和价值( 效用性知识) 。 形态性知识、内容性知识、效用性知识三者一起构成了完整的知识。常识是被普遍公认因 而无需证明的知识。总之，知识是人们实践经验的结晶：经验，是有待确证的准知识。由 信息提炼知识的基本方法是归纳抽象：即把原始的具体的信息( 事物运动状态及其变化方 式) 通过归纳处理，成为抽象的、具有一定普遍意义知识( 事物运动状态及其变化规律) 。 当然，除了归纳抽象的基本方法之外，由信息加工提炼知识的过程也还存在其它的方法( 如 类比、联想、趋势外推、中值内插等等) 。至于由原有知识推演出新知识的基本方法，则主 要是演绎推理。在粗糙集理论中，知识被认为是一种将现实或抽象的对象进行分类 ( c l a s s i f i c a t i o n ) 的能力。人们的行为是基于分辨现实的或抽象的对象的能力。对象( o b j e c t l 指任何我们可以想到的东西，例如实际物体、状态、抽象概念、过程、时刻等，某些对象 的集合称为论域u ( u n i v e r s e ) 。 假定我们具有关于某个论域的某种知识，并使用属性( ( a t t r i b u t e ) 及其值( v a l u e ) 来描述 论域中的对象。例如：空间物体集合u 具有“颜色”、“形状”这两种属性，“颜色”的属 性值取为红、黄，“形状”的属性值取为方、圆。从离散数学的观点看，“颜色”、“形状” 构成了u 上的一族等价关系( e q u i v a l e n t r e l a t i o n ) 。u 中的物体，按照“颜色”这一等价关 系，可以划分为“红色的物体”、“黄色的物体”等集合；按照“形状”这一等价关系。可 以划分为“方的物体”、“圆的物体”等集合：按照“颜色 形状”这一合成等价关系，又 可以划分为“红色的圆物体”、“黄色的方物体”、等集合。如果两个物体同属于“红色 的圆物体”这一集合，它们之间是不可分辨关系( 1 n d i s c e r n i b i l i t yr e l a t i o n ) ，因为描述它们 的属性都是“红”和“圆”。不可分辨关系是粗糙集理论的基石，它揭示出论域知识的颗粒 ( g r a n u l a r i t y ) 状结构。 2 2 2 粗糙集理论的有关概念 为了更好地学习和应用粗糙集理论，我们先看几个有关概念。 ( 1 ) 知识，给定一对象的论域u ，对于任何子集x u ，可称之为u 中的一个概念或 范畴t 并且u 中的任何概念族称为关于u 的抽象知识，简称知识( k n o w l e d g e ) 。 ( 2 ) 近似空间一个近似空间( a p p r o x i m a t es p a c e ) ( 或知识库) 定义为一个关系系统 ( 或二元组) k = ( u ，r ) 其中，u 不空，是一个被称为全域或论域的所有要讨论的个体的集合，r 是u 上等价 关系的一个族集。 ( 3 ) 不可分辨关系，设p c r ，且p 不空，p 中所有等价关系的交集称为p 上的一种 不可分辨关系( 或不可区分关系。不分明关系) ，记作i n d ( p ) ，即 【x 】i n d ( p ) = n x h r e p 注意i n d ( p ) 也是等价关系且是唯一的。 ( 4 ) 粗糙隶属函数，设x u 且x e u ，集合x 的隶属函数( m e m b e r s h i pf u n c t i o n ) ( 或 阿北农业大学硕士学位论义 称租糙隶属函数( r o u g hm e m b e r s h i pf u n c t i o n ) ) 定义为 ；( x ) = c a r d ( x 7 【x 】r ) c a r d ( i x r ) 其中r 是不可分辨关系， x 】r = ( y ：( y u ) a ( y r x ) ) c a r d ( x ) 表示集合x 的基数。 根据以上定义，可以得剑以下性质： a ：( x ) = l 当且仅当 x l r x ： b ；( x ) o 当且仅当【x r n x m c 卢；( x ) = o 当且仅当 x 】r nx = o 显然；( x ) 【o ，1 】，我们可以看到，这里的隶属关系是根据已有的分类知识客 观计算出来的，可以被理解为一种条件概率，能够从全域上的个体加以计算，而不是主观 给定的。 ( 5 ) 下近似、上近似、边界 设集合x c _ u ，我们称r ( x ) = ( x ：( x a u ) ( ! ( x ) = 1 ) ) 为x 的下近似( 1 0 w e r a p p r o x i m a t i o n ) ；r ( x 户( x ：( x u ) a ( ；( x ) o ) ) 为x 的上近似( u p p e r a p p r o x i m a t i o n ) ： b n r ( x ) _ r ( x ) 一r 。( x ) 为x 的边界或边界区域( b o u n d a r y ) 。 显然，如果b n r ( x ) 中或r ( x ) r ( x ) ，则x 就是一个粗糙概念。 还有如下定义： 下近似也称正区，p o s r ( x ) = r ( x ) 称为x 的r 正区域( r - p o s i t i v er e g i o n ) ， n e g r ( x ) = r ( x ) 称为x 的r 负区域( r n e g a t i v er e g i o n ) ，b n a ( x ) 称为x 的r 边界 域( r - b o u n d a r yr e g i o n ) 。当对象x ep o s r ( x ) 时，则x 称为x 的r 正例( r - p o s i t i v ee x a m p l e ， 对n e g r ( x ) 和b n r ( x ) 也可以有类似的称呼。 正区域p o s r ( x ) 或x 的下近似是那些对于知识r 能完全确定地归入集合x 的对象的 集合。类似地，负区域n e g r ( x ) 是那些对于知识r 绝对不属于集合x 的元素的集合。边界 域是某种意义上论域的不确定域。对于知识r 属于边界域的对象不能确定地划分是属于x 或是x x 的上近似是由那些对于知识r 我们不能排除它们属于x 的可能性的对象构成 的，从形式上看，上近似就是正区域和边界域的并集。 6 基于粗糙集埋论的数据挖掘研究 圈21 粗糙集中的近似集合 f i g u r e2 1a p p r o x i m a t i o no fs e ti nr o ug is e t s 2 2 3 信息系统和决策表 信息系统的基本成分是研究对象的集合而这些对象的知识是通过指定对象的基本特 征( 属性) 和它们的特征值( 属性值) 来描述的。 一个信息系统( i n f o r m a t i o ns y s t e m ，i s ) 可以表达为 i s = ( u ，c ，d ，v d 这里u 是对象的有限集合，c ud = a 是属性集合，子集c 和d 分别称为条件属性集 和决策属性集，v 是属性值的集合，v = u 屹，f ：u a + v 是一个信息函数，它指定u a e a 中每一对象x 的属性值。 信息系统的这个定义可以用表格来描述。知识的表格描述法可以看作是一种特殊的形 式语言，用符号来表达等价关系这样的数据表称作信息系统属性值表，或决策表。 决策表是一类特殊而重要的信息系统，它指定当满足某些条件时，决策( 行为) 应当怎 样进行，多数决策问题都可以用决策表形式来表达，因此这- - z 具在决策应用中起着重要 的作用。 决策袭可定义为 t = ( u ，a ，c ，d ) 其中u ，a ，c ，d 的意义同上。不可分辨关系i n d ( c ) 和i n d ( d ) 的等价类分别称为条 件类和决策类。 对于每个x u ，a a ，我们定义一个函数： d x ：a v ，d x ( a ) = a ( x ) 函数d x 称为表t 中的决策规则，x 是决策规则d x 的标识，即决簧表中集合u 的 元素不表示任何实际的事物，只是决策规则的标识符。 当d x 为一决策规则时，d x 对于c 的约束记作d x ( c ) ，d x 对于d 的约束记作d x ( d ) ， d x ( c ) 和d x ( d ) 分别称为d x 的条件和决策。如果对于每个y x ，d x ( c ) = d y ( c ) 意 味着d x ( d ) = d y ( d ) ，则称决策规则d x 是一致的否则称d x 是不一致的；只有当所有 河北农业大学硕士学位论文 的决策规则都是一致的，决策表才是一致的，否则是不一致的。 在决策表中，列表示属性，行表示对象( 如状态，过程等) ，并且每行表示该对象的一 条信息，决策表可以通过观察、实验得到。容易看出，一个属性对应一个等价关系，一个 决策表可以看作是定义的一族等价关系。 因为知识库和决策表之间有一一映射关系。这样，所有涉及知识库的定义都可以用决 策表的定义来描述，因此，知识库中任一等价关系在决策表中表示为一个属性和用属性值 表示的关系。表中的行可看作菜些概念的名称，而整个表包含了相应知识库中所有概念的 描述，包含了能从表中数据推导出的所有可能的规律。所以。决策表是对知识库中有效事 实和规律的描述。 2 2 4 决策表的约简 决策表的各个条件属性之间往往存在着某种程度上的依赖关系。约简可以理解为在不 丢失信息的前提下，可以较简单地表示决策系统的决策属性集合对条件属性集合的依赖关 系即约简就是化简决策表中的条件属性。约简后的决策表与约简前的决策表具有相同的 信息。但是约简盾的决策表具有更少的条件属性。因此，决策表的约简在工程应用中相当 重要，同样的决策可以基于更少量的条件，使我们通过一些简单的手段就能获得同样要求 的结果。 决策表的约衙步骤： ( 1 ) 条件属性的约简，即从决策表中消去某些列； ( 2 ) 消去重复的行； ( 3 ) 消去每一决策规则中属性的冗余值。 注意到，与信息系统的一般表示相比，这里的行不表示对任何实际对象的描述。因此 重复行表示的是同样的决策，所以可以把它( 们) 消去。约简后的决策袭是一个“不完全” 的决策表。它仅包含鄢些在决策时新必需的条件属性值，但它具有原始信息系统的所有知 识。 2 2 5 知识的约简 在稳糙集理论中，知识约简是研究近似空间中每个等价关系是否都是必要的，以及如 何删除不必要的知识。知识约简在信息系统分析领域具有重要的应用价值。 在粗糙集理论应用中，约简和核 2 1 , 2 2 】是最重要的两个基本概念。直观地，所谓知识的 约简是指知识的本质部分，它足以定义所研究的知识中遇到的所有基本概念，而核是其最 重要的部分。 定义2 2 1 令r 为一个等价关系族，且r r ，当i n d ( r ) - i n d ( r 一( r ) ) ，称r 为r 中可省略的( d i s p e n s a b l e ) ，否则r 为r 中不可省略的( i n d i s p e n s a b l e ) 。若对于任一r r 为 r 中不可省略的，则族r 为独立的( i n d e p e n d e n t ) ，否则就是依赖的( d e p e n d e n t ) 或非独立 的。 基于粗糙集理论的数据挖掘研究 定义2 2 z当q c p 是独立f l 勺，并且i n d ( q ) = i n d ( p ) ，则q 为p 的约俺( r e d u c t ) 。显 然p 可以有多个约简( 约简的不惟一性) 。 定义2 2 3p 中所有不可省略关系的集合，称为p 的核( c o r e ) ，记作c o r e ( p ) 。 c o r e ( p ) = nr e d ( p ) 其中r e d ( p ) 是p 的所有约筒族。 关于垓这个概念有两点说明：首先它可以作为所有约简的计算基础。因为核包含在所 有的约筒之中，并且计算可以直镁进行；其次它可解释为当知识约蔼对它是不能消去的知 识特征部分的集台。 定义2 2 4 令p 和q 为u 上的等价关系的族集，族集q 的p - 正域( p p o s i t i v er e g i o no f q ) ，记为p o s p ( q ) ，即： p o s t ( q ) _ u p ( x ) x e u ，口 族集q 的p 一正域是全域u 中所有用分类u p 所表运的知识，能够正确的分类于u q 的等价类之中的对象的集合。一个集合x 相对于一个等价关系p 的正区域就是这个集台的 下近似p ( x ) ：而