Graph-Based Feature Selection in Classification: Structure and Node Dynamic Mechanisms

Recently, researchers pay more attention to designing graph-based methods to address the feature selection problem, since these methods can effectively utilize the underlying topology structure and complex relationships between nodes in the constructed feature graph. Therefore, they can obtain the feature subset with high quality. The existing graph-based methods mainly focus on using different graph-theoretical techniques to select features from the constructed feature graphs. However, little attention is focused on constructing a suitable feature graph for feature selection, which is also an important component for achieving a good feature subset. To fill the gap, in this paper, a novel graph-based algorithm named GBFS-SND is proposed for feature selection, where the structure and node dynamic mechanisms are designed to directly optimize the performance of feature selection. To be specific, in GBFS-SND, a candidate feature graph is firstly created by considering both the importance of feature and the relations between features. Then, on the created candidate graph, an MOEA-based structure dynamic mechanism is suggested to acquire a feature subgraph with better structure, from which we can obtain a promising feature subset. Finally, a node dynamic mechanism is also suggested, with which the weights of the nodes are dynamically adjusted as the structure of feature graph changes. Thus, the performance of GBFS-SND can be further enhanced. Empirical studies are conducted by comparing the proposed algorithm with several state-of-the-art feature selection methods on different data sets. The experimental results demonstrate the superiority of GBFS-SND over the comparison methods in terms of both the accuracy and the number of selected features.