4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Bitwise Jul 14 '13 at 17:36
2
+50
$\begingroup$

The way you formulate your problem, as a black box, invites to use (as Bitwise says) combinatorial search methods. The most accurate is Branch and Bound, but you may consider suboptimal and less computationally heavy methods like the floating selection methods, which are also quite trivial to implement. The latests are basically greedy search algorithms.

As I understand, all these methods apply for your particular problem, since you are using a distance function which thus verify the monotonicity condition. This paper offers you a more up to date overview on the topic.

P.S. In forward feature selection you start with an empty feature set. Then you look for the feature out of the total set which leads the maximum KLD. And then you go on proceeding like this until you see very small or no improvement, or until you reach a given number of features. In backward selection you proceed in the opposite direction: you start with the whole set of features, and go step by step eliminating the one whose absence worsens the maximum distance the least. The one whose removal harms the least.

That should be easy to try. For more advanced techniques, you may have a look at some packages like scikit or weka.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, it helps a bit. I think I should give me some guidance $\endgroup$ – sirus Jul 16 '13 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.