基于不可区分度的启发式快速完备约简算法

计算机科学 ›› 2009, Vol. 36 ›› Issue (8): 196-200.

基于不可区分度的启发式快速完备约简算法

滕书华,魏荣华,孙即样,谭志国,胡清华

(国防科学技术大学电子科学与工程学院长沙 410073);(河北工程技术高等专科学校计算机网络教研室沧州 061001);(哈尔滨工业大学能源科学与工程学院哈尔滨 150001)

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(60703013)资助。

Complete Algorithm of Quick Heuristic Attribute Reduction Based on Indiscernibility Degree

TENG Shu-hua,WEI Rong-hua,SUN Ji-xiang,TAN Zhi-guo,HU Qing-hua

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 在已有的粗糙集属性约简算法基础上，给出了一个新的度量属性重要性的不可区分度函数，分析了不可区分度的性质，提出了一种能有效处理噪声的基于不可区分度的快速完备约简算法，最坏时间复杂度为max(O(∣A∣∣U∣),O(∣A∣2∣U/A∣))。理论分析和实验结果表明，该约简算法在效率上较现有算法有显著提高，能较好抵制数据噪声，适于对大数据集进行处理。

关键词: 粗糙集，完备，约简，不可区分关系

Abstract: After analyzing the attribute reduction algorithm based on rough set, a new definition of indiscernibility degree was given for mcasurcing the importance of attribution, and the property of indiscernibility degree was analyzed.Then based on the indiscernibility degree, a new heuristic reduced algorithm was proposed, which is useful to deal with the noise and makes the worst time complexity cut down to max(O(∣A∣∣U∣),O(∣A∣2∣U/A∣)).The theoretical analysis and experimental results show that this new method is not only useful in solving data noise but also robust and efficient.

Key words: Rough set, Complete, Reduction, Indiscernitility relation

滕书华,魏荣华,孙即样,谭志国,胡清华. 基于不可区分度的启发式快速完备约简算法[J]. 计算机科学, 2009, 36(8): 196-200. https://doi.org/

TENG Shu-hua,WEI Rong-hua,SUN Ji-xiang,TAN Zhi-guo,HU Qing-hua. Complete Algorithm of Quick Heuristic Attribute Reduction Based on Indiscernibility Degree[J]. Computer Science, 2009, 36(8): 196-200. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed