《知识发现中粗糙集基本算法的应用研究》由会员分享，可在线阅读，更多相关《知识发现中粗糙集基本算法的应用研究（56页珍藏版）》请在金锄头文库上搜索。
1、华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 I摘摘 要要 随着数据采集工具的成熟以及海量存储设备的广泛应用，目前许多大型企业己经积累了大量的数据。为满足管理、经营的需要，这些数据必须得到有效地处理；使用传统的数据分析和检索方法处理这些数据，不仅将耗费大量的计算时间，而且依赖于事先对数据关系的假设和估计，难于得到其中的有效信息。目前面临的要求是如何自动和智能的将待处理的数据转化为有用的信息和知识。二十世纪八十年代初波兰数学家Pawlak.Z提出了粗糙集理论， 它是一种处理含糊和不确定性的新型数学工具，可以有效的用于知识约简和提取。 为在知识发现
2、中更好地应用粗糙集理论，将主要研究工作集中在粗糙集约简算法以及应用粗糙集理论处理多值系统的查询和检索方面，为多值系统中的知识发现应用提供了方法，并建立了两种算法用于满足知识发现中的不同约简需要。 首先，在分析属性分类能力后，给出一个易于理解、方便交互的启发式约简算法，可以有效满足知识发现中领域专家对控制并调整约简过程的需求； 其次，为提高约简算法效率，对正区域进行深入的分析和研究后，给出并证明一种新的正区域等价定义，以此推导了高效的正区域基本算法； 为满足大数据集上对约简算法效率的要求，通过对不同约简属性集所对应的属性子集、论域子集和正区域间的关系，以及正区域递增算法中约简属性的性质等方面，推
3、导相应的性质和推论后，建立了一个高效的属性约简算法并证明了其完备性。实验数据的分析，表明该算法可以有效地应用于大数据集上的约简计算； 最后，建立多值数据属性的检索和查询方法，使得多值系统上的知识发现应用成为可能。 关键词：关键词： 粗糙集理论，属性约简，知识发现，正区域，粗糙查询 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 IIAbstract With the development and application with the computer and the large-scale storage system, the massi
4、ve data was accumulated by many industries and companies. While process these data, traditional data analysis and retrieval method, not only will cost the massive computing time, moreover depend on the data relations supposition and the estimate. So it has urged people to develop a set of practical
5、techniques and methods for intelligently and automatically drawing the interesting knowledge from a very large number of data having been continuously generated. Early in 1980s, a Polish mathematician Pawlak.Z advocated the Rough set theory. It was a new mathematical tool for processing vagueness an
6、d uncertainty. It can analyze the facts hidden in the data without any additional knowledge about the data. This article discusses the Rough set theory application in knowledge discovery. The work mainly focuses on two things, attribute reduction and rough query. The main works were listed as follow
7、s: (1) An attributes reduction algorithm based condition attributes classification power is proposed and discussed. (2) Propose and prove an equivalent and efficient method for computing positive region. (3) Research the incremental computing of positive region; and deduces some lemma to decrease th
8、e numbers of objects in the source decision table. Then an attribute reduction algorithm is proposed and its completion is proved. The algorithm is tested by the data sets from the machine-learning database, UCI. (4) Analysis the knowledge discovery system process. Propose a method of rough query. B
9、y supplying a real value, this method is useful to deal the rough query for different purposes. Keyword：Rough set theory, attribute reduction, knowledge discovery, positive region, rough query 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。据我所知，除文中已经标明引用的内容外，本论文不包括任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献
10、的个人和集体，均已在文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容列入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保证和汇编本学位论文。 保密，在 年解密后适用本授权书。 本论文属于 不保密。 (请在以上方框内打“”) 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月
11、日 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 11 综综 述述 介绍粗糙集理论的产生背景、 思想和方法上的特点， 分析其研究现状和发展方向，并简述研究内容。 1.1 粗糙集理论产生背景粗糙集理论产生背景 知识工程和信息处理研究中，一直存在如何计算和处理信息含糊性的问题。含糊性可以分为三种：术语的模糊性、噪声引起的数据误差以及知识自身的不确定性。如“高、矮”的不确定性属于术语的模糊性；而如规则的前后件间的依赖关系不完全一致，则属于知识自身的不确定性。计算领域的基础理论之一基于布尔运算的经典逻辑方法不足以解决这些不确定性问题。 为此，谓词逻辑的
12、创始人G.Frege首先于1904年提出了含糊(Vague)一词，并把它归结到边界线区域，其含义为在全域上存在一些个体既不能在其某个子集L被分类，也不能在该子集的补集上被分类。20世纪60年代初，L.A.Zadeh提出了模糊集(Fuzzy Set)理论1，不少理论计算机科学家和逻辑学家，试图通过这一理论解决G.Frege提出的含糊概念；但是，模糊集方法虽然可以逼近任意非线性映射，但它需要先验知识，尤其是隶属度和隶属函数的制定和建立需要人工干预，至今没有给出相应的完备数学理论，故无法计算出它的具体的含糊元素数目，如模糊集中的隶属函数和模糊逻辑中的算子都是如此。而其它一些解决方法，包括统计方法及D
13、empster-Shaffer证据理论，都存在一些内在缺陷或限定范围；在研究和应用中表现不足，例如，基于统计的方法在理论上还令人难以信服等等。 波兰的Z. Pawlak根据G. Frege的边界线区域思想，在1982年首先提出了粗糙集理论2。粗糙集认为知识是一种对对象进行分类的能力，并通过将无法确认的个体都归于边界线区域，把边界线区域定义为上近似集和下近似集之差集。由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述，所以含糊元素数目可以被计算出来， 即可以计算出真假二值间的含糊程度(Vagueness)， 从而实现了G.Frege的边界线思想和并解决了含糊元素的计算问题。 华 中
14、科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 21.2 粗糙集方法及其特点粗糙集方法及其特点 粗糙集理论的核心思想，反映了现实世界人们处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能力，或依据观察、度量到的某些不精确的结果而进行分类数据的能力。 粗糙集理论中234，认为知识是一种对对象进行分类的能力，这里的“对象”是指所能描述的任何事物，比如实物、状态、抽象概念、过程和时刻等等。也即，知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为论域(universe)，对于论域及知识的特性并没有任何特别限制；在
15、以上的概念下，知识可以认为是某一特定领域中分类模式的一个族集(family)，它不仅提供了关于现实的显事实，还提供了能够从这些显事实中推导出隐事实的推理能力。 在形式上，为便于计算和处理，一般将分类模式表示为论域上的等价类形式，而论域则用信息系统来表示。信息系统可以被看成是一数据表，表中的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来表示的。如果将信息系统中的属性进一步分成条件属性和决策属性，则该信息系统称为决策表。 相对其它处理不确定性的计算工具，尤其是模糊集理论而言，粗糙集有以下特点5678： (1) 粗糙集不需要先验知识。模糊集和统计方法作为处理不确定信息的常
16、用方法，需要一些数据的附加信息或先验信息，如模糊隶属函数和分布模型等，不得不依赖于人工干预以及事先的假设。而粗糙集分析方法仅需利用信息系统中数据本身提供的信息，而无须任何先验知识，即粗糙集可以“让数据自己说话” ； (2) 粗糙集具有很强的数据分析和知识表达能力。它能表达和处理不完备信息；能在保留关键信息和分类能力不变的前提下对数据进行化简并求得知识的最小规则，并得到知识的各种不同颗粒(granularity) 层次；能识别并评估数据之间的依赖关系，揭示出概念的简单模式；能从论域实际数据中获取易于证实的规则知识； (3) 粗糙集与模糊集分别刻画了不完备信息的两个方面；粗糙集以不可分辨关系为基础，侧重分类，模糊集基于元素对集合隶属程度的不同，强调集合本身的含混华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位
