Relevant Feature Selection from High-Dimensional Data Using MST Based Clustering

Feature selection is the process of identifying a subset of the most useful features that produces compatible results as the original entire set of features. Features provide the information about the data set. In High-dimensional data representation each sample is described by many features. The data sets are typically not task-speciï¬c, many features are irrelevant or redundant and should be pruned out or ï¬ltered for the purpose of classifying target objects. Given a set of features the feature selection problem is to find a subset of features that “maximizes the learner’s ability to classify patternsâ€. A graph theoretic clustering algorithm based on boruvka’s algorithm is implemented and experimentally evaluated in this paper. The proposed algorithm works in two steps. In the first step, features are divided into clusters by using graph-theoretic clustering methods. In the second step, the most representative feature that is strongly related to target classes is selected from each cluster to form a subset of features. All the representative features from different clusters form the final feature subset. After finding feature subset accuracy of a classifier, time required for classification and proportion of features selected can be calculated.

Keywords: Boruvka’s Algorithm, Graph theoretic clustering, Filter Method, Wrapper Method, Embedded Approach