异常数据挖掘研究毕业答辩论文样本.doc

异常数据挖掘研究毕业答辩论文 毕 业 设 计（论文）中文题目异常数据挖掘研究英文题目Research on outlier data mining 系 别：计算机科学与技术系专业年级：计算机科学与技术09级姓 名：杜海丰学 号：指导教师：陈玉明职 称：讲师2011 年 5 月 20 日毕业设计（论文）诚信声明书本人郑重声明：在毕业设计（论文）工作中严格遵守学校有关规定，恪守学术规范；我所提交的毕业设计（论文）是本人在 指导教师的指导下独立研究、撰写的成果，设计（论文）中所引用他人的文字、研究成果，均已在设计（论文）中加以说明；在本人的毕业设计（论文）中未剽窃、抄袭他人的学术观点、思想和成果，未篡改实验数据。本设计（论文）和资料若有不实之处，本人愿承担一切相关责任。学生签名： 年 月 日摘 要粗糙集理论，它是一种分析处理数据的理论，在20世纪80年代由波兰科学家Pawlak建立。一开始由于语言交流上的问题，建立该理论的时候只有一些东欧学者会研究和应用它，后来随着该理论的发展才慢慢受到全球上知名数学学者和计算机学者的重视。知识粒度的基本思想在许多领域都有体现，如粗糙集、数据库、聚类分析、模糊集、证据理论、数据挖掘和机器学习等。，知识粒度获得了人们越来越多的关注。经过多年的发展，知识粒度已在知识发现、数据挖掘、软计算中扮演越来越重要的角色。在本论文中，本人引入知识粒度这一个方法作为一个统一的框架去理解和实施异常点挖掘。此外，还给出了基于知识粒度的异常点挖掘算法。该算法结合粗糙集与数据挖掘技术研究异常数据。理论研究和实验结果表明，知识粒度方法对评定异常是有效且适用的。关键词：粗糙集；异常检测；数据挖掘；知识粒度ABSTRACTRough set theory, it is a theory of data analysis and processing, 80 in the 20th century by Polish scientists Pawlak established. The beginning of the problems due to language exchanges, the establishment of the theory, when only a few Eastern European scholars would study and apply it, and later with the development of the theory slowly by the global computer on the well-known scholars and scholars in mathematics seriously.The basic idea of knowledge granulation in many areas, such as rough sets, database, clustering analysis, fuzzy sets, evidence theory, data mining and machine the first time in the world and discussed after the knowledge granulation of fuzzy, the knowledge granulation obtained people more and more years of development, knowledge granularity in knowledge discovery, data mining, soft computing plays an increasingly important role.In this paper, we introduce this method of knowledge granularity as a unified framework to understand and implement outlier mining. In addition, we also give the size of knowledge-based algorithm for mining outliers. The algorithm combines rough sets and data mining of abnormal data. Theoretical and experimental results show that the method of assessment of knowledge granularity is an effective and appropriate exception.朗读显示对应的拉丁字符的拼音字典Key Words: rough sets; outlier detection; data mining; knowledge granulation目录第1章 引言1 概述1 研究的目的和意义2 国内外研究现状3 数据挖掘的研究现状3 粗糙集的研究现状3 知识粒度的研究现状4第2章 数据挖掘66 数据挖掘的有趣故事7 数据挖掘的几种知识表示方法与模式8 广义知识挖掘8 关联知识挖掘8 类知识挖掘8 预测型知识挖掘9 特异型知识挖掘9 粗糙集知识挖掘9 数据挖掘与知识发现9 把KDD看成数据挖掘的一个特例10 数据挖掘存在于KDD过程中10 数据挖掘与知识发现相近似11第3章 粗糙集理论12 粗糙集理论的基本概念12 信息集12 集合的上近似，下近似与边界值13 粗糙集理论的优点14 属性约简14 属性依赖15 属性约简15 信息熵16 知识粒度17 基于粗糙集理论的知识粒度表示1718 应用实例19第4章 基于知识粒度的异常检测20 知识粒度的异常检测20 基于知识粒度异常点的定义20 基于知识粒度异常点的例子22 基于知识粒度的异常检测算法26 基于知识粒度异常点检测的算法流程图26 基于知识粒度异常点检测的算法描述26第5章 实验与分析29 实验结果29 实验分析31 淋巴数据的检测31 漏检和误检32第6章 结论与展望34 结论34 进一步工作的方向34致 谢35参考文献36第1章 引言 概述相较于传统的数据挖掘的问题，其主要目的是通过建立一个普遍的模式映射到大多数的数据，而异常检测1的目标则是挖掘那些与大多数常规的数据相比，行为较特殊的稀有数据。基于距离的挖掘算法是现今最流行的方法之一，是由Knorr和Ng提出的。一个数据集中的某个异常数据是指该数据的距离与其它普通常规数据的距离大于dmin。这个概念总结概括了许多以分布为基础的研究方法，且它拥有较好的检测精度。假设一个对象在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则我们认为该对象也属于这个类别，称之为KNN算法2。换句话说，在不依赖于统计检验的情况下，我们可以将通过距离计算出那些没有“足够多”邻居的对象看作是异常点，这里的对象是根据给定对象的距离来定义的，这是一种研究挖掘异常点K的高效算法。然而，因为KNN异常检测算法是要计算点到其他点的所有空间的距离，所以如果可用的对象数量非常多的话，那么这是很费时的。而且，使用KNN算法来进行数据挖掘则将会产生很大的空间，这样很有可能导致性能和质量成本上的问题。异常检测可以粗略的分成五大类3，除了之前讲到的基于距离的异常检测方法外，还有基于统计的方法、基于深度的方法、基于聚类的方法和基于密度的检测方法。利用统计学的方法处理数据异常点的问题已经有很长的历史，并且它已经有了一套完整的理论和方法。统计学的方法就是对给定的数据集假设了一个分布或者称为概率模型（例如正态分布），然后再根据模型通过不一致性检验来确定数据异常点，所以不一致性检验要求我们事先知道数据集模型的参数（如正态分布）、分布的参数（如均值等）和预期异常点的数目。它最大缺点就在于测量的数据分布在实际中是很难被发现的。基于深度的方法是通过计算几何和计算不同层的k-d凸壳和标记外层的对象作为异常点。然而，众所周知的是该算法采用维数，不能应付大量的对象集。聚类分类对输入数据进行分类。它检测异常点作为副产品。由于主要目的是分类归并，它不适合用于异常检测。基于密度的方法4最初是由Breunig提议的。它采用局部异常因子来确定异常数据的存在与否。它的主要思想是，计算出对象的局部异常因子（LOF）。高局部异常因子（LOF）就认为它更可能异常。这种解决方案的缺点是，它对邻居的参数定义非常敏感的。粗糙集理论（Rough Set Theory）5，用于研究不完整性数据和不精确的知识表达，学习归纳的数学分析理论，并成功的应用于机器学习、模式识别和数据挖掘等领域上。其算法特点是简单，无需提供数据以外的任何先验信息，可直接根据给定问题的描述集合出发，然后通过不可分辨关系和等价类来确定问题的近似域，再找出该问题的规律。为了评估粗糙集理论在分辨不确定性知识上的能力，。它提出了关于领域划分的描述，更直观和更具有结构性。许多知识上的检测在信息系统上有提出。这些测量包括粗糙集，知识粒度和信息熵。这些测量应用于属性约简，分类，特征选择与不确定性的推理。然而，这些年很少有基于知识粒度检测异常数据的文章发表出来。本文提出了一种异常检测的新方法，是基于知识粒度的。它采用了基于知识粒度的距离度量，研究不确定信息。有些在UCI数据集上进行了实验分析。结果表明，该检测系统可以把大部分异常点检测出来。 研究的目的和意义随着计算机和网络等信息技术的飞速发展，对信息的处理在整个社会乃至世界规模上已经迅速产业化。随着信息的慢慢堆积，人们所积累的数据已经越来越多，以至数据和信息系统中的不确定性问题更加的明显了。海量杂乱的信息数据背后隐藏着很多我们不知道的，但对我们来说又非常重要的信息，所以人们希望能够通过对其进行深入的分析，方便我们能更好的利用并使用这些隐藏中的数据信息6。现在的数据库系统虽然可以实现对数据的增删改查及统计等功能，但它却无法发现数据间存在的关系和规则，它没法根据数据中所变现出来的隐藏信息来预测未来的发展趋势。缺少挖掘数据背后隐藏的信息手段就造成了我们所说的“数据丰富却知识贫乏”的现象。自从 20世纪 90年代中期以来，数据挖掘一直引起人们的广泛兴趣，以至它得到了迅猛的发展。通常，数据挖掘被人们划分成四种类型7：类别的判定、 类别的描述、相关依赖关系的发现、 粗糙或异常 (Outlier)数据挖掘。前三个类型主要针对的是数据集中服从的数据模式的大部分数据记录，而异常检测的目的则在于找出隐藏在海量数据中的相对稀疏而又孤立的异常数据模式，这也造就了异常检测与传统面向数据主体的数据挖掘间的区别。早期，在对数据集进行预处理时，我们通常把异常点当作噪声，或者干脆修正异常点的值，让其减少对正常数据的影响。虽然异常检测是以发现数据集中的隐藏数据为主要目的，但是异常数据挖掘常常能比其他类型的挖掘来得更有价值，更有研究意义，因为十万个正常的记录里很可能只覆盖了一条规则，而十个异常记录里则很可能就意味着拥有十条不同的规则。实际生活中，异常检测是有着很广泛的应用，比如信用卡恶意透支、贷款证明的审核、网络入侵检测等。 国内外研究现状 数据挖掘的研究现状知识发现（KDD：Knowledge Discovery in Databases）8是指从数据集中辨别出新颖的、有效的、潜在有用的且最终可理解的模式的一个非平凡过程。知识发现就是将信息变为知识，从数据的海洋中找到蕴藏的知识石油，它为知识的创新和知识经济的发展做出了伟大贡献。知识发现的术语是在1989年美国底特律召开的第一届KDD国际学术会议上出现的。随后KDD得到了广泛的发展。1995年第一届知识发现与数据挖掘国际学术会议在加拿大召开。1998年，在美国纽约召开了第四届知识发现与数据挖掘国际学术会议，其中有30多家国际公司陈列出了他们的研究产品，其中的一些产品都已广泛的在发达国家中应用了。至此数据挖掘和知识发现成为当前数学界与计算机科学研究界的一大研究的热点。 粗糙集的研究现状随着粗糙集关于数据推理的理论这篇文章的发表，国际上掀起了一场粗糙集的学习热潮。在1992年，众多知名学者齐聚波兰，召开了第1届国际粗糙集理论的研讨会，这次会议主要讨论了数据集合近相似的基本思想和应用，其中在粗糙环境下的机器学习的研究是这次会议的重点之一。20世纪90年代第2届国际粗糙集与知识发现研讨会在加拿大召开了，这次会议极大的推动了全球对粗糙集理论的研究。一些著名的学者参加了这次会议，并且介绍和演示了许多基于粗糙集理论的数据挖掘方法和系统。在1995年ACM Communication将粗糙集理论列为“新兴的计算机科学”的研究课题。1996年在日本的东京召开了第5届国际粗糙集研究会。“第一届粗糙集和计算的当前趋势”学术会议于1998年在波兰华沙召开了。1999年，在日本召开了“第七届粗糙集、Fuzzy集、数据挖掘和粒度一软计算的国际学术研讨会”，阐明了目前粗糙集、模糊集的研究现状和未来发展趋势，最终指出将着重在数据库、AI、软计算的近似推理理论和应用方面发展。目前，美国、日本、波兰、加拿大都建立了粗糙集研究的专门机构。粗糙集理论的研究虽然在我国起步晚，但发展迅速。“第一届中国软计算学术与粗糙集研讨会”于2001年在重庆的邮电大学开办了。主办方还邀请了粗糙集理论的始祖。这次研讨会的举行大大推动了我国乃至亚洲地区对粗糙集的应用及其理论的研究。粗糙集与软计算专业委员会于2003年由中国人工智能学会组建。加拿大的粗糙集研讨会议于2005年9月举办时，我国研究者的论文已经超过了会议采用论文总数的1/4。2006年7月在重庆举行了第一届粗糙集与知识技术国际研讨会议。如今，国内学者从事粗糙集理论研究的人员越来越多越来越强大，已形成了一支较为稳定且实力强大的学术队伍，中国学者在粗糙集这一领域的影响力也越来越巨大，俨然成为了这一领域的重要科研力量。在对大型数据库中不完整数据的分析和学习方面都取得了显著的成果，使得粗糙集理论以及数据挖掘的研究成为热点领域。 知识粒度的研究现状粒度计算9是信息处理的一种全新的概念和计算范式，它覆盖了所有关于粒度的理论、技术、方法和工具的研究，现已成为了人工智能界的研究热门之一。在美国知名学者 ，人们在1979年第一次发表并且讨论了关于模糊集粒度化信息的问题，虽然这推动了逻辑的模糊的应用以及理论的进一步研究，但在当时却没有吸引人们的眼球。直到“词计算理论”这一演说于1996 ，才宣告着模糊集粒度化信息理论的诞生。它的主要思想在于通过我们的自然语言，进行模糊的判断和推理，以便实现模糊智能控制的方法。随后，美国多特蒙德大学的 Helmut Thiele 教授于 1998 年发表了“粒计算理论的语义模型”，促进了粒度计算理论的发展。粒度计算理论对Internet上的海量信息资源的利用有着深远的影响。基于 的模糊集理论的粒度计算的研究，已成为“粒度计算”方面的重要研究方向之一。在国内，著名学者张铃教授和张钹院士曾提出了一个模型是基于商空间的粒度计算。其主要思想是通过子集来表示概念，然后我们把不同粒度的概念可以认为是不同粒度的子集，一簇的概念我们就当成了空间的一个划分（商空间），叫知识基10，不一样的概念也就簇成了不同的知识基。而粒度计算问题，也可以把它看作是研究在给定知识基上的各种不同子集合之间的关系与转换。 对同一问题，我们可以采取不同的粒度。通过对不同的粒度进行分析，综合获取对所提问题的求解。在此基础上，学者张钹和张铃在 2003 年提出了关于模糊商空间的理论。总的来说，粒度计算的研究在我国还属于刚起步阶段，尚未引起广泛的关注。但我们相信，在不久的将来会有更多的学者加入到我们的队伍中来，一起对该领域的研究做出伟大的贡献。第2章 数据挖掘我们先对数据挖掘的定义进行讲解，然后通过一个故事来了解数据挖掘在我们生活中的应用，在介绍几种知识表示方法与模式，最后在讨论数据挖掘与知识发现之间的关系。数据挖掘（Data Mining）11是一个多学科交叉研究领域，它融合了数据库（Database）技术、人工智能（Artificial Intelligence）、机器学习（Machine Learning）、高性能计算（High-Performance Computing）、知识工程（Knowledge Engineering）、统计学（Statistics）、信息检索（Information Retrieval）、面向对象方法（Object-Oriented Method）以及数据可视化（Data Visualization）等最新技术的研究成果。经过十几年的研究，产生了许多新方法和新概念。尤其是最近几年，大部分基本方法和概念越来越清晰了，它们的研究正逐步向着更深入的地方发展。数据挖掘之所以被大家称为是未来处理信息的中坚技术之一，主要在于它是以一种通过新概念来改变着人们使用数据的方式。在20世纪，数据库技术取得了关键性的胜利而且它已经广泛的应用于我们的生活中。但是，数据库技术作为一种基本的信息存储和管理方式，仍然以联机事务处理12（On-Line Transaction Processing ：OLTP）为核心应用，缺少对决策、分析、预测等高级功能的支持（Decision Support）以及分类（Classification）、聚类（Clustering）等复杂应用成为必然。面对这一问题，数据挖掘和知识发现使得数据处理的技术进入了一个崭新的高度。它不仅能对以往的数据进行查询，而且能够找出以往数据之间的潜在联系，然后进行更多的分析操作，以便更好地做出理想的决策并预测未来的发展趋势等。通过数据挖掘，我们则可以把有价值的知识、规则和高层次的数据信息从数据库的相关集合中抽取出，从而使大型数据库成为一个可靠的、丰富的源信息然后可以为提取知识提供服务。特别需重点指出的是，数据挖掘的技术的开发目标就是要面向应用的。它不仅仅只是面对特定数据库的简单调用、查询和检索，而且它还要对这些数据进行宏观、中观乃至微观的分析、推理、统计和综合。知识发现在这里所要表达的不是要求我们发现的是万物而皆准的真理，也不是为了去发现新的数学的公式或者自然科学的定理。我们发现的都是相对而言的知识，是面向特定领域的，而且我们还需确保发现的知识是能够易于被用户理解的。 数据挖掘的有趣故事数据挖掘的价值是随时随地都能够体现的。也许在我们平时的一些小事上，我们通过数据挖掘就能够获取到事情背后隐藏的信息，然后通过这些信息，我们能够对这件事进行更好的处理。接下来我们看个简单的例子，通过这个例子，我们可以更加形象的了解数据挖掘对我们生活的重要性。在一家超市里，有个奇怪的现象13：人们一进入就会发现啤酒和奶粉摆在同一个货柜上贩卖，出奇的是商家的这种行为却双双增加了奶粉和啤酒的销售量。这不是虚构的，这是美国一家家乐福真实的案例。家乐福拥有国际上最大的数据信息库，商家们为了了解顾客经常购买的物品，对顾客的历史购物信息进行分析。通过对原始交易数据进行数据挖掘，商家们发现了一个惊人的信息，那就是与啤酒一起购买的商品竟然是奶粉。经过商家们大量分析与实际查证，得出了一个隐藏在“啤酒和奶粉”身后的人们的一种生活模式。对于许多年轻的美国人父亲，他们一下班就会去超市购买奶粉，而买奶粉的同时，他们也不会忘了给自己买啤酒，因为他们的太太会叮嘱他们下班需要买奶粉，而买奶粉时他们也会带回自己喜欢的啤酒。按照人们的正常思维，人们会认为啤酒和奶粉是面向两种不同消费对象的产品，但是将它们拜访一起贩卖却起到了提高商品销售量的现象，其实这都多亏了数据挖掘。因为家乐福借助了数据挖掘的技术，通过对大量的原始交易信息进行分析挖掘，他们得到了许多不能通过普通检查而得到的宝贵信息，通过这个信息，我们可以寻找出一个有价值的规律。所以这个案例也告诉了我们一件事，数据挖掘对于如今的社会生产和发展是多么紧密相连的，它的发展是社会进步的必然结果，那么接下来我们就要来讨论下数据挖掘的方法。 数据挖掘的几种知识表示方法与模式发现知识是Data Mining的最终目的，知识是经过一定的模式得出的。我们知道有非常丰富的知识表示模式被用于Data Mining的，我们由知识表示模式和它所使用的方法来进行检测，对Data Mining的系统特点更加了解。 广义知识挖掘用来描述类别特征的概括性就是指广义知识14。我们明白，在源数据库中大多存放的都是一些普通的数据，而人们大多想从较高点的地方上观察或处理这些数据，数据所蕴涵的逻辑或概念都是进行了不同层次上的泛化得来的，这是数据分析的条件。广义知识挖掘模式主要采用的是概念描述方法、多维数据分析和多层次概念描述问题的方法。 关联知识挖掘关联知识14就是反映一个事物与另一个事物之间的关联或依赖。现实世界中事物联系的表现跟数据库中的数据关联是一样的。数据库是一种结构化的组织模型，数据间的关联我们可以利用它所依附的数据模型来刻画了。但是，数据之间的关联是变化万千的，依附在数据模型中的关联只是一部分，大部分的关联都是蕴藏着的。找出数据库中隐藏的关联信息就是关联知识挖掘的目的。 类知识挖掘类知识15刻画了一类事物，这类事物在一定的意义上具有相同的特征，和不相同类事物有明显的区别。在这里我们所指的类知识就是Data Mining的聚类和分类两种Data Mining应用所对应的知识。聚类是吧一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的差别尽可能的小，而不同类别上的个体间的差别尽可能的大。在2000年，Han等归纳了基于划分、层次、密度、网格和模型五大类聚类算法。Data Mining中的一个重要的任务和目标就是分类，大多数的研究都应用在商业上。学会一个分类模型就是分类的目，给定类别中，通过模型我们能把数据库中的项映射到里面。许多技术都可以应用到分类应用中，如决策树、贝叶斯分类、神经网络、遗传算法、进化理论和类比学习。 预测型知识挖掘预测型知识挖掘16是指由历史的和当前的数据产生的并能推测未来数据趋势的只是。这类知识可以被认为是以时间为关键属性的关联知识。预测型知识挖掘也可以借助传统的机器学习、神经网络和统计方法等技术，但最近几年，许多新的应用模式已经发展了起来。如神经网络、序列模式、周期分析模式和趋势分析模式。 特异型知识挖掘源数据中所蕴藏着的与其他数据存在明显差异的知识描述或个性特例就称为特异型知识16，它发现了那些不同于常规的异常规律。并不是数据库中的所有数据都是正常的，从常规数据中检测出其所含有的特异性信息是一件很有意义的事。我们可以通过孤立点分析、序列异常分析和特异规则发现来帮我们了解特异型知识挖掘的任务和方法。 粗糙集知识挖掘粗糙集是用于数据简化（删除与任务无关的记录或字段），数据意义评估，对象相似或差异性分析，因果关系及范式采掘等。它的主要思想如下：可以把对象的属性分为条件和决策。按各属性值相同进行等价分类。条件属性上的等价类T与决策属性上的等价类D之间的关系有三种情况：下近似：D包含与T；上近似：D和T的交集为非空；无关：D和T的交集为空。对下近似建立确定性的规则，对上近似建立不确定性的规则(包含可信度)，对无关情况则不存在规则。 数据挖掘与知识发现谈到数据挖掘，必须提到另外一个名词：数据库中的知识发现（Knowledge Discovery in Database, KDD）。1989年8月在美国底特律召开的第十一届国际人工智能联合会议的专题讨论会议上首次出现KDD这个术语。随后的几十年，开展了数次KDD专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。关于KDD与Data Mining 的关系，有许多不同的看法。我们可以从这些不同的观点中了解数据挖掘的技术含义。 把KDD看成数据挖掘的一个特例既然数据挖掘系统可以在事务数据库、文本数据、空间数据库、数据仓库、关系型数据库等数据挖掘知识，那么数据库中的KDD就是属于数据挖掘的一个特例17。这是早期比较流行的观点，在许多文献可以看到这种说法。因此，从这个方面理解，我们把从数据库等存储方式中挖掘有用知识的过程称为数据挖掘。这种说法是为了强调说明数据挖掘在数据库等数据形式上的多样化。 数据挖掘存在于KDD过程中为了达成共识，在知识发现与数据进展中，FAYYD等知名学者对Data Mining与KDD的给出了全新定义以便将两者区分开来。（1）在Data Mining时知识发现在可接受的计算效率限制内通过一定的算法生成特定模式的一个步骤。（2）KDD是从信息数据库中识别可理解的、潜在有用的、新颖的、有效的模式的过程。人们一般认为KDD是由三个阶段组成：数据预备；数据挖掘；最终解释与表达。我们可以清楚的明白知识库或者用户可以与数据挖掘进行交互，。 这种观点得到大多数学家认同，它是具有的合理性的。我们虽然可以从数据仓库等源数据中进行知识挖掘，但是这些源数据和数据库技术都是有相关的。因此知识发现具有一个更广义的定义，它包括模式生成、数据选择、数据集成、数据挖掘、数据转换、数据清洗及评估等一系列步骤。这样，我们把一些基本功能构建的系统化协同工作系统看作是知识发现，而这个系统中的一个关键的部分则是数据挖掘。将数据挖掘作为知识发现的关键步骤来看待，可以使我们更轻松容易的进行重点研究，有效地解决问题。 数据挖掘系统的结构示意图 数据挖掘与知识发现相近似有许多人认为，知识发现与数据挖掘只是名字的不一样，其实它们的含义是一样18。实际上，在当前的许多文献资料中，人们仍然不区分地使用这两个术语。一些人说，数据挖掘在数据库界更流行，而知识发现在人工智能界使用率更高。所以，数据挖掘有狭义和广义的定义。从狭义的观点上来看，我们可以定义从一定形式的数据源中检测知识的过程称为数据挖掘。所以数据挖掘的概念虽然在不同的技术层面上进行理解，但是它的要点还是在数据源中挖掘知识。接着我们从广义的观点来看，从大型数据源（可能是不确定性的、有噪声的、不完全的等存储形式）中，挖掘隐藏在数据背后不无人知的，却对人们非常有用的信息知识的过程称为数据挖掘。所以也有人称数据挖掘为知识挖掘。第3章 粗糙集理论粗糙集理论的观点是“知识（人的智能）就是一种对对象进行分类的能力”，这里的“对象”是指我们所能言及的任何事物，比如时间、抽象概念、过程、状态和事物等，也就是说，我们称论域为知识必须与具体或抽象世界的特定语境相关的各种分类模式联系在一起，论域一般是一个非空的有限集合。 粗糙集理论的基本概念 信息集在粗糙集理论中，信息系统A中每个个体uU用一个信息集（information set）表示InfA（u）=（a，a（u）：aA，对应着数据表A中元素u所在的行。两个个体u，w可能有相同的信息集InfA（u）= InfA（w），在这种情况下我们称这两个个体是A-不分明的（A-indiscernible），关系IND（A）=(u,w): InfA（u）= InfA（w）称为A-不分明关系（不可区分关系，不可分辨关系）（A-indiscernibility relation），它是一个等价关系。符号uA表示关系ind（A）中包含u的等价类。对任何的BA也可以定义不分明的概念。B-信息集定义为InfB（u）=（a，a（u）：aB；B-不分明关系定义为ind（B）=(u,w): InfB（u）= InfB（w），由B-不分明关系中的等价类形成B-可定义集。集合A中的属性定义全域U中的概念。一个概念XU称为A-可定义的，是指对于每个uU，或者uAX或者uAUX。也就是说，概念X是A-可定义的相当仅当X是等价类的并，即X=UuA：uX，A-可定义的集合有下面属性：他们在集合论意义上的并集，交集和补集都是A-可定义的，也就是说，A-可定义的集合形成一个域。根据信息集的定义，我们接下来就要对粗糙集理论的重要思想，上近似、下近似和边界值进行讲解。 集合的上近似，下近似与边界值粗糙集理论是基于传统的集合理论衍生出，它把知识分类嵌套到集合内，作为集合组成的一部分。根据传统的方法来判断一个对象a 是否属于集合X，我们可以分成3种情况:对象a 可能属于也可能不属于集合X；对象a 肯定不属于集X；对象a 肯定属于集合X，。 粗糙集的粗略图通过我们所掌握的关于论域的知识进行集合的划分，这种划分不是绝对的是相对的。有一个非空的有限集合U，我们称之为论域，I 为U 中的一个等价类关系，即关于U 的知识，则二元对 K = (U，I ) 称之为集合U的一个近似空间。假设X为集合U 的一个子集，x 为集合U 中的一个对象，所有与x 不可区分的对象所组成的一个集合设为I (x )，也就是说，该等效类是由x 决定的，我们也可以理解为I (x ) 中的每个对象都与对象x 有同样的特征属性。对于每个子集XU和一个等价关系I IND (K)，都可以定义两个子集。集合X 关于I ： (3. 1)完全属于集合X的对象组成的集合，我们称为下近似，有时也称之为X 的正区，记作POS (X )。同样的，由肯定不属于X 的对象组成的集合称为X 的负区，记作N EG (X )。 集合X 关于I ： (3. 2)所有与X 相交且非空的等价类I (x ) 的并集就是I* (X )，也就是那些可能属于集合X 的对象所组成的最小的集合。显然，I* (X ) + N EG (X ) = 论域U。 集合X ： (3. 3)BND (X ) 为集合X 的上近似与下近似之差。如果BND (X ) 是空集，则称X 关于I 是清晰的(crisp )；反之如果BND (X ) 不是空集，则称集合X 为关于I 的粗糙集( rough set)。 粗糙集理论的优点粗糙集方法的简单实用性是令人惊奇的，它能在创立后的不长时间内得到迅速应用是因为具有以下特点：(1) 粗糙集是以分类为主并以不可分辨关系为基础，而模糊集则是基于元素对集合的隶属程度大小，强调集合自己本身的含混性。(2) 粗糙集也是一个使用便捷的数据分析方法。它可以求得知识的最小表示而且能保留关键信息的，只需对数据进行化简；能揭示概念间的简单模式，判断数据与数据间的依赖关系；最终从数据中挖掘其规则知识。(3) 粗糙集是不要先了解知识的。处理不确定信息的常用方法是概率统计和模糊集方法，但这些方法都是要先了解数据信息或知识等，如概率分布和模糊隶属函数等，其实这些数据并不是那么容易可以获得的。而粗糙集分析方法不需要任何先验信息，利用数据本身就可以推理和决策了。 属性约简在实际问题中，我们常常遇到数据约简19的问题在保持决策表的基本性质的前提下删除冗余的数据，运用Rough Set理论进行数据约简是在保持决策属性和条件属性之间的依赖关系不发生变化的前提下对决策表进行简化，包括属性约简和属性值约简。前者是在原始决策表上，删除冗余属性，使得决策规则更简洁，有更高的适应性；后者是在前者的基础上，在决策规则中删除冗余的条件属性，得到不含冗余属性的决策规则。而本文则主要是使用到属性约简。 属性依赖决策系统是一个三元组Ad=（U，A，d），其中（U，A）是信息系统，d是决策属性，d：UVd，d A。当ind（A）ind（d）时，决策属性d和条件属性集A之间的关系可以用函数依赖A d来表示；当ind（A）ind（d）不成立时，将个体集限制在集合POSA（d）=uU | uAud上时，函数依赖A d还是成立。通常决策属性是有一定的依赖度（依赖度的取值范围为0，1），而不一定是完全依赖条件属性。： () 属性约简在IS系统（U，A）中，属性集合A中的子属性都是对U有一定的分类能力，但是A（或它的子集BA）的分类能力可能与它的子集相同，也就是说A中可能有些属性是冗余的。下面我们就要讨论这个问题。(1) 如果属性aB满足ind（B）=ind（B-a），则称a是可约去的；否则称a是不可约去的。(2) 如果任意aB都是B中部可约去的，则称属性集B是独立的，否则B是相关的。(3) 如果BB是独立的，且ind（B）=ind（B），则称B为B的一个约简。因此，一个约简是保持划分的属性集合。也就是说，一个约简是指能使的论域中的元素在分类相同的情况下属性集合的最小子集，分类的冗余属性是不属于约简的。(4) 我们把B中所有不可约去的属性称为B的核（core），记为core（B）。()式中，red（B）是B的所有约简族。因为核是所有约简的交集，它包含在每个约简当中，删除核中的任何属性都会影响划分，所以，从某种意义上说，核是最重要的属性子集。在决策系统Ad=（U，A，d）中，如果我们给定一个依赖B d（其中BA），d可能不依赖整个集合B，而仅仅依赖B的子集B，我们往往对这个子集感兴趣。为解决这个问题，我们需要定义相对约简（relative reduct）。(5) 如果属性aB满足POSB（d）=POS（B-a）（d），则称属性aB在B中是d-可约去的；否则称aB在B中是d-不可约去的。(6) 如果属性集B中所有的属性都是d-不可约去的，则称B是d-独立的。(7) 如果BB是d-独立的且满足POSB（d）=POSB（d），则称B是一个B的d-约简。(8) 我们把B中d-不可约去的属性称为B的d-核，：()式中，redd（B）是B的d-约简。如果ind（d）=ind（B），那么相对约简就退化为前面的普通约简了，所以我们下面只在决策系统中讨论相对约简。在决策系统Ad=（U，A，d）中。属性aC的重要性是将该属性删去后对决策影响的度量，：()可以简单表示为(a)。显然0(a) 1，(a)越大属性a越重要。 信息熵信息熵(Information Entropy)20是在数学上非常抽象的一个概念，在这里不妨把信息熵看成一种特定信息的出现概率也可以理解为离散随机事件的出现概率。如果一个系统是有序的，信息熵就较低；反之，如果一个系统是混乱无章的，信息熵就高。信息熵也可以看成是一个系统有序化程度的尺度。 根据著名学者Bennett对Demon的解释21，信息的销毁我们认为是一个不可逆过程，所以销毁信息完全符合热力学的第2定律。而信息的产生，则是为引入负熵的一个过程。常言道，当一种信息被传播得更广泛的时候，则表明它出现概率更高，也可以说，该信息被关注的程度更高。那么我们认为，从信息被传播的情况来看，信息熵也可以表示为一个信息的价值。这样我们通过信息熵来衡量信息价值高低的