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

哈尔滨工程大学硕士学位论文 摘要 随着数据库的不断增长，自动从数据库中获取有用的知识成为人们日 益迫切的需要。粗糙集理论( r o u g hs e t s ) 就是在这样背景下不断发展起来的 一种用于不精确、不确定数据挖掘与处理的新型数学理论。粗糙集理论也 凭借其独特的优势而在k d d 领域中具有越来越重要的地位。 属性约简是粗糙集理论研究的核心问题之一，本文首先介绍了p a w l a k 粗糙集模型以及决策表、差别矩阵和约简等基本概念，为后面章节中的属 性约简算法打下了理论基础。 本文把属性重要性作为启发式信息，以核属性为寻求约简的起点，通 过对算法中加入启发式信息，减少了搜索空间。对属性约简的基本算法做 出了改进，把本来是对差别矩阵进行逻辑运算的计算转化成代数运算，在 定程度上简化了计算，提高了约简效率。在文章的最后利用约简算法对 远程教学网站中的课程进行等级评价，实验证明，该算法可以获得令人满 意的约简。 关键词：数据挖掘；粗糙集；属性约简；差别矩阵 哈尔滨工程大学硕士学位论文 a b s t r a c t d a mm i n i n gh a sk e n 锄u r g e n tn e db e m u s eo fi n c r c a s i n gs i z eo f 锄盯c n t b a s e s r o u 曲s c tt h e o 彤an e wm a t h 锄a t i c a lt h c o r yf o rm i n i n ga n d p r o c e s s i n gi m p r e c i a n du n a a md a t ah 弱g o t 掣e a ti m p r o v c m 锄tu n d c ft h i s b a c k w o o d r o u g h s c tt h e 棚f ) ，h a sa l s ob e c o m eam a i nm e t h o df o rk d dd u et o i t su l l i q u ea d v 础g ei nk n o w l c d g cd i s c o v e 呼 蒯b u t er c d i l d i 衄i so n eo ft h ek e yt o p i c si nt h er o u os c tt h r o wf i e l d 融t ，m c m o d e lo f r 0 u g hs e t t h e o f yo f p a w l a l 【i s 劬砸u c e d i n t h i sp a p e ra n d i t sb a s i cc o n c c p t ss u c h 弱d e c i s i o nt a b l e ，d i s c e m i b i l i t ym a t r i x ，a n dr e d u d i o n 1 1 l c a r cb 弱i ct h e o r i e sf o rt h el a “e rc h a p t e 砖a b o u ta t t r i b u t er e d u c 【i o n “g o f i t h m s t h es i 弘i f i c a n c co fa n r i b i i t ei su s e d 鹅t h eh e u r i s t i ci n f o 姗a t i o n ，硒dt h e c o r ea u 劢u t c 勰t h es t a r to ft h c 蛔6 t h m ，t h 哪，t h es i z eo fs e a r c 】晡n gs p a c cc a n b yr e d u c e db ya d d i n gh e u 6 s t i ci n f o 珊a t i o nt 0t h ea l g 嘶t h m t h i s 蛔f i t h m c o n v e r t st h cl o 舀co p e r a t i o nt ot h e 姆b r a i co p e r a t i o n , i tc a ns i n l p l i f yt h e o p e r a t i o n 柚de n h a n c ct h ee 伍d e n c yo fs e e k i n gt h er e d u d i i ns o m ee x t e n t l 舔ti nt h i sp a p e rd 够s 衄t h cs i t eo fr e m o t ei 鹪t n l c t i i sc v a l u a t e db ya n r i b m e 砖d l l d i 姆f i t h m ，柚db y 让a l y z i n g 也i ti sc o n d u d c d t h a tt h ea l 9 0 6 t h mc a n o b t a i nb e h e ri c d u c t i o na n dc v e nc a ng e tt h c o p t i m a la t t f i b u t e r c d u c t i o n m e t j m 懿 k e y w o r d s ：d a t am i n i n 岛r o u g l is c t , a t t r i b u t er c d u c t i ，d i s c e r n j b i l i t ym a t r i x 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用己在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：“年厂月1 日 哈尔滨工程大学硕士学位论文 第1 章绪论 如何有效地实现对数据的分析和处理，如何快速地从数据中提取出隐 含的知识，长期以来一直是人工智能领域的研究热点。机器学习作为人工 智能领域的关键技术之一，己经在专家系统、语言处理、故障诊断和智能 控制等众多领域“1 获得了长足的进展，并日益体现出其应用价值和发展前 景。近年来，随着数据库技术的发展和数据库管理系统的广泛应用，人类 获取和处理的数据量急剧增加。在这种背景下，一些新的智能数据处理技 术，如数据库知识发现( k d d ) ，数据挖掘( d a t am i n i n g ) 等应运而生，并 在理论和应用上都有一定的成果。因此，知识发现和数据挖掘是应用需求 推动下跨学科发展的产物嘲。 1 1 课题研究的意义与背景 在8 0 年代，人们就估算全世界的数据总量2 0 个月就会翻一番，进入 9 0 年代后，数据量会增长的更快。近些年来，商务贸易电子化、企业和政 府事务电子化的迅速普及都产生了大规模的数据，同时日益增长的科学计 算和大规模的工业生产过程也提供了海量数据。在这样的增长速度下，“信 息爆炸”和“数据过剩”( d a t ag l u t ) 成为当今数字化社会面临的巨大挑战 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积 累的数据越来越多，而大量激增的数据背后隐藏着许多重要的信息，因此 人们希望能够对其进行更高层次的分析，以便能够更好地利用这些数据。 目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但是 无法发现数据中存在的关系和规则，无法根据现有数据库中的数据预测未 来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段方法，导致了“数据 哈尔滨工程大学硕士学位论文 爆炸但知识贫乏”的现象瑚。 数据挖掘和知识发现正是在这种情况下产生发展的一种新型数据分析 技术。1 9 8 9 年8 月，在第1 1 届国际人工智能联合会议的专题研讨会上，首 次提出基于数据库的知识发现技术。到了1 9 9 5 年，在美国计算机年会 ( c a c m ) 上，提出了数据挖掘的概念。 数据挖掘是指从数据库的大量数据中提取隐含的、先前未知的并有潜 在价值的信息和知识的过程m 。在这个定义中，要求数据源应该是大量的、 真实的、含有噪音的；所发现的信息和知识是潜在的并隐藏在大量数据背 后的，是用户感兴趣的、可理解的、可运用的知识。 在传统的数据研究上，很大一部分的数据分析与处理的工作由具有专 业知识的专家利用简单的数据表示工具( 例如：电子表格、电子图表等) 和分析方法( 例如：统计等) 来完成，这种做法费时费力，而且效率较低， 只能获彳导这些数据的表层信息，丽不能获得数据属性的内在关系和隐含信 息，即不能获得人们比较感兴趣的知识，因此研究高效智能的知识获取方 法朔具有很大的现实意义。 在知识工程研究中，一直存在着信息的含糊性嘲等问题，含糊性有三种， 术语的模糊性，如大小；数据的不确定性，如由噪声引起的；知识自身的 不确定性，如规则前后间的依赖关系并不是完全可靠的。人工智能的基础 理论之经典逻辑不足以解决这些不确定性问题。 粗糙集理论( r o u g hs e t ) 忉正是在这种情况下逐步建立并发展起来的。 1 9 9 1 年，p a w l a k 发表了专著 r o u g hs e t ：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 g a b o u t d a t a ) ，奠定了粗糙集理论的基础，从而掀起了粗糙集的研究高潮。1 9 9 2 年，在波兰召开了第一届国际粗糙集研讨会，在以后的各届的研讨会上， 都有力地推动了粗糙集理论的发展。 粗糙集理论与其他处理不确定性问题的最显著的区别是它无需提供问 2 哈尔滨工程大学硕士学位论文 题所需处理的数据集合之外的任何先验信息，如统计中要求的先验概率和 模糊集中要求的隶属度；算法简单、易于操作等。近几年来，粗糙集合理 论已应用于机器学习、知识发现、决策支持与分析、专家系统、智能控制、 模式识别等领域。 属性约简是粗糙集理论的核心内容之一川，众所周知，知识库中的知识 ( 属性) 并不是同等重要的，甚至其中某些知识是冗余的。特别是当数据 是随机采集时，其冗余性更为普遍。冗余知识的存在，一方面是对资源( 存 储空间) 的浪费；另一方面，干扰人们作出正确而简洁的决策。 所谓属性约简。就是在保持数据库分类或决策能力不变的条件下，删 除其中不相关或不重要的知识嗍。 对于一个知识库，其对应的决策表可能存在多个属性约简。因为知识 约简的目的是导出关于决策表的决策规则，约简中属性的多少直接影响着 决策规则的繁简。 因此，人们期望找到具有最少属性的约简，即最小约简。然而，遗憾 的是w o n g s i c m 和z i a r k o w 已经证明了找出一个决策表的最小约简是 n p h a r d 问题嗍。导致属性约简问题是n p h a r d 问题的主要原因是属性组合 爆炸问题，尤其是当数据库规模较大时问题尤为突出，在人工智能中，解 决这类问题的一般方法是采用启发式搜索，通过对算法中融入启发性知识， 缩小问题求解的搜索空间嗍。寻找高效的属性约简算法仍然是人们关心的热 门研究问题之一。 属性约简一般包括属性( 个数的) 约简和属性值的约简，前者同时可 以缩减样本空间中的个体数量，而粗糙集理论中规则抽取的过程正是属性 值约简的过程。这两个过程是互相联系的，属性约简是属性值约简的前提 和基础，而后者则是前者的必然趋势。 一般来说，粗糙集理论只能处理离散属性，所以有人也把属性约简过 3 哈尔滨工程大学硕士学位论文 程归类到符号( s y m b o l i c ) 机器学习中”。由于粗糙集理论可以支持知识发 现的多个步骤，如数据预处理，数据缩减、规则生成等，因此基于粗糙集 理论的k d d 系统被认为具有独特的优势。 1 2 粗糙集理论的发展及国内外现状综述 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年首先提出的一个分析数据 的数学理论，在分类的意义下，这个理论定义了模糊性和不确定性的概念。 在该理论刚刚问世的几年，由于理论还不成熟，因而并未受到国际计算机 学界的重视，当时主要在波兰等几个东欧国家进行研究。直至八十年代末， 粗糙集理论才引起了世界各国学者的注意l l 习。自1 9 9 2 年在波兰举行了r o u g h s e t 理论的第一届国际研讨会以来，每年一度的国际r o u g hs e t 理论研讨会 定期在世界各国召开。可以这样说，目前r o u g hs e t 理论己经成为国际上人 工智能研究的热点。 目前，国外对粗糙集理论的研究和应用发展的都比较快，尤其是1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其相关方法1 1 4 比较研究的论文集的 出版，推动了国际上对粗糙集理论和方法的深入研究。1 9 9 2 年，在波兰召 开了第一届国际粗糙集研讨会，这次会议着重讨论了集合近似定义的基本 思想及其应用，其中粗糙集环境下机器学习的基础研究是这次会议的四个 专题之一但是，参加这次会议的研究者较少，范围也不太广泛。1 9 9 3 年 在加拿大召开了第二届国际粗糙集与知识发现研讨会，这次会议极大地推 动了国际上对粗糙集理论与应用的研究，其主题是粗糙集、f u z z y 集与知识 发现。1 9 9 4 年在美国召开了第三届国际粗糙集与软件研讨会，这次会议广 泛探讨了粗糙集与模糊逻辑、神经网络、进化论等融合问题。 粗糙集理论及应用的几位主要倡导者，在1 9 9 5 年第1 1 期a c m 通讯上 撰文，概括性地介绍了目前人工智能应用新技术之一的粗糙集理论的基本 4 哈尔滨工程大学硕士学位论文 概念，及其在知识获取和机器学习、决策分析、知识发现等领域的具体研 究项目和进展。尤其是1 9 9 5 年召开的第4 届模糊理论与技术国际研讨会， 在这次会议上，针对粗糙集与模糊集合的基本观点与相互关系展开了激烈 的讨论，较大地促进了粗糙集的研究。1 9 9 6 年在日本东京召开了第5 届国 际粗糙集研讨会，这是第一次在亚洲地区召开的范围广泛的粗糙集研讨会。 1 9 9 9 年1 1 月在日本、2 0 0 0 年1 0 月在加拿大又召开了第1 届和第2 届“粗 糙集和计算的当前趋势”学术会议，来自波兰、美国、加拿大、日本、挪 威、俄罗斯、乌克兰和印度等国家的研究人员参加了会议，会议阐述了当 前粗糙集、模糊集的研究现状和发展趋势，指出将着重在软计算、数据库、 人工智能和近似推理等理论和应用方面发展。目前，许多关于人工智能、 模糊理论、信息管理与知识发现等国际会议上经常可以看到涉及粗糙集的 论文。 在国内，对粗糙集理论的研究和应用还处在起步阶段。1 9 9 6 年王珏、 苗夺谦等在模式识别与人工智能发表了关于粗糙集理论与应用论述， 介绍了粗糙集理论的主要原理、基本算法和在知识发现、决策分析等方面 的应用，开始了国内粗糙集理论的研究和应用“”；1 9 9 8 年曾黄麟编写的粗 集理论与应用是国内第一本关于粗糙集理论的专著“日。常犁云等对属性值 约简算法做出了改进，提高了样本分类的正确率m ；韩祯祥，张琦等将粗糙 集方法应用于电力系统故障诊断( 警报处理) ，效果良好“”。对租糙集理论 研究得比较深入和透彻的是苗夺谦、王珏等，他们不但提出了基于粗糙集 的多变量决策树的构造方法旧，而且还把粗糙集中的概念和运算从代数角度 提升到信息角度，对人们深刻理解粗糙集理论的本质和寻找高效的知识约 简算法奠定了基础。 目前，国内对粗糙集理论的研究和应用还处于探索阶段，没有成形的 实验系统。但是我国在这个领域的发展速度很快，目前中科院、清华大学 5 哈尔滨工程大学硕士学位论文 等研究所和高校己经加入到这个领域中，并取得了一定的成果。相比之下， 国外己建立了不少的数据库领域知识发现( k d d ) 系统，它们一般都由数 据预处理、基于粗糙集或其扩展理论的数据约简、决策算法等部分组成。 其大概思想是先进行必要的数据预处理，为数据约简做准备，并在此基础 上根据值约简等减少属性和个体数目，最终提取规则并将之应用于新对象 的分类。比较有代表性的有美国k a n s a s 大学开发的基于粗糙集的实例学习 系统( l e r s ) ，r o u g hs e td a t ae x p l o r e r ( r o s e ) ，r e g i n a 大学利用粗糙集 理论开发的知识发现系统k d d r ，该系统目前被广泛的应用于医疗诊断、 电信业等领域硼，还有美国k a n s a s 大学开发的l e r s ( l e a r n i n gf r o m e x a m p l e sb a s e do nr s ) 系统，该系统被应用于医疗诊断、社区规划、全球 气象等研究方面酬。 国外目前在粗糙集领域的研究主要集中在约简的优化算法、粗糙集理 论和模糊理论，粗糙集理论同神经网络理论等其他人工智能技术的结合、 粗糙逻辑等课题上。本文中，对于粗糙集的约简算法的研究正是当前粗糙 集领域中一个非常重要的课题。 1 3 论文的主要内容 本论文的主要内容是基于粗糙集理论的属性约简及值约简策略。 在本文的第二章中，简单地说明了数据库中的知识发现和数据挖掘的 基本概念、当前常用的数据挖掘技术和工具、数据挖掘的步骤，基于粗糙 集的数据挖掘模型。 在本文的第三章中，主要阐述了粗糙集的基本理论，这其中包括：集 合的基础知识、粗糙集的概念、知识与知识库的定义、上近似和下近似、 约简和核、决策表等，并举例说明的相对约简的应用，为以后打下理论基 础。 6 哈尔滨工程大学硕士学位论文 第四章的属性约简策略是本文的重点，主要是基于差别矩阵的属性约 简方法。首先提到的是基于差别矩阵的基本约简算法，通过差别矩阵，利 用差别函数得到信息系统的全部的约简，当然基于差别矩阵的基本约简算 法缺乏通用性，当问题规模较大时，变得不易操作或不可操作。因此，引 入启发式知识，用代数运算代替复杂的逻辑运算，提高了计算速度和约简 的效率。改进后的算法主要包括基于差别矩阵属性频度的约简与利用依赖 度的约简，在第五章的实验中，主要应用依赖度进行属性约简；接下来的 值约简则提取出决策规则，从而得到最小约简。 第五章主要是利用第四章的算法进行远程教学网站中的课程等级的评 价，对其中的各种属性进行约简，最终得到决策的规则。 7 哈尔滨工程大学硕士学位论文 第2 章数据挖掘与粗糙集理论 首先，讨论数据库中的知识发现、数据挖掘和粗糙集理论的一些基本 概念，然后讨论它们之间的关系。 2 1 数据库中的知识发现 数据库中的知识发现k d 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 s ) 这个术 语在1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专 题讨论会上首次出现。实际上，数据库中的知识发现是一门交叉学科，涉 及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、 高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在 信息管理、过程控制、科学研究、决策支持等许多方面。 k d d 是近年来随着人工智能和数据库技术的发展而出现的一门新兴技 术，它是从大量数据中提取出可信的、新颖的、有效的并能被人理解的知 识模式的高级处理过程阎。它主要采用机器学习算法或统计方法进行知识学 习，一般将k d d 中进行知识学习的阶段称为数据挖掘d m ( d a t am i n i n g ) 。 严格地讲，数据挖掘是为寻找未知的知识模式或信息趋势而在大量具体数 据中进行搜索的过程。可见，d m 是k d d 实施过程的一个阶段。较为典型 的由u f a y y a d 等给出的k d d 处理过程模型如图2 1 所示。 图2 1k d d 处理过程示意图 8 哈尔滨工程大学硕士学位论文 在图2 1 的处理过程模型中，k d d 的处理过程共分为如下几个处理阶 段： ( 1 ) 数据准备 数据准备又可分为两个子步骤：数据采集选择及数据预处理。数据选 取的目的是确定发现任务的操作对象，即目标数据，它是根据用户需要从 原始数据中抽取的一组数据。预处理一般包括除去噪声、推导计算缺值数 据、消除重复数据、完成数据类型转换，消减数据维数或降维。 ( 2 ) 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目标是什么，如数据总结、分 类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决 定使用什么样的挖掘算法。 同样的任务可以用不同的挖掘算法来实现，选择实现算法有两个考虑 因素：一是不同的数据有不同的特点，需要用与之相关的算法来实现；二 是用户与实际运行的要求，有的用户可能希望获取描述型的、容易理解的 知识，而有的用户或系统的目的是获取预测准备尽可能高的预测型知识。 完成了上述准备工作以后，就可以实施数据挖掘工作了。需要指出的 是，尽管数据挖掘算法是数据挖掘的核心，也是目前研究人员主要努力的 方向，但要获得好的挖掘结果，必须对各种挖掘算法的要求或前提假设有 充分的理解。 ( 3 ) 结果解释和评估 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗 余或无关的模式，这时需要将其剔除；也可能有的模式不满足用户的需求， 这时需要整个发现过程退回到发现之前，如重新选取数据、采用新的数据 变换方法、设定新的数据挖掘参数值，甚至换一种算法。另外，由于k d d 始终是面向人类用户的，因此可能要对发现的模式进行可视化，或者把结 9 哈尔滨工程大学硕士学位论文 果转换为用户易懂的另一种表示，如把分类决策树转换为i f t h e n 规则。 由图2 1 可见，数据挖掘只是k d d 中的一个非常重要的处理步骤。人 们进行关于k d d 的研究是为了将研究成果应用于实际数据处理中，为科学 决策提供支持。正因为这样，目前所进行的关于k d d 的研究，大多着眼于 对数据挖掘的研究。所以许多时候，人们将k d d 与d m 混同为一个概念， 往往不加区分地使用。但一般来说，在工程应用领域多称数据挖掘，而在 研究领域人们则多称数据库中的知识发现l 。 2 2 数据挖掘简介 2 2 1 数据挖掘模式类型 常见的数据挖掘”模式有以下几类： ( 1 ) 关联( a s s o c i a t i o n s ) 模式 表示数据项之间的关联规则。例如：“购买尿布的顾客中有三分之一同 时购买啤酒”。 ( 2 ) 聚类( c l f i s t e r i n g ) 模式 将数据库中记录划分成不同的组，同组的记录具有相似的属性。组问 记录差别应尽可能大，组内记录差别应尽可能小。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 模式 它是由一个分类函数( 分类器) 把数据集中的数据项映射到某个给定 类上。 ( 4 ) 序列( s e q u e n t i a l ) 模式 把数据之间的关联性与时间联系起来。为了发现序列模式，不仅需要 知道事件是否发生，而且需要确定事件发生的时间。 例如，在购买彩电的顾客中，6 0 的顾客会在3 个月内购买影碟机。 l o 哈尔滨工程大学硕士学位论文 ( 5 ) 时间序列( t i m es e q u e n t i a l ) 模式 可根据数据随时问变化的趋势预测将来的值。 2 2 2 数据挖掘方法一分类发现 根据数据挖掘模式，比较重要的数据挖掘方法有分类发现、聚类和关 联规则等等。 分类在数据挖掘中是一项非常重要的任务，在商业上应用最多。分类 的目的是找出一个分类函数或分类模型( t g 常常称作分类器) ，该函数或模 型能把数据库中的数据项映射到给定类别中的某一个。分类可用于预测， 预测的目的是利用历史数据纪录自动推导出对给定数据的趋势描述，从而 能对未来数据进行预测。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组 数据库记录或元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向量，除此之外，训练样本还有一个类别标记。一个具体的 样本形式可为：( v l ，v 2 ，v n ；c ) ，其中v i 表示字段值，c 表示类别。 分类器的构造方法有统计方法、机器学习方法、神经网络方法、粗糙 集方法等等。 ( 1 ) 统计方法 包括贝叶斯法和非参数法( 近邻学习或基于事例的学习) ，对应的知识 表示则为判别函数和原型事例。 ( 2 ) 机器学习方法 包括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后 者则一般表示为产生式规则。 ( 3 ) 神经网络方法 主要是b p 算法，它的模型表示是前向反馈神经网络模型( 由代表神经 1 1 哈尔滨工程大学硕士学位论文 元的节点和代表联接权值的边所组成的一种体系结构) ，该算法本质上是一 种非线性判别函数。 ( 4 ) 粗糙集( r o u g hs e t ) 方法 它的知识表示是产生式规则。 2 3 粗糙集理论的特点 粗糙集理论是一种应用于分类发现来进行数据挖掘的理论，它的知识 表示是产生式规则。若输入样本的形式记为：( v 1 ，v 2 ，v a ；c ) ，则v i 是条件属性值，c 是决策属性值。 粗糙集理论和数据挖掘关系密切，它能为数据挖掘提供新的方法和工 具，且具有以下特点： ( 1 ) 数据挖掘研究的对象多为关系型数据库。关系表可以看作为粗糙 集理论中的决策表，这给粗糙集导出的方法的应用带来极大的方便。 ( 2 ) 现实世界中的规则有确定性的，也有不确定性的。从数据库中发 现不确定性的知识，为租糙集导出的方法提供了用武之地。 ( 3 ) 从数据中发现异常，排除知识发现过程中的噪声干扰也是粗糙集 导出的方法的特长。 ( 4 ) 运用粗糙集导出的的知识发现算法有利于并行执行，可以极大地 提高发现效率。对于大规模数据库中的知识发现来说，正是求之不得的。 ( 5 ) 数据挖掘中采用的其它技术，如神经网络的方法，不能自动地选 择合适的属性集，而利用粗糙集导出的方法进行预处理，去掉多余属性， 可提高发现效率，降低错误率。 ( 6 ) 粗糙集方法比模糊集方法或神经网络方法在得到的决策规则和推 理过程更易于被证实和检测。 随着数据挖掘的兴起，粗糙集理论受到数据挖掘研究者的重视。 哈尔滨工程大学硕士学位论文 2 4 基于粗糙集理论的数据挖掘模型 结合图2 1 知识发现的处理过程和基于粗糙集理论数据分析的特点，给 出基于粗糙集理论的数据挖掘的处理过程模型如图2 2 所示。 图2 2 基于粗糙集理论的数据挖掘的处理过程模型 基于粗糙集理论的数据挖掘的处理对象是决策表，从决策表的数据中 提取规则进行预测和分析大致包括以下几个步骤：数据预处理、知识约简 和知识获取等。 事实上，在图2 1 中的数据准备阶段并不是基于粗糙集理论的鲫，在基 于粗糙集理论的模型中称为数据获取和数据选择与清理，功能和k d d 的数 据准备阶段基本相似如：数据获取就必须了解相关领域的有关情况，熟 悉有关的背景知识等；比如，在网络入侵检测应用中，如何获得各种网络 哈尔滨工程大学硕士学位论文 相关的数据就和网络知识密切相关。这里的数据选择与清理是指对数据的 一些基本操作，目的是形成适合粗糙集方法处理的信息系统( 决策表) 。 如果经过数据选择与清理得到的决策表是一个完整的并且离散的信息 表，就可以进入属性约简阶段，否则将进行数据预处理。数据预处理又包 括两个阶段( 根据具体情况选择相应的阶段) ：数据的补齐和数据的离散化。 ( 1 ) 数据的补齐 数据的补认齐也叫不完整数据的完整化运算。现实信息表中经常由于 各种原因，如数据遗失，记录不全，导致数据不完备，给发现、评估和解 释一些重要的模式带来了困难。 目前的数据补齐方法有c o m b i n a t o r i a l c o m p l e t e r 算法，m e a n c o m p l e t e r 算法等嗍。 ( 2 ) 数据的离散化 由于粗糙集理论对信息表进行处理的时候都考虑的是离散值的情况， 所有的连续值都必须经过离散化处理。离散化处理的方法很多嗍，既可以 采用统计的方法，如等距离、等频率划分方法，也可采用等价类划分，即 离散化处理过程不改变系统的等价类划分。 ( 3 ) 知识约简 知识约简( 也称属性约简a t t r i b u t er e d u c t i o n 或特征提取f e a t u r e s e l e c t i o n ) 是粗糙集理论的核心内容之一。由于知识库中的某些知识是冗余 的，不必要知识的存在，一方面是浪费资源；另一方面，干扰人们作出正 确而简洁的决策。知识约简，就是在保持知识库的分类或决策能力不变的 情况下，删除其中不相关或不重要的知识目前的算法有基于逻辑运算的 属性约简算法闭、基于互信息的启发式算法阳等。 ( 4 ) 知识获取 知识获取也称值约简( v a l u er e d u c t i o n ) 。对信息系统进行知识约简后 1 4 哈尔滨工程大学硕士学位论文 可以简化信息系统的复杂程度，那么通过知识约简之后的信息系统是否可 以作为最终的规则知识? 很明显，知识约简后的信息表，表达每条记录的 所有条件属性值并不都是必须的。值约简过程就是对表中记录逐条进行考 察，删除所有不影响规则表达的冗余条件属性值。目前，在运用粗糙集理 论进行值约简方面已经有不少方法，其中通过分析信息系统中决策属性值 问的不可区分关系是最直接的方法。此外，还有采用各种附加信息的启发 式算法。 ( 5 ) 预测和分析结果 接下来就可对测试样本集进行分析测试。在对挖掘得到的知识进行评 测后，根据结果可以决定是否重新进行某些处理阶段，在处理的任意阶段 都可以返回以前的阶段进行再处理，以得到满意的结果。 从上述分析可见，基于粗糙集理论的数据挖掘模式是一种分类模式。 2 5 本章小结 严格地讲，数据挖掘只是k d d 的一个重要阶段。目前所进行的关于 k d d 的研究，大多着眼于对数据挖掘的研究。许多时候，人们将k d d 与 d m 混同为一个概念，往往不加区分地使用。而粗糙集理论因其处理不完备 和不确定性问题的独特优点在近年来得到数据挖掘工作者们的广泛关注， 应用成果显著。在本章，简单地介绍了一些有关粗糙集理论的基本概念， 并总结了基于粗糙集理论的数据挖掘模型。 哈尔滨工程大学硕士学位论文 第3 章粗糙集理论基础知识 粗糙集理论是经典集合理论的扩展，因此在讨论粗糙集理论之前，先 简单地看看集合论方面的知识。 3 1 集合论基础 集合是现代数学和逻辑学的基本概念之一。集合论对现代数学和逻辑 学的发展产生了巨大的影响，今天它已成为数学和逻辑学的一种基础理论。 下面看看集合论的一些基本定义： 集合：按照某一目的或特点，将所有研究的对象组合在一起，就叫集 合。集合中的每一个对象称为集合的元素。 论域：在讨论具有某种共同性质的对象所组成的集合时，把具有这种 共同性质的一切元素组成的集合，叫作论域。 有序对：设有集合x 和y ，a e x ，b e y ，称( a ，b ) 为有序对。有序 对是和顺序有关的，( a ，b ) 和( b ，a ) 是两个不同的有序对。当x 和y 是 同一个集合时，有序对中的两个元素来自与同一个集合。 笛卡儿乘积：由集合x 和y 的有序对作为元素所构成的集合称为集合 x 与y 的笛卡儿乘积。例如由集合x = 1 1 ，2 ，3 ，4 ，5 ) 和集合y = a ，b ， c ) 的笛卡尔乘积为 ( 1 ，a ) ，( 1 ，b ) ，( 1 ，c ) ，( 2 ，a ) ，( 2 ，b ) ，( 2 ，c ) ， ( 3 ，a ) ，( 3 ，b ) ，( 3 ，c ) ，( 4 ，a ) ，( 4 ，b ) ，( 4 ，c ) ，( 5 ，a ) ，( 5 ，b ) ， ( 5 ，c ) ) 。 关系：集合x 与y 的笛卡儿乘积的任意一个子集，就是x 到y 上 的一个关系r 。例如集合x = 1 ，2 ，3 ，4 ，5 1 ，集合y = a ，b ，c ) ，它 们的笛卡尔乘积的一个子集 ( 2 ，a ) ，( 2 ，b ) ，( 3 ，c ) ，( 4 ，a ) ) 便是x 到 哈尔滨工程大学硕士学位论文 y 上的一个关系r 。当x 和y 是同一个集合时，就称为x 上的一个关系r 。 关系具有下面的性质： ( 1 ) 自反性：如果对任意a e x ，有：( a ，a ) r ，则称r 满足自反 性。 ( 2 ) 对称性：如果对任意a e x ，b x ，若有( a ，b ) e r ，则必有 ( b ，a ) e r ，那么就称r 满足对称性。 ( 3 ) 传递性：如果对任意a e x ，b x ，c e x ，若有( a ，b ) e r ， 并且( b ，c ) e r ，则必有( a ，c ) e r ，那么就称r 满足传递性。 根据这些性质，可以得到两个比较重要的概念。 ( 1 ) 等价关系：当关系r 满足自反性、对称性、和传递性时，关系r 就为等价关系。 ( 2 ) 等价类：所有与元素a 具有等价关系的元素构成的集合，称为a 所生成的等价类。记为 a i r 。b p a l x = x l x x ，( a ，x ) r ) 。 集合x 的等价关系r 有下面的性质： 对于所有的x ，y e x ，或者【x 】r = 【y 】r 或者 x l r n 【y l r = o ，u 【x r = u 例：给定一个玩具积木的集合u = ( x 1 ，白) ，( x 2 ，蓝) ，( x 3 ，红) ， ( x 4 ，蓝) ，( x 5 ，黄) ，( x 6 ，黄) ，( x 7 ，红) ，( x s ，黄) ，( x 9 ，白) ，( x l o ， 青) ) ，在这些积木中，具有“相同颜色”的等价类如下：红： ( x 3 ，红) ， ( x 7 ，红) ；黄： ( x 5 ，黄) ，( x 6 ，黄) ，( 】【8 ，黄) ；青： ( x 1 0 ，青) ； 蓝： ( x 2 ，蓝) ，( x 4 ，蓝) ；白： ( x l ，白) ，( x 9 ，白) ) 3 2 粗糙集理论的一般知识 3 2 1 知识与知识库 在粗糙集理论中，“知识”被认为一种将现实或抽象的对象进行分类的 1 7 哈尔滨工程大学硕士学位论文 能力川。如在远古时代，人们为了生存必须能分辨出什么可以食用，什么不 可以食用；医生给病人诊断，必须辨别出患者得的是哪一种病。这些根据 事物的特征差别将其分门别类的能力均可以看作是某种“知识”。 设u 一曲是研究对象组成的有限集合，称为论域。任何子集x _ u ，称 为u 中的一个子集或范畴。u 中的任意概念族称为关于u 的抽象知识，简 称知识。本文主要是对在u 上能形成划分的那些知识感兴趣。一个划分f 定 义为：z = x l ，x 2 ，x n ，x i c _ u ，x i - 妒，x i nx j = 妒，对于i j ，i ， j = 1 ，2 ，n ；u ) ( i - - u 知识库：u 上酌一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 一个知识库就是一个关系系统k = ( u ，r ) ，其中u 是非空有限集，r 为 u 上等价关系的一个族集。 u r 表示r 的所有等价类( 或者u 上的分类构成的集合，【碉r 表示的 是包含元素x e u 的r 等价类。 等价关系；若p r ，且p 一面，则p 中所有等价关系的交集也是一个 等价关系，称为p 上的不可分辨关系，记为i n d ( p ) ，且有【) qi a d ( p ) f f in 【z k j f 这样，u i n d ( p ) ( 即等价关系i n d ( p ) 的所有等价类) 表示与等价关 系族p 相关的知识，称为k 中关于u 的p 基本知识( p 基本集) 。 为简单起见，用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的 基本概念或基本范畴。 特别地，如果q e r ，则称q 为k 中关于u 的q 初等知识，q 的等价 类为知识r 的q 初等概念或q 初等范畴。 同样，当k = ( u ，r ) 为一个知识库，i n d ( k ) 定义为k 中所有等价 关系的族。 现举例3 1 1 说明，给定一玩具积木的集合u = x l ，x 2 ，x 3 ，x 4 ，x 5 ， 1 8 哈尔滨工程大学硕士学位论文 ) ( 6 ，x 7 ，) ( 8 。现在这些积木有不同的颜色( 红、黄、蓝) ，形状( 方、 圆、三角) ，体积( 小，大) 。 因此，这些积木就可以用颜色、形状、体积这些知识来描述。 例如一块积木可以是蓝色、方而大的，或者黄色、圆而小的。 现在根据某一属性描述这些积木的情况，就可以按颜色、形状、体积 分类。 按颜色分类，红：x l ，x 3 ，x t ：黄：x 5 ，x 6 ，x s ；蓝：x 2 ，x 4 ： 按形状分类，方：x 2 ，x 6 ：圆：x l ，x s ：三角：x 3 ，x 4 ，x 7 ，x s ： 按大小分类，小：x l ，x 3 ，x 4 ，x 5 ，) ( 6 ；大：x 2 ，x 7 ，x s 。 换种说法，定义三个等价关系( 即属性) ：颜色r i ，形状r 2 和大小r 3 ， 通过这些等价关系，可以得到下面三个等价类： 4 u r 1 = “x 1 ，x 3 ，4x 7 ) ， x 5 ，) ( 6 ，x s ) ， x 2 ，x 4 m u r 2 = x 2 ，x 6 ， x l ，x 5 ) ， x 3 ，) ( 4 ，x 7 ，) ( s ) ； u r 3 = x t ，x 3 ，x 4 ，x 5 ，x 6 ， x 2 ，x 7 ，x s ) 可以看出，这些等价类是由知识库k = ( u ， r l ，r 2 ，r 3 ) 中的初等 概念( 初等范畴) 构成的。 基本范畴是初等范畴的交集构成的，例如下列集合： x l ，x 3 ，x 7 n x 3 ，x 4 ，x 7 ，x s = x 3 ，x 7 ； x 2 ，) 【6 n x 2 ，x 4 - - - - x 2 ) 。 。 它们分别为 r 1 ，r 2 的基本范畴，即：红色三角形，蓝色方形。 下列集合： x l , x 3 ，x 7 n x 3 ，x 4 ，x 7 ，x g n x 2 ，x 7 ，x s = x 7 ) ； x 2 ，) ( 6 ) n x 2 ，x 4 ) n x 2 ，x 7 ，x s ) = x 2 ) 。 它们分别为 r i ，r 2 ，r 3 ) 的基本范畴，即：红色大三角形，蓝色大方 形。 哈尔滨工程大学硕士学位论文 3 2 2 近似与粗糙集 令x u ，r 是u 上的一个等价关系。当x 能表达成某些r 基本范畴 的并时，称x 是r 可定义的；否则称x 是r 不可定义的。 r 可定义集是论域的子集，它可以在知识库中精确的定义，而r 不可 定义集不能在这个知识库中定义。r 可定义集也称为r 精确集，而r 不可 定义集也称为r 非精确集或r 粗糙集。 对于粗糙集可以近似地定义，使用两个精确集，即粗糙集的上近似 ( u p p e ra p p r o x i m a t i o n ) 集和下近似( 1 0 w e ra p p r o x i m a t i o n ) 来描述。 下近似集和上近似集：设集合x u ，r _ i n d ( k ) ，定义两个子集： 乡。岬u r i y 石( 3 - 1 ) 麟- u y u r i y n 工一以 分别称它们为x 的r 下近似集和r 上近似集。集合b n a ( x ) = 尼r 一星r 称为x 的r 边界域；p o s r ( x ) = 笪称为x 的r 正域；n e gr ( x ) = u 一肼称为x 的r 负域。 麟或p o s r ( x ) 是由那些知识r 判断肯定属于x 的u 中元素组成的 集合；r x 是由那些知识r 判断可能属于x 的u 中元素组成的集合；b n r ( x ) 是由那些知识r 既不能判断肯定属于x 又不能判断肯定属于( 即 u x ) 的u 中元素组成的集合；n e g a ( x ) 由那些知识r 判断肯定不属 于x 的u 中元素组成的集合。 下面的性质是显而易见的： ( 1 ) x 为r 可定义集当且仅当解= 丛； ( 2 ) x 为r 粗糙集当且仅当r x - 丛。 哈尔滨工程大学硕士学位论文 也可以将鱼描述为x 中的最大可定义集，将r x 描述为含有x 的最 小可定义集。 根据集合x 的上近似和下近似的不同情况，可以定义四种不同的重要 的粗糙集： r 粗糙可定义：如果墼妒且心：l j ，则称x 为r 粗糙可定义。 r 内不可定义：如果点= 妒且r x u ，则称x 为r 内不可定义。 r 外不可定义：如果r x 希且尼y = u ，则称x 为r 外不可定义。 r 全不可定义：如果查= 妒且尼r = u ，则称x 为r 全不可定义。 这种划分的直观意义是这样的： 如果集合x 为r 粗糙可定义，则意味着可以确定u 中的某些元素属于 x 或。 如果集合x 为r 内不可定义，则意味着可以确定u 中的某些元素是否 属于x ，但不能确定u 中的任一元素是否属于x 。 如果集合x 为r 外不可定义，则意味着可以确定u 中的某些元素是否 属于x ，但不能确定u 中的任一元素是否属于嵌。 如果集合x 为r 全不可定义，则意味着不能确定u 中的任一元素是否 属于x 或嵌。 粗糙集理论与传统的集合论有着相似之处，但是它们的出发点完全不 同。传统集合论认为，一个集合完全由其元素决定，一个元素要么属于这 个集合，要么不属于这个集合，即它的隶属函数儿( x ) o 册。模糊集合对 此做了拓广，它给成员赋予一个隶属度，即以f ) 【0 朋，使得模糊集合能 够处理一定的模糊和不确定数据，但其隶属度往往具有