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

• 作者: 刘作鹏 宋威 徐章艳 杨炳儒
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 粗糙集 正区域 属性重要性 属性约简 计算复杂度 近似质量
• 年，卷（期）: 2006,（3）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 391-399
• 页数: 9页
• 分类号: TP18
• 字数: 9017字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2006.03.006

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨炳儒	北京科技大学信息工程学院	319	4361	32.0	49.0
2	徐章艳	北京科技大学信息工程学院	120	1992	21.0	40.0
6	宋威	北京科技大学信息工程学院	39	926	16.0	30.0
7	刘作鹏	北京科技大学信息工程学院	2	303	2.0	2.0