基于粗糙集的属性约简算法

《基于粗糙集的属性约简算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、软件天地《微计算机信息》(测控自动化)2009年第25卷第9-1期文章编号:1008-0570(2009)09-1-0212-02基于粗糙集的属性约简算法TheApproachforAttributesReductionBasedonRoughSetTheory(牡丹江师范学院)夏春艳李树平刘世勇XIAChun-yanLIShu-pingLIUShi-yong摘要:本文主要研究基于粗糙集理论的属性约简算法。提出了一种同时适合于相容信息表和不相容信息表的启发式约简算法,并通过算例验证了该算法的可行

2、性和有效性。关键词:粗糙集;属性约简;属性依赖度中图分类号:TP311文献标识码:AAbstract:ThispaperresearchesattributesreductionofRoughSetTheory.Putforwardaheuristicattributereductionalgorithmbasedonthetableofcompatibilityinformationandincompatibleinformationatsametime.Theexperimentalresu

3、ltsshowthatthealgorithmisverifiedtobemorefeasibleandeffective.Keywords:RoughSet;AttributeReduction;Attributedependencies技定义1.2设R是U上的等价关系,若PR且≠φ,那么∩引言术P(P中所有等价关系的交集)也是一个等价关系,称为P上的不粗糙集理论是由波兰华沙理工大学Z.Pawlak教授在1982可区分关系,记为ind(P)。U/R表示R的所有等价类构成的集创年提出的,是一种研

4、究不精确、不确定性知识的数学工具。该理合,[x]R表示包含元素x∈U的R等价类。论已经在数据挖掘、机器学习、过程控制、决策分析和模式识别定义1.3对于一个知识系统S=(U,V,f,R),PR,不可区分关新等领域得到了广泛的应用,并取得了良好的效果。属性约简就是系可用如下表示:在保持分类能力不变的前提下,通过对知识的化简导出问题的ind(P)={(x,y)∈U×U｜p∈P,f(x,a)=f(y,a)}决策或分类规则,是粗糙集理论中的一个重要研究课题。它的意如果(x,y)∈ind(P),则称x和y是

5、不可区分的。符号U/ind(P)义在于可以删除冗余信息,形成精简的规则库以便人们(或者机表示不可区分关系ind(P)在U上导出的分类,可简记为U/P。器人)作出快速、准确的决策。高效的约简算法是粗糙集应用于定义1.4给定知识库S=(U,R),对于每个子集XU和一个知识发现的基础,但属性的最小约简仍是个NP—hard问题。等价关系R∈IND(S),定义两个子集:目前,国内外已有很多关于属性约简的算法,如吕静基于分明矩阵的属性约简算法,胡可云基于属性频率的约简算法等等,这些算法简单、迅速并具有较好的

6、属性约简效果。但是,这些算分别称它们为X的R下近似集和R上近似集。集合法都是根据区分矩阵先求出属性的核,然后在核的基础上逐步称为X的R边界域称为的R扩展求出属性约简。而通过区分矩阵计算核的方法只能适合于正域;称为X的R负域。相容信息系统,对于不相容信息系统则不适合。本文为适应不相定义1.5令P和Q为U中的等价关系,Q的P正域记为容信息系统,给出对于相容和不相容信息系统都适用的求核方POSP(Q),即法,并根据属性的重要度提出一种启发式属性约简算法。实例证明,本算法在相容与不相容信息系统中都能求出

7、属性的核,并能定义1.6知识的依赖性可形式化地定义如下:令S=(U,R)是一个知识库,PR,QR,则知识Q依赖于知识P(记作P==>Q)当得到属性约简的较好结果。且仅当IND(P)IND(Q)。1粗糙集基本概念及相关定义令S=(U,R)为一知识库,且P,QR,当定义1.1信息系统S=(U,A,f,V),其中U为域;A是有限属性k=(Q)=

8、POSP(Q)

9、/

10、U

11、集,分为条件属性集C和决策属性集D,即A=C∪D,C∩D=Φ;V我们称知识Q是k度依赖于知识P的,记作P==>kQ。系数是属性集A的值

12、域;而f:A→V是从属性到值域的映射;信息系(Q)可以看作Q和P间的依赖度。定义1.7令C为条件属性的集合,D为决策属性的集合,在统常略写为(U,A)。已知条件属性R的前提下,一个属性a∈C-R关于决策属性D夏春艳:助教硕士研究生的重要度定义为:基金项目:基金申请人:李树平;项目名称:基于粗集SGF(a,R,D)=R∪

13、a

14、(D)-R(D)理论的属性约简算法的研究;基金颁发部门:黑龙江省2启发式约简算法教育厅(11531389);项目名称:不分明度量理论;牡丹江师范学院科学技术研究基金项目(NO