Research on Efficient Algorithms for Rough Set Methods
Liu Shao · Chinese Journal of Computers · 2003
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.