Attribute Reduction Based on Sorting and Incremental Method

ABSTRACT

Positive region is one of the core concepts in rough set theory. Time complexity of computing the positive region can directly affect other algorithms. In this paper, a new algorithm for computing equivalence classes based on generalized quick sort and insertion sort is provided and its time complexity for computing U/C is cut down to O(|C||U|) compared with other traditional algorithms. On this basis, an algorithm for fast computing positive region by adding identifier attributes to sorted decision tables is proposed and its time complexity for computing POS_C(D) is cut down to O(|C||U|) accordingly. By using this foundation, two incremental algorithms for fast computing positive region are designed. They make full use of equivalence classes and positive region which already exist to compute positive region incrementally. Thus, these algorithms can reduce the computational work significantly and get higher efficiency. Among them, the algorithm based on multi-way tree is the most efficient. Its time complexity for computing POS_C(D) is far less than O(|C||U/C|). Finally, an attribute reduction algorithm based on incremental method is given and its time complexity is O(|C|²|U/C|). The sample analysis and experimental results show that the attribute reduction algorithm presented in this paper is feasible and efficient.

Keywords: