一个复杂度为max(O(|C||U|),O(|C|2|U/C|))的快速属性约简算法

摘要：

以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度被降为O(|C||U|).经研究发现,以近似质量作为启发信息并非十分理想,故以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式,并给出了该公式的递归计算公式.计算该公式的算法复杂度被降低到O(| C-P||U'-U'P|).用新公式作为启发信息,设计了一个时间复杂度为max(O(|C||U|,O(|C|2|U/C|))的快速属性约简算法,并用一个实例说明了算法.实验结果表明新算法不仅具有高效性而且能处理大型决策表.

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

所属期刊栏目：29

分类号：TP18(自动化基础理论)

在线出版日期：2006-04-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：391-399