首页 | 本学科首页   官方微博 | 高级检索  
     

Rough集高效算法的研究
引用本文:刘少辉,盛秋戬,吴斌,史忠植,胡斐.Rough集高效算法的研究[J].计算机学报,2003,26(5):524-529.
作者姓名:刘少辉  盛秋戬  吴斌  史忠植  胡斐
作者单位:1. 中国科学院计算技术研究所智能信息处理重点实验室,北京,100080
2. 中国科学院计算技术研究所智能信息处理重点实验室,北京,100080;北京邮电大学计算机科学与技术学院,北京,100876
3. 上海体育学院体育管理系,上海,200438
基金项目:国家自然科学基金 (60 173 0 17,60 0 73 0 19,90 10 40 2 1),北京市自然科学基金重点项目 (4 0 110 0 3 )资助
摘    要:深入分析了现有Rough集算法低效性的根源,围绕不可区分关系和正区域两个核心概念,研究了不可区分关系的性质,给出并证明了正区域的一种等价计算方法,从而得出高效的Rough集基本算法;随后,分析了正区域的渐增式计算,并给出了一种完备的同性约简算法.理论分析和实验结果表明,该约简算法在效率上较现有的算法有显著提高.

关 键 词:Rough集  高效算法  属性约简  人工智能
修稿时间:2002年7月18日

Research on Efficient Algorithms for Rough Set Methods
LIU Shao-Hui SHENG Qiu-Jian WU Bin , SHI Zhong-Zhi HU Fei.Research on Efficient Algorithms for Rough Set Methods[J].Chinese Journal of Computers,2003,26(5):524-529.
Authors:LIU Shao-Hui SHENG Qiu-Jian WU Bin  SHI Zhong-Zhi HU Fei
Affiliation:LIU Shao-Hui 1) SHENG Qiu-Jian 1) WU Bin 1,2) SHI Zhong-Zhi 1) HU Fei 3) 1)
Abstract:This paper makes an deep study of the reasons of the algorithms' inefficiency, mainly focuses on two important concepts: indiscernibility relation and positive region, analyzes the properties of indiscernibility relation, proposes and proves an equivalent and efficient method for computing positive region. Thus some efficient basic algorithms for rough set methods are introduced with a detailed analysis of the time complexity and comparison with the existing algorithms. Furthermore, this paper researches the incremental computing of positive region. Based on the above results, a complete algorithm for the reduction of attributes is designed. Its completeness is proved. In addition, its time complexity and space complexity are analyzed in detail. In order to test the efficiency of the algorithm, some experiments are made on the data sets in UCI machine learning repository. Theoretical analysis and experimental results show that the reduction algorithm is more efficient than those existing algorithms.
Keywords:rough set  upper approximation  lower approximation  core  reduct
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号