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

基于粗糙集的数据约简算法研究与应用 摘要 数据挖掘，简单地说，就是从庞大的观察数据集中提炼并分析出不能轻易 察觉或断言的关系，最后给出一个有用的并且可以理解的结论。粗糙集理论是 一种处理模糊和不精确问题的数学工具。众所周知，许多实践问题不能满足现 存计算机的求解条件，特别是机器学习、模式识别、人工智能等，这些困难常 常使得不能建立描述个体的算法，粗糙集理论及其扩充对于建立此类个体的近 似描述，提供了一种精确的数学技术。 随着信息化社会的到来和知识经济的发展，信息系统中的信息量积累越来 越大，解决信息系统中信息量膨胀问题不仅是信息系统本身的研究课题，而且 也是i n t e r n e t 上的重要研究方向。信息系统约简主要是减少信息量，将一些无 关或多余的信息剔除，而不影响原有的功能。将约简后的信息重新组合，产生 新的决策规则，这些决策规则的前提信息和结论信息可能不同于约简前的任何 一条决策规则，但它们能够经过推理而得到相同或相近的结果。 本文主要介绍了数据挖掘、粗糙集等相关基本理论及其研究现状；对数据 挖掘过程中的核心问题数据约简，进行了深入分析与探讨；提出了一种基 于二叉树结构的信息系统数据约简算法，该算法使得属性约简和属性值约简得 以一致计算，缩短了约简时间，对于时间复杂度及空间复杂度也得以进一步降 低。最后就算法的实际应用做了一定研究。本文所做的主要工作如下： ( 1 ) 针对目前的有关约简算法需反复遍历决策表中各个数据项，使得时 间复杂度及空间复杂度较高，针对这一现状，我们进行了认真、深入研究。 ( 2 ) 提出了一个主要基于二叉树结构的数据约简方法，包括属性约简与 属性值约简等。该方法根据分辨函数的合取式动态建立相应二叉树，借助构造 出的二叉树，最终有效地完成数据约筒。 ( 3 ) 此外，我们设计了基于= 叉树结构的数据约简算法原型系统，在此 系统平台上，通过对u c i 提供的多个标准测试数据集进行测试，证明该算法的 有效性与优越性，并应用到教学评价系统中。 关键词：数据挖掘；粗糙集；属性约简；二叉树；分辨矩阵 r e s e a r c ho fd a t ar e d u c t i o na n d a p p l i c a t i o nb a s e do nr o u g hs e t s a b s t r a c t d a t am i n i n gi st oe x t r a c ta n da n a l y z es o m es u b t l er e l a t i o n s h i p si n s i d et h e e n o r m o u sd a t as e t s ，a n dt h e nc o m e st oau s e f u la n du n d e r s t a n d a b l ec o n c l u s i o n t h e t h e o r yo fr o u g hs e t s i sam a t h e m a t i c a lt o o lf o rp r o c e s s i n ga m b i g u o u sa n d i n a c c u r a t ep r o b l e m i ti sw e l l k n o w nt h a tm u l t i t u d e so fp r a c t i c a lp r o b l e m sc a n tb e s o l v e db yt h ep r e s e n tc o m p u t e rs y s t e m s ，e s p e c i a l l yt h o s el i k em a c h i n el e a r n i n g ， p a t t e r nr e c o g n i t i o n a n da r t i f i c i a l i n t e l l i g e n c e ，w h i c h m a k et h ea l g o r i t h mf o r d e s c r i b i n gi n d i v i d u a l si m p o s s i b l e t h et h e o r yo fr o u g hs e t sa n di t se x p a n s i o nc a n p r o v i d ea na c c u r a t em a t h e m a t i c a lt e c h n o l o g yf o rr o u g hd e s c r i p t i o no fs u c h i n d i v i d u a l s w i t hd e v e l o p m e n to fk n o w l e d g ee c o n o m ya n dt h ec o m i n go fi n f o r m a t i o n s o c i e t y , m o r ea n dm o r ei n f o r m a t i o na c c u m u l a t e sw i t h i ni t ss y s t e m s o l v i n gt h e p r o b l e mo fi n f o r m a t i o ne x p a n s i o ni sn o to n l yt h er e s e a r c hs u b j e c to ft h es y s t e m i t s e l f , b u ta l s o a ni m p o r t a n t s t u d yf i e l d o nt h ei n t e r n e t t h er e d u c t i o no f i n f o r m a t i o ns y s t e mc a nr e d u c et h ei n f o r m a t i o nv o l u m eb yr e m o v i n gi r r e l e v a n ta n d u n n e c e s s a r yi n f o r m a t i o nw i t h o u ta f f e c t i n g i t sf u n c t i o n s a f t e rr e d u c t i o n ，t h e i n f o r m a t i o nw i l lb er e a r r a n g e da n dn e wr u l e so b t a i n e d t h e s er u l e sd i f f e r e n tf r o m t h ep r e v i o u so n e si nt e r m so ft h e i rp r e m i s ea n dc o n c l u s i o ni n f o r m a t i o n h o w e v e r , t h es a m eo rs i m i l a rr e s u l t sc a nb ea c h i e v e dt h r o u g hd e d u c t i o n t h i st h e s i sm a i n l yi n t r o d u c e st h eb a s i ct h e o r i e sa n dp r e s e n tr e s e a r c h e so f r o u 【g hs e t s ，a n a l y s e sd a t ar e d u c t i o n ，t h ec o r eo fd a t a m i n i n gp r o c e s s ，a n ds u g g e s t sa d a t ar e d u c t i o na l g o r i t h mo fi n f o r m a t i o n a ls y s t e m ，b a s e do l lb i n a r yt r e e s t h i s a l g o r i t h mm a k e sa t t r i b u t er e d u c t i o nc o n s i s t e n tw i t hi t sv a l u er e d u c t i o n ，s h o r t e n s t h er e d u c t i o nt i m e ，a n dl o w e r st h ec o m p l i c a t i o nd e g r e e so ft i m ea n ds p a c e t h em a j o ra c h i e v e m e n t sa n di n n o v a t i o n sm a d ei nt h i st h e s i sa r ea sf o l l o w s ： ( 1 ) t h ep r e s e n td a t ar e d u c t i o na l g o r i t h mi ss t u d i e d ，w h i c hn e e d st og o t h r o u g ha l ld a t ai nt h ed e c i s i o n - f o r mt ol o w e rt h ec o m p l i c a t i o nd e g r e e so ft i m ea n d s p a c e ( 2 ) b a s e do nb i n a r yt r e e s ，an e wd a t ar e d u c t i o na l g o r i t h mi sp u tf o r w a r d ， i n c l u d i n ga t t r i b u t er e d u c t i o na n di t sv a l u er e d u c t i o n w i t ht h eh e l po ft h en e w b i n a r yt r e e si n v e n t e df r o mt h ed y n a m i cs y n t h e s i so fr e v o l v i n gf u n c t i o n ( 3 ) a p r o t o t y p es y s t e mo fd a t ar e d u c t i o na l g o r i t h mi sd e v i s e d ，b a s e do nt h e s t r u c t u r eo fb i n a r yt r e e s t h ev a l i d n e s sa n dh i g he f f i c i e n c yo ft h i sa l g o r i t h mi s p r o v e dt h r o u g ht e s t i n gs e v e r a ls t a n d a r dt e s td a t as e t sp r o v i d e db yu c i ，a n di th a s b e e nu e s e di nt h et e a c h i n ge v a l u a t i o ns y s t e m k e y w o r d s ：d a t am i n i n g ；r o u g hs e t s ；a t t r i b u t er e d u c t i o n ：b i n a r yt r e e s ：d i s c e r n a b l e m a t r i x 图表清单 图1 1 数据挖掘流程3 图2 1 粗糙集示意图1 0 图4 1 树结点结构2 8 图4 2 二叉树t 2 8 图5 1 原型系统结构图3 6 图5 2 系统主界面3 6 图5 3 数据选择界面3 7 图5 4 数据预处理3 7 图5 5 规则显示3 8 图5 6 系统体系结构4 0 表2 1 一个知识表达系统1 3 表4 1 不相容决策表2 5 表4 2 不相容决策表的分辨矩阵2 5 表4 3 一个信息系统2 9 表4 4 经属性约简后的决策表3 2 表4 5 属性值分类表3 2 表4 6 规则集3 3 表5 1 实验数据3 8 表5 2 实验数据( 响应时间比较) 3 9 表5 3 实验数据( 规则数比较) 3 9 表6 4 教师教学评价部分数据4 i v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 金胆王些去堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：五叫 签字目期：d 7 年6 月c f 日 学位论文版权使用授权书 本学位论文作者完全了解金壁王些太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权尘 胆些态堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 1 剐j 签字日期：卯年6 月f 够日 ， 学位论文作者毕业后去向： 工作单位； 通讯地址； 导师签名： 髟膨 签字日期：哆7 年月乎日 电话： 邮编； 致谢 首先我要衷心感谢我的导师王浩教授，在整个论文资料收集、选题到撰写、 修改等过程都给予了我无微不至的关怀和毫无保留的教导。王教授严谨的治学 态度、渊博的学术知识，开拓创新的学术作风，平易近人的高尚品德，勤勉踏 实的工作态度，对我在做人、治学、工作等诸方面产生了深远影响，将让我终 生受益，并将指导我在以后的人生道路中不断进步。值此论文完成之际，谨向 导师王浩教授致以最诚挚的敬意和衷心的感谢。 同时，我也要诚挚地感谢计算机与信息学院的胡学钢教授，他给予了我很 多的关心与指导，对我的研究工作提出了许多中肯、宝贵的意见，在此表示感 谢。胡学钢教授高尚的师者风范，深深地影响我，将让我终生受益。 我还要感谢计算机与信息学院的老师，特别是方帅老师、姚宏亮老师，在 论文撰写的过程中，他们给予了我很多的帮助。感谢在实验室共同探讨的同仁 们，同你们进行交流，让我获得了更多更新的知识，给予我更多有益的启示。 最后，我要感谢我的母亲和我的爱人，是她们教给我做人的道理，是她们 给予我向前的勇气，是她们在背后默默地支持我。她们的爱、她们的关心将永 远是我前进的动力。 i l l 作者：王刚 2 0 0 7 年5 月1 8 日 第一章绪论 1 1 本课题的来源和意义 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，已 经从单机系统发展到分布式系统，甚至到i n t e r n e t 全球信息系统，使得无论企 业、科研机构或是政府部门，在很短时间内积累了海量的、以不同形式存储的 数据资料。如一些大型超市的p o s 系统每天都要存储上万笔的顾客购买物品的 数据，各种同步卫星每小时传回地球的遥感图像数据就达5 0 千兆字节这些数 据如果仅仅依靠传统的数据库查询机制和统计学方法已经远远不能满足现实需 要，它迫切要求自动地和智能地将待处理的数据转化为有用的信息和知识，从 而达到为决策服务的目的。数据挖掘正是为迎合这种需要而产生并迅速发展起 来的用于开发信息资源的一种新的数据处理技术。 目前数据挖掘已经被越来越多的领域所采用，并取得了较好的效果，为人 们的正确决策提供了很大的帮助，具有较为广泛的应用前景。在数据挖掘的过 程中，存在大量冗余数据影响我们的决策。粗糙集理论【3 1 - 3 2 , 4 1 是一种处理模糊 和不确定性知识的数学工具，为我们在获取决策规则和推理过程方面提供了一 个有效的方法，它不但可以在不影响数据所表达的信息下使原来的数据量大为 减少( 数据浓缩) ，而且可以产生决策规则，从而可以挖掘数据中的有效模式。 它己经在机器学习、知识获取、决策分析、知识发现、专家系统和模式识别等 领域取得了一些成功的应用。 用粗糙集理论从数据库中发现规则需经过以下步骤 4 1 】：数据预处理、约简、 规则获取等，其中约简是粗糙集理论中的核心内容。一个信息系统或决策表可 能有多个约简。约简中属性的个数将直接影响粗糙集理论导出的规则和规模。 一般来说，约简中属性个数越少，则由它导出的规则数就越少，用这些规则对 那些新的对象进行分类时，其产生的检验代价就越低。在实际应用中，人们总 是希望找出信息系统或决策表中的那些尽量小的约简。 对目前已有的约简算法【4 瑚出】进行分析，发现存在的主要问题有：首先，绝 大多数约简算法处理的对象是相容决策表，没有对不相容决策的情况进行考虑， 但实际应用中这种情况应该说是十分普遍的。其次，目前绝大多数约简算法是 启发式算法，即找到一个约简即可，这样无法找到最佳约简。再次，绝大多数 约简算法，具体来说，就是属性约简，但是经过属性约简后并没有达到最小约 简目的，仍然有许多冗余数据，如果不去掉这些冗余数据，对其后的知识获取 将产生很大影响。此外，目前大多数算法着眼于单个属性进行考虑，极易陷入 局部最优的困境，对属性约简与属性值约简分别考虑，无法实现整个约简的一 体化。 传统的数据库模式都是由许多不同属性组成的，但是在求解某个给定的数 据挖掘问题时可能并不需要全部属性事实上，其中的一些属性可能会对数据 挖掘任务的正确执行造成干扰，而另外一些属性则可能增加算法的复杂性并降 低算法的效率。这个问题有时被称作维数灾难，即由于涉及属性较多，导致难 以确定使用哪些属性高维问题的一个解决方案是减少属性的个数但是，确 定哪些属性是多余的，并非能够轻易完成的任务。 因此研究准确快速的约简算法对数据挖掘技术的发展应有很大促进作用。 1 2 数据挖掘概述 1 2 1 数据挖掘技术的发展 1 9 8 9 年举行的第十一届国际联合人工智能学术会议上首次提出了从数据库 中发现知识( k d d ) 一词。到1 9 9 9 年为止，由美国人工智能协会主办的k d d 国际 研讨会己经召开了8 次，规模由原来的专题讨论会发展到国际学术大会，研究 重点也逐渐从发现方法转向系统应用，注重多种发现策略与技术集成，以及多 学科之间的相互渗透。其它内容的专题会议也把数据挖掘和知识发现列为议题 之一，成为当前计算机科学的一大热点【1 。射。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也 纷纷开辟k d d 专题或专刊。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 技术专刊，注重k d d 研究的最新成果和动态，包括k d d 系 统方法论、发现结果的评价、k d d 系统设计的逻辑方法等。 与国外相比，国内对数据挖掘方面研究稍晚。目前，国内的许多科研单位 和高等院校竞相开展数据挖掘的基础理论及其应用研究，这些单位包括清华大 学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中， 北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究；北 京大学开展了对数据立方体代数方面的研究；合肥工业大学开展了基于粗糙集 合理论的概念格模型研究：南京大学、四川大学和上海交通大学等单位也分别 探讨和研究了非结构化数据的知识发现以及w e b 数据挖掘等。最近，g a r t n e r g r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对 工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘 列为未来五年内投资焦点的十大新兴技术前两位。根据最近g a r t n e r 的h p c 研 究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多 地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来刨 建新的商业增长点。”1 1 5 - 1 6 j i 2 2 数据挖掘定义 数据挖掘1 1 ，1 4 】最早是在1 9 9 5 年美国计算机年会( a c m ) 上提出的概念，数据挖 掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际数 据中，提取隐含在其中的、人们感兴趣的、潜在有用的信息和知识的过程。这 个定义包括的含义有：数据源必须是真实的、大量的、含噪声的；发现的是用 户感兴趣的知识；发现的知识可接受、可理解、可运用；知识需要支持特定的 发现问题。 知识的定义从广义上理解，数据、信息也是知识的表现形式，但是人们更 把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的 源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据 库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在 网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可 以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询优化、 决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门 交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘 知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是 数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者 和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 因此它是一种具有强大实际作用和前途的学科。 1 2 3 数据挖掘过程 数据挖掘是一个完整的过程，通过这一过程，从大型数据库中挖掘出先前 未知的、有效的、可实用的信息，并应用这些信息作出决策或者丰富知识。数 据挖掘是分步实现的过程，主要有三个阶段：数据准备、数据挖掘、结果的解 释和评估。数据挖掘可以表示为这三个阶段的反复过程，如图1 1 所示，它描 述了数据挖掘的基本过程和主要步骤【1 0 _ 13 1 。 图1 1 数据挖掘流程 1 2 4 数据挖掘的功能及常用技术 数据挖掘功能是指用于指定数据挖掘任务的模式类型。数据挖掘任务一般 一3 一 可以分为两类：描述型和预测型。描述型任务描述了数据的一般特性，预测型 任务预测未来趋势及行为。数据挖掘功能主要体现在以下几个方面1 t 3 , 1 5 l ： ( 1 ) 自动预测趋势和行为 预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数 据或者被丢失的数据种类、特征等。例如，根据同单位其他职工的工资，预测 某职工的工资。 ( 2 ) 关联分析 关联分析是从数据库中发现知识的一类重要方法。若两个或多个数据项的 取值之间重复出现且概率很高时，就存在某种关联，可以建立起这些数据项的 关联规则。例如，买面包的顾客有9 0 的人还买牛奶，这是一条关联规则。 在大型数据库中，这种关联规则是很多的，需要进行筛选。一般用。支持 度”和“置信度”两个阀值来淘汰那些无用的关联规则。对于形如“a b ”的关 联规则，“支持度”表示该规则所代表的事例占全部事例的百分比，即包含a 和 b 的元组数占元组总数的百分比；“置信度”表示该规则所代表事例占满足条件 事例的百分比，即包含a 和b 的元组数占包含a 的元组数的百分比。 ( 3 ) 聚类 数据库中的数据可被划分为一系列有意义的子集，即聚类。在同一类别中， 个体之间的距离较小，而不同类别的个体之间的距离较大聚类增强了人们对 客观现实的认识，通过聚类建立宏观概念，是概念描述和偏差分析的先决条件。 ( 4 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者 描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有 对象的共性，生成区别性描述的方法很多，如决策树方法、遗传算法等。 ( 5 ) 偏差检测 数据库中的数据存在很多异常情况。从数据分析中发现这些异常情况也是 很重要的，应该引起人们的足够重视。偏差包括很多潜在的知识，如分类中的 反常实例、不满足规则的特例、观察结果与模型值的偏差、量值随时间的变化 等。 数据挖掘常用技术主要涉及到人工神经网络、决策树、遗传算法、最近邻 技术、规则推导、粗糙集方法和可视化等| 6 - 8 , 1 4 - 1 6 。其中，人工神经网络从结构 上模仿生物神经网络，是一种通过训练来学习的非线性预测模型，可以完成分 类、聚类、特征开采等多种数据挖掘任务。决策树用树形结构来表示决策集合， 这些决策集合通过对数据集的分类产生规则，典型的决策树方法有分类回归树。 遗传算法是一种新的优化技术，基于生物进化的概念设计了一系列的过程来达 到优化的目的，这些过程有基因组合、交叉、变异和自然选择，为了应用遗传 - - 4 - - 算法，需要把数据挖掘任务表达为一种搜索问题而发挥遗传算法的优化搜索能 力最近邻技术通过k 个与之最相近的历史记录的组合来辨别新的记录，有时 也称这种技术为k 最近邻方法，这种技术可以用作聚类、偏差分析等挖掘任务。 规则推导是通过统计方法归纳、提取有价值的“如果一那么”规则，规则推导 的技术在数据挖掘中被广泛使用，例如关联规则的挖掘。可视化技术采用直观 图形方式将信息模式、数据的关联或趋势呈现给决策者，决策者可以通过可视 化技术交互地分析数据关系。粗糙集理论是八十年代初z p a w l a k 针对g f r e g e 的边界域思想提出的，基于给定训练数据内部的等价类来建立，用一对上、下 近似集合来逼近数据库中的不精确概念，用于分类，可以发现不准确数据或噪 声数据内在的结构联系。用于特征归约，可以识别和删除无助于给定训练数据 分类的属性。用于相关分析，可以根据分类任务评估每个属性的贡献或意义。 其主要思想是将数据库中的属性分为条件属性和决策属性，对数据库中的实例 根据各个属性不同的属性值分成相应的子集，在保持分类能力不变的前提下， 通过知识约简，导出问题的决策或分类规则。 采用上述技术的某些专门的分析工具己经发展了十多年的历史，而现在这 些技术己经被直接集成到许多大型的工业标准的数据仓库和联机分析系统中。 1 2 5 数据挖掘应用 数据挖掘技术的最终目的就是应用。在商业领域，通过应用数据挖掘技术 可以提高企业竞争力，降低生产成本；而更为重要的是它所带来的社会效益， 它能够应用到医疗，交通等与人类生活密切相关的领域，从而使整个人类社会 受益。现今，支持数据挖掘的一些基础技术已经日趋成熟，它们是海量数据搜 集、强大的多处理器计算机以及数据挖掘算法。 1 3 基于粗糙集的数据挖掘 利用粗糙集理论进行数据挖掘有着较传统挖掘方法不具有的优点【“4 “。粗 糙集理论处理数据不需要数据的先验信息，譬如统计学中的概率分布、 d e m p s t e r s h a f e r 理论中的概率赋值或者模糊集理论中的隶属度或概率值。基于 粗糙集的数学模型更易于被理解，针对一个特定的大型数据库，利用粗糙集理论 比其它理论更容易建立数学模型。许多实验表明，对于同一个数据集，在粗糙 集理论工具下进行处理，最终得到的信息更简单、更准确、更易于被决策者接受 和理解。 基于粗糙集的数据挖掘算法实际上是对决策表进行约简的过程，这个处理 过程具体如下 2 1 , 3 1 j ： ( 1 ) 删除决策表中重复的实例； ( 2 ) 删除多余的属性； ( 3 ) 删除每个实例中多余的属性值； ( 4 ) 求出最小约简，由最小约简导出逻辑规则。 1 4 本文研究的内容及组织结构 本文在研究粗糙集理论和数据挖掘技术的基础上，对基于粗糙集的数据挖 掘过程中约简算法进行深入研究，重点对已有的约简算法的不足进行剖析，寻 求准确、快速的约简算法。 本文的内容组织结构如下： 第一章系统地介绍了与数据挖掘相关的一些基础理论，包括数据挖掘技术 的研究发展、数据挖掘的基本概念、数据挖掘过程、数据挖掘的功能及常用技 术、基于粗糙集的数据挖掘相关知识等。 第二章介绍粗糙集基本理论，并就知识的绝对约简、知识的相对约简、属 性的重要度等内容做具体分析研究。 第三章对一些常见的基于粗糙集的数据约简算法进行深入研究与探讨，分 析其利弊所在。 第四章在前面第三章分析、探讨的基础上，提出了一种基于二叉树结构的 数据约简算法，从算法思想、实现过程、时间复杂度等方面进行较为深入地研 究。 第五章对基于二叉树结构的数据约简原型系统进行认真分析、研究，设计 相应的原型系统，通过实验来验证本算法有效性及优越性，并研究其实际应用。 第六章对全文进行总结，并对下一步的工作进行了展望。 第二章粗糙集基本理论 2 1 粗糙集理论的产生与发展 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在于真和假二值 之间。长期以来许多逻辑学家就致力于研究含糊概念。早在1 9 0 4 年，谓词逻辑 的创始人g f r e g e 就提出了含糊一词( 英文词f u z z y ) 【”i ，并把它归结到边界线 区域上，也就是说在全域上存在一些个体，它们既不能在某个子集上被分类， 也不能在该子集的补集上被分类。 1 9 6 5 年，l a z a d e h 提出了模糊集【1 9 】，不少理论计算机科学家和逻辑学家 试图通过这一理论解决g f r e g e 的含糊概念。但模糊集理论采用隶属度函数来 处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的 主观性。 2 0 世纪8 0 年代初，波兰科学家z p a w l a k 针对g f r e g e 的边界线区域思想 提出了粗糙集( r o u g hs e t ) 理论，他把那些无法确认的个体都归属于边界线区域， 而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学 公式描述，完全由数据决定，所以更具有客观性。粗糙集理论兴趣在于它恰好 反映了人们用粗糙集方法处理不可辨识问题的常规性，即以不完全信息或知识 去处理一些不可辨识现象的能力，或依据观察、度量到的某些不精确的结果而 进行分类数据的能力 粗糙集理论自被提出以来，许多计算机科学家和数学家对粗糙集理论及其 应用进行了坚持不懈的研究，使之在理论上日趋完善。特别是由于2 0 世纪8 0 年代末和9 0 年代初它在知识发现等领域得到了成功的应用而越来越受到国际上 的广泛关注。 1 9 9 1 年z 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 9 9 2 年r s l o w i n s k i 主 编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，推动了国际上 对粗糙集理论与应用的深入研究。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙 集学术讨论会，主要讨论了集合近似定义的基本思想及其应用。1 9 9 4 年，在美 国s a n j o s e 召开了第三届国际粗糙集与软计算研讨会，这次会议主要讨论了粗 糙集与模糊逻辑、神经网络、进化理论的融合问题。次年，召开的第四届模糊 理论与技术国际研讨会，主要针对粗糙集与模糊集之间的关系进行了讨论，促 进了粗糙集的发展。1 9 9 9 年，在日本召开第七届粗糙集、模糊集、数据挖掘和 粒度一软计算国际会议，主要阐述了当前粗糙集、模糊集的研究现状和发展趋 势。广大中国学者也以很高热情积极投入到粗糙集理论的研究之中。目前在国 - 7 - 内，粗糙集理论与知识发现是一个研究的热点，也形成了若干专门的研究机构， 如中科院自动化研究所、浙江大学智能信息研究所等；其它还有很多高校自发 形成的研究，如清华大学、西安交通大学、重庆大学等。2 0 0 1 年在重庆召开了 国内第一次租糙集理论国际研讨大会目前，粗糙集已成为人工智能领域中一 个较新的学术热点，越来越多的科技人员以极大的热情积极从事该领域的研究。 粗糙集理论己经构成了k d d 的一个完备基础，可以预言，粗糙集方法将在数据 挖掘和软计算，特别是处理大型数据库和复杂问题等方面，显示出重要的作用 1 9 ，2 5 - 4 9 1 2 2 粗糙集理论 2 2 1 知识与知识库 ( 1 ) 论域：设u d 是我们感兴趣的对象组成的一个有限集合。 ( 2 ) 知识：u 上的任何子集称为u 中的一个概念，知识则是u 中的任何概 念族。 ( 3 ) 等价类与划分：设r 是集合u 的一个等价关系，那么r 的等价类形成 u 的一个划分；同样，一个划分中的任意集合都当作一个等价类，就形成了一个 等价关系。 这就是说，等价关系与划分的概念是一一对应的。设u 为一个论域，r 为集 合u 上的一个等价关系，以r 的所有等价类作为元素的集合来划分x 可得到 u r ( 基本知识) ：u r = x l x e u ) = x 1 ，x 。) 。 ( 4 ) 知识库；知识库可定义为序对形式：f f = ，r 为一等价关系，即知 识。在知识库k = 中，把i n d ( k ) 定义为k 中所有等价关系的族，记作 i n d ( k ) - - i n d ( p ) lp r ，且p d 。 ( 5 ) 不可分辨关系：在知识库k = 中，p r ，且p d ，则n p ( p 中全 部等价关系的交集) 也是一个等价关系，称为p 上的不可分辨关系，记为i n d ( p ) 。 不可分辨关系的等价类形成知识的基本模块，处于等价类中的任何对象， 我们都无法分辨。在数学上，租糙集理论把知识看作是关于论域的划分，论域 上的一个划分与其上的一个等价关系是等价的，知识的这种颗粒状结构是通过 等价关系的等价类来予以体现。正是由于知识的这种“颗粒”状，导致了知识 的粗糙性嘲。 2 2 2 粗糙集的基本概念 等价关系或者说不可分辨关系的等价类中的对象，我们无法识别，这些等价 类构成了知识的粒度，从而产生了不确定性。这种不确定性，与模糊集所产生 的不确定性不一样，是由于我们知识的不完全性而造成的，而模糊集则是由于 模糊子集的概念不确定性而产生的。在粗糙集理论中，我们所要表达的某个子 集是完全确定的。 定义2 1 ：设x u ，r 为u 上的一个等价关系( 或不可分辨关系) ，k = 是一个近似空间，如果x 是一些r 基本类的并集，称x 是r 可定义的；反之， 称x 是r 不可定义的。 定义2 2 ：在知识库k = 中，如果存在一个等价关系r e i n d ( k ) 使得x c _ u 是r 一致的，则集合x 被称作k 中的精确集；如果x u 对于任意r e i n d ( k ) ，x 都是r 不可定义的，则x 被称作k 上的粗糙集。 如何近似地定义粗糙集? 为此，引入两个概念：上近似集，下近似集【3 0 l ， 上、下近似集是指当一个集合不能利用有效的等价关系被恰当地分类时，则可 以通过另外的集合来达到这个集合的近似。 定义2 3 ：设x _ c u 是任一子集，r 是u 上的等价关系，则有 r ( x ) = uf y e u r i y c _ x r ( x ) = u y u r ly n x o 分别称它们为x 的r 一下近似和r 一上近似，其中d 是空集，y 是类集u r 中 的元素。下近似被解释为所有那些被包含在x 里面的等价类的并集；上近似被 解释为所有那些与x 有交的等价类的并集。下近似和上近似也可以用下面的等 价形式来表达： r ( x ) = x e u l x r x r ( x ) = ( x e u f x r n x p 显然有下面的性质： ( 1 ) x 为r 精确集当且仅当r 。( x ) = r + ( x ) ( 2 ) x 为r 粗糙集当且仅当r ( x ) r ( x ) 一个集合的下近似和上近似将论域划分为三个不相交的区域：正区域 p o s r ( x ) 、负区域n e g r ( x ) 和边界区域b n r ( x ) 。 定义2 4 ：r 边界区域：b n r ( x ) = r ( x ) 一r ( x ) 称为x 的r 边界域。 r 正区域：p o s r ( x ) = r ( x ) 称为x 的r 正区域。 r 负区域：n e g r ( x ) = u - - r 。( x ) 称为x 的r 负区域。 由上面的定义，r 。( x ) 或p o s r ( x ) ，它是如此一些个体元素的集合，这些元 素完全属于x 的成员；r ( x ) 是那些根据知识r 判断可能属于x 的u 中元素组成 的集合；b n r ( x ) 是那些根据知识r 既不能判断肯定属于x 又不能判断肯定不属于 x 的u 中元素组成的集合；n e g r ( x ) 它是如此一些个体元素的集合，这些元素不 是任意模糊地用等价关系r 确定的，它们不属于x ，而是属于x 的补集x 。 下近似和上近似以及边界域的概念可以用图2 1 来清楚的描述【3 0 】： y： 丈 爻 羹 蕊， k 一 、l 舻鼬，p o s 冀0 0x 图2 1 粗糙集示意图 砸魄 图中由曲线围起来的部分就是我们需要表达的某个子集x ，由里边粗黑线围 起来的就是这个子集的下近似，外边粗黑线围起来的就是这个子集的上近似， 位于两者之间的就是边界域。小方格就是由我们的知识r 所产生的等价类。它 也就表示了知识r 的粒度性。集合x 无法用小方格准确地表示出来，但是，它 可以由两个集合：上近似和下近似粗略地表示【2 8 - 3 l l 。 粗糙集的表示只是由两个精确集近似地表示。这种近似的大小是可以刻画 的。由上图可以看出：粗糙集的不精确性是由于边界域的存在而引起的。边界域 越大，其精确性越低。如果边界域为空集，则粗糙集便成为精确集。 定义2 5 ：设x u 且x d 我们称 a r ( x ) = c a r d ( r ( x ) ) c a r d ( r 。( x ) ) 为x u 的近似精度，其中c a r d ( s ) 表示s 的基数。 定义2 6 ：设x c u 且x d ，r 粗糙度定义为：pr ( x ) = i - ar ( x ) a r ( x ) 表示我们获得关于集合x 的知识是否完全的程度。对于每一个r 和x ， 有o ar ( x ) 1 。当or ( x ) - - i 时，则说明x 的r 边界域为空集，集合x 就是r 的精确集；否则，集合x 有非空r 边界域，集合x 是r 的粗糙集。而x 的r 粗 糙度pr ( x ) 与精度正好相反，它表示的是集合x 的知识的不完全程度。 由近似精度和粗糙度可知，粗糙集理论与模糊集和概率论不同 1 z j 3 】，不精 确的数值不是事先假定的，而是通过表达知识不精确性的概念近似计算得到的， 这种不精确性的数值表示的是有限知识( 知识的粒度性) 的结果。粗糙集理论 不需要预先指定一个精确数值去表达不精确的知识。 2 3 知识约简 知识约简是研究近似空间中每个等价关系是否都是必要的，以及如何删除 不必要的知识。知识约简在信息系统分析与数据挖掘等领域都具有重要的意义。 知识之间的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重 要性往往是知识约简的重要启发式信息。 2 3 i 知识的绝对约简 在一个知识库里，希望同样的问题能够用较少的知识把它表达出来，但又 不失其原有的表达能力，在粗糙集理论中，可借助于约简来达到目的。约简 ( r e d u c t i o n ) 定义为不含多余属性并保证分类正确的最小条件属性集。 令r 为一等价关系族，r e r ，如果i n d ( r ) = i n d ( r - r ) ，则称r 在r 中是可 以被约去的知识，r 在r 中是不必要的。也就是说，r 和( r 一 r ) 能够表达相同 的知识，r 在r 中的作用不大，删除它不影响对原来系统的描述 如果每一个r r 都为r 中必要的，则称r 为独立的；否则称r 为相关的。 如果r 为独立的，则说明r 中的每个等价关系r 都是必要的，都不可省略，即r 具有最小性。 定义2 7 ：设r 为一等价关系族，r e r ，如果p = r 一 r 是独立的，则p 是r 中的一个约简。 根据这个定义可知，约简有两个方面的性质：首先，约简所表达的对系统的 划分与原来的知识库所形成的划分是一致的，即约简所表达的知识和原来的知 识具有相同的表达能力；其次，就是独立性与最小性，约简是能够表达原来知 识库的最小集合，约简里边一般不可再进行约简p o l 。 定义2 8 ：r 中所有必要的关系称为核，由它构成的集合称为r 的核集，记 为c o r e ( r ) 。 对于核与约简，有如下性质： c o r e ( p ) = n r e d ( p ) 其中r e d ( p ) 表示p 的所有约简族。核作用【4 9 l 主要体现在作为所有约简计算 的基础，因为核包含在所有的约简之中，并且计算可以直接进行；其次核可解 释为在知识约简时它是不能消去的知识特征集合。 2 3 2 知识的相对约简 在应用中，一个分类( 不可分辨关系) 相对于另一个分类( 不可分辨关系) 的 关系十分重要【2 0 埘l 。首先给出如下定义： ， q 的p 正区域：p o s p ( q ) = u