Abstract HTML Views: 256 PDF Downloads: 190 Total Views/Downloads: 446
Abstract HTML Views: 157 PDF Downloads: 117 Total Views/Downloads: 274
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 POSC(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 POSC(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|2|U/C|). The sample analysis and experimental results show that the attribute reduction algorithm presented in this
paper is feasible and efficient.