# Select best distance for feature selection

Suppose I have matrix $X \in R^{n \times m}$, where $n$ is the number of individuals and $m$ is the number of features and $X[i,j] \in \{0,1\}$; $1$ indicates that the individual $i$ has the feature $j$, and $0$ means not.

Individuals only belong to one of the two classes.

Given a distance metric $Dist$ (any distance), I want to select the best set of features that gives me the maximum $KLD$ between the two classes.

Is there any feature selection algorithm that can given a distance select the best features?

Ultimately, I would like to test a bunch of distances.

• Your first step should probably be to write the problem down formally as a combinatorial optimization problem. Then you need to figure out of if the problem is NP-complete (note that many such problems are NP-complete). If it is NP-complete, you will not be able to find the optimal solution unless your dataset is very small. However, you can still use heuristics or approximate algorithms to find a reasonable solution. – Bitwise Jul 14 '13 at 17:36