基于数据分析方法的属性简约算法的实现

摘要：属性约简是粗集理论中的研究热点之一。 文章通过数据分析方法讨论了属性约简问题，该算法直观，易于理解，能计算出所有的约简，克服了启发式算法的不完备性，以及基于区分矩阵的属性约简算法中出现时间和空间浪费的问题。实例表明，该法是行之有效的。

关键词：粗糙集理论；数据分析方法；信息系统；决策表；属性约简

中图分类号：TP18 文献标识码：A文章编号：1009-3044(2007)06-11651-01

1 引言

粗糙集（Rough Set）理论[1]是波兰数学家Z.Pawlak于1982年提出的，它建立在完善的数学基础之上，是一种新的处理含糊性和不确定性问题的数学工具。其主要思想是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则[2]。由于粗糙集理论不需要任何预备或额外的有关数据信息，使得粗糙集理论成为研究热点之一，被广泛应用与知识发现、机器学习、决策分析、模式识别、专家系统和数据挖掘等领域。

属性约简是粗糙集理论中核心研究内容之一[3]。在众多的属性约简算法中，大致可以分为两类：一类是基于信息熵的启发式算法[4]，这类算法往往不能得到系统的所有约简．另一类是基于区分矩阵和区分函数构造的算法[5]，这种算法直观，易于理解，能够计算出所有约简。但在区分矩阵中会出现大量的重复元素，造成时间和空间的浪费，从而降低了属性约简算法的效率。

本文基于数据分析方法[6]的属性简约算法是在保持分类能力不变的前提下，逐个约去冗余的属性，直到不再有冗余的属性，此时得到的属性集是最小属性集，即为约简。该算法简单，能够求出所有约简，不会出现区分矩阵中大

量的重复元素，从而提高了属性约简的效率。

2 粗糙集概念

定义2.1设U为所讨论对象的非空有限集合，称为论域；R为建立在U上的一个等价关系族，称二元有序组S=(U，R)为近似空间。

定义2.2令R为等价关系族，设P?哿R，且P≠?I，则P中所有等价关系的交集称为P上的不可分辨关系，记作IND(P)，即有：[x] IND(P)= ∩ [x]R,显然IND(P)也是等价关系。

定义2.3称4元有序组K=(U，A，V，f)为信息系统，其中U为所考虑对象的非空有限集合，称为论域；A为属性的非空有限集合；V=∪Va，Va为属性a的值域；f：U×AV是一个信息函数，?坌x∈U，a∈A，f(x,a)∈Va。对于给定对象x，f(x,a)赋予对象x在属性a下的属性值。信息系统也可简记为K=(U，A)。若A=C∪D且C∩D=?I，则S称，为决策表，其中C为条件属性集，D为决策属性集。

显然，信息系统中的属性与近似空间中的等价关系相对应。

定义2.4设K=(U，A，V，f)为信息系统，P?哿A且P≠?I，定义由属性子集P导出的二元关系如下：

IND(P)={(x,y)|(x,y)∈U×U且?坌a∈P有f(x,a)=f(y,a)}

则IND(P)也是等价关系,称其为由属性集P导出的不可分辨关系。

定义2.5称决策表是一致的当且仅当D依赖于C，即IND(C)?哿IND(D)，否则决策表是不一致的。一致决策表说明：在不同个体的条件属性值相同时，他们的决策属性值也相同。

定义2.6设K=(U，A)为一个信息系统。若P?哿A是满足IND(P)=IND(A)的极小属性子集，则称P为A的一个约简，或称为信息系统的一个约简。

定义2.7设K=(U，CUD)为一个决策表，其中C为条件属性集，D为决策属性，若P?哿C为满足POSC(D)=POSP(D)的极小属性子集，则称P为决策表K的一个约简。其中POSC(D)表示决策D关于属性集C的正域。

