# Classifier optimization

Suppose we have a set E of entities. Each entity is described by a set P of binary properties (i.e. each element e of E has a defined true/false value for each element p of P).

|P| >> |E|

We now want to select a subset of fixed size (e.g., 10) of P that will enable us distinguish the elements in E as accurately as possible.

In extensions of this basic scenario, the properties could assume numeric values.

Has this problem been studied? Under what name?

A practical example: there is a set of 100 bacterial species that are characterized for the presence or absence of 1000 genes. We now want to select a subset of 10 genes that, upon typing of a novel sample, will tell us which bacterial species that sample represents.

• I'm not sure how to tag this. There's "classifier" in the title, but nowhere in the body. There's "optimization" in the title, but you don't require an optimal anything in the body. Anyway: is clustering what you want?
– Raphael
Jan 8 '16 at 18:04
• 1. How you want to measure "accuracy"? I can imagine multiple ways to do it, each of which would lead to a different optimum answer. Do you have a particular way in mind? 2. Have you looked at methods from machine learning, e.g., ID3 for building decision trees, etc.? 3. How large is $|P|$? Is it small enough that you could plausibly consider all subsets of size 10?
– D.W.
Jan 8 '16 at 19:34
• @Raphael: clustering is probably not what I want. Optimization comes in via "as accurately as possible", but I recognize that I haven't specified a loss function - more or less deliberately, because I am not necessarily looking for a specific solution but for keywords and known approaches to seach for relevant literature. Jan 9 '16 at 13:21
• @D.W.: 1.There will be some probability distribution over the elements of |E|, and there will be a decision rule for cases in which the chosen subset won't allow for un-ambiguous resolution. Something where we assing the same cost to each mis-assignment, and then the expected value of this measure? 2. Not in detail. In particular, ID3 is new to me. Thanks. 3. No - |P| could have billions of elements. Jan 9 '16 at 13:23

If you need the optimal answer, the best solution I know is exhaustive search: try all ${|P| \choose 10}$ different subsets, and see which is best. The running time of this will be $O(|P|^{10})$, though, which is probably too high to be feasible.
One standard approach is to use a greedy algorithm: you iteratively build up a set of properties, one by one. At each step, if your set is currently $S$, you choose the property $p$ that makes $S \cup \{p\}$ as accurate as possible, and then add $p$ to $S$. To turn this into a full algorithm, you need to decide how you want to measure/evaluate each candidate $S \cup \{p\}$.