一个复杂度为max（O（｜C｜｜U｜），O（｜C^2｜U／C｜））的快速属性约简算法  

A Quick Attribute Reduction Algorithm with Complexity of max（O（｜C｜｜U｜） ,O（｜C^2｜｜U/C｜））

作　　者：徐章艳[1] 刘作鹏[1] 杨炳儒[1] 宋威[1] 

机构地区：[1]北京科技大学信息工程学院

出　　处：《计算机学报》2006年第3期391-399,共9页Chinese Journal of Computers

摘　　要：以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度被降为O(|C||U|).经研究发现,以近似质量作为启发信息并非十分理想,故以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式,并给出了该公式的递归计算公式.计算该公式的算法复杂度被降低到O(|C-P||U′-UP′|).用新公式作为启发信息,设计了一个时间复杂度为max(O(|C||U|,O(|C|2|U/C|))的快速属性约简算法,并用一个实例说明了算法.实验结果表明新算法不仅具有高效性而且能处理大型决策表.Computing U/C is one of the most important and time-consuming computation in attribute reduction based on positive region. At present, the idea of the best algorithm for computing U/C is based on quick sorting, and it＇s time complexity is O（｜C｜｜U｜log｜U｜）. In this paper, a new algorithm based on radix sorting for computing U/C is provided, and its complexity is cut down to O（｜C｜｜U｜）. On the other hand, it is not fully reasonable to regard approximate quality as heuristic information in attribution reduction algorithm based on positive region. So a new and relatively reasonable formula measuring attribution importance is designed for reducing searching space as quickly as possible, and the recursive calculating method of the formula is provided. The algorithm complexity of calculating the formula is descended to O（｜C-P｜｜U＇-Up＇｜）. Then the formula measuring attribute importance is used as heuristic information to design an efficient attribute reduction algorithm, whose worst time complexity is cut down to max（O（｜C｜｜U｜） ,O（｜C^2｜｜U/C｜））. An example is used to illustrate the efficiency of the new algorithm. At last, experimental result shows that the new algorithm is not only efficient but also scalable.

关 键 词：粗糙集 正区域 属性重要性 属性约简 计算复杂度 近似质量 

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