A novel approach to improving C-Tree for feature selection

Rough set approach is one of effective feature selection methods that can preserve the meaning of the features. So far, many feature selection (also called feature reduction) methods based on Rough set have been proposed. Of which, methods based on discernibility matrix are of considerable benefits for their conciseness and effectiveness, but have much higher space complexity. In order to reduce the storage space of the existing feature selection methods based on discernibility matrix, a novel condensing tree (C-Tree) structure was introduced, which is an extended order-tree, every nonempty element of a discernibility matrix is stored in one path in the C-Tree by given order of features and lots of nonempty elements share one path or sub-path, so the C-Tree has much lower space complexity as compared to discernibility matrix. However, the size of a C-Tree greatly depends on the order of features in most cases, hence how to set the proper order of features is of importance. To generate a higher compressed C-Tree, in this paper, after introducing an efficient trick for efficiently measuring the relative importance of every feature, we present a new feature ordering strategy according to the descending order of their importance. Further, based on the new feature ordering strategy, corresponding two heuristic algorithms for feature selection are introduced. Algorithms of this paper are experimented using six standard datasets and five synthetic datasets for testing both time and space complexities. Experimental results show that the newly improved feature selection algorithm can further efficiently reduce cost of storage in most cases.