Stable Feature Selection with Minimal Independent Dominating Sets

In this paper, we focus on stable selection of relevant features. The main contribution is a novel framework for selecting most informative features which can preserve the linear combination property of the original feature space. We propose a novel formulation of this problem as selection of a minimal independent dominating set (MIDS). MIDS of a feature graph is a smallest subset such that no two of its nodes are connected and all other nodes are connected to at least one node in it. In this way, the diversity and coverage of the original feature space can be preserved. Furthermore, the proposed MIDS framework complements standard feature selection algorithms like SVM-RFE, stability lasso and ensemble SVM RFE. When these algorithms are applied to feature subsets selected by MIDS as opposed to all the input features, they select more stable features and achieve better prediction accuracy, as our experimental results clearly demonstrate.