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

摘要:以属性在可分辨矩阵中出现的频率作为启发,对HORAFA算法做了一些改进。引入二进制可辨识矩阵,利用二进制可辨识矩阵求出相对核。以相对核为基础,依次加入属性重要度大的属性,直到不能再加。

关键词:粗糙集;属性约简;二进制可辨识矩阵

中图分类号:TP183文献标识码:A文章编号:1009-3044(2009)13-3524-03

1 引言

属性约简是粗糙集理论的核心内容之一。决策表属性约简的过程,就是从决策表系统的条件属性中去掉不必要(对得到决策不重要)的条件属性,从而分析所得约简中的条件属性对于决策属性的决策规则。在不同的系统中,或者在不同的条件环境下,人们对属性约简的要求和期望是不一致的。如果在某个系统中,存在一些属性,它们的属性值难于得到(测量这些属性值所花的代价很高),我们希望将这些属性从决策表中去掉。通常,人们希望得到的约简结果所包含的条件数目尽可能少,或者得到的决策规则的规则数最少,等等。

2 HORAFA算法

HORAFA算法[1]利用属性在可辨识矩阵中出现的频率作为启发,从而对信息系统进行约简。它完全摆脱了对原来信息系统(数据表)的依赖,仅仅利用可辨识矩阵中属性出现的频率来计算。因为不用计算粗糙集,而仅仅使用简单的计算,提高了效率。

2.1 算法原理

一个约简和可辨识矩阵的每一项的交都不能为空。如果它和可辨识矩阵的某项cij的交为空的话,对象i和对象j对于该约简就是不可区分的了。这和约简能够区分所有对象的最小属性集合相矛盾(这里假定数据集是一致的)。

利用这个事实算法可以这样设计。首先设候选约简集合R=?I,检查可辨识矩阵的每一项cij和候选约简集合R的交。如果交为空,随机从cij中选择一个属性插入到R中;否则就跳过这一项。重复这一过程,直到可辨识矩阵的每一项都检查完。这时候,我们在R中得到的就是一个“约简”。

但是,如果在可辨识矩阵的某项和当前候选集的交为空,并且该项由多于一个的属性组成时,如何知道优先选择哪个属性呢?当生成可辨识矩阵时,每个属性出现的频率同时被记录,供以后使用。这些频率用来评估属性的重要性,并用于属性优先级的选择。这一点是基于一个属性出现的越频繁,它的潜在区分能力就越大来考虑的。在计算属性出现的频率时,并不是简单的计数,而是要加权。加权大小的根据是属性所出现在可辨识矩阵中的长度。

每当计算出一个新的可辨识矩阵项c,相应的属性频率函数f(a)就更新为:

f(a)=f(a)+|A|/|c|对于每个a∈c

其中|A|是信息系统总的条件属性个数。例如,设f(a1)=3,f(a3)=4,系统总共由10个属性,新的可辨识函数项是{a1,a3}。则处理这项后,属性的频率被更新为:f(a1)=3+10/2=8;f(a3)=4+10/2=9。

2.2 算法描述

输入:信息系统S(U,A∪{d}),其中A=∪ai,i=1,n;

输出:约简Red;

step1:Red=?I,count(ai)=0,对于i=1,n

step2:计算可辨识矩阵M并同时计算属性的加权频率count(ai)

step3:合并相同的项并且按照每项的长度和频率对可辨识矩阵排序;

step4:For M中的每项m do

step5:if (m∩Red==?I)

step6:选择m中的具有最多的count(a)的属性a

step7:Red=Red∪{a}

step8:End if

step9:End For

step10:Return Red

在step2中,每计算M的一个新项c,count(ai)就更新为count(ai):=count(ai)+n/|c|,其中ai∈|c|。step4~9遍历M并生成约简。

2.3 实例分析

如表1所示的一组申请信用卡的数据,其中条件属性C={账户,余额,职业,月消费},决策属性D={申请决策};表1经泛化处理后得到表2。

其中a,b,c,d为条件属性,C={a,b,c,d},D为决策属性。根据HORAFA算法计算过程为:根据可辨识矩阵定义得到可辨识矩阵如表3。化简后得{bd, abd, ab, abd, ad,b,abd,abd,bd,bcd,abc,abcd,abc,abcd,abc,abd}。下面以属性a为例,根据HORAFA算法,计算count(ai):设f(a0)=0。系统一共有4个属性,可辨识矩阵中出现的第一个含有条件属性a的可辨识函数项为{abd},则根据定义f(a1)=3/4,f(a2)=10/3,f(a3)=14/3,f(a4)=20/3,f(a5)=24/3,f(a6)=28/3,f(a7)=32/3,f(a8)=35/3,f(a9)=39/3,f(a10)=43/3,f(a11)=46/3,f(a12)=50/3.

因此count(a)=50/3。依次类推,count(b)=24,count(c)=19/3,count(d)=52/3。

根据HORAFA算法的描述,合并后的可辨识矩阵项为{bd, abd, ab, ad, b, bcd, abc, abcd}。下面对于可辨识矩阵中每一项进行循环,由于现在Red为空,并且count(b)>count(d)>count(a)>count(d),选择第一个函数项{bd}中count值最大的属性b,加入到Red中,继续循环,当循环到函数项{ad}时,Red∩{ad}=φ,将属性d加入到Red中。至循环结束后,Red={b,d}。

3 HORAFA算法的改进算法

实验证明[2]HORAFA算法并不是一定能够找到信息系统的最优约简或者是较优约简,甚至是约简。这是因为属性对系统的重要性是有重复的,属性之间的重复性越大,对系统的重复性也就越大。在这种情况下,就属性频率函数对整个信息系统的重要性而言(已经取得一些属性作为约简的一部分),属性频率函数大的未必就比属性频率函数小的属性重要性大。

3.1 改进算法原理

基于以上因素,文中对HORAFA算法提出了以下的改进:

先将决策表转换成二进制可辨识矩阵MT,,可以很容易的求出属性集的相对核。从区分矩阵中删除相对核中属性所在的元素,此时属性频率函数就等于区分矩阵中删除相对核中属性所在的元素之后属性出现的频率。以相对核为基础,加入属性重要性最大的属性,直到不能再加为止。在此基础上,如果属性重要性相等的情况下,将相等的属性加入到不同的约简集合中,得到不同的约简。

3.2 改进算法描述

输入:信息系统S=(U,A,V,f),其中U为论域,A为属性集,A=C∪D,C∩D=?I,C为条件属性集合,D为决策属性集合;

输出:约简Red;

1) Red=?I,core=?I,count(ai)=0,i=1,2,……,n,n=0

2) 将决策表转换成二进制p*q可辨识矩阵MT,即有p个决策属性不同的对象对,q个条件属性;

3) 将MT的第i行横向相加,结果存入row(i)中。若row(i)=1,则求出此行中值为1对应的列j,即第j列对应的属性为相对核,加入相对核core中

4) 计算可辨识矩阵M,合并矩阵中相同的元素

5) Red=core,删除M中包含相对核中属性的项,计算count(ai),同时计算|M|

6) If |M|≠0

7) If count(ai)=count(aj)

8) 先将ai加入到Red1,n++,删除M中包含ai的所有项,重新计算count(ai),并计算

9) 将aj加入到Red2,n++,删除M中包含aj的所有项,重新计算count(aj),并计算

10) Else将count(ai)最大的ai加入到Red,n++,删除M中包含ai的所有项,重新计算count(ai),并计算|M|

11) End if

12) End if

13) 输出:Red

3.3 实例分析

如表1所示的一组申请信用卡的数据,其中条件属性C={账户,余额,职业,月消费},决策属性D={申请决策};将表2转换为二进制可辨识矩阵MT,得到到表4。

将MT的每一行横向相加,结果存入row()中。可以很容易得出二进制可辨识矩阵中,属性对象对(4,5)对应的行相加的结果为1,求出此行中值为1对应的列为b,根据定理1,列b对应的属性为相对核,加入相对核core中,core={b}。可辨识矩阵如表4-2所示,合并后的可辨识矩阵为{bd,abd,ab,ad,b,bcd,abc,abcd},删除可辨识矩阵中包含b的所有项,得到{ad},计算count(a)=count(d)=2,先将属性a加入到Red1中得到Red1={a,b},删除包含属性a的所有项,计算|M|=0,停止计算,得到约简Red1={a,b};将属性d加入到Red2中得到Red2={b,d},删除包含属性d的所有项,计算|M|=0,停止计算,得到约简Red2={b,d}。这和利用粗糙集的知识计算的结果是一样的。

4 总结

本文提出了一种改进的启发式属性约简算法。此算法利用二进制可辨识矩阵,求出相对核,并加入到约简中,在此基础上对可辨识矩阵中每个属性的频率进行加权,属性频率函数等于区分矩阵中删除当前约简之后的属性出现的频率,用来进行属性的选择。此算法能够快速的找到信息系统的属性约简。实验证明此算法优于HORAFA算法。

参考文献:

[1] Duoqian M, Wang J.An information―based algorithm for reduction of knowledge[C].IEEE.ICIPS'97,1997:1155-1158.

[2] 刘清.Rough集及Rough推理[M].北京:科学出版社,2001.

[3] 胡,李智玲,李春伟.一种基于区分矩阵的属性约简算法[J].计算机应用,2006,26(B06):80-82.

[4] 张文修,吴志伟,梁吉业,等.粗糙集理论与方法[M].北京:科学出版社,2005.

张永平(1958-),男,辽宁东沟人,硕士生导师,副教授,研究方向:计算机网络,信息安全;

李娜(1983-),女,江苏徐州人,硕士,研究方向:粗糙集理论,数据挖掘。