粗糙集在知识约简中的应用

摘要:将粗糙集应用于数据挖掘领域,能提高对不完整数据进行分析和学习的能力,属性约简能删除冗余属性,提高系统潜在知识的清晰度,降低发现规则的时间复杂性。目前已在人工智能、知识发现、模式分类等方面得到了应用。文中描述了粗糙集的基本理论,并通过实例分析了粗糙集理论在知识约简中的应用。

关键词:粗糙集;不可区分关系;知识;约简

中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)19-5295-02

Rough Set Knowledge Reduction Application

JI Sheng-jun

(Department of Soft Engineering Xi'an University of Finance and Economics, Xi'an 710100, China)

Abstract:Rough set data mining application, able to improve incomplete data, analysis and learning ability, attribute reduction can delete redundant attributes potential knowledge to improve the clarity of the system and reduce the time complexity of the rules found. Currently in artificial intelligence, knowledge discovery, pattern classification method can be applied. The article describes the basic theory of rough sets, and with an example of the rough set theory in knowledge reduction application.

Key words: rough set; not distinguish relationships; knowledge; reduction

粗糙集理论是由波兰数学家Z.Pawlak 教授提出的,用于研究不完整数据和不精确知识的表达,学习归纳的数学分析理论。粗集理论的核心思想是在保持分类能力不变的前提下,通过对知识的化简,导出问题的决策或分类规则。由于粗集理论不需要任何先验知识即可对已有知识进行处理,并提炼出隐含知识的特点,所以广泛应用于模式识别、机器学习、数据挖掘以及决策分析等领域,并取得了一定的成果。

1粗糙集中的基本概念

1.1 粗糙集的定义及性质[1-2]

设R?哿U×U是U上的一个等价关系,则R将U划分成不相交的子集,称这些不相交的子集为由R决定的等价类,也称为基本集或知识R的基本概念。同一等价类中的元素称为相对于R是不可分辨的。基本集的并称为相对于R是可定义集,空集也被认为是可定义集。称(U,R) 是一个近似空间,对任意的X?哿U, 如果X是不可定义的,则称X是粗糙的。对于粗糙集X可以分别定义X的下、上近似集合:

R={x:[x]R?哿X},RX={x:[x]R∩X≠?I}

下近似集合和上近似集合也可以用以下两个等价的公式来表示:

RX=∪{[x]R:[x]R?哿X, RX=∪{[x]R:[x]R∩X≠?I.

1.2 知识约简和核

定义1:令R为等价关系族,R∈R,如果有IND(R)=IND(R-{R}),则称R为R中不必要的;否则称R为R中必要的。如果每一个R∈R都为R中必要的,则称R为独立的;否则称R为依赖的。

定义2:设Q?哿R,若Q独立的,且IND(R)=IND(Q),则称Q是等价关系族P的一个约简,记作:RED(P)。P中所有不必要关系的集合称为等价关系族P的核,记作:CORE(P)。

定理1:等价关系族P的核等于P的所有约简的交集,即CORE(P)=∩RED(P)

1.3 相对约简和相对核

在应用中,一个分类(知识)相对于另一个分类(知识)的关系十分重要,因此需要引入知识的相对约简和相对核的概念[3-4]。

定义3:设P和Q为论域上的等价关系,Q的P正域记作POSP(Q),

定义4:设P和Q为论域上的等价关系族,R∈P,若有:

则称R为P中Q不必要的,否则称R为P中Q必要的。若P中的任一关系R都是Q必要的,则称P为Q独立的。

定义5:设S?哿P,称S为P的Q约简,当且仅当S是P的Q独立子族,且POSS(Q)= POSP(Q)。P中所有Q必要的原始关系构成的集合称为P的Q核,记作:COREQ(P)。

2 粗糙集在知识中的应用

给定一个知识库(U,S),其中,论域U={X0,X1,X2,……,X8},且S={R1,R2,R3},等价关系R1,R2,R3和IND(S)对应的等价类分别为[5]:

U/R1={{X1,X4,X6},{X2,X8},{X3},{X6,X7}};U/R2={{X1,X3,X6},{X6},{X2,X4,X7,X8}};

U/R3={{X1,X5},{X6},{X2,X7,X8},{X3,X4}};U/IND(S)={{X1,X5},{X2,X8},{X3},{X4},{X6},{X7}};

因为U/IND)S-{R1})= [xR]={{X1,X5},{X3},{X6},{X2,X7,X8},{X4}}U/IND(S)

所以,R1为S中必要的。同理,R2为S中不必要的。R3为S中不必要的。

显然,CORE(S)={R1}。因为

U/IND){R1,R2})=[xR] ={{X1,X5},{X3},{X6},{X2,X8},{X4},{X7}}=U/IND(S)

显然,U/IND({R1,R2}) U/R1,说明R1在IND({R1,R2})中为必要的。

同理,R2在IND({R1,R2})中为必要的。

因此,{R1,R2}?哿{R1,R2,R3}满足定义2,所以,它是{R1,R2,R3}的一个约简。可以推出{R1,R3}?哿{R1,R2,R3}。

以上可知,知识S={R1,R2,R3}有两个约简,即{R1,R2}和{R1,R3}

3 结束语

文章介绍了粗糙集理论的基本概念和应用实例,可以看出该理论可应用于发现对象和属性间的依赖,去除冗余数据,评价属性对分类的重要性,从而对信息系统中的知识进行约简。

参考文献:

[1] 贾俊芳.基于相对知识量重要度的属性约简算法[J].山西大同大学学报,2010(2):17-19.

[2] 冯林.基于粗糙集理论的不确定信息处理与知识获取方法研究[D].成都:西南交通大学,2004.

[3] 贾平.基于粗糙集理论的知识发现方法研究[D].杭州:浙江大学,2008.

[4] 裴小兵.粗糙集的知识约简研究[D].武汉:华中科技大学,2006.

[5] 妙夺谦,李道国.粗糙集理论、算法及应用[M].北京:清华大学出版社,2008.