基于可分辨矩阵的属性集依赖度计算方法

摘要在决策表中，为了评价某条件属性的重要性，不但要考虑这个属性（单一属性）相对于决策属性的重要性，还要考虑该条件属性与其他条件属性构成的属性集的重要性.在属性集依赖度比单一属性依赖度更加可信的事实基础上，提出了一个基于可分辨矩阵的属性集依赖度计算方法.该方法能够较快地获得可分辨矩阵，并直接求出属性集的依赖度，从而大大降低了算法的时间复杂度.实例验证了该方法具有较好的有效性和较低的时间复杂度.

关键词粗糙集；决策表；可分辨矩阵；依赖度

中图分类号TP301文献标识码A文章编号1000-2537（2013）02-0024-04

粗糙集理论[1]于1982年由波兰学者Pawlak提出，现已被广泛应用于机器学习、数据挖掘等领域 [2-6]，其核心研究内容就是依据决策表或者信息表的条件属性集、决策属性集以及对象集，进行知识约简从而获得最具代表性的属性约简集以及最简分类规则集[7-10].知识约简包括属性约简和分类规则约简，目前国内外学者主要在属性约简方面进行研究[11].

在属性约简中，衡量某个属性的重要程度一般是根据决策属性对该属性的依赖程度来做出判断，依赖度为1，则完全依赖；依赖度为0，则完全不依赖，其余则部分依赖[12].对于那些依赖度为0的属性，一般认为并不影响决策表分类的结果，在属性约简时可以直接删除[13-14].但是，这样不但会在某种程度上造成知识损失，而且还割断了该属性与其他属性的联系，从而造成更大程度的损失.

为此，本文在可分辨矩阵的基础上，研究属性集依赖度，提出了一种属性集依赖度计算方法，并用实例验证了该方法具有较好的有效性和较低的时间复杂度.

1基本理论

该方法由于要对多个属性以字串相加的形式构成单一属性，如果有m个条件属性，n个对象，则要进行∑mk=1Ckm次字串相加操作.在形成单一属性后，再进行条件属性等价类划分.该方法时间复杂度约为O（n2×m2），这是比较高的，对求解属性约简集不利.

从表2可以看出，对于本文算法和文献[15]算法，在各个实验数据集上，各属性依赖度的计算结果都近似一致，但本文算法的耗时较低，尤其是数据集较大的时候，这个优势更加明显.

4结束语

在信息表中，那些依赖度等于0的属性也可能对其他属性产生影响.在这种情况下，属性集依赖度就更能反映现实情况.为此，本文提出了一个新型基于辨识矩阵的属性集重要度评价方法，实例验证了该方法的有效性和较低的时间复杂度，从而使得本文方法在属性约简中有一定的实用价值.

参考文献：

[1]朱颢东，钟勇.基于优化的文档频和粗糙集的特征选择方法[J].湖南师范大学自然科学学报， 2009，32（3）：27-31.

[2]CHEN D G， HU Q H， YANG Y P. Parameterized attribute reduction with Gaussian kernel based fuzzy rough sets[J]. Int J Inform Sci， 2011，181（23）：5169-5179.

[3]黄媛玉，毛弋.基于主成分分析法的遗传神经网络模型对电力系统的短期负荷预测[J].湖南师范大学自然科学学报， 2011，34（5）：26-31.

[4]胡强.优化的互信息特征选择方法[J].湖南师范大学自然科学学报， 2010，33（3）：28-31.

[5]KIYOSHI H， MICHAUD K， MASAMOTO A. Application of data mining to quantitative structure-activity relationship using rough set theory[J].Int J Chem Intell Lab Sys， 2009，99（1）：66-70.

[6]MICHAEL N， GUDRUN S， GERHARD S. Adapted variable precision rough set approach for EEG analysis[J].Int J Artif Intell Med， 2009，47（3）：239-261.

[7]马建敏，张文修，朱朝晖. 基于信息量的序信息系统的属性约简[J]. 系统工程理论与实践， 2010，30（9）：1679-1683.

[8]FAN T F， LIAU C J， LIU D R. A relational perspective of attribute reduction in rough set-based data analysis[J].Eur J Opera Res， 2011，213（1）：270-278.

[9]QIAN Y H， LIANG J Y， PEDRYCZ W. An efficient accelerator for attribute reduction from incomplete data in rough set framework[J].Pattern Recog， 2011，44（8）：1658-1670.

[10]HE Q， WU C X， CHEN D G， et al. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Sys， 2011，24（5）：689-696.

[11]胡寿松，何亚群. 粗糙决策理论与应用[M]. 北京：北京航空航天大学出版社， 2006.

[12]YAO Y Q， MI J S， LI Z J. Attribute reduction based on generalized fuzzy evidence theory in fuzzy decision systems[J].Fuzzy Sets Sys， 2011，170（1）：64-75.

[13]QIAN Y H， LIANG J Y， PEDRYCZ W. Positive approximation： an accelerator for attribute reduction in rough set theory[J].Artif Intell， 2010，174（9）：597-618.

[14]SALAM M， LPEZ-SNCHEZ M. Rough set based approaches to feature selection for case-based reasoning classifiers[J]. Pattern Recog Lett， 2011，32（2）：280-292.