粗糙集与数据约简

第34卷第4期 2017年4月计算机应用与软件Computer Applications and SoftwareV o L34No. 4Apr. 2017基于MapReduce的高效粗糙集属性约简算法吕洁1刘利民1胡皎月1许志伟131(内蒙古工业大学信息工程学院内蒙古呼和浩特010080)2(中国科学院计算技术研究所北京100086)摘要针对粗糙集理论中传统的基于正域的属性约简算法和基于信息熵的属性约简算法无法得到最小约简集的问题，给出基于信息熵改进的属性约简算法，即先使用条件熵识别出重要度值最大的属性，使用正域进行约 简判断。

在此基础上，设计了高效的基于M a p R e d u c e的信息熵改进属性约简算法。

以真实海量气象数据为基础, 在H a d o o p集群上实现上述算法，验证了该算法的有效性和效率。

关键词 属性约简粗糙集理论信息熵中图分类号T P311文献标识码A D O I：10. 3969/j. issn. 1000-386x. 2017. 04.046EFFICIENT ROUGH SET ATTRIBUTE REDUCTION ALGORITHMBASED ON MAPREDUCELii Jie1Liu Limin1H u Jiaoyue1X u Zhiwei1’21(College of Information Engineering, Inner Mongolia University of Technology ,Huhhot 010080, Inner Mongolia, China)2 (Institute of Computing Technology ^Chinese Academy of Sciences, Beijing 100086, China)Abstract Aiming at the problem that the traditional attribute reduction algorithm based on positive domain and the attribute reduction algorithm based on information entropy can ,t get the m i n i m u m reduction set in rough set theory,an optimized attribute reduction algorithm based on information entropy is proposed. T h e conditional entropy is used to identify the attribute with the highest significance value, and the positive domain is used to the reduction judgment. O n this basis,an efficient algorithm of information entropy improved attribute reduction based on M a p R e d u c e is designed. Based on the real meteorological data, the algorithm is implemented on H a d o o p cluster, and the effectiveness and efficiency of the algorithm are verified.Keywords Attribute reduction R o u g h set theory Information entropy熵改进属性约简算法，通过真实海量气象数据，验证了 〇弓丨言算法的有效性。

基于遗传算法的粗糙集知识约简摘要:知识约简是粗糙集理论的核心内容之一。

本文通过知识表达系统中条件属性对决策属性的重要性,来描述由条件属性所提供的知识对整体决策的重要程度,利用遗传算法,提出一种基于遗传算法的粗糙集知识约简方法。

关键词:遗传算法;粗糙集;知识约简粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。

其主要思想就是在保持分类能力不变的前提下,通过知识约简,导出问题的决策或分类规则。

目前粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域,成为近年来的热点研究方向。

知识约简是粗糙集理论的核心内容之一。

众所周知,知识库中知识(属性)并不是同等重要的,甚至其中某些知识是冗余的。

知识约简,就是在保持知识库分类能力不变的条件下,删除其中不相关或不重要的知识,使得高维数据降为低维数据,从而有效地实现数据缩减、减少冗余信息,是知识发现中的重要步骤。

1知识约简的相关概念定义1K=(U, R)为一个知识库,其中U≠是对象的有限论域,R是U上的所有等价关系的集簇。

显然,如果P∩R,P≠,则∩P(P中所有等价关系的交集)也是一个等价关系,称为P上的不可区分关系,记为ind(P)。

定义2令R为一族等价关系,R∈R,如果ind(R)=ind(R-{R}),则称R为R中不必要的;否则R为R中必要的。

定义3如果每一个R∈R都为R中必要的,则称R为独立的;否则称R为依赖的。

定义4设Q∈P,如果Q是独立的,且ind(Q)= ind(P),则称Q为P的一个约简。

显然,P可以有多种约简。

P中所有必要关系组成的集合称为P的核,记作core(P)。

核与约简有如下关系core(P)=∩red(P)其中red(P)表示P的所有约简。

定义5令K=(U,R)为一个知识库,且P,Q∩R,当时,我们称知识Q是k(0≤k≤1)度依赖于知识P的,记作P Q 。

定义6设S=(U,A,V,f )为一个知识表达系统,A=C∪D,C∩D≠,其中C和D分别条件属性集和决策属性集,属性子集C’∩C关于D的重要性为特别当C ‘={a}时,属性a∈C关于D的重要性为传统的约简算法,主要是从粗糙集的核出发,采用启发式搜索的方法构造所含条件属性最少的约简,即最小约简。

如何使用粗糙集理论进行数据预处理粗糙集理论是一种用于数据预处理的有效工具。

在现实生活中，我们经常面临着大量的数据，而这些数据中往往包含着冗余、不完整和模糊的信息。

为了更好地处理这些数据，提取有用的信息，粗糙集理论应运而生。

粗糙集理论是由波兰学者Zdzislaw Pawlak于1982年提出的，它通过对数据进行粗糙化处理，将数据集分为精确和不确定两个部分。

通过粗糙化处理，可以消除数据中的冗余信息，提取出核心和边缘的概念，从而更好地理解数据。

数据预处理是数据挖掘中的重要步骤，它包括数据清洗、数据集成、数据转换和数据规约等过程。

粗糙集理论在数据预处理中可以发挥重要作用。

首先，它可以帮助我们发现数据中的冗余信息。

冗余信息是指在数据集中存在多余的、重复的或无用的信息。

通过粗糙集理论，我们可以对数据进行粗糙化处理，去除冗余信息，从而减少数据集的大小，提高数据处理的效率。

其次，粗糙集理论可以帮助我们处理数据中的不完整信息。

不完整信息是指在数据集中存在缺失、不确定或不可靠的信息。

通过粗糙集理论，我们可以对数据进行粗糙化处理，将不完整的信息转化为精确和不确定两个部分，从而更好地处理数据中的不确定信息。

