Summary: A decision tree (aka identification tree) is trained on a training set with a largish number of features (tens) and a large number of classes (thousands+). It turns out that every feature is important to distinguish some subset of classes, but most classes require only a small number of features to unambiguously classify them. This is a different set of features for every class. When classifying new observations, instead of observing all features at once and feeding that into the classifier, I want to observe one feature at a time, and decide on the next most interesting feature based on the features observed up to that point. How can I do this?
As an example, consider the following imaginary scenario:
A physician has found that he is often able to accurately diagnose many patients by looking solely at their biochemical test results. He draws some blood from the patient, sends it to the lab, which subjects it to a barrage of tests all of which yield a ternary result: Positive, negative or inconclusive. Each test has its own associated cost, and requires additional volume of blood drawn, so tests that fail are not automatically re-done unless specifically requested, and occasionally all tests may yield incorrect results. The physician notices that with the full set of 50 measurements, it is usually possible to diagnose anyway even if some are incorrect or inconclusive, provided that most are correct.
The physician asks me to automate this process into a software. He has already performed 1,000 diagnoses in this way, and kept a record of the full set of 50 results with about 300 different diseases between them. Some diseases are observed more than others, but in all no single disease is observed more than 10 times. I decide to use this is as training data for a decision tree, after which for every new patient the test panel results can be simply fed into the tree and automatically assigned to a disease.
After getting this set up and trying it on a few new patients, we find that the model can accurately diagnose patients as expected, if given a full set of 50 tests. However, we also notice that many diseases can be diagnosed with high certainty using only a small subset of tests, such as 5-15. They are different tests for each cluster of diseases. For example, tests #1, #6, #38, #42 and #47 will only be positive in diseases A and C, which can be distinguished with only tests #8 and #11. So if we happen to know that #1, #6, #38, #42 and #47 are all positive, all we need to do is perform two more tests, and we will be able to diagnose the patient with only 7 tests instead of 50. But this is only applicable for patients that happen to have A or C. Patients with other diseases will come back negative for 1 of these 5 tests, and we will have to order more tests. A similar situation exists with D, F and H: Only these three diseases are negative on #5, #7, #31, #36, #47 and #49. Given this, they can be distinguished among themselves by looking at results of #2, #3 and #5. So for diagnosing diseases D, F and H only 9 tests in all are sufficient, but they are not the same tests as in A/C. This turns out to be a common situation in my dataset, such that no features are unimportant, every feature is important for some classes, and most classes require only a subset of features while very few classes require all features or most features to be known to classify them.
In this case, we can select some number of initial features using standard feature importance methods, and have those tested by default for every patient. However, by looking at the results of that first set of tests, we can substantially narrow down the possible classes, and which of the remaining features are worth looking at. However, since the data contains some error, this narrowing down is probabilistic - even though a class is "ruled out" by a given test result, it may still be the case that the test result was an error, and when subsequent additional tests produce unexpected results this error should become apparent.
So the logical conclusion of this is, as in my summary, to go in sets of 1. The first feature can be selected in some way, and then based on its result, the next feature can be selected, then the next one, and so on. The path through the features (ie. the walk on the decision tree) will be different for every sample. But, for a single vector, given the values of $n$ features, how can we determine the $n+1$th most informative feature?
I am using the DecisionTreeClassifier from scikit-learn. In theory I would be traversing down the tree and the next node is the most relevant feature, but:
- How do I get this out of
scikit-learn? - What about second-best classes?
PS: I have since stumbled on a lecture by Dr. Winston where he seems to discuss very related concepts, but in the context of learning the decision identification tree rather than actually classifying. I feel like I just about know what to do, but can't quite put my finger on exactly what, whether it will still work with contradictory (noisy) inputs, and how to apply it with scikit-learn.
