共 5 条
一个复杂度为max(O（|C||U|）,O（|C|2|U/C|）)的快速属性约简算法
被引：216
作者：
徐章艳
刘作鹏
杨炳儒
宋威
机构：
[1] 北京科技大学信息工程学院
来源：
关键词：
粗糙集;
正区域;
属性重要性;
属性约简;
计算复杂度;
近似质量;
D O I：
暂无
中图分类号：
TP301.6 [算法理论];
学科分类号：
081202 ;
摘要：
以基数排序的思想设计了一个新的求U/C的算法,其时间复杂度被降为O(|C||U|).经研究发现,以近似质量作为启发信息并非十分理想,故以快速缩小搜索空间为目的设计了一个新的较为合理的度量属性重要性的计算公式,并给出了该公式的递归计算公式.计算该公式的算法复杂度被降低到O(|C-P||U′-UP′|).用新公式作为启发信息,设计了一个时间复杂度为max(O(|C||U|,O(|C|2|U/C|))的快速属性约简算法,并用一个实例说明了算法.实验结果表明新算法不仅具有高效性而且能处理大型决策表.
引用
收藏
页码：391 / 399
页数：9
相关论文