另外，粗糙集理论还可以帮助我们处理数据中的模糊信息。

模糊信息是指在数据集中存在模糊、不明确或模糊的信息。

通过粗糙集理论，我们可以将模糊信息转化为精确和不确定两个部分，从而更好地处理数据中的模糊信息。

在使用粗糙集理论进行数据预处理时，我们需要注意一些问题。

首先，我们需要选择合适的粗糙集算法。

目前，有许多粗糙集算法可供选择，如基于属性约简的粗糙集算法、基于属性约简和决策规则的粗糙集算法等。

我们需要根据具体的数据集和预处理目标选择合适的算法。

其次，我们需要考虑数据预处理的效果。

数据预处理的目的是提取有用的信息，减少冗余和不确定信息。

因此，在使用粗糙集理论进行数据预处理时，我们需要评估预处理的效果，判断是否达到了预期的目标。

粗糙集约简方法简介粗糙集约简方法是数据挖掘领域中一种常用的特征选择方法。

在众多特征选择方法中，粗糙集约简方法以其简单快速、易于理解的特点而受到广泛关注。

它通过粗糙集理论的基本原理，对原始数据集进行约简，从而得到一个更精简的特征子集，提高数据挖掘效率。

粗糙集理论基础粗糙集理论是由波兰学者Pawlak于1982年提出的，是一种处理不确定性信息的方法。

它基于集合论和近似推理，并尝试解决数据集中存在的不确定性和模糊性问题。

在粗糙集理论中，将数据集划分为对象的集合和属性的集合，并使用近似关系来描述属性与对象之间的关系。

约简的概念与意义约简是指通过对原始数据集进行操作，得到一个特征子集，该子集包含了原始数据集中的重要、有用的特征信息，而丢弃了无关、冗余的特征信息。

约简的过程就是在保持数据集中信息完整性和准确性的基础上，减少特征的数量，提高数据挖掘的效率。

约简所起到的作用有以下几个方面： - 减少特征的数量，提高数据挖掘算法的效率和性能； - 去除冗余信息，减少数据挖掘模型的复杂度； - 提高数据可视化效果，减少特征数量可以降低维度，更方便数据的可视化和分析。

粗糙集约简方法的步骤粗糙集约简方法一般包括以下几个步骤：1.确定属性集合和决策集合：首先确定数据集中的属性集合和决策集合。

属性集合是指数据集中待选择的特征集合，决策集合是指用于分类或预测的结果集合。

2.计算属性间的依赖度：使用粗糙集理论中的依赖度指标，计算属性集合中各个属性之间的依赖程度。

具体来说，可以计算属性集合中每个属性与决策集合之间的依赖度，衡量该属性对于分类结果的贡献程度。

3.确定依赖度阈值：根据需求和实际情况，确定一个依赖度阈值。

该阈值可以根据经验选择，也可以通过交叉验证等方法进行确定。

4.生成约简的特征子集：根据依赖度阈值，从属性集合中选择具有较高依赖度的特征，构成约简的特征子集。

5.验证约简的质量：使用约简的特征子集，进行数据挖掘任务，比如分类、预测等。

粗糙集理论的数据预处理方法及其效果评估引言：在当今大数据时代，数据的处理和分析变得尤为重要。

然而，原始数据往往存在噪声、缺失值和冗余等问题，这些问题会对数据分析的结果产生负面影响。

因此，数据预处理成为了数据分析中不可忽视的一环。

本文将介绍粗糙集理论在数据预处理中的应用方法，并对其效果进行评估。

一、粗糙集理论的基本原理粗糙集理论是一种用于处理不确定性和不完备性数据的数学工具。

它最早由波兰学者Pawlak于1982年提出，被广泛应用于数据挖掘、模式识别和决策支持等领域。

粗糙集理论的核心思想是通过近似描述来处理不完备和不确定的信息，通过建立决策规则集来实现数据的分类和预测。

二、粗糙集理论在数据预处理中的应用方法1. 数据清洗数据清洗是数据预处理的第一步，它主要是对原始数据进行噪声和异常值的检测与处理。

粗糙集理论可以通过属性约简和决策规则的生成来实现数据清洗。

属性约简可以帮助我们找出对数据分类和预测最重要的属性，从而减少数据的冗余和噪声。

决策规则的生成则可以帮助我们发现数据中的异常值，并进行相应的处理。

2. 数据集成数据集成是将来自不同数据源的数据进行合并和整合。

在数据集成过程中，往往会出现数据的冗余和冲突。

粗糙集理论可以通过属性约简和决策规则的生成来解决这些问题。

属性约简可以帮助我们找出不同数据源中相同属性的重要性，从而减少冗余。

决策规则的生成则可以帮助我们发现不同数据源中的冲突，并进行相应的处理。

3. 数据变换数据变换是将原始数据转化为适合分析的形式。

在数据变换过程中，往往需要对数据进行规范化、离散化和降维等处理。

粗糙集理论可以通过属性约简和决策规则的生成来实现数据变换。

属性约简可以帮助我们找出数据中最重要的属性，从而减少数据的维度。

决策规则的生成则可以帮助我们发现数据中的规律和模式，并进行相应的变换。

三、粗糙集理论在数据预处理中的效果评估1. 数据质量评估数据质量评估是评估预处理后数据的质量和可信度。

