Rough集高效算法的研究  

Research on Efficient Algorithms for Rough Set Methods

作　　者：刘少辉[1] 盛秋戬[1] 吴斌[1] 史忠植[1] 胡斐[2] 

机构地区：[1]中国科学院计算技术研究所智能信息处理重点实验室,北京100080 [2]上海体育学院体育管理系,上海200438

出　　处：《计算机学报》2003年第5期524-529,共6页Chinese Journal of Computers

基　　金：国家自然科学基金 (60 173 0 17;60 0 73 0 19;90 10 40 2 1);北京市自然科学基金重点项目 (4 0 110 0 3 )资助

摘　　要：深入分析了现有Rough集算法低效性的根源 ,围绕不可区分关系和正区域两个核心概念 ,研究了不可区分关系的性质 ,给出并证明了正区域的一种等价计算方法 ,从而得出高效的Rough集基本算法 ;随后 ,分析了正区域的渐增式计算 ,并给出了一种完备的属性约简算法 .理论分析和实验结果表明 ,该约简算法在效率上较现有的算法有显著提高 .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.

关 键 词：ROUGH集 高效算法 属性约简 人工智能 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]