【粗糙集在数据挖掘中的应用研究9100字】

粗糙集在数据挖掘中的应用研究目录TOC\o"1-2"\h\u7395粗糙集在数据挖掘中的应用 1293引言 140一粗糙集和数据挖掘的背景和研究现状 214837二数据挖掘的基本概念和任务 3311032.1数据挖掘的任务 332706（1）关联模式 315170（2）序列模式 31817（3）聚类模式 411519（4）分类模式 420919（5）回归模式 418499（6）时间序列模式 4324352.2数据挖掘的方法 429851（1）统计分析方法 420719（2）模糊集方法 49405（3）粗糙集理论 417952（4）决策树 517924（5）神经网络 510979（6）遗传算法 523701（7）可视化技术 5155522.3等价类和不可分辨关系 5148282.4粗糙集的上、下近似集 6125572.5粗糙集方法与其他方法的关系 726793三、粗糙集在数据挖掘中的应用 8286793.1分类规则 8327133.2不确定性问题 834883.3数据预处理 8247583.4属性约简 95585四案例分析 9160864.1医院流感患者诊断案例 9124064.2商业决策系统的应用案例 111146参考文献 14引言当今，社会已经进入了网络信息时代，计算机技术在这十几年来得到了迅猛的发展，特别是存储技术、数据库技术和网络技术。存储设备单位价格的不断下跌而容量的急剧扩大，关系数据库、对象数据库、多媒体数据库、地理信息数据库和空间数据库的不断成熟并得到广泛的应用，数据库管理系统的日益普及，自动数据采集系统的引入以及互联网络在全球的不断深入应用，这些都使得人们轻而易举地就可以获得容量达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属性约简属性约简可以通过以下方法：一是通过构造启发函数判断各属性的重要性，从而对不重要的属性进行约简；二是依据近似精度对属性进行约简；三是利用可辨识矩阵的对称性。小结粗糙集的应用非常广泛，粗糙集与数据挖掘的结合，为更多研究提供了便利。粗糙集中的关系表同关系型数据库中的决策表相联系，可以为数据挖掘带来很大的方便。利用粗糙集的约简属性去掉数据处理中的多余属性等，都在数据挖掘方法中广泛被运用。四案例分析4.1医院流感患者诊断案例例如在医院里有100例流感患者的诊断记录，根据记录得知其中有85%的患者伴有体温偏高，干咳，头痛，肌肉酸痛的症状。而剩余的15条规则可能伴有其它一些症状，其出现的概率自然远远小于那85条记录中所记录的体温偏高、干咳、头痛、肌肉酸痛的症状出现的概率。这样在诊治时如果患者伴有体温偏高，干咳，头痛，肌肉酸痛的症状，就有较大地把握说患者患了流感。由此可见对重复样本进行一定的处理在实际应用中还是很有利用价值的。为此笔者设计了如下的算法来对重复的样本进行处理。算法的核心思想是采用基于频率的算法对各条规则进行加权运算，得到一个带有重复权值的决策表（这里所说的重复权值就是某规则出现的次数与决策表中所有规则的条数的比值）。例如对于原始决策表6.1：在表6.1中共有7条规则，其中规则1出现的频率为5/7，而规则2出现的频率为1/7，规则5出现的频率为1/7。可以在决策属性栏后加上一个重复权值栏，得到表1：然后再分别进行属性约简和属性值约简，最后得到表2:即最后得到的规则为：b2c2→d2e0权值为5/7；b0→d0e1权值为1/7；C1→d1e1权值为1/7；在实际的应用中，可以根据用户需求定义最小的重复权值，从而获得满足用户要求的规则。该算法虽然增加了计算的复杂性，但是提高了用粗糙集方法进行正确决策的概率，也有利于在决策过程中发现个别的噪音数据。在一些决策支持系统中，可以根据数据样本的频率来制定决策，而不会被一些个别数据误导做出错误的决策。在例子里，发现在患者流感记录中存在的“非主流”的15条记录，其导致原因最起码有两种：一是由于输入错误引起的误差，二是可能还有其它的未知影响因素（也就是说，数据库中的知识可能是不完全的，按照现有的属性还不能够完全做出某些问题的结论）。若是第二种原因，就有必要对此进行更进一步的研究。因为每个人的流感症状未必相同。如果对这些数据进行深入的研究，那必定会发现新的“知识”，对传统的观念有新的突破，从而做出更加正确的决策。算法的核心思想同样是基于频率的矛盾加权算法。之所以采用加权运算而不采用支持度，是因为用支持度来处理统计信息时，可能会遗漏一些令人感兴趣的规则。为了减少对那些小支持度但重要的规则的遗漏，我们定义了一个矛盾权值。对于符合最后约简规则的数据，统统把其权值设为0，而对那些不符合最后约简规则的，则另外加入该规则表，其矛盾权值为与对相同样本的处理一样，在实际的应用中，可以根据用户需求定义最小的矛盾权值，从而获得满足用户要求的规则。事实证明，该算法虽然增加了计算的复杂度，但是能更加有效地发现隐藏在数据决策表后的信息，避免由于缺乏对某些事例的深入了解，而将其错误地划分到其它类里，从而做出更加正确的决策。因此该算法在某些特定的环境里（如诈骗识别、入侵检测等）还是大有用武之地的。4.2商业决策系统的应用案例设计思想:根据所给领域知识,通过机器学习形成决策系统.决策系统原则上分为条件属性和结论属性,根据所给的数据信息.找出一个或多个库中一个或多个属性之间的潜在规则.这种规则是对海量的数据进行挖掘处理而得出来的,有相当高的可信度,可作为将来经销决策之用.但该思想可广泛应用于司法、金融、气象等等不同领域.对于本实例设计,是以找出客户所在区域与所购买商品的品牌、类别、规格之间的关系.系统功能如图1所示.通过以图2所示几个步骤,运用所提供的领域知识,可以提取出商品的类别、品牌、规格和地域等各种属性。系统要求提供商业企业在经营管理决策时所需的各种市场信息,包括市场供需、商品库存及品牌类别等各种信息.本次设计只从商品的类、品、格与地域之间是否存在某种联系进行考虑.根据置信度的计算公式以及预先设定的阀值[3],从而淘汰置信度小于阀值所对应的记录,余下的就是我们所想要的最终的数据决策系统如表2.可以推出四者之间潜在的联系,因为整个设计过程是运用海量的数据信息,故这种联系具有客规性.在商业决策系统的实现过程中高效算法是非常关键的.如果算法是指数级或更高级,那么将它用于特别大规模的数据,产生的运算量将是难以忍受的.尽管发现任意规则的通用算法不存在,但我们可一些方法如限制规则类型,使用近似算法,仔细选择样本来避开这个问题.将来的系统需要在很多层次上的一致性.通过访问现在的数据库和数据字典,这些系统将能不同的把学习和发现方法结合起来.挖掘出的知识不会独立存在,将重新被输入以发现更多的知识,或用于其他的系统.递近的、基于知识的交互式系统可将现实的静态数据库变为将来深化的信息系统[4].通过对算法的具体实施,基本达到设计要求,能够挖掘出4种属性之间潜在的联系.为完成商业决策系统的研究提供了理论基础。数据挖掘系统所涉及的数据库大多为大型数据库,种类繁多,有关系型数据库、事务数据库、工程数据库、多媒体数据库等.现在还不可能作出一种数据开采系统,使它从各种数据库中都能有效地提取知识,大多系统都是针对一种数据库而设计.从关系数据库中提取知识,因为关系数据库是使用最广泛的数据库.粗糙集理论的出发点是,根据目前已有的对给定问题的知识将问题的论域进行划分,然后对划分后的每一个组成部分确定其对某一概念、肯定不支持此概念和肯定支持此概念和可能支持此概念.在粗糙集理论中,以上3种情况分别用3个近似集合来表示为上近似、下近似和边界.为描述方便,可以采用文献[1]提出的知识表示系统和决策系统对问题进行描述,这样,粗糙集的方法和模型就可以建立一种非常直观的二维表的基础上.刚好适合现阶段在商业领域广泛应用的关系数据库。参考文献[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:proceedingsof