定义2.8数据分析方法对于信息系统K=(U，A)，逐个移去A中的属性，每移去一个属性即刻检查新得到的属性子集的不可分辨关系，如果等于IND(A)，则该属性可被约去，否则该属性不可被约去；对于决策表K=(U，CUD)，逐个移去C中的属性，每移去一个属性即刻检其决策表，如果不出现新的不一致，则该属性可被约去，否则该属性不可被约去。

3 基于数据分析方法的属性简约算法

3.1 算法思路

利用函数的递归调用，逐个判定信息系K=(U，A)中属性a(a∈A)，若IND(A)＝ND(A－{a})，则a可以约去，A‘=A－{a}，否则a不可以约去，继续检查A‘中的每个属性是否能被约去，此过程一直进行下去，直到出现某一属性子集中的每个属性都不可约去为止，此时该属性子集即为所求的属性简约。对于决策表，每次检查是否增加了不一致的决策规则，作为是否约去属性的依据。

算法如下：

输入：信息系统K=(U，A)。

输出：K的属性约简。

Match(A') // A’=A-{a}//

begin

for i=1to|U|-1 //|U|表示U的基数//

for j=i+1to|U|

begin

r=|R|//|R|表示属性个数//

if((f(ui，a1)= f(uj，a1))∧（f(ui，a2)= f(uj，a2)）∧….∧（f(ui，ar)= f(uj，ar)))

then a不可被约去，return0

end

a可以被约去return1

end

Reduce (A)

begin

flag=1

for i=1 to |R|//|R|表示属性个数//

begin

a=ai

A'=A-{ai}

if match(A')thenflag =0 ， reduce (A’)

if (flag且A未被输出)then

输出A中所有元素//flag≠0，说明A中所有元素不可移去，且不会被重复输出//

End

end

以上给出的函数是求解信息系统的属性约简算法；对于决策表，只要将Match(A’)函数中的if语句的条件换成(f(ui，a1)= f(uj，a1))∧（f(ui，a2)= f(uj，a2))∧….∧(f(ui，ar)= f(uj，ar))∧(f(ui，ag)≠f(uj，ag))，r=|C|是条件属性个数，ag是决策属性。Reduce (A)函数中|R|换成|C|即可。该算法适用于一致决策表，对非一致决策表，算法类似，也就是逐个移去属性并检查决策表是否出现新的不一致，作为约去此属性的依据。

4 举例

文献[7]中决策表1，a，b，c，d，e是条件属性，g是决策属性，求出的约简是{a,b,d}

应用本算法，求得的属性约简为{a,e}和{a,b,d}，得到决策简化表2和表3。

表1 决策表表2简化表表3简化表

如果将决策表表1看作一信息系统，运用本算法，求得的属性约简有{c,d,e,g}, {b,e,g}, {a,c,d,g}, {a,c,d,e}, {a,b,g}, {a,b,e}h和{a,b,d}

5 结束语

本文通过数据分析方法讨论了属性约简问题。该算法是基于不可分辨关系的，具有直观、易于理解和完备性的特点。当属性和对象都较少时，效率较高，但当属性和对象较多时，计算的复杂度较高。实例表明，该算法是有效的。

参考文献：

[1]PAWLAK z．Rough set[J]．International jom：ua ofcomputer and information science，1982，(11)：341―356．

[2]张文修，吴伟志，梁吉业等．粗糙集理论与方法[M]．北京：科学出版社，2001．

[3]Pawlak Z．Slowinski R．Rough set approach to muhiattribute decision analysis．Ivited Review[J]．European Journal of Operational Research．1994，72：443-459

[4]王国胤，于洪，杨大春．基于条件信息熵的决策表约简[J]．计算机学报，2002（7）：760―765．

[5]Skowron A，Rauszer C．The Discernibility Matrices and Functions in Information Systems[A]．I Slowinsk R．ntelligent Decision Support― Handbook of Applications and Advances of the Rough Sets Theory[c]．1991，331-362．

[6]刘请．Rough集及Rough推理[M]．北京：科学出版社，2001．

[7]李珊，肖怀铁，付强．改进的粗集属性约简的启发式算法[J]．电光与控制，2006（4）：46―48．

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。