改进的快速属性约简算法  

Improvement to Quick Attribution Reduction Algorithm

作　　者：葛浩[1,2] 李龙澍[2] 杨传健[3] 

机构地区：[1]滁州学院电子信息工程系,安徽滁州239012 [2]安徽大学计算机学院,安徽合肥230039 [3]滁州学院计算机系,安徽滁州239012

出　　处：《小型微型计算机系统》2009年第2期308-312,共5页Journal of Chinese Computer Systems

基　　金：安徽省自然科学基金(O50420204)资助;安徽高校省级自然科学研究项目(KJ2008B117)资助

摘　　要：属性约简是决策表信息系统中一个重要操作.目前最高效的算法是徐章艳给出的RedueBaseSig算法,其时间复杂度为max{O(︱C︱︱U︱),O(︱C︱2︱U︱)},但在某些情况下,该算法求得的并不是约简.文中分析了徐章艳算法的局限性,并提出改进的快速属性约简算法.该算法优化了等价类划分和正区域求解,以核属性为初始约简集,不断将重要性大的属性加入约简集中.在最坏情况下改进后算法的时间复杂度为O(C2U);而且实验结果表明,该算法是正确的、高效的.The attribute reduction is an important operation of decision table information system. Currently the most efficient algorithm is Xu Zhang Yan＇s RedueBaseSig algorithm, its time complications is max {O（｜C｜ ｜U｜）,O（｜C｜^2｜U｜）}. However, in some eases, the algorithm is not obtained reduction. In the paper, we analyze the limitation of the Xu Zhang Yan＇s algorithm and propose an improvement to quick attribution reduction algorithm. The algorithm optimizes the method of the equivalence partition and computing positive region, uses core attributes as the initial reduction sets, and adds the most important eondition attribute into the reduetion sets. The time complexity of the improved algorithm is O（ ｜C｜^2 ｜U｜ ） in the worst ease. The experimental results show that the algorithm is correct and effieient.

关 键 词：决策表 粗糙集 属性约简 正区域 核 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]