Integration of dense subgraph finding with feature clustering for unsupervised feature selection

• Unsupervised feature selection approach using densest finding approach followed by feature clustering.
• Usage of normalized mutual information scores for computing similarity as well as dissimilarity.
• Superiority over three existing methods is established for eight data sets.

In this article a dense subgraph finding approach is adopted for the unsupervised feature selection problem. The feature set of a data is mapped to a graph representation with individual features constituting the vertex set and inter-feature mutual information denoting the edge weights. Feature selection is performed in a two-phase approach where the densest subgraph is first obtained so that the features are maximally non-redundant among each other. Finally, in the second stage, feature clustering around the non-redundant features is performed to produce the reduced feature set. An approximation algorithm is used for the densest subgraph finding. Empirically, the proposed approach is found to be competitive with several state of art unsupervised feature selection algorithms.