摘要
属性约简是决策表信息系统中一个重要操作.目前最高效的算法是徐章艳给出的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.
出处
《小型微型计算机系统》
CSCD
北大核心
2009年第2期308-312,共5页
Journal of Chinese Computer Systems
基金
安徽省自然科学基金(O50420204)资助
安徽高校省级自然科学研究项目(KJ2008B117)资助
关键词
决策表
粗糙集
属性约简
正区域
核
decision table
rough set
attribute reduction
positive region
core
