（计算机应用技术专业论文）基于粗集属性约简的数据挖掘技术的研究与应用.pdf

摘要 近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存 在大量可供使用的数据，并且迫切需要将这些数据转换成有用的信息和 知识。 进行数据挖掘的方法很多，粗集方法便是其中的主要方法之一，将 粗糙集应用于数据挖掘领域，能提高对大型数据库中的不完整数据进行 分析和学习的能力，具有广泛的应用前景和实用价值。 属性约简又是粗糙集理论中的一个重要课题，如果能将冗余属性删 除，将会大大提高系统潜在知识的清晰度，降低发现规则的时间复杂性， 提高发现效率。 本文主要研究基于粗集理论属性约简的数据挖掘技术。首先，对数 据挖掘和粗集理论进行研究，并在分析和综合原有基于粗集理论的数据 挖掘算法的基础上，提出了改进的启发式属性约简方法，即基于加权平 均和频度的双向选择约简算法。其次，介绍了数据挖掘系统，一是产生 规则，利用属性约简算法约简属性，从而得出规则；二是规则分类，利 用已产生的规则分类新对象。最后，通过实例验证了本文提供的方法是 可行的和有效的。 关键词：数据挖掘粗集属性约简启发式算法 a b s t r a c t d a t am i n i n ga 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 r r e a s o ni st h a tl a r g ea m o u n to 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 s u r g e n t l yl l e c e s s a f y t oc o n v e r tt h e s ed a t ai n t ou s e f u li n f o r m a t i o na n d k n o w l e d g e t h e r ea r es o m em e t h o d sf o rd a t am i n i n g ，r o u g hs e t sm e t h o d o l o g yi s o n eo fi m p o r t a n tm e t h o d s ，a p p l y i n gr o u g ht h e o r yi nd a t am i n i n gf i e l dc a n i m p r o v et h ea n a l y z i n ga n dl e a r n i n ga b i l i t yf o ri n c o m p l e t ed a t ao fl a r g e d a t a b a s e ，w h i c hh a se x t e n s i v ea p p l i e dp r o s p e c ta n da p p l i e dv a l u e a t t r i b u t er e d u c t i o ni sas i g n i f i c a n tt o p i co fr o u g hs e tt h e o r y , i tc o u l d i m p r o v ep o t e n t i a lk n o w l e d g ed e f i n i t i o no fs y s t e m ，l o w e rt i m ec o m p l e x i t yo f d i s c o v e r i n gt h er u l e s ，a n dr a i s ed i s c o v e r i n ge f f i c i e n c yi ft h er e d u n d a n t a r t r i b u t e sc o u l db ee l i m i n a t e d t h i sp a p e rr e s e a r c h e sad a t am i n i n gt e c h n o l o g yb a s e do na t t r i b u t e s r e d u c t i o no fr o u g hs e tt h e o r y f i r s t l y , r o u g hs e tt h e o r yh a sb e e nd i s c u s s e d ， b yt h ea n a l y s i sa n ds y n t h e s i so fd a t am i n i n ga l g o r i t h mb a s e do nr o u g hs e t t h e o r y ，a ni m p r o v e dh e u r i s t i e sa l g o r i t h mo fa t t r i b u t e s r e d u c t i o nw a s p r o p o s e d ，w h i c hw a sb a s e do nt h ew e i 曲e ds u ma n df r e q u e n c ya l g o r i t h mo f b i d i r e c t i o n a ls e l e c t i o na t t r i b u t er e d u c t i o n s e c o n d l y i ti n t r o d u c e dd a t a m i n i n gs y s t e m ，o n ei sr u l e sg e n e r a t i o n ，i tc r e a t e sr u l e sa f t e ra t t r i b u t e sa r e r e d u c e d b y t h ea t t r i b u t e sr e d u c t i o n a l g o r i t h m sa b o v e ；t h e t h e ri s d a s s i f i c a t i o n i tg i v e sac l a s s i f i c a t i o nf o rn e wo b i e c t sa c c o r d i n gt ot h e s e r u l e sw h i c hh a v eb e e nc r e a t e di nr u l e sg e n e r a t i o n f i n a l l y , t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h ea l g o r i t h mi sv e r i f i e dt ob em o r ef e a s i b l ea n de f f e c t i v e k e yw o r d s ：d a t am i n i n g ( d 旧r o u g hs e t a t t r i b u t e sr e d u c t i o n h e u r i s t i c sa l g o r i t h m 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，( ( 基于粗集 属性约简的数据挖掘技术的研究与应用是本人在指导教 师的指导下，独立进行研究工作所取得的成果。除文中已 经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的作品成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全 意识到本声明的法律结果由本人承担。 作者签名：基蠢未色地1 2 年立月幺日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学 硕士、博士学位论文版权使用规定”，同意长春理工大学 保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅。本人授权长春理工大学 可以将本学位论文的全部或部分内容编入有关数据库进 行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文。 作者签名：宣盎立些塑1 2 年，王月筮日 指删雠名2 撕年尹节 第1 章绪论 1 1 研究的目的和意义 随着科学技术的飞速发展，经济和社会都取得了极大的迸步，与此 同时，在各个领域产生了大量的数据，激增的数据背后隐藏着许多重要 的信息。人们不再满足于数据库的查询功能，希望能够对其进行更高层 次的分析，以便能从数据中提取信息或者知识为决策服务。目前的数据 库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数 据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。 缺乏挖掘数据背后隐藏的知识的手段，导致“数据爆炸但知识贫乏”的 现象。与此同时，传统的统计技术面临着极大的挑战，这就急需有新的 方法来处理这些海量数据，数据挖掘就是为顺应这种需要应运而生发展 起来的数据处理技术。它的出现为自动和智能地把海量数据转化为有用 的知识提供了有力的手段“”“。人们把原始数据看作是形成知识的源 泉，就象从矿石中采矿一样。原始数据可以是结构化的，如关系数据库 中的数据；也可以是半结构化的，如文本、图形、图象数据；甚至是非 结构化的异构数据，如分布在网络上的w e b 数据。发现知识的方法可以 是数学的，也可以是非数学的：可以是演绎的，也可以是归纳的。发现 的知识可以用于信息管理、查询优化、决策支持、过程控制等，还可以 用于数据自身的维护。因此，数据挖掘是一门广义的交叉学科，它汇聚 了不同领域的学者，尤其是数据库技术、人工智能、数理统计、模式识 别、数据可视化、高性能计算等方面的学者和工程技术人员。但在现实 世界中，由于事物发生的随机性、人类知识的不完全、不精确以及自然 语言中存在的模糊性和歧义性使人们所面对的数据源存在各种不确定 性，这种不确定性造成了具有相同描述信息的对象可能属于不同概念， 因此在数据挖掘和数据库知识发现的诸多研究方法中，解决不确定性问 题受到研究者的广泛重视。在人工智能领域提出了许多方法处理不确定 性问题，其中应用得最广泛的是概率论、模糊集、证据理论和租糙集理 论以及这些方法的相互渗透和补充。 进行数据挖掘的方法有很多，粗糙集方法是主要方法之一。粗糙集 理论是8 0 年代初由波兰数学家z p a w l a k 教授提出的，用于研究不完整数 据和不精确知识的表达、学习归纳的数学分析理论。1 。其核心思想是在 保持分类能力不变的前提下，通过对知识的化简，导出问题的决策或分 类规则。由于粗集理论不需要任何先验知识即可对已有知识进行处理， 并提炼出隐含知识的特点，所以广泛应用于模式识别、机器学习、数据 挖掘、智能控制、医疗诊断、专家系统以及决策分析等领域，并取得了 一定的成果。粗集理论的数据约简包括属性约简和值约简两种。属性约 简是粗集理论中的一个重要研究课题“】，它的意义在于可以删除冗余信 息，形成精简的规则库以便人们( 或者机器人) 作出快速、准确的决策。 确切的说，属性约简是对决策表中的条件属性进行简化，且约简后的决 策表与原决策表具有相同的性质，但是约简后的决策表具有更少的条件 属性。属性的最小约简是个n p h a r d 问题，导致n p _ _ h a r d 问题的主要原 因是属性的组合爆炸。高效的约简算法是粗糙集应用于知识发现的基 础，要在令人可接受的时间内获得约简的通常做法是基于启发式知识的 约简方法，国内外学者在这方面做了大量的研究，现尚不存在一种非常 有效的方法，因此寻求快速的约简算法及其增量版本这一问题仍是粗糙 集理论的研究热点之一。 总的来说，随着k d d 的兴起，粗集理论越来越受至u k d d 研究者的重视 有以下几点原因。 首先，k d d 研究的对象多为关系型数据库，关系表可被看作为粗集 理论中的决策表，这给粗集方法的应用带来了极大的方便。 第二，现实世界中的规则有确定性的，也有不确定性的。从数据库 中发现不确定性知识，为粗集方法提供了用武之地。 第三，从数据中发现异常，排除知识发现过程中的噪声干扰也是粗 糙集方法的特长。 第四，运用粗集方法得到的知识发现算法有利于并行执行，可以极 大的提高发现效率，对于大型数据库中的知识发现来说，这是非常关键 的。 第五，k d d 采用的其它技术，如神经网络的方法，不能自动的选择 合适的属性集，而利用粗集方法进行预处理，去掉多余属性，可以提高 发现效率。 第六，用粗集方法得到的决策规则及推理过程，比模糊集方法或神 经网络方法，更容易验证和检测。 所以，粗集方法在数据挖掘中的应用越来越广。 综上所述，通过应用粗集理论的属性约简于数据挖掘的领域，能对 大型数据库中不完整数据进行分析和学习，并取得了一定的成果，因此， 基于耜集的属性约简有着广泛的应用前景和一定的应用价值。 2 1 2 国内外研究现状 数据库中的知识发现技术( k d d ) 是随着数据库和人工智能技术的发 展而产生的。它首次出现于1 9 8 9 年在美国举行的第十一届国际人工智 能联合学术会议上。随后k d d 及其核心技术数据挖掘得到了广泛的发 展。1 9 9 5 年，数据挖掘界召开了第一届知识发现与数据挖掘国际学术 会议。该会议是由1 9 8 9 至1 9 9 4 年举行的四次数据库中知识发现国际研 讨会发展起来的。随着参与人员的不断增多，k d d 国际会议发展成为年 会。由于数据挖掘可以为企业构筑竞争优势，为社会带来巨大的经济效 益，一些国际知名公司也纷纷加入数据挖掘的行列，研究开发相关的软 件和工具。美国的i b m 公司于1 9 9 6 年研制了智能挖掘机，用来提供数 据挖掘解决方案；s p s s 股份公司开发了基于决策树的数据挖掘软件一 - - s p s s c h a i d ；思维机器公司在1 9 9 7 年开发了d a r w i n 这一数据挖掘套 件，还有o r a c l e 公司、s a s 公司和m a p i n f o 公司等都开发了相关的产 品。此外，在i n t e m e t 上还有不少k d d 电子出版物，其中以半月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威，另一份在线周刊为d s ( 决策 支持) ，1 9 9 7 年开始出版。自由论坛d me m a i lc l u b 可以通过电子邮件 讨论数据挖掘和知识发现的热点问题。1 9 9 7 年数据挖掘和知识发现的 国际学术刊物d a t am i n i n ga n dk n o w l e d g en i s c o v e r y 开始创刊，许多 杂志刊物也为数据挖掘开辟了学术专栏，为该领域的研究与交流提供了 广阔的舞台。1 9 9 8 年，数据挖掘界建立起一个新的学术组织 a c m s i g k d d ，即a c m 下的数据库中的知识发现专业组( s p e c i a l i n t e r e s t e dg r o u po nk 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 ) 。同年， 在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上不仅仅 进行了学术讨论，而且有3 0 多家软件公司展示了他们的数据挖掘软件 产品，其中的一些软件产品已在北美、欧洲等国得到应用。1 9 9 9 年a c m s i g k d d 组织了第五届知识发现与数据挖掘国际学术会议。其它内容 的专题会议也把数据挖掘和知识发现列为重要议题之一。数据挖掘和知 识发现已成为当前计算机科学界的一大研究热点。 目前，国外数据挖掘的发展趋势及其研究方面主要有：对知识发现 方法的研究进一步发展；传统的统计学回归法在k d d 中的应用；k d d 与 数据库的紧密结合。数据挖掘广泛应用于生物、金融、商业甚至法律和 情报等领域，国外很多计算机公司也非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心进行这方面的工作，此外，一些公司的 相关软件也开始在国内销售，如p l a t i n u m 、b o 以及i b m ，随着数据挖 掘方法的不断创新与研究以及数据挖掘技术的不断更新与成熟，数据挖 3 掘的应用范围将会越来越广。 今天，数据挖掘面临的主要问题与挑战有以下几方面： 噪音：可能由于数据丢失，属性值为空值、测试错误等原因造成。 困难的训练集：无代表性的数据，无边界的例子，有限的信息。 数据库：数据库是动态的，可能是巨大的。 粗集理论是波兰科学家z p a w l a k 教授于1 9 8 2 年提出。八十年代， 许多波兰学者对粗集理论及其应用进行了坚持不懈的研究，其中主要 对粗集理论的数学性质及逻辑系统进行了广泛的研究。1 9 9 1 年， z p a w l a k 的专著粗糙集一一关于数据推理的理论问世标志着粗糙 集理论及其应用的研究进入了活跃时期。1 9 9 2 年在波兰k i e k r z 召开 了第一届国际粗集研讨会。着重讨论了集合近似定义的基本思想及应 用，其中粗集环境下的机器学习的基础研究是这次会议的四个专题之 一。1 9 9 3 年在加拿大b a n f f 召开了第二届国际粗集与知识发现研讨会。 积极推动了国际上对粗集理论与应用的研究。会议主题是粗集、模糊 集与知识发现。1 9 9 4 年在美国s a nj o s e 召开了第三届国际粗集与软 计算研讨会，讨论了粗集与模糊逻辑、神经网络、进化理论等的融合 问题。1 9 9 5 年在美国w i l m i n g t o n 召开了粗集研讨会。粗集理论及应 用的几位主要倡导者，在1 9 9 5 年第1 1 期a c m 通讯上撰文，概况性地 介绍了作为目前人工智能应用新技术之一的租集理论的基本概念，及 其在知识获取、机器学习、决策分析和知识发现等领域的具体研究项 目和进展。在1 9 9 5 年召开的第四届模糊理论与技术国际会议上，针对 粗集理论与模糊集的基本观点与相互关系展开了激烈的讨论，推动了 粗集理论的研究。1 9 9 6 年底在日本东京召开了第五届国际粗集研讨会， 这是第一次在亚洲地区召开的范围广泛的粗集研究会。1 9 9 8 ，2 0 0 0 和 2 0 0 2 年，分别召开了三届r s c t c ( r o u g hs e t sa n dc u r r e n tt r e n d si n c o m p u t i n g ) 国际会议，表明粗糙集的研究已步入发展期。 与国外相比，国内研究稍晚。1 9 9 3 年国家自然科学基金首次对k d d 领域的研究项目给予资助。国内粗糙集的研究始于1 9 9 4 年，王珏、苗 夺谦、王国胤、曾黄麟等人在将粗糙集理论引入我国方面作出了重要 的贡献。刘清等探讨了粗糙集在近似推理、模态逻辑和智能代理方面 的理论研究情况，张文修、梁吉业、吴伟志等人提出了基于随即集的 粗糙集模型，并研究了粗糙集理论同包含度理论之间的关系。马志锋、 刑汉承等在粗糙控制方面作了深人的研究。从2 0 0 1 年开始，每年都召 开了一次中国粗糙集与软计算学术研讨会。2 0 0 1 年5 月，在重庆邮电 学院举办了首届中国粗糙集和软计算学术研讨会，2 0 0 2 年l o 月在苏 州大学举办了第二届中国粗糙集和软计算学术研讨会，2 0 0 3 年5 月， 在重庆邮电学院同时举办第三届中国粗糙集和软计算学术研讨会和第 4 九届粗糙集、模糊集、数据挖掘与粒度计算国际学术会议，这些会议 的举办表明我国粗糙集理论和数据挖掘研究的队伍正在不断壮大，已 经得到国际同行的重视和认可。2 0 0 4 年1 0 月，在浙江海洋学院召开 第四届中国粗糙集和软计算学术研讨会，本次研讨会是粗糙集与软计 算领域的一次盛会。研讨会收到论文2 1 3 篇，经专委会组织专家严格 审稿，录用了“o 篇论文，覆盖了粗糙集理论及其应用、数据挖掘与 机器学习、神经网络、进化计算与支撑向量机、智能系统与多a g e n t 技术和模式识别与图象处理等领域，现已由核心期刊计算机科学 出版论文专集。国内从事数据挖掘研究的人员主要在大学，也有部分 在研究所或公司。目前进行的大多数研究项目是由政府资助进行的， 如国家自然科学基金、8 6 3 计划、“九五”计划等，但还没有关于国 内数据挖掘产品的报道。但总体来说，粗糙集在国内的研究起步较晚， 其研究主要集中于理论方面，成功开发及应用的实例几乎没有。 1 3 数据挖掘 近年来，数据挖掘引起了信息产业界的极大关注，迫切需要将数 据转换成有用的信息和知识。 1 3 1 什么是数据挖掘 关于数据挖掘的描述有许多不同的说法，其中最普遍的定义如下： 数据挖掘是指从大量数据中抽取隐含的、不为人知的、有用的信 息。 数据挖掘也能被描述为试图创建一个数据库中描述的复杂世界的 简单模型，因而我们也可以说数据挖掘是处理大量信息的方法，并且 它有助于以比人更快的速度发现有用的信息。许多人把数据挖掘视为 另一个常用的术语，数据库中知识发现或k d d 的同义词，而另一些人 只是把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发 现过程有以下步骤组成：数据清理、数据集成、数据选择、数据变换、 数据挖掘、模式评估、知识表示。 数据挖掘( d m ) 通常是指从大量的原始数据中发现隐含的、未知 的、有用的知识的非平凡过程u ”。简单的说，就是从数据到知识的 过程。数据挖掘的对象数据，既可以是集中在主机上的数据库， 也可以是分布存放在互联网上的各种数据。这些数据一般可能有千兆 字节或更多，故数据挖掘一般需要某些领域知识。 1 3 2 训练集和测试集 在数据挖掘系统中被用来抽取知识的数据集称为训练集“”。通过 训练这个数据集中的数据，系统试图创建一般规则、模式的描述以及 数据库中的关系，获得的知识不仅对所考虑的数据集是有效的，而且 还要适合其他类型( 非训练集) 的数据。 另一个数据集用来测试已获得的知识，被称为测试集“”。如果在 训练集中发现的模式对其他数据也是有效的，此模式是清晰的。 一般情况下，数据库被分为两部分，一部分是训练集，一部分是 测试集。数据库中7 0 用作训练集，且用其训练数据挖掘系统。原始 数据库的剩余部分则作测试集，测试从训练集中获取的知识是否合适。 1 3 3 学习 数据挖掘的基础是来自机器学习和统计领域的技术。通过使用数据 库( 训练集) ，进行一个学习过程且获得数据库的模式。由此可以考虑 学习的两种不同的方法：推理和归纳。推理学习结合数据库中已有的信 息去提取存在于数据库中的新信息。个推理系统通过预先定义的规则 集推理数据。 归纳学习“”是发现存在于不同数据中的隐藏模式，这个模式将导致 更多的有意义的一般知识。归纳学习是数据挖掘的一个重要手段“”。就 数据挖掘来讲，归纳学习是最适合的，也是最好用的。这是由于用这种 方法产生的知识不仅对所用的数据库对象适用，而且对其它数据具有普 适性。 通过使用有导师或无导师学习，会帮助解决有关已获知识对系统帮 助有多大这一问题。在数据挖掘系统中，有导师学习的基本概念是分类。 1 3 4 数据挖掘的功能可以挖掘什么类型的模式 对一个数据挖掘系统而言，它应该能同时搜索发现多种模式的知 识，以满足用户的期望和实际需要。此外，数据挖掘系统应能够挖掘出 多种层次( 抽象水平) 的模式知识，允许用户来指导挖掘搜索有价值的 模式知识。数据挖掘的功能以及它们可以发现的模式类型介绍如下： 1 概念描述：对含有大量数据的数据集合进行概述性的总结并获 得简明、准确的描述，一般分为定性概念描述和对比概念描述。 2 关联分析：就是从给定的数据集中发现频繁出现的项集模式知 6 识( 又称关联规则) “”。 3 分类和预测：分类找出一组能够描述并区分数据或概念的模型， 以便能够使用模型预测未知的对象类。 4 聚类分析：所分析处理的数据是无事先确定的类别归属，是一 种无教师监督学习方法。 5 异类( 孤点) 分析：数据集中那些不符合大多数数据对象所构 成的规律( 模型) 的数据对象被称为异类( o u t l i e r ) ，在某些特定应用 场合( 如商业欺诈行为的自动检测) ，小概率发生的事件( 数据) 比经 常发生的事件( 数据) 更有挖掘价值”1 。 6 演化分析：对随时间变化的时间对象的变化规律和趋势进行建 模描述。 1 3 5 数据挖掘的方法 数据挖掘中采用的方法综合了数据库、人工智能、统计学、模式识 别、机器学习、数据分析等领域的研究成果。现有的数据挖掘方法主要 有以下几种： 1 决策树方法 利用信息论中的互信息( 信息增益) 寻找出数据集中具有最大信息 的字段，建立决策树中的每一个结点，再根据字段的不同取值建立树的 分支的过程，即建立决策树。国际上最有影响的决策树方法是q u i n l a n 研究的i d 3 方法。 2 神经网络方法 它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础，建立 了三大类神经网络模型。 前馈式网络，以反向传播模型、函数型网络为代表，用于预测、模 式识别等方面。 反馈式网络，以h o p f i e l d 离散模型和连续模型为代表，分别用于 联想记忆和优化计算。 自组织网络，以a p t 模型，k o h o l o n 模型为代表，用于聚类。 3 模糊集合论方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式 识别和模糊聚类分析。模糊性是客观存在的，系统的复杂性越高，模糊 性越强，这是z a d e h 总结出的互克性原理。 4 遗传算法 是模拟生物进化过程的算法，由三个基本算子组成： 选择，是指从一个旧种群( 父代) 中选出生命力强的个体，产生新 7 种群( 后代) 的过程。 杂交，是选择两个不同的个体的部分进行交换，形成新的个体。 变异，对某些个体的某些基因进行变异。 遗传算法已在优化计算和分类机器学习等方面发挥了显著的作用。 5 粗糙集方法 粗糙集理论是八十年代初z p a w l a k 针对g f i r e g e 的边界域思想提 出的，基于给定训练数据内部的等价类，用上下近似集合来逼近数据库 中的不精确概念。用于分类，可以发现不准确数据或噪声数据内在的结 构联系；用于特征归约，可以识别和删除无助于给定训练数据分类的属 性；用于相关分析，可以根据分类任务评估每个属性的贡献或意义。其 主要思想是在保持分类能力不变的前提下，通过知识约简，导出问题的 决策或分类规则。 此外，数据挖掘方法还有：云理论、统计分析，值预测等。数据挖 掘是数据领域中一个高速发展的分支，它应用于不同的领域，其它领域 的知识和理论也广泛地应用到数据挖掘的研究中，结合实际需要，往往 能开发出更高效的算法。 1 4 本文的主要研究内容和机构 粗集理论核心之一是对系统进行约简，删除冗余属性，最终为获取 最好规则提供保证，因此本文主要针对粗集的核心知识点进行了相关探 讨，从面向实现的角度提出约简的一些启发式算法和规则的获取方法， 其中对属性约简算法的研究是本文的重点。 全文按如下章节进行介绍。 第l 章：首先，综述了研究数据挖掘和粗糙集的目的和意义以及国 内外在这方面的研究现状；其次，探讨了数据挖掘的相关概念、功能和 方法。 第2 章：是全文的理论基础，深入分析了粗糙集的基本概念。首先， 介绍了粗集的基本思想和信息系统：其次，分析了知识与不可分辨关系 以及不精确范畴、近似和粗糙度；再次，研究了区分矩阵以及知识约简 和核；最后介绍了知识的依赖性与属性的重要性以及决策规则的产生。 第3 章：是本文的主要部分，也是本文的研究重点。首先，介绍了 基于粗集理论属性约简的典型算法：其次，对几种启发式约简算法进行 了深入分析；最后，提出了改进的启发式约简算法，并给出了算法的描 述过程。 第4 章：首先，论述了分类规则发现的原理、算法步骤和模式；其 8 次，研究了规则，讨论了规则的描述和有效性，提出了规则产生的算法； 再次，探讨了分类决策和分类方法。 第5 章：通过具体实例分析本文所提出的约简算法和分类规则方法。 首先，通过实例说明如何求属性的约简和核；然后，分析如何从约简集 中得到决策规则：最后，分析讨论得出结论。 第6 章：对全文工作进行了总结，并给出了今后研究工作的方向。 9 第2 章粗糙集理论基础 近年来，粗集理论和应用的研究取得了很快的发展，为处理 不完整、不精确的数据提供了一种很好的方法。粗集理论同模糊 集、神经网络、证据理论等其他理论一起，成为不确定性计算的 一个重要分支。 2 1 基本思想 人们为了掌握客观事物，按事物相似的程度组成类别，这就 是分类。在已有分类的基础上，通过学习和训练形成一定的规则， 机器学习就是在这样规则的基础上，预测和判断新例的类别。而 分类的基本思想就是把一些性质相同的元素归为一类：这里所指 的性质常常可以认为是由一些基本属性和所讨论对象在该属性下 的取值组成。粗集理论就是建立在分类机制的基础之上，将分类 理解为在特定空间上的等价关系，而等价关系构成了对该空间的 划分。粗集理论将知识理解为对数据的划分，每一划分的集合称 为概念。粗集理论的主要思想是利用已知的知识库，将不精确或 不确定的知识用已知知识库中的知识来( 近似) 刻画。但是，由于 这个理论没有包含处理不精确或不确定原始数据的机制，因此对 对象的分类是建立在已有知识的基础之上：或者说在构建分类之 前，如果已有知识是不完善的，不精确的都将直接影响着我们获 取有价值的规则，这就要求我们必须对其进行处理。目前主要的 处理方法有神经网络、模糊集( f u z z ys e tt h e o r y ) 、可信度理论、 证据理论( dst h e o r y ) 等，后三种方法的处理又不可避免的受到 先验知识的影响；而神经网络的方法常常对知识的划分又过于精 确，例如用神经网络的方法离散化实型数据，断点常常出现在所 求曲线的拐点处，而在实际情况下断点又无须这样精确。粗集理 论提供了一套严格处理k d d 中最基本的分类问题的数学方法，通 过对数据的分析，生成确定与可能的形式规则。另外，粗集理论 包括了知识的一种形式模型，这种模型可将知识定义为不可区分 关系的一个族，使知识具有了一种清晰的数学意义，并且可使用 数学方法来分析处理。 粗糙集理论在数据分析中善于解决的基本问题包括发现属性 间的依赖关系、约简冗余属性与对象、寻求最小属性子集以及生 成决策规则等等。粗糙集与其他不确定性问题理论的最显著区别 是它无需提供任何先验知识，如概率论中的概率分布、模糊集中 的隶属函数等，而是从给定问题的描述集合直接出发，找出问题 的内在规律。 2 2 信息系统 基于粗集理论进行数据分析的全部对象的数据集合称为信息 系统( i s ) ，也称知识表达系统。一个信息系统可以用一个四元组 来定义：i s - - - - ( u ，a ，v ，f ) ，其中u = x ，x 。，x 是对象的非 空有限集合，称为论域；a - - - - a ，a 2 ，a l i ) 是属性的非空有限 集合；v 是属性a 所构成的域，即v iy 屹，v 是属性值域，v 。是属 口i 已i 性a 的值域；f ：u a v 是一个信息函数，u 中任一元素取属性a 在v 中有唯确定值，即v a a ，x u ，f ( x ，a ) v 。 信息系统的数据可以用关系表的形式表达，表的行代表对象 x u ，列代表属性a e a ，表中的数值代表对象x 对应属性a 的属 性值，记为a ( x ) 。因此，一个信息系统可以简化定义为i s - - - - ( u ， a ) 。容易看出，一个属性对应一个等价关系，一个表可以看作是 定义的一个等价关系簇，即知识库，知识约简可以转化为属性约 简。 决策表是一类特殊而重要的信息系统，多数决策问题都可以 用决策表形式来表达。决策表可以根据信息系统定义如下： 设i s = ( u ，a ，v ，f ) 是一个信息系统，a = c u d ，且c n d o ， c 称为条件属性集，d 称为决策属性集，v 是属性的值域，f 是对象 属性到值域的映射。具有条件属性和决策属性的信息系统称为决 策表。 决策表表头是各属性，它的每一行表示论域中的一个成员或 称一条决策规则，每一列表示属性及属性值。对于一个信息系统 i s ，若决策属性集d 不存在，就是一般意义上的信息表达系统： 若决策属性集d 存在，一般称为决策表系统。实际上，决策表系 统就是一般信息系统的一个特例。例如表2 1 就是一个信息系统， 而表2 2 3 是一个决策表系统。其中u - - - - l ，2 ，3 ，4 ，5 ，a - - - - a = s t u d i e s ，b = e d u c a t i o n ，c 2 - w o r k s ，d - - - - i n c o m e ，v = “n o ， y e s ) ， g o o d ，p o o r ， n o ，y e s ， h i g h ，l o w ，n o n e ，m e d i u m ) 。 c = a ，b ，c ，d ：( d 。在这种信息系统中，我们关心的是一个人 的收入与其生活状况的关系。粗集理论恰恰是直接从给定问题的 描述集合出发，通过不可分辨关系和等价类确定给定问题的近似 解。 表2 - 1 信息系统 2 3 知识与不可分辨关系 基本粗集理论认为知识是人类和其它物种所固有的分类能 力。分类是人类的最基本的智能行为，是推理、学习与决策中的 关键问题。因此，粗集理论重点讨论对对象进行分类的能力。这 里的“对象”指我们所能言及的任何具体或抽象的事物，我们称 为“论域( u n i v e r s e ) ”。一般认为，知识是人类实践经验的总结 和提炼，具有抽象和普遍的特性，是属于认识论范畴的概念。事 实上，知识便是对某一感兴趣领域中各种分类模式的个簇集， 这个簇集提供了关于现实的事实以及从这些事实中推导出隐含事 实的推理能力。 设u a 是我们感兴趣的对象组成的有限集合，称为论域。任 何子集x u 称为u 中的一个概念或范畴。为规范化起见，我们认为 空集也是一个概念。u 中的任何概念族称为关于u 的抽象知识，简 称知识。u 上的一族划分称为关于u 的一个知识库，它构成了一个 特定论域u 的分类。 1 2 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成 的集合， x 。表示包含元素x u 的r 等价类。 设r 是u 上的一族等价关系，若p r ，且p g ，则n p ( p 中所有等价关系的交集) 也是一个等价关系，称为p 上的不可分 辨( i n d i s c e r n i b i l i t y ) 关系用i n d ( p ) 来表示，即 【工j 删p ) 2 是| p f 工k ) 不可分辨关系是物种由属性集p 表达时，论域u 中的等价关 系。u i n d ( p ) 表示由等价关系i n d ( p ) 划分的所有等价类，且将其 定义为与等价关系p 的族相关的知识，称为p 基本知识。同时， 也将u i n d ( p ) 记为u p ，i n d ( p ) 的等价类称为关系p 的基本概念 或基本范畴。 对于表2 2 给出的收入决策表的例子，计算u i n d ( c ) 有如下结 果： u i n d ( a ，b ，c ) ) = “1 ，2 ， 3 ， 4 ，5 ) 从中可以看出对象被统一划分，并且组成划分的一个对象在 使用选定属性时是不可区分的。一个等价关系就是一个划分。表 2 - 3 是使用表格形式表示的划分：类a 来自对象1 和2 ，类b 来自 对象3 ，类c 来自对象4 和5 。注意类c 的两个对象有不同的决策 值。 表2 - 3 收入决策表的等价划分结果 2 4 不精确范畴、近似和粗糙度 令x g j ，r 为u 上的一个等价关系。当x 能表达成某些r 基 本范畴的并时，称x 是r 可定义的：否则称x 为r 不可定义的。r 可定义集也称作r 精确集，而r 不可定义集也称为r 非精确集或 r 粗糙集。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙 集的上近似( u p p e r a p p r o x i m a t i o n ) 和下近似 ( l o w e r a p p r o x i m a t i o n ) 来描述。给定知识库k = ( u ，r ) ，对于每 个子集x _ c u 和一个等价关系r i n d ( k ) ，定义两个子集： 蚪一u r u r i y z ( 2 2 ) p , x i j r z u r f y lx a ( 2 3 ) 分别称它们为x 的r 下近似集和r 上近似集。集合 b n r ( j ) z 厨一型称为x 的r 边界域：p o s r ) 一型称为的r 正域；m e g 。僻) 一u 一豆r 称为x 的r 负域。显然有 r xte o s , ( x ) u n n 月( x ) ( 2 4 ) r x 或p o s k 伍) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合；瓦r 是那些根据知识r 判断可能属于x 的u 中元素组成的集合；b n r ( x ) 是那些根据知识r 既不能判断肯定属 于x 又不能判断肯定属于x 的u 中元素组成的集合；n e g 。( x ) 是那 些根据知识r 判断肯定不属于x 的u 中元素组成的集合。用图2 1 可以形象地表示这种关系。 图2 i 粗糙集概念示意图 从图中2 1 可以看出，整个近似空间由划分成基本区域的长方 块构成的( u ，r ) 定义，每一个基本区域代表r 的一个等价类。不 规则曲线代表集合x ，内层粗线里面的区域就是集合x 的下近似集， 也就是正域，外面的区域是负域；外层粗线里面的区域是集合x 的上近似集；阴影部分就是集合x 的边界。 集合的不精确性是由于边界域的存在而引起的，集合的边界 域越大，其精确性越低。为了更准确地表达这一点，我们引入了 精度概念。由等价关系r 定义的集合x 的近似精度为： l 口l ，i 口。伍1 一；：兰斗( 2 5 ) i p o t i 其中x d ，ixi 表示集合x 的基数。 精度用来反映我们对集合x 的知识的了解程度。显然，o ( x ) 1 。当幽( x ) = 1 时，我们说集合x 是r 可定义的：当a i t ( x ) l 时，我们说集合x 是r 不可定义的。 1 4 当然，也可以用其它量度来定义集合x 的不精确程度，比如， 用x 的r 粗糙度p r ( x ) 来定义： o t ( x ) = l 一嘞( x ) ( 2 6 ) x 的r 粗糙度与精度恰恰相反，它表示关于集合x 知识r 的 不完备程度。 2 5 区分矩阵 区分矩阵( d i s c e r n i b i l i t ym a t r i x ) 是由波兰华沙大学的著 名数学家s k o w r o n 提出来的，利用这个工具，可以将存在于复杂 的信息系统中的全部不可区分关系表达出来。 一个信息系统i s - - - - ( u ，a ) ，对于属性集b a ，区分矩阵定义 如下： m ( b ) = ( m 。) 。，1 i ，j n = i u i n d ( b ) l ， m 。，= a b l a ( x 。) c a ( x ，) ，i ，j = l ，2 ，n ( 2 7 ) 区分矩阵的元素m t ，是b 中能区分对象类x ”x j e u i n d ( b ) 的 属性集。 对于一个决策系统i s = ( u ，c u d ) ，区分矩阵定义如下： m ( c ，d ) = ( m d ( i ，j ) ) 。，1 i ，j n = i u i n d ( c ) i ， u i n d ( b ) = x 。，x ：，x 一 ( i ，j ) = i 彩d ( x 。) - - - - d ( x j ) i a c i a ( x 。) c a ( x j ) 其它 ( 2 8 ) 表2 2 收入决策表对应的区分矩阵由表2 - 4 收入决策表的区 分矩阵给出。 表2 - 4 收入决策表的区分矩阵 2 6 知识的约简和核 知识约简是粗糙集理论的核心内容之一。所谓知识约简，就 是在保持知识库分类能力不变的条件下，删除其中不相关或不重 要的知识。知识约简的两个重要概念是约简和核。 2 6 1 约简和核 设r 为一个等价关系簇集，p e r ，如果i n d ( r ) = i n d ( r - - p ) ) ， 则称p 为r 中不必要的：否则称p 为r 中必要的。如果每一个p r 都为r 中必要的，则称r 为独立的，否则称r 为依赖的。 设q p ，如果q 是独立的，且i n d ( q ) = i n d ( p ) ，则称q 为p 的一个约简，记为r e d ( p ) 。显然，p 可以有多个约简。p 中所有 不可缺的等价关系组成的集合称为p 的核，记作c o r e ( p ) 。 核与约简有如下关系： c o r e ( p ) = n r e d ( p )( 2 1 1 ) 其中，r e d ( p ) 表示p 的所有约简。显然，核这个概念有两方 面的用处：首先它可以作为所有约简的计算基础，因为核包含在 所有的简式之中，并且计算可以直接进行；其次可解释为在知识 约简时它是不能消去的知识特征集合。 例2 1 设( u ，r ) 是一个知识库，其中g = x 。，x ：，x 。，x 4 ，x 5 ，x 6 ，新，x 8 ) ，r = r i ，r 2 ，r ，) ，r 。，r 2 和r 。有下列等价类： u r = “x 。，】【，x 5 ， x ：，x 8 ， x 3 ) ， x e ，x 7 ) ， u r 2 = “x i ，x 3 x 5 ， ) 【6 ， x 2 ，x ，x 7 ，】【8 j ， u r 3 = “x 。，x 5 ， x 6 ) ， x 2 ，x 7 ，x 8 ， x 3 ，x 4 ) l 。 关系i n d ( r ) 的划分为： u i n