基于粗糙集的属性约简算法夏春艳1李树平2刘世勇3牡丹江师范学院计算机科学与技术系,黑龙江省牡丹江市157012TheApproachforAttributesReductionBasedonRoughSetTheoryAbstract:ThispaperresearchesattributesreductionofRoughSetTheory.Putforwardaheuristicattributereductionalgorithmbasedonthetableofcompatibilityinformationandincompatibleinformationatsametime.Theexperimentalresultsshowthatthealgorithmisverifiedtobemorefeasibleandeffective.Keywords:RoughSetAttributeReductionAttributedependencies摘要:本文主要研究基于粗糙集理论的属性约简算法。提出了一种同时适合于相容信息表和不相容信息表的启发式约简算法,并通过算例验证了该算法的可行性和有效性。关键词:粗糙集属性约简属性依赖度中图分类号:TP311文献标识码:A0引言粗糙集理论是由波兰华沙理工大学Z.Pawlak教授在1982年提出的,是一种研究不精确、不确定性知识的数学工具[1]。该理论已经在数据挖掘、机器学习、过程控制、决策分析和模式识别等领域得到了广泛的应用,并取得了良好的效果。属性约简就是在保持分类能力不变的前提下,通过对知识的化简导出问题的决策或分类规则,是粗糙集理论中的一个重要研究课题[2]。它的意义在于可以删除冗余信息,形成精简的规则库以便人们(或者机器人作出快速、准确的决策。高效的约简算法是粗糙集应用于知识发现的基础,但属性的最小约简仍是个NP—hard问题。目前,国内外已有很多关于属性约简的算法,如吕静[3]基于分明矩阵的属性约简算法,胡可云[4]基于属性频率的约简算法等等,这些算法简单、迅速并具有较好的属性约简效果。但是,这些算法都是根据区分矩阵先求出属性的核,然后在核的基础上逐步扩展求出属性约简。而通过区分矩阵计算核的方法只能适合于相容信息系统,对于不相容信息系统则不适合。本文为适应不相容信息系统,给出对于相容和不相容信息系统都适用的求核方法,并根据属性的重要度提出一种启发式属性约简算法。实例证明,本算法在相容与不相容信息系统中都能求出属性的核,并能得到属性约简的较好结果。基金项目:申请人:李树平;项目名称:基于粗集理论的属性约简算法的研究基金颁发部门:黑龙江省教育厅;编号:11531389;牡丹江师范学院科学技术研究基金项目:项目名称:不分明度量理论(NO.KY20080071粗糙集基本概念及相关定义定义1.1信息系统S=(U,A,f,V,其中U为域;A是有限属性集,分为条件属性集C和决策属性集D,即A=C∪D,C∩D=Φ;V是属性集A的值域;而f:A→V是从属性到值域的映射;信息系统常略写为(U,A。定义1.2设R是U上的等价关系,若P?R且≠φ,那么∩P(P中所有等价关系的交集也是一个等价关系,称为P上的不可区分关系,记为ind(P。U/R表示R的所有等价类构成的集合,[x]R表示包含元素x∈U的R等价类。定义1.3对于一个知识系统S=(U,V,f,R,P?R,不可区分关系可用如下表示:ind(P={(x,y∈U×U∣?p∈P,f(x,a=f(y,a}如果(x,y∈ind(P,则称x和y是不可区分的。符号U/ind(P表示不可区分关系ind(P在U上导出的分类,可简记为U/P。定义1.4给定知识库S=(U,R,对于每个子集X?U和一个等价关系R∈IND(S,定义两个子集:{}/|YURYX=∈?U{}/|YURYX=∈≠?IU分别称它们为X的R下近似集和R上近似集。集合(RBNX=-称为X的R边界域(RPOSX=称为的R正域;(RNEGXU=-称为X的R负域。定义1.5令P和Q为U中的等价关系,Q的P正域记为POSP(Q,即/(PXUQPOSQ∈=U定义1.6知识的依赖性可形式化地定义如下:令S=(U,R是一个知识库,P?R,Q?R,则知识Q依赖于知识P(记作P?Q当且仅当IND(P?IND(Q。令S=(U,R为一知识库,且P,Q?R,当k=γP(Q=|POSP(Q|/|U|我们称知识Q是k度依赖于知识P的,记作P?kQ。系数γP(Q可以看作Q和P间的依赖度。定义1.7令C为条件属性的集合,D为决策属性的集合,在已知条件属性R的前提下,一个属性a∈C-R关于决策属性D的重要度定义为:SGF(a,R,D=γR∪|a|(D-γR(D2启发式约简算法计算属性的最小约简已被证明是NP-hard问题,为降低约简的复杂性,并获得较优的结果,应采用启发式算法。为此,粗糙集提出了核的概念,核是所有约简中不可缺少的属性。而利用区分矩阵求属性的核只适合于相容决策表,为此给出对于相容与不相容信息系统都适合...
