A fast attribute reduction algorithm based on sorting and quantity of information

Abstract

Attribute reduction means that redundant attributes are excluded from decision table and it is an important topic in rough set theory research. Firstly, this paper proposes a new algorithm for computing equivalence classes based on subsection quick sort and obtains a higher efficiency compared with traditional algorithms. On this basis, the algorithm for computing refined decision table is given, which makes it possible to discover attribute reduction by using part objects. Finally, a fast attribute reduction algorithm which uses quantity of information as heuristic information is presented. Time complexity of the algorithm is O( $|$ C ${|}^2|$ U/C $|$ ). Theoretical analysis and experimental results show that the algorithm proposed in this paper is efficient and provides a good job for follow-up work.