A novel attribute reduction algorithm using condensing tree

Attribute reduction is one of the key problems in rough set theory, and many algorithms based on discernibility matrix have been proposed and studied about it. Unfortunately, the existing algorithms have much higher space complexity. In order to reduce the computational complexity of discernibility matrix method, a novel condensing tree (C-Tree in short) is introduced for storing the same elements or the same attribute prefixes in discernibility matrix. However, the size of a C-Tree greatly may rely on the order of attributes in most cases. In this paper, we present a new attribute ordering strategy using indiscernibility attribute and improve the C-Tree for compressing discernibility elements. Further, we design a novel attribute reduction algorithm with the improved C-Tree. Experiments show that our algorithm outperforms other attribute reduction algorithms.