一种基于二进制分辨矩阵的属性约简新算法.pdf

《一种基于二进制分辨矩阵的属性约简新算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第24卷第4期重庆邮电大学学报(自然科学版)V01．24NO．42012年8月JournalofChongqingUniversityofP0stsandTelecommunications(NaturalScienceEdition)Aug．2012DOI：10．3979／j．issn．1673—825X．2012．04．019一种基于二进制分辨矩阵的属性约简新算法赵军，陈宸(重庆邮电大学计算机科学与技术研究所，重庆400065)摘要：决策表的属性约简是粗糙集理论中的关键问题之一，高效启发式约简算法有待

2、深入研究。基于二进制分辨矩阵，定义“加权重要度”来度量属性相对重要性；这一概念综合利用分辨矩阵行和列2个方向的特征，将其集成为一个归一化的概念，因而在排序过程中能有效避免从行、列2个方向独立排序。基于“加权重要度”概念，提出一种新的启发式属性约简算法；仿真实验结果表明，与参考算法相比，新算法有效缩短了运行时间，更有可能获得系统的最优约简。关键词：粗糙集理论；决策表；属性约简；二进制分辨矩阵；加权重要度中图分类号：TP18文献标识码：A文章编号：1673825X(2012)04-0490-05Newalgo

3、rithmforattributereductionbasedonbinarydiscernibilitymatrixZHAOJun，CHENChen(InstituteofComputerScienceandTechnology，ChongqingUniversityofPostsandTelecommunications，Chongqing400065，P．R．China)Abstract：Theattributereductionofdecisiontablesisoneofthekeyissues

4、inroughsettheory．Efectiveandeficientheu—risticreductionalgorithmsaredeservedtobefurtherstudied．Herein．aconceptof“weightedimportance’’isdefinedbasedonbinarydiscernibilitymatrixtoheuristicallymeasurethesignifieancesofattributesofadecisiontable．Theconceptcom

5、—prehensivelymakesgooduseofthecharacteristicsofcolumnsandrowsofbinarydiscernibilitymatrixandintegratesthemintoanormalizedconcept；consequently，independentsortingcomputationinrespectivedirectionsofcolumnandrowiseffec—tivelyavoided．Thenanewheuristicalgorithm

6、forattributereductionisproposedbasedOfconceptof“weightedimpor—tance”．Simulationexperimentresultsshowthatcomparedwithsomebenchmarkalgorithms，thenewalgorithmrunsfasterandismorepossibletogetoptimalreductionsofdecisiontables．Keywords：roughsettheory；decisionta

7、ble；attributereduction；binarydiscernibilitymatrix；weightedimportance这些算法从信息熵、正区域或分辨矩阵等不同的角0引言度来度量属性的相对重要性。其中，信息熵概念依粗糙集(roughset)理论刮能处理不一致、不完赖于样本分布概率估算的准确性，当样本规模较小备和不精确信息，目前已被广泛应用于模式识别、医时难以保证其约简性能；在后两者中，尽管基于分辨疗诊断、机器学习、决策分析等各个领域剖。决策矩阵的算法时间复杂度相对略高，但这类方法却很直表的

8、属性约简是粗糙集信息处理模型中的一个核心观，易于实现，因此在许多研究和应用中仍然受到重内容。所谓决策表的属性约简，就是要在保持条件视。经典的分辨矩阵以属性集合为矩阵元素，其属性相对于决策属性的分类能力不变的前提下，删空间复杂高、处理效率低，于是有人将其优化为二进除其中不必要的或者不重要的条件属性。已经证制的分辨矩阵，在此基础上提出了新的属性约简算明，最优属性约简是一个NP难题J。于是，很多学法【15-18]，但这类算法的性能仍