Rough集高效算法的研究

Research on Efficient Algorithms for Rough Set Methods

深入分析了现有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.