【粗糙集在数据挖掘中的应用7000字（论文）】

粗糙集在数据挖掘中的应用目录TOC\o"1-2"\h\u20084引言 215954一粗糙集和数据挖掘的背景和研究现状 221209二数据挖掘的基本概念和任务 3255502.1数据挖掘的任务 45250（1）关联模式 410784（2）序列模式 415045（3）聚类模式 431300（4）分类模式 430127（5）回归模式 427435（6）时间序列模式 4212972.2数据挖掘的方法 4669（1）统计分析方法 415120（2）模糊集方法 41537（3）粗糙集理论 412031（4）决策树 58831（5）神经网络 56340（6）遗传算法 512057（7）可视化技术 5323502.3等价类和不可分辨关系 583692.4粗糙集的上、下近似集 6298282.5粗糙集方法与其他方法的关系 818196三、粗糙集在数据挖掘中的应用 8107453.1分类规则 8254723.2不确定性问题 8313563.3数据预处理 9277143.4属性约简 911886参考文献 9【摘要】在大数据时代，不仅数据挖掘是人们常用的一种方法，粗糙集近些年来也被广泛应用到各项知识领域中。目前，数据挖掘中常用到的技术有：统计分析方法、决策树、神经网络、遗传算法、模糊集方法、粗糙集理论、可视化技术等等。在诸多方法中，粗糙集理论与方法对于处理复杂系统不失为一种较为有效的方法。本文从粗糙集和数据挖掘的基础概念和知识出发，进一步总结了近些年来粗糙集在数据挖掘中的应用。【关键词】数据挖掘；粗糙集引言当今，社会已经进入了网络信息时代，计算机技术在这十几年来得到了迅猛的发展，特别是存储技术、数据库技术和网络技术。存储设备单位价格的不断下跌而容量的急剧扩大，关系数据库、对象数据库、多媒体数据库、地理信息数据库和空间数据库的不断成熟并得到广泛的应用，数据库管理系统的日益普及，自动数据采集系统的引入以及互联网络在全球的不断深入应用，这些都使得人们轻而易举地就可以获得容量达GB甚至TB的数据，并且这些数据每天都还在不断地增长中。因此，如何从大量的、杂乱无章的、强干扰的数据中挖掘出潜在的、有利用价值的信息，便成为人类智能信息处理中面临的前所未有的挑战。由此产生了人工智能研究的一个崭新领域——数据挖掘（DataMining，简称DM）。数据挖掘是一个多学科领域，它从多个学科吸取营养。这些学科包括数据库技术、人工智能、机器学习、模式识别、统计学、高性能计算和可视化技术等。数据挖掘是一个新兴的具有广泛应用前景的研究领域。一粗糙集和数据挖掘的背景和研究现状自上世纪九十年代以来，数据挖掘逐步兴起。数据挖掘，简单来说，就是在海量的数据中找到隐含的与用户需要有关的知识，然后对其进行分类和预测，找出对用户有利的数据。有一个典型例子，在一个超市中，人们发现啤酒喝尿布这两样完全没有关系的商品竟然摆放到了售货架的同一处，然而更令人惊讶的是，这样的摆放收到却给超市带来了非凡的效益，超市的营业额非但没有减少而是大幅上升。其实这其中蕴含着智慧，超市管理人员通过调查发现，由于母亲属于哺乳期，在家带孩子的任务当之无愧，因此外出购物，购买生活必需品便成了男人的责任。而男人大部分都是喜欢喝酒的，管理人员就猜想，如果男人来超市为自己的孩子购买尿布等必需品时，恰巧他非常喜爱的啤酒就在不远处的柜台，根据男人的正常心理，大多数男人都会顺手带走一瓶啤酒，这样超市的收益就可以提高。这个例子便是最经典的数据挖掘的例子，通过对人性的心理分析和预测，得出利于自己一方的数据，或者说是利益信息，这便是我们通过数据挖掘最终要达成的效果，也是我们研究数据挖掘的意义所在。粗糙集理论是波兰数学家Z.Pawlak于1982年提出的一种数据分析理论。1991年波兰Pawlak教授的《RoughSets：TheoreticalAspectsofReasoningaboutData》和1992年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，在国际上有了很大的影响，由此越来越多人开始研究粗糙集。粗糙集是基于不确定信息的一门新学科。粗糙集针对无法确定的数据，提出了边界线区域的概念。同时这种边界线区域被定义为两个新的概念，上近似集合下近似集。粗糙集中还涉及了对于粒度的分析，同时与它相关的学科有粒计算和商空间理论。粗糙集的诞生与问世，为人工智能领域提供了便利。近几年来，粗糙集理论的研究包括很多方面。如今在与其他不确定性理论的融合协作非常之多。其中包括粗糙集与概率统计相融合，与模糊集相融合，与神经网络相融合等。粗糙集方法与其他知识的处理方式各自有各自的独到之处，因此与其他知识领域的融合也一直在探索中，尤其同遗传算法、神经网络、等技术的相互结合，取得了良好的效果，并且是目前研究的热点之一。二数据挖掘的基本概念和任务数据挖掘（DataMining，DM）是从大量的、不完全的、模糊的、随机的数据中提取人们感兴趣的知识的过程。通过数据挖掘，才能把有价值的知识、规则从数据库的相关数据集合中抽取出来，为决策提供依据。数据挖掘和知识发现有密切的联系。知识发现是指从数据中发现有用知识的整个过程，数据挖掘是这一过程中的一个特定步骤。知识发现包括数据选择、数据预处理、数据转换、数据挖掘、模式解释和知识评价等多个步骤，是应用特定数据的挖掘算法和评价解释模式的一个循环反复过程，并要对发现的知识不断求精深化，使其易于理解；数据挖掘是知识发现过程中的一个关键步骤，它利用特定的数据挖掘算法从数据中抽取模式，数据挖掘算法是数据挖掘与知识发现整个过程的核心。知识发现强调知识是数据挖掘的最终产品，利用相应的数据挖掘算法，按指定方式和阈值提取有价值的知识，因此，知识发现包括数据挖掘前对数据的预处理、抽样及转换和数据挖掘后对知识的评价解释等方面，而数据挖掘是知识发现整个过程中的一个步骤。数据挖掘的处理过程如图1.1所示：目前数据挖掘与知识发现已经成为国际上数据库和信息决策领域最前沿的研究方向之一，学术界和产业界给予了高度的关注。到目前为止，数据挖掘已经在很多领域取得了一定的成果。随着数据挖掘与知识发现在国外的兴起，我国也很快跟上了国际步伐，一大批数据库、人工智能、机器学习等领域的学者投入到数据挖掘与知识发现的研究中，并在各种刊物和会议论文集中开辟数据挖掘与知识发现专题。与国外相比，国内对数据挖掘与知识发现的研究稍晚，没有形成整体力量，但数据挖掘技术的研究也引起了学术界的高度重视，国家自然科学基金曾资助有关研究项目，许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，数据挖掘技术的研究已经取得了一些成果。数据挖掘的任务数据挖掘的任务是从数据中发现模式，可分为以下6种：关联模式关联模式用于发现事物间的关联规则，或称相关程度。序列模式序列模式与关联模式相仿，差别在于数据间关联性与时间联系起来。即不仅需指导实践是否发生，而且需确定事件发生的时间。聚类模式聚类模式事先并不知道分组及怎样分组，而是按某种原则将数据划分为组，要求组之间差别尽可能大，组内差别尽可能小。分类模式分类模式把数据集中的数据项映射到某个给定的类上，如决策树方法、统计方法及粗糙集方法等。回归模式分类模式的预测值是离散的，回归模式的预测值是连续的。时间序列模式时间序列模式根据数据随时间变化的趋势，发现某一时间段内数据的相关处理模型，预测将来可能出现值的分布。数据挖掘的方法下面对现阶段数据挖掘所采用的主要技术方法进行简单的介绍：统计分析方法统计分析方法是利用统计学、概率论的原理对关系中各属性进行统计分析，从而找出它们之间的关系和规律。统计分析方法是最基本的数据挖掘技术方法之一。常用的统计分析方法有：判别分析、因子分析、相关分析、回归分析和偏最小二乘回归方法等。模糊集方法模糊集是表示和处理不确定性数据的重要方法。模糊集不仅可以处理不完全数据、噪声或不精确数据，而且在开发数据的不确定性模型方面是有用的，能提供比传统方法更灵巧、更平滑的性能。粗糙集理论粗糙集理论是基于一个机构（或一组机构）关于现实的大量数据信息，以对观察和测量所得数据进行分类的能力为基础，从中发现、推理知识和分辨系统的某些特点、过程、对象等。粗糙集理论是建立在分类机制的基础上，它将分类理解为在特定空间上的等价关系，而等价关系构成了对空间的划分。其主要思想是利用已知的知识库，将不确定或不精确的知识库中的知识来近似刻划。它无需提供所处理的数据集合之外的任何先验信息，对问题的不确定的描述或处理是比较客观的。决策树利用树形结构来表示决策集合，这些决策集合通过对数据集的分类产生规则。利用训练集生成一个测试函数，根据不同取值建立树的分枝；在每个分支子集中重复建立下层结点和分支，这样便生成一棵决策树；然后对决策树进行剪枝处理，最后把决策树转化为规则，利用这些规则可以对新事例进行分类。这种方法实际上是根据信息论原理，对数据库中存在的大量数据进行信息量分析，在计算数据特征信息的基础上提取出反映类别的重要特征。神经网络神经网络是一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型。这种计算模型的特点是，利用大量的简单计算单元（即神经元）连成网络，来实现大规模并行计算。神经网络的工作机理是通过学习改变神经元之间的连接强度。常用的神经网络计算模型有多层感知机、反传网络、自适应特征映射网络SOFM等。在实际应用中，人工神经网络还常与遗传算法、模糊集、混沌和小波等相结合。遗传算法遗传算法是按照自然进化原理提出的一种优化策略。在求解过程中，通过最好解的选择和彼此组合，可以期望解的集合将会愈来愈好。在数据挖掘中，遗传算法用来形容变量间的依赖关系假设。遗传算法可以与模糊逻辑、神经网络和人工免疫等相结合进行数据挖掘。可视化技术可视化技术使用户能交互式地、直观地分析数据，并用直观图形将信息模式、数据的关联或趋势呈现给决策者，可视化技术将人的观察力和智能融合入挖掘系统，极大地改善了系统挖掘速度和深度。等价类和不可分辨关系不可分辨关系是粗糙集理论的最重要概念，它揭示出论域知识的颗粒状结构，而知识的粒度又是造成使用已有知识不能精确地表示某些概念的原因。它也是论域U的等价关系，其定义如下：设U是非空的论域，当R为U上的等价关系（equivalencerelation），则RU/为R（或U的分类）的所有等价类族，或称U的分类：UX⊆，用[]RX表示R中包含X的等价类（equivalenceclass），或子集X属于R中的一个范畴（category）。若R是由U上的划分R表达的等价关系，RU〉〈,称为一个近似空间（approximationspace）。若RP⊂，Uxxji,∈，定义二元关系PIND)(称为不可分辨关系如下：PIND)(=)()(,:),(jijiUxxp=∈∀×∈xpxpPU，则称ix和jx在S中关于属性P是不可分辨的，当且仅当)()(jixpxp=对所有的Pp∈成立，即ix和jx不能用P中的属性加以区别。对所有的Pp∈，可以验证PIND)(也是一种U的等价关系。2.4粗糙集的上、下近似集为了近似地定义粗糙集，我们借用了上、下近似集的概念，粗略地来讲下近似集是指当一个集合不能利用有效的等价关系被恰当地分类时，则可以通过另外的集合来达到这个集合的近似。设UX⊆是任一子集，R是U上的等价关系，则有⊆∈=XYRUYR}{∗Υ:/，∗ΙΥXYRUYR:/≠∈=}{φ，分别称它们为X的R-下近似和R-上近似，其中φ是空集，Y是U上按等价关系R作成的等价类。下近似被解释为所有那些被包含在X里面的等价类的并集，上近似被解释为所有那些与X有交的等价类的并集。下近似和上近似也可以写成下面等价的形式：R{x[]XxUX}R⊆∈=∗:)(，{]≠∈=φ}∗RxXxUXR:)。上近似和下近似之间的差被称作X的R-边界线集，并被表示成：XRXRXBN)()()(R∗∗−=。它是那些通过等价关系R既不能在X上分类，也不能在～X上被分类的元素的集合。这样一个概念X被称之为粗糙集，换句话说，粗糙集就是边界区域不为空集的集合。以上说明：如果通过已掌握的信息看这个集合X，只能观察到X的下和上近似，而不能观察到X的全貌。边界线集为空，则通过等价关系可以恰当地观察X；相反XBN)(≠φR，只能粗糙地观察集合X。前者是分明的，而后者是粗糙的。形式上集合X是R-分明的当且仅当XBN)(=φR，否则X是R-粗糙的。X是R-可定义的，当且仅当XRXR)()(∗∗=；X关于R是粗糙的，当且仅当XRXR)()(∗∗≠。X的R-正区域被记为XRXPOS)()(R∗=，它是如此一些个体元素的集合，这些元素完全属于X的成员；X的R-负区域被记为XRUXNEG)()(R∗−=，它是如此一些个体元素的集合，这些元素不是任意模糊地用等价关系R确定的，它们不属于X，而是属于X的补集~X。其关系如图2.2所示：Rough集示意图由图2.2可以看出决策表就是上面所说的POSNEGΥ（正域+负域）。定义8：设P和Q是论域U上的两个等价关系的族集，令:称关系Q是k()≤≤10k度依赖于关系P的，记作QPk⇒，其中X表示集合X的基数。若k=1，称Q完全依赖于等价关系P，这时论域U上的所有元素根据等价关系P划分后，都能包含在U/R中；当ππ10k时，称Q部分（粗糙）依赖于P，在这种情况下，论域U上只有用P来分类时，属于U/R正区域的那些集合的元素才能正确地划分到Q中；若k=0，则Q完全独立于P的，论域上的所有元素都不能用P来分类于U/Q。定义1：一个近似空间(approximatespace)(或知识库)定义为一个关系系统K=(U,R)，其中U≠Φ(Φ为空集)是一个论域的集合，R是U上等价关系的一个族集。设P哿R，且P≠Φ，P中所有等价关系的交集称为P上的一种不分明关系(indiscernbilityrelation)，记作IND(P)[x]IND(p)=IR缀P[x]R给定近似空间K=(U,R)，子集X哿U称为U上的一个概念(concept)，非空子族集P哿R所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)，称为基本知识(basicknowledge)，相应的等价类称为基本概念(basicconcept)；如果关系Q∈R，则关系Q就称为初等知识(elementaryknowledge)，相应的等价类就称为初等概念(elementaryconcept)。X的下近似：R*(X)={x:(x∈U)∩([x]R?X)}X的上近似：R*(X)={x:(x∈U)∩([x]R∩X≠φ)}X的边界区域：BNR(X)=R*(X)–R*(X)若BNR(X)≠φ，则集合X就是一个粗糙概念。POSR(X)=R*(X)称为集合X的R-正区域，NEGR(X)=U-R*(X)称为集合X的R-反区域。UpperApproximation:RX=Y{Y∈U/R:Y∩X≠Φ}LowerApproximation:RX=Y{Y∈U/R:YX}2.5粗糙集方法与其他方法的关系粗糙集概念在某种程度上与其他处理含糊和不精确问题而研制的数学工具具有相似之处，特别是和Dempster-Shafer（DS）证据理论和模糊（Fuzzy）集理论。但是粗糙集理论和它们有很大的区别，它的主要优势在于它不需要任何预备的或额外的有关数据信息，比如统计学中的概率分布、DS证据理论中的基本概率赋值、模糊集理论中的隶属度等。DS理论利用置信和似然推理函数作为主要的工具，而粗糙集理论利用上、下近似集。Fuzzy集理论无法计算出具体的含糊度，而粗糙集理论是可以计算的。粗糙集理论和Fuzzy集理论之间有一些重叠，但两者不能相互替代。在粗糙集理论中，模糊性是集合（概念）的性质，它是由集合的边界区域引起的；而不确定性是集合元素的性质，它与粗糙隶属函数有关。Fuzzy集理论是采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或领域专家给出，所以具有相当的主观性；而粗糙集理论则采用概念的上、下近似来处理模糊性，由此，也可以从给定的数据中导出类似的粗糙隶属函数。由它们之间的比较可以看出，这两种理论不是相互冲突，而是相互补充的。总之，粗糙集理论和Fuzzy集理论对于不完全的知识来说有各自独立的方法。尽管基本粗糙集理论与其他处理不确定性的理论相比，具有不可替代的优越性，但是仍然存在着某些片面性与不足之处。如对原始数据本身的模糊性缺乏相应的处理方法；对于粗糙集边界区域的刻画比较简单；粗糙集的分类通常是确定的。所以粗糙集通常不单独使用，它常与其他方法结合起来使用。另外针对粗糙集理论存在的问题，提出了一些扩展模型，如可变精度粗糙集模型、相似模型、基于粗糙集的非单调逻辑模型、与Fuzzy集合理论结合模型、与DS理论结合模型等，从而大大地提高了粗糙集的适应力和生命力。三、粗糙集在数据挖掘中的应用3.1分类规则在数据挖掘分类规则领域，利用粗糙集的决策属性和知识约简提出了一个在数据集中发现没有冗余属性的最小归纳依赖关系,由此简化了数据挖掘算法。由此解决了数据库中数据的深层利用，使挖掘出的分类规则的条件被简化。提高了分类规则的应用价值。3.2不确定性问题在数据挖掘的信息系统中，有一些属性是未知属性。则这些未知属性就很可能造成挖掘过程中的分类中断以及分类不明确，这就间接造成了不确定性问题的产生。而粗糙集恰是处理不确定性问题的一类有用的工具，因此两者的结合便可以有效的解决这个问题。3.3数据预处理在数据挖掘的数据的预处理阶段，粗糙集理论中的不可分辨关系可以将数据预处理中的不完备数据进行处理，使数据挖掘算法能解决属性值缺失的数据的处理。对于由冗余数据等其他原因产生的不确定数据，可以通过上近似集、下近似集来解决。3.4属性约简属性约简可以通过以下方法：一是通过构造启发函数判断各属性的重要性，从而对不重要的属性进行约简；二是依据近似精度对属性进行约简；三是利用可辨识矩阵的对称性。小结粗糙集的应用非常广泛，粗糙集与数据挖掘的结合，为更多研究提供了便利。粗糙集中的关系表同关系型数据库中的决策表相联系，可以为数据挖掘带来很大的方便。利用粗糙集的约简属性去掉数据处理中的多余属性等，都在数据挖掘方法中广泛被运用。参考文献[1]Z.Pawlak.Roughsets[J].InternationalJournalofComputerandInformationSciences,1982:11(5):341–356[2]张宏宇.粗糙集理论及其在数据挖掘中的应用研究[J].太原：山西大学2003届硕士研究生学位论文[3]王国胤.Rough集理论与知识获取[M].西安：交通大学出版社，2001[4]HYu,GWang，DYang.Knowledgereductionalgorithmsbasedonroughsetandconditionalinformationentropy[C].In:proceedingsofspie:dataminingandknowledgediscovery:theory,toolandtechnologyIV,volume4730:422–431[5]王国胤，于洪等.基于条件信息熵的决策表约简[J].计算机学报，2000:25(7):759–766[6]J.W.Grzymala–Busse,ChienPeiE.Wang.Classificationandruleindu