粗糙集属性约简的方法ComputerEngineeringandApplica~ons计算机工程与应用◎数据库,信号与信息处理@粗糙集属性约简的方法王培吉,赵玉琳27吕剑峰W ANGPeiii,ZHAOYulin,LVJianfeng1内蒙古科技大学数理与生物工程学院,内蒙古包头0140102内蒙古第一机械集团公司二分公司,内蒙古包头0140321.SchoolofMath.,Physics&BiologicalEng.,InnerMongoliaUniversityofSciencean dTechnology,Baotou,NeiMongol014010,China2.Branch2,InnerMongoliaFirstMachineryGroupCorporation,Baotou,NeiMongol01403 2,ChinaW ANGPeiji,ZHAOYulin,LVJianfeng.Newmethodofattributereductionbasedonroughse puterEngineeringandAp—plications,2012,48(2):113—115.Abstract:Objectsclassificationisstrictexcessivelyandtoosensitiveonnoise.Aimingatdeci sionsystemwithuncertainfactor.anal? gorithmofattributereductionbasedondependabilityisestablished.Theattributesinthesyste mwithuncertaininformationandnoisedataarereduced,wherebyfindingareducibleimpliedpatternofthedata,anddeletingthosere dundantrulesinthesystem.Anditcan keeptheoriginalpropertiesandfunctionsofthesystem.Theimplementationofalgorithmisd escribedbyintroducinganexample.Keywords:roughset;dependability;attributereduction;implementation摘要:传统粗糙集分类方法过于严格,对噪音过分敏感.针对带不确定因子决策系统,提出一种基于属性依赖度的约简算法,使含不确定信息及数据噪音的系统中的属性得以简化,找到一种具有广泛表达能力的数据隐含格式,删去冗余的规则,并保持系统的原有用途和性能.通过一个例子实现了该算法.关键词:粗糙集;依赖度;属性约简DOI:10.3778/j.issn.1002—8331.2012.02.032文章编号:1002.8331(2012)02.0113.03文献标识码:A中图分类号:TP311基于粗糙集理论】的知识获取的核心问题之一是属性约简,有很多学者作了这方面的工作,其中应用较多的是基于辨识矩阵以及在此基础上的一些改进算法1.一般说来,知识库中的知识(属性)并不是同等重要的,还存在冗余,这不利于做出正确而简洁的决策.属性约简要求在保持知识库的分类和决策能力不变的条件下,删除不相关或不重要的属性.一般而言,较优的属性约简有如下指标:约简后属性个数较少;约简后规则数目较少;最终范化规则数目较少等.已证明求决策表所有约简和最小约简是一个典型的NP嘲问题,不过,在实际应用中,往往只要求出某种次优的属性约简就可以了.传统粗糙集分类方法过于严格,以及数据中存在噪音,造成知识的遗漏.如:条件属性下的两个等价类.,,分别有100个元素,对决策属性等价类,,只有一个元素属于,而,只有一个元素不属于,基于传统的粗糙集模式,,,同属于的边界区,对都不能作出肯定的判断,然而A,中只有一个元素不属于,也许是由噪音导致的,说明传统粗糙集对噪音是非常敏感的,而在机器学习,专家系统等实际应用中,获得的数据含有噪音是不可避免的,因此传统粗糙集模式在一定程度上限制了它更有效的应用,本文提出的针对带不确定因子决策系统的分类方法可将原来由于噪音的影响,被划到边界的等价类划回到正区(如上面的,)或负区(如上面的),克服了粗糙集对噪音过分敏感的缺点,使在有噪音的环境下获得的知识更可靠.1带不确定因子决策系统定义1称=fU,CUD,{},,imp}为带不确定因子的决策系统,记为S,D=},d是带不确定因子(0<-I.t1)的结论属性,=1表示该元素对结论有完全肯定的判断,即该元素所在等价类属于结论属性的正区POSB(D),=0表示该元素对结论有完全否定的判断,即该元素所在等价类属于结论属性的负区NEG09);imp是中元素在中的重要度,体现元素在中的重要性./1,imp由领域知识及数据库操作得到.如表1为一带不确定因子的决策系统.表1带不确定因子的决策系统075O.67O-350750.670_35表1中U={1,2,3,4,5,6),条件属性集C={日1,口2),1={1,2),2={1,2,3),决策属性D={,={1,2,3),每一元素的重要度imp={4,3,4,4,3,4},及不确定因子={O.75,0.67,0.35,0.75,0.67,0.35}.基金项目:国家自然科学基金(No.81060238).作者简介:王培吉(1968一),男,副教授,主要研究领域为数据库,数据挖掘;赵玉琳(1968一),男,高级工程师;吕剑峰(1984_),男,助教.E-mail:*************收稿日期:2011-01.24;修回日期:2011-04.26;CNKI出版:2011-07—25;/kcms/detail/11.2127.TP.20110725.1624.020.html ComputerEngineeringandApplications计算机工程与应用2属性依赖度与属性约筒2.1属性依赖度定义2在S中,BcC,,YcU/B且处于边界,划POSB(D):rflJY;~IJ)kNEG口(D)的误差p()和,l(】,)分别定义为: ):—Z—(impi_x(1一-,ui))厶l州,,?(y):—~.,(im_Pixiai)乙Ilnl划入正区和y划入负区的误差水平分别记为,.即:p()P时,XcPOSB(D);n(】,)≤Ⅳ时,YcNEG口(D●.定义3对,在误差水平为和下,结论屙陛d对条件属性集合C依赖度Dep(C,D,,)是U/C被划入正区POSc(D)和Y划入负区NEG(D)中元素重要度的和与所有元素重要度之比.2.2属性约简定义4在中,误差水平为P和,BC,a∈B,Dep(B,D,,Ⅳ)=Dep(B-{a},D,,aN),称a为B中可省略的,否则a为当中不可省略的;当所有a∈B在中不可省略的,且Dep(B,D,,Ⅳ)=Dep(C,D,,Ⅳ),即D对B,C有相同的依赖度,则是c的一个约简u.定义5在S中U/C={,,…,},称)为的辨识矩阵,其中,"一C:a(X)~a(Xj),D()≠D()}1,其他'其中l≤f,j<t.m包含使得,具有不同结论属性值的所有属性.称/=,vm为S的分辨函数,其中V表示m中所有属性的析取运算,^表示合取运算.如果一个属性在信息系统中是可省略的,删除此属性并不影响信息系统的依赖关系,且能与c一样分辨所有元素的属性子集,但这样的约简不是唯一的,co~(c1表示C的所有约简的交集.核.表1表示的带不确定因子信息系统中P=0.3,=0.6条件属性C的等价类:={l}={2}={3}={4}={5}={6}由P()={{4×(1.0—0.75)j=0.25P()={{3x(1.0—0.67)}=0.33P()={4×(1.0～o.75)}:0.25P()={{3×(i.0一o.67)}:0.33Ⅳ()={4×0_35))=0.35Ⅳ(x6):{4×0_35)}=0.35及P=0.3,Ⅳ=0.6得P(D):{,(D):{,}BND(D)={,}DEP(C,D,P,Ⅳ)=I-(4+4+4+4)=0.73等价类,划回到正区,等价类,划回到负区;而用传统粗糙集进行分类,它们却都属于边界类,造成了知识的遗漏和偏差.3基于属性依赖度的属性约简算法步骤1根据挖掘目标,选取一屙l生为结论屙陛,其余为条件属性;对数据进行归纳,形成宜于实施挖掘的数据形式,同时,结合统计结果及领域知识为每一对象赋一重要度imp及不确定因子,形成带不确定因子的决策系统=(￡,,CUD, {},imp).步骤2由及不可分辨关系形成条件属性等价类和结论属性等价类,对处于边界的等价类,根据,imp及和划入正区和负区,由新的等价类形成可辨识矩阵.步骤3由可辨识矩阵找出该不可分辨关系的核B=COl~(C).步骤4C=C—B.步骤5对每一属性a∈C,计算Dep(BU{a},D,,,)一Dep(B,D,P,Ⅳ)并按降序排列C.步骤6DoJl[~序取a∈C,B=BU{a},C=C一{a}计算Dep(B,D,p,Ⅳ)UntilDep(B,D,P,Ⅳ)=Dep(C,D,dP,Ⅳ)步骤7For/=1to1B1Do如果a诺co~(c),则B:-{a}若Dep(B,D,,ON)~:Dep(C,D,P,Ⅳ)则B=BU{a.1.步骤8得条件属性c的约简为子集B.步骤9由约简简化带不确定因子的决策系统,形成由约简属性集为条件属性的决策系统S=,BU{d}).步骤10合并相同和相近元素(若结论相同,条件中仅有一项不同,则该项对该结论无关紧要).步骤11知识表示.4实例分析决策系统=,CU{d}),按结论属性d排序,为每一对象赋一重要度imp及不确定因子(如可将条件属性下每一等价类元素个数作为该对象的重要度imp),得到带不确定凶子的决策系统=(,CUD,{}c,,imp),见表2.由表2得条件属性C的等价类为={1),:{2}1={3},={4},={5,12},:{6j,={7,9},={8},=flo},Xl.:{1l},={13},:={14,15}.合并等价类得表3,进而得辨识矩阵(见表4).由可辨识矩阵得COl~(C)={a3}.:CORE(C)={a3),C={Ⅱ1,a2,a4,a5}.对每一属性a∈C,计算Dep(BU{aD,,).王培吉,赵玉琳,吕剑峰:粗糙集属性约简的方法2012,48(2)115 表2带不确定因子的决策系统表3=U,CUD,{)Ⅲ,,帅)表4辨识矩阵910l1a2a4a2a3a5ala2a3a5a2a4a2a3a5ala2a3a5a2a4a2a3a4a5dla2a3a4a5a2a4a2a3a4a5ala2a3a4a5ala4a5ala3a4a5a3a4a5a1a2a4ala2a3a4a5a1a2a3a4a5a2a4a5a2a3a4ala2a3a4a2a3a4a2a3a4a5ala2a3a4a5a3a4a2a3a4a3a2a3ala2a3a5ala3a3a5由条件属性co~(c)U{al}的等价类为={1,5,6,7,8,9,12,13},={2},={3),:{4,10},={14,15}及)=(1×(1—0.6)×2+2×(1—0.9)×4+1×(1—0.8)+l×(1—0.9))/12=0.158,z()=(1×0.6×2+2×0.9×4+1×0.8+1×0.9)/12=0.842 p(x2)p(X3)1×(1—0.9)/1=0.1n()n(X3)1x0.9/1=0.9P(X4)=(1×(1—0.9)+1×(1—0.8))/2=0.15H()=(1×0.9+1×0.8)/2=O.85)(2×(1—1)+2×(1—1))/4=0n(Xs)=f2×1+2x1)/4=l得正区等价类为={2)={3)x4={4,10}={14,15};边界等价类为={1,5,6,7,8,9,12,13).这样Dep(CORE(C)U1}, D,P,Ⅳ)=9/21.同理可得:Dep(CORE(C)U{a2},D,P,Ⅳ)=21/21Dep(CORE(C)[J{a4},D,,Ⅳ)=19/21Dep(CORE(COU{a5},D,P,Ⅳ):9/21按依赖度降序排列C={a2,a4,al,a5}B=cD衄(c)U{a2}:{a2,a3}Dep(B,D,P,Ⅳ)=21/21B=曰U{a4)={a2,a3,a4}可求得:Dep(B,D,,Ⅳ)=19/21a2硭CORE(C),贝0B=B-{a2)={a3,a4)又Del~B,D, P,Ⅳ)=19/21DIC,D,P,aN).这样,求得条件属性c的约简为子集B={a3,a4,.由约简B={口3,a4},表3简化为表5.=3对应的五:a3=3,a4=2及五:a3=3,a4=3中仅有口4的值不同,将对应的a4值去掉合并墨,化为表6.表5决策系统"=",BU{d})表6决策系统=,BU{d})知识表示:{(口3=3)^(a4=1)}v{(a3=2)^(a4=2)}(=2)(a3=3)=3)(a3=4)^(a4=3)=4)5结束语本文针对带不确定因子决策系统,提出了一种基于属性依赖度的属性约简算法,本算法能从属性集合中有效去除冗余属性,使属性选择的结果更合理,数据噪音的影响更小,获得的知识更可靠.在大部分情况下本算法都能快速有效地找到属性子集的最优解或令人满意的次优解.(下转129页)m56789m¨刘兴阳,毛力:基于f分布变异的自适应差分进化算法2o12,48(2)129进化代数进化代数进化代数进化代数图1sphere函数寻优曲线对比图2R0senbr0ck函数寻优曲线对比图3Griewallk函数寻优曲线对比图4Ackley函数寻优曲线对比表1三种算法寻优结果比较5结论本文提出一种基于f分布变异算子的自适应差分进化算法:其一在变异过程中使用f分布变异算子有效地将高斯变异和柯西变异进行结合;其二根据进化的不同阶段,提出新的自适应方式来调节进化策略及交叉概率.通过采用四个典型测试函数对新算法进行测试,实验结果表明本文提出的改进算法具有较好的全局探索能力和局部开发能力.参考文献:[1】StornR,PriceK.Differentialevolution-asimpleandefficient heuristicforglobaloptimizationovercontinuousspaces[J].Jour- nalofGlobalOptimization,1997,11(4):341—359.【2]ZhangM,LuoW,WangXF.Differentialevolutionwithdynamic stochasticselectionforconstrainedoptimization[J].Information Sciences,2008,178(15):3043.3074.【3]3唐德翠,朱学峰.改进差分进化PID参数优化及在凝絮中的应用[j]. 计算机工程与应用,2009,45(24):204.206.[4】MaulikU,SahaI.Modifieddifferentialevolutionbasedfuzzy clusteringforpixelclassificationinremotesensingimagery[J]. PaaemRecognition,2009,42(9):2135-2149.【5】RahnamayanS,TizhooshHR,SalamaMMA.Opposition-based differentialevolution[J].IEEEComputationalIntelligenceSociety,2008,12(1):64—79.[6】潭跃,谭冠政,伍雪冬.基于交叉变异策略的双种群差分进化算法[J]. 计算机工程与应用,2010,46(18):9-12.[7】DasS,AbrahamA,ChakrabortyUK.Differentialevolutionusing aneighborhood—basedmutationoperator[J].IEEETransactions onEvolutionaryComputation,2009,13(3):526.553.【8】LanKuo-Tong,LanChun-Hsitmg.NotesonthedislinctionofGaussian andCauchymutations[C]//EighthInternationalConferenceonIn. telligentSystemsDesignandApplications,2008:272-277.[9】Y aoX,LiuY,LinG.Evolutinaryprogrammingmadefaster[J].IEEE TransactionsonEvolutionaryComputation,1999,3(2):82—102.【1O】周方俊,王向军,张民.基于t分布变异的进化规划【J].电子, 2008,36(4):667.671.(da接l15页)参考文献:【1】PawlakZ.Roughset[J].InterofComputerandInformationSci- ences,1982,11.【2】刘清,刘少辉,郑非.Rough逻辑及其在数据挖掘中的应用【J】.软件,2001,12(3):415—419.【3】刘银山,吴孟达,王丹.粗糙集中求取所有最小约简快速算法【J].计算机工程与科学,2007,29(I):97—100.[4】苗夺谦,胡桂荣.知识约简的一种启发式算法[J】.计算机研究与发展,1999,36(6):681.684.【51HuXiaohua,CerconeN.Learninginrelationaldatabases:a roughsetapproach[J].ComputationalIntelligence,1995,11(2):323.337.[6]胡或,李智玲,李春伟.一种基于区分矩阵的属性约简算法[J].计算机工程与应用,2007,43(9):178.181.[7】黄治国,王端.基于粗糙集的数据约简方法研究[J】.计算机工程与设计,2009,30(18).【8】WongSK,ZiarkoW.Onoptimaldecisionrulesindecisionta-bles[J].BulletinofPolishAcademyofScience,1985,33:693-696.(上接123页)【7】ZhuZhengyu,XuJingqiu,RenXiang,eta1.QueryExpansionBased onaPersonalizedWebsearchmodel[C]//ThirdInternationalCon- ferenceonSemantics,KnowledgeandGrid,2007:128—133.【8】ZhuZhengyu,ZhouZhi,YuChunlei.Aquantizedanalyzingmethod forfindingauser'sinterestedwebpagesbasedontheuser's browsingactionsandquerywords[C]//InternationalConference onWebInformationSystemsandMining,2009.【9】ZhuZhengyu,TianYunyan,YuanKunfeng,eta1.Animproved Webdocumentsclausteringmethord[J].JournalofComputational InformationSystems,2007,3(3):1087—1094.[10】蒋萍.基于用户兴趣挖掘的个性化模型研究与设计[D].苏州大学, 2005:39-40.[11】张敏,宋睿华,马少平.基于语义关系查询扩展的文档重构方法[J].计算机,2004(10).【l2】瞿瑞彩,谢伟松.数值分析【M】.天津:天津大学出版社,2001:2-3. [13】LovicS,LuMeiliu,ZhangDu.Enhancingsearchengineperfor- manceusingexpertsystems,informationreuseandintegration[C]g IEEEIntema~IonalConferenceonSept2006:567.572.^趔卿籁闺。

粗糙集理论中属性相对约简算法张腾飞,肖健梅,王锡淮(上海海事大学电气自动化系,上海200135) 摘　要:　粗糙集理论是近年来发展起来的一种有效地处理模糊和不确定性知识的数学工具,而求核与约简是粗糙集理论中的两个重要问题,现已证明求决策表所有约简和最小约简是一个典型的NP 难题.本文在分析粗糙集理论的基础上,发现了正区域的一些有用性质,提出了一种利用正区域直接求核的方法,并利用正区域的启发式信息给出了两种相对约简算法.关键词:　粗糙集;求核;相对约简;决策表中图分类号:　TP18 文献标识码:　A 文章编号:　0372-2112(2005)11-2080-04Algorithms of Attribute Relative Reduction in R ou gh Set TheoryZHANG Teng -fei ,XI AO Jian -mei ,W ANG Xi -huai(Depart me nt of El ectr ical and Aut omati on ,Shanghai Maritime Unive rs ity ,Shanghai 200135,C hina )Abstract :　Rough set is a valid mathematical theory developed in recent years ,which has the abilit y to deal with imprecise ,un -certain ,and vague in formation .The core and reduction of attributes are two imp ortant topics in the research on rough set theory .It has been proven that computing all the reductions and the optimal (minimal )reduction of decision table is a NP -hard problem .In this paper ,Rough set theory is deeply investigated ;a number of useful properties of the positive region are discovered .Based on the above findings ,we present a calculation algorith m for core directly .And then ,two algorithms for relative reduction based on the positive re -gion are designed .Key words :　rough set theory ;finding core ;relative red uction ;decision table1　引言 粗糙集理论是波兰数学家Z .Pawlak 教授提出来的一种新型的处理模糊和不确定性知识的数学工具[1,2].经过二十多年的研究和发展,粗糙集理论已经在决策与分析、故障诊断、模式识别、数据挖掘、系统建模、动态目标识别及跟踪等领域取得了很大的成功[3～6].粗糙集理论是以不可分辨关系为基础,通过引入上近似(upper approximation )集和下近似(lower approximation )集来描述一个集合.信息系统的求核与约简是粗糙集理论和应用研究的焦点问题.信息系统分为无决策信息系统和有决策信息系统,在实际应用中大多为有决策信息系统,用决策表来表示,它是粗糙集研究的主要对象,因此决策表信息系统的求核与约简的研究更为重要.由于求所有属性约简是NP 难题,因此到目前为止,还没有一个高效的求最佳与所有属性约简的算法.不过,在实际应用中,往往只要求出某种次优的属性约简就可以了.为此,人们已提出了若干个属性求核和约简算法,其中应用较多的是基于差别矩阵以及在此基础上的一些改进算法[7,8];文献9给出了基于信息论的方法,用信息熵作为选择重要属性的启发式信息;文献[10]基于变精度粗糙集理论,利用可辨识属性矩阵研究了不协调目标信息系统的知识约简算法;文献[11]将包含度概念和证据理论引入到粗糙集理论中,建立了包含度与粗糙集数据分析中的度量之间的关系,这几种方法的主要缺点是空间复杂度高,计算繁琐,不适用大规模数据.经过深入分析粗糙集理论,本文发现了正区域的一些性质,提出了一种直接求核的方法,并利用正区域的启发式信息给出了两种属性相对约简算法.实验结果表明,本文的方法简单有效.2　粗糙集的基本理论 决策表是一类特殊而重要的知识表达系统,多数决策问题都可以用决策表形式来表达,这一工具在粗糙集理论中起着重要的作用.决策表可以根据知识表达系统定义如下:设S =〈U ,R ,V ,f 〉为一知识表达系统,U 是论域,R =C ∪D ,C ∩D =Υ,C 称为条件属性集,D 称为决策属性集.V收稿日期:2004-03-01;修回日期:2004-09-25基金项目:国家自然科学基金(No .60074004);上海市教委科学研究重点项目(No .04F A02);上海市重点学科建设项目(No .T0602)第11期2005年11月电 子 学 报ACTA ELECTRONICA SINICA Vol .33　No .11Nov .　2005为属性值的集合,f:U×R※V是一个信息函数,它指定U中每一个对象x的属性值.具有条件属性和决策属性的知识表达系统称为决策表.定义1　在信息系统S中,对于属性子集P R,不可分辨关系定义为:IND(P)={(x,y)∈(U×U:a∈P,a(x)=a(y)}显然IND(P)也是等价关系,对象x在属性集P上的等价类[x]IN D(P)={y:y∈U,xIND(P)y}.U/R表示R的所有等价类.定义2　给定信息系统决策表S=〈U,R,V,f〉,对于每个子集X U和不可分辨关系P,X的下近似集和上近似集可以分别定义为:RX=∪{y∈U/R Y X}RX=∪{y∈U/R Y∩X≠Υ}.下近似集RX也称为X的R正区域,记为:PO S R(X).众所周知,知识库中知识(属性)并不是同等重要的,甚至其中有些知识是冗余的.这就需要知识约简.所谓知识约简就是在保持分类能力不变的条件下,删除其中不相关或不重要的知识.定义3　设R为一族等价关系,r∈R,如果IND(R)=IND(R-{r}).则称r为R中不必要的;否则称r为R中不必要的,不可以约简的.如果每一个r∈R都为R中必要的,则称R为独立的;否则称R为依赖的.设P R,若P是独立的,且IND(P)=IND(R).则称P为R的一个约简;R的约简往往不止一个,所有约简的交集称为核,记作Core(R).在信息系统决策表的应用中,需要研究条件属性的分类相对于决策属性的分类之间的关系,因此相对约简和相对核的概念十分重要.定义4　设P和Q为U中的等价关系,Q的P正区域记为PO S P(Q),即P OS P(Q)=∪X U/QPXQ的P正区域是U中所有根据分类U/P的信息可以准确划分到关系Q的等价类中去的对象集合.定义5　设P和Q为U中的等价关系,r∈P,如果PO S P (Q)=PO S(P-{r})(Q),则称r为P中Q不必要的,否则r为P 中Q必要的.如果P中每个r都为Q必要的,则称P为Q独立的.设R P,如果R为Q独立的,且P OS R(Q)=P OS P(Q).则称R为P的Q约简.P的所有Q约简的交集称为P的Q核.记为Co re Q(P). P的Q核是P中所有Q必要的原始关系构成的集合.3　属性求核算法 在粗糙集理论中,相对核与约简都是基于正区域而定义的.对于信息系统决策表S=〈U,R,V,f〉,其中U为论域,R =C∪D,设属性a i∈C,由不可分辨关系的定义可知关系C 要比(C-{a i})对U的分类细,再由定义4,显然有正区域的如下性质:性质1　PO S(C-{ai})(D)PO S C(D).定理1　a i是C中的一个属性,若满足PO S(C-{ai})(D)=PO S C(D)则a i不是C相对于决策属性D的核属性.证明:由定义5可知,若上式成立,则a i就是C中相对于决策属性D不必要的,显然,a i不是核属性.定理2　C中的一个属性a i是C相对于决策属性D的核属性的充分必要条件是PO S(C-{ai})(D)≠PO S C(D)证明:充分性.如果P OS(C-{ai})(D)≠POS C(D),根据定义5,a i 就是C中必要的,即为不可以约简的,为了说明属性a i为核属性,采用反证法.假设a i为非核属性,根据核的定义,至少有一个约简P 不包含属性a i.由于P为C的约简,且不包含a i,由性质1可得:P OS P(D)PO S(C-{ai})(D)POS C(D)根据约简的定义可知必然有P OS P(D)=P OS C(D)所以:PO S(C-{ai})(D)=PO S C(D)这与条件PO S(C-{ai})(D)≠PO S C(D)相矛盾.充分性得证.必要性.如果P OS(C-{ai})(D)=PO S C(D),由定理1可知a i一定为非核属性.所以如果a i为核属性,则PO S(C-{ai}) (D)≠PO S C(D).证毕.根据上述两个定理,我们可以得到一个基于正区域的直接求核算法.算法1　信息系统决策表相对核计算方法.输入:信息系统决策表S=〈U,R,V,f〉,R=C∪D是属性集合,C={a i i=1, 2,…,m}和D={d i i=1,2,…,n}分别称为条件属性集和决策属性集;输出:信息系统决策表相对核Cor e;Step1　求P OS C(D);Step2　令Co re=Υ;Step3　对条件属性集C中的每个属性a i,如果PO S(C-{ai})(D)≠PO S C(D)则Co re=Core∪{a i}.Step4　结束,集合Core为输出.4　属性相对约简算法 在决策表中不同的属性可能具有不同的重要性,为找出某些属性的重要性,通常的方法是从决策表中去掉这个属性,2081第　11　期张腾飞:粗糙集理论中属性相对约简算法考察没有该属性后分类的变化情况.若去掉该属性相应变化较大,则说明该属性比较重要;反之,说明该属性不是太重要,即重要性较低.这里我们应用正区域作为属性重要性的启发式信息,把pos =PO S C (D )-PO S (C -{r })(D )的大小作为属性重要性的判断条件.下面给出两个基于正区域的决策表约简算法.算法2是以核集为基础,逐步选择比较重要的属性加入该集合,直到满足条件POS Redu ct (D )=POS C (D ),Reduct 即为约简.算法3是把整个条件属性集C 作为一个约简,利用正区域的启发式信息逐步将该集合中不必要的属性约去,但仍满足上述条件,保证得到的属性集合Reduct 为约简.算法2　基于核的相对约简算法.输入:信息系统决策表S =〈U ,R ,V ,f 〉,R =C ∪D 是属性集合,C ={a i i =1,2,…,m }和D ={d i i =1,2,…,n }分别称为条件属性集和决策属性集;输出:信息系统决策表相对约简Reduct ;Step 1　计算决策属性D 对于条件属性C 的正区域PO S C(D );Step 2　计算条件属性C 相对于决策属性D 的核属性集Co re D (C );并令Reduct =Co re D (C );Rem =C -Cor e D (C ).Step 3　若Reduct =Υ,直接转下一步;若Reduct ≠ ,计算PO S Red uct (D ).如果P OS Redu ct (D )=PO S C (D ),则终止,Reduct 为约简.否则转下一步;Step 4　从Rem 中选择属性a i ,使下式的值最大:pos =PO S Rem (D )-PO S (Rem -{a i})(D )Reduct =Reduct ∪{a i }Rem =Rem -{a i }Step 5　若PO S Reduct (D )=PO S C (D ),则终止,输出约简为Reduct ;否则转Step 4.算法3　信息系统决策表相对约简计算方法.输入:信息系统决策表S =〈U ,R ,V ,f 〉,R =C ∪D 是属性集合,C ={a i i =1,2,…,m }和D ={d i i =1,2,…,n }分别称为条件属性集和决策属性集;输出:信息系统决策表相对约简Reduct ;Step 1　计算决策属性D 对于条件属性C 的正区域PO S C(D );Step 2　对每个属性a i 计算po s =PO S C (D )-PO S (C -{a i})(D );Step 3　令Reduct =C ;将属性a i 按po s 从小到大的顺序排列,对每个a i 执行操作:若PO S (Reduct -{a i})(D )=PO S C (D ),则属性a i 应约简,Reduct =Reduct -{a i };否则a i 不能被约简,Redu ct 不变;Step 4　结束.由粗糙集理论知道,任何决策表的相对核都是唯一的,而且包含在所有的相对约简之中,算法2把相对核作为约简算法的起点,逐步增加对决策分类能力较大的属性,直到满足由相对约简定义的条件,所以基本可以保证得到最小的约简;算法3则是以条件属性全体为基础,在保证对决策表分类不变的前提下,逐步消去对决策分类能力较小的属性,算法简单,只需对各个属性扫描一遍即可.5　实例分析 为了验证上述算法的有效性,本节选择了一个已知核与约简的Wong -Ziarko 决策表[12]和UCI 机器学习数据库[13]中的三个决策表进行计算,实验结果如表1所示.表1　求核与约简算法结果决策表实例数条件属性数算法1算法2算法3Wong -Ziarko decis ion table 219{D ,I }{A ,D ,E ,I }{B ,D ,F ,G ,I }BUP A liver disorders 3456{}{A ,B ,E }{C ,D ,E }Glas s Identification 21410{}{A }{A }Ionosphere Databas e35134{}{4,18,24}{30,33,34} 实验结果表明,算法2和3对于属性相对约简是有效的,并且大多情况下可以得到最小约简.对于Wong -Ziarko 决策表,算法3虽然没有得到最小约简,但也得到了次优约简.6　结论 决策表核的确定和属性约简算法是粗糙集理论研究的焦点问题,本文在深入理解粗糙集基本概念的基础上,发现了正区域的一些有用性质,在此基础上给出直接利用正区域的信息求属性核,并给出了两个求属性相对约简的算法,实验结果表明了算法的有效性.由于利用正区域作为属性约简的启发式信息,也仅是从等价关系分类能力的角度对属性重要性进行粗略度量,并不能严格分辨出各个属性的重要程度.因此,如何利用粗糙集理论知识来度量属性重要性以便可以简单的求取最小约简还有待进一步的研究.参考文献:[1]　Pawlak Z .Rough sets [J ].International Journal of Computer and Information Science ,1982,11(5):341-356.[2]　Pawlak Z .A rough set view on Bayes 'theorem [J ].Interna -tional Journal of Intelligent Systems ,2003,18(5):487-498.[3]　Tay F ,et al .Fault diagnosis based on rough set theory [J ].Engineering Applications of Artificial Intelligence ,2003,16(1):39-43.[4]　Zhang T F .Dynamic system modeling based on rough sets and RBF neural networks [A ].Proc of the 5th World Congress onIntelligent Control and Automation [C ].Hangzhou ,2004.185-189.[5]　徐捷等.基于粗糙集理论的动态目标识别及跟踪[J ].电子学报,2002,30(4):605-607.Xu Jie ,et al .Dynamic objects identifying and tracing based2082 电 子 学 报2005年on rough set theory[J].Acta Electronica Sinica,2002,30(4):605-607.(in Chinese)[6]　张文修,等.Rough集理论与方法[M].北京:科学出版社,2001.[7]　Hu X H,et al.Learnin g in relational databases:A rough setapproach[J].International Journal of Computational Intelli-gence,1995,11(2):323-338.[8]　刘文军,等.基于可辨识矩阵和逻辑运算的属性约简算法的改进[J].模式识别于人工智能,2004,17(1):119-123.[9]　王国胤,等.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766.[10]　Mi J S,et al.Approaches to knowledge reduction based onvariable precision rough set model[J].Information Sciences,2004,159(3):255-272.[11]　Zhang M,et al.A rough set approach to knowledge reductionbased on inclusion degree and evidence reasoning theory[J].Expert Systems,2003,20(5):298-304.[12]　Wong S K M,et al.On optimal decision rules in decision ta-bles[J].Bulletin of Polish Academy of Science,1985,33(11-12):693-696.[13]　/mlearn/MLRePOSitory.html[DB/OL].作者简介:张腾飞　男,1980年出生于河南省,博士研究生,主要从事粗糙集和神经网络的研究.肖健梅　女,1962年出生于辽宁省大连市,教授,主要从事智能控制,智能信息处理等方面的研究.王锡淮　男,1961年出生于江苏省淮安市,博士,博士生导师,主要从事粗糙集理论,复杂系统建模与控制等方面的研究.E-mail:wxh@.2083第　11　期张腾飞:粗糙集理论中属性相对约简算法。

如何利用粗糙集理论解决多源异构数据集成与融合的问题多源异构数据集成与融合是当今信息时代面临的一个重要问题。

随着数据量的不断增加和数据来源的多样化，如何将来自不同数据源的信息整合起来，提取有用的知识和信息，成为了一个亟待解决的难题。

在这个问题中，粗糙集理论可以发挥重要的作用。

粗糙集理论是一种处理不完备、不确定信息的数学工具，它可以用于对多源异构数据进行集成与融合。

其核心思想是通过粗糙集的近似计算方法，将不同数据源中的数据进行分类和归纳，从而得到一个更加全面和准确的数据集成结果。

首先，利用粗糙集理论可以解决数据集成的问题。

在多源异构数据集成过程中，不同数据源的数据格式和结构往往存在差异，这给数据集成带来了困难。

粗糙集理论通过对数据的粗糙度进行度量和计算，可以将不同数据源中的数据进行统一和整合。

通过对数据的粗糙度进行度量，可以找到不同数据源之间的相似性和差异性，从而实现数据的集成和统一。

其次，粗糙集理论还可以解决数据融合的问题。

在多源异构数据融合过程中，不同数据源的数据可能存在冲突和不一致的情况。

粗糙集理论通过对数据的粗糙程度进行度量和计算，可以找到数据之间的一致性和相似性，从而实现数据的融合和整合。

通过对数据的粗糙程度进行度量，可以找到数据之间的差异和冲突，从而实现数据的融合和整合。

此外，粗糙集理论还可以解决数据质量的问题。

在多源异构数据集成和融合过程中，不同数据源的数据质量可能存在差异和问题。

粗糙集理论通过对数据的粗糙度进行度量和计算，可以评估数据的质量和可信度。

通过对数据的粗糙度进行度量，可以找到数据的缺失和错误，从而提高数据的质量和可信度。

综上所述，粗糙集理论可以有效解决多源异构数据集成与融合的问题。

通过对数据的粗糙度进行度量和计算，可以实现数据的集成、融合和质量评估。

粗糙集理论在处理多源异构数据集成与融合问题中具有重要的应用价值。

未来，随着数据量的不断增加和数据来源的多样化，粗糙集理论将会在多源异构数据处理领域发挥更加重要的作用。