逄玉俊 李 爽
摘 要：针对信息系统在属性约简过程中存在属性频率值相同的问题进行改进，改进后的算法在基于可辨识矩阵属性频率约简算法的基础上，引进强等价集概念，以属性在可辨识矩阵中出现的次数越多其重要性越大为启发式信息，利用强等价集中的属性是可以约简的特性，在属性频率约简过程中判断具有相同属性频率属性是否最终包含在核属性集里，提出改进的属性频率约简算法。通过理论和实例的分析证明，该算法在保持时间复杂度不变的情况下，处理具有相同属性频率信息系统的属性约简，使其准确性得到提高，与原算法相比，改进后的算法可以得到一个更为精准的约简结果。
关键词：粗糙集;可辨识矩阵;强等价集;属性频率
中图分类号：TP391 文献标识码：B 文章编号：1004－373X(2009)04－145－03
Attribute Frequency Reduction Arithmetic Based on Discernibile Matrix of Rough Set
PANG Yujun,LI Shuang
(Shenyang Institute of Chemical Technology College,Shenyang,110142,China)
Abstract：In the view of improving system exsists the same attribute frequency value in attribute reduction,the improved algorithm based on discernibile matrix affribute frequency reduction arithmentic,the concept of strong equivalent set is introduced to identify attributes in the matrix in the number of the more importance to the greater heuristics.Using strong focus on the strong equivalent set is the reduction of the frequency attribute reduction in judgements have the same attributes′frequency of property included in the final set of attributes,and the properties frequency reduction algorithm is improved.Through theoretical analysis and examples prove that the algorithm to maintain the same time complexity of the situation,to deal with the same attributes′ frequency of information systems attribute reduction,the accuracy is improved,compared with the original algorithm,improved algorithm can get a more precise reduction results.
Keywords：rough set;discernibility matrix;strong compressible set;attribute reduction
0 引言
粗糙集理论是由波兰数学家Z.Pawlak在1982年提出的一种智能决策分析数学工具。它是研究不完整，不确定知识和数据的表达、学习、归纳的理论方法。粗糙集目前主要被广泛地应用与数据挖掘、人工智能、模式识别、网页分类、故障诊断和专家系统等领域［1］。
属性约简是粗糙集理论中重要的核心内容之一。属性约简主要目的是保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性，从而简化原有的系统。虽然Wond等已经证明找出一个决策表的所有约简和最小约简是NP－hard问题，但是利用启发式信息减小搜索空间，还是能得到一个相对最优的约简［2］。
以基于可辨识矩阵的属性频率约简算法为基础，引入强等价集概念，以属性在可辨识矩阵中出现的次数越多，其重要性越大为启发式信息。提出一种新的有效的属性约简算法，该算法可以处理当属性频率相同时，对决策表的属性约简可以高效准确的进行。
1 相关概念和证明
1.1 决策表
形式上，四元组S=(U,A,V,f)是一个知识表达系统，其中U为对象的非空有限集合，称为论域；A为属性的非空有限集合；V=∪a∈AVa，Va是属性a的值域;f为U×A→V是一个信息函数，它为每个对象的每个属性赋予一个信息值，即对于所有的a∈A,x∈X,f(x,a)∈Va［3］。
知识表达系统也称为智能系统。通常也用S=(U,A)来代替S=(U,A,V,f)。
1.2 约简和核
在信息系统S中，对于P罜，则P在S的不可分辨关系IND(P)定义为：
IND(P)={(x,y)∈U2|衋∈P,a(x)=a(y)}
IND(P)把对象集U划为k个等价类，记为U/P={X1,X2,…,Xk}。
定义1［4］：设Q罚，如果Q是独立的，并且IND(Q)=IND(P)，则称Q是P的一个约简。P中所有必要关系的集合称为P的核，用CORE(P)来表示。
定理1：簇集P的核等于P的所有约简的交集。即CORE(P)=∩RED(P)。
1.3 可辨识矩阵
令决策表系统S=＜U,R,V,f＞,R=C∪D是属性集合；子集P={a i|i=1,2,…,m}和D={d}分别称为条件属性和决策属性集；U={x1,x2,…,xn}是论域，ai(xj)是样本xj在属性ai上的取值。CD(i,j)表示可辨识矩阵中第i行和第j列的元素，则可辨识矩阵CDФㄒ澹5］为:
CD(i,j)={ak|ak∈P∧ak(xi)≠ak(xj)},d(xi)≠d(xj);
0,d(xi)=d(xj)
其中：i,j=1,2,…,n。
1.4 强等价集
设a∈A，如果存在某一集合B粒踑］，则称集合B是属于a的强等价集［6］。
定理2：A的子集B罙是强等价集的充分必要条件是：B被区分矩阵中2个或2个以上项同时包含，且B与区分矩阵中其它项的交为空。
定理3：如果C是一个约简，B是强等价集，且{a,b}∈B，则{a,b}不包含于C。
此定理可用反证法证明，证明过程［6］如下：
证明：假定C是一个约简，且有{a,b}罜因为{a,b}∈B且B是强等价集，所以有Dis({a})=Dis({b})，于是有Dis(C－{a})=Dis(a)即IND(C－{a})=IND(C)，这与C是一个约简相矛盾，因此应有{a,b}不包含于C。可见，任何一个约简最多只能包含强等价集中的一个属性，简而言之，强等价集中的属性是可以约简的。
2 基于可辨识矩阵的属性频率约简算法
2.1 算法思想
胡可云博士提出关于属性频率有两种重要的启发式思想［7］：
（1） 属性在可辨识矩阵中出现的次数越多，该属性的重要性越大；
（2） 在可辨识矩阵中属性项越短，属性的重要性越大。
由思想（2）可知：在可辨识矩阵中，可能会有一些只有1个属性的属性项，则这个惟一的属性一定是核属性，可直接把它加入到约简集中。提出一种新的计算属性频率的函数：
g(ai)=countai∑nj=2(counterai/j)
式中：countai体现出属性在可辨识矩阵中出现的次数越多，这个属性的重要性越大；counterai为属性ai在可辨识矩阵中出现的总次数；j为含有属性ai的属性项中属性的个数，n为含有属性ai所有项中，属性个数最多的项的属性个数。基于此公式，可以计算出属性频率。
在文献［3］中，算法的缺陷在于不能很好地解决出现2个属性频率相同时的情况。针对这个问题，这里引入强等价集概念对属性进行区分。定理2表明强等价集中的属性对分类具有相同的重要性。利用定理3判断，当属性频率相同时是否有属性包含在强等价集中，可以保留出现在强等价集中的某个属性去掉其他属性。
2.2 算法描述
输入：决策表S=(U,C∪D,V,f)，其中C={a1,a2,…,an}；
输出：决策表的约简集Red。
（1） 把决策表S转化成相应的可辨识矩阵M，并初始化候选约简集合Red=h，令counterai=0；
（2） 将可辨识矩阵中属性组合数为1的条件属性（核属性）直接加到约简集Red中，去掉含有核属性的属性项；
（3） 利用属性频率函数g(ai)对剩余属性项中的各属性计算属性频率。判断是否有属性频率相同的属性，有则转（4），否转（5）；
（4） 对有相同属性频率的属性用定理2判断是否为强等价集，若是则在可辨识矩阵M中保留强等价集中任一属性去除其他属性。否则转（5）；
（5） 找出属性频率最高的属性记作a1则Red=Red∪{a1}，去掉可辨识矩阵中含有属性a1的属性组合；
（6） 判断可辨识矩阵是否为h，是结束，否则转（3）。
显然，该算法给处理具有相同属性频率的决策表属性约简提供了较好的方法。大量数据表明遇到出现相同属性频率的情况非常多，所以该算法的实用性很广泛。与文献［3］的算法相比，改进的基于属性频率的算法的实现对条件属性的更优的约简，其计算的主要时间花费在计算g(ai)上，为O(|C||U|2)，而原算法的时间复杂度亦为O(|C||U|2)，可见新的算法在保持计算的时间复杂度不变的前提下，得到更精确的约简结果。
3 实例分析
表1［4］是一个信息系统。应用这里改进算法对该信息系统进行属性约简。
表1 信息系统
objectSizePanelBackMidClassification
1ShortDarkBluePale0
2TallDarkBrownMatt1
3TallRedBluePale0
4ShortBlondBlueMatt1
5TallBlondBluePale1
6TallDarkBluePale0
7TallBlondBrownMatt1
8ShortDarkBrownMatt1
式(2)为可辨识矩阵:
0
SBM0
hPBM0
PMhSPM0
SPhPh0
hBMhSPMP0
SPBMhPBMhhPBM0
BMhSPBMhhSBMh0〗(1)
式(3)为去掉核属性后的可辨识矩阵:
0
SBM0
hh0
hhh0
hhhh0
hBMhhh0
hhhhhh0
BMhhhhSBMh0〗(2)
表1变换成对应的可辨识矩阵，得式(1)所对应的可辨识矩阵。式(2)是在式(1)的基础上由算法第（2）步得到P为核属性直接加入到约简Red中后，去掉含有P的属性项得到化简后的新可辨识矩阵；在新的可辨识矩阵中可以得出属性B,M频率一样，g(B)=g(M)=12.33，{B,M}有可能是强等价集，此时再利用定理1求出原可辨识矩阵的强等价集为{B,M}，根据强等价集的定理2，在可辨识矩阵中可以去掉M保留B，最后得到的约简集合{P,B}。再去掉含有B的属性项，此时可辨识矩阵为h，则算法结束。而按照文献［3］中的算法得到的约简集合为{P,B,M}，又由定理2中关于强等价集的性质中可知，包含在强等价集中的属性是可以约简的，所以{P,B,M}不是最后的约简结果。实例证明新算法可以实现更加有效精确的数据属性约简。
4 结 语
由于现实信息系统的数据复杂度很高，出现相同频率属性的几率很大，所以在基于粗糙集属性频率的约简算法的基础上，引入强等价集概念，较好地解决了出现相同属性频率时属性约简的问题，具有一定的实际意义和应用价值。与原算法相比，在保持计算速度保持不变的前提下实现了对信息系统更为精确的属性约简。
参 考 文 献
［1］Pawlak Z.Rough Set:Theoretical Aspects of Reasoning about Data.Dordrecht:Kluwer Academic Publisher,1991.
［2］Roman W Swiniarski,Andrzej Skowrin.Rough Set Methods in Feature Selection and Recognition.Pattern Recognition Letter,2003,24(6):833－849.
［3］任小康,吴尚智,马如云.基于可辨识矩阵的属性频率约简算法［J］.兰州大学学报,2007,43(1):138－141.
［4］芦晓红,陈世权,吴今培.基于可辨识矩阵的启发式属性约简方法及其应用［J］.计算机工程,2003,29(1):56.
［5］薛安荣,韩红霞,潘雨青.基于可辨识矩阵的快速粗糙集属性约简算法［J］.计算机工程与设计,2007,28(20):49－87.
［6］陶志,许宝栋,汪定伟.基于区分矩阵与强等价集的启发式知识约简算法［J］.系统工程理论方法应用,2004,13(6):513－514.
［7］胡可云.基于概念格和粗糙集的数据挖掘方法研究［D］.北京:清华大学,2001.
［8］张文修,吴伟志,梁吉业,等.粗糙集理论和方法［M］.北京:科学出版社,2001.
［9］王国胤.Rough集理论与知识获取［M］.西安:西安交通大学出版社,2001.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
