Mathematical calculation behind decision tree classifier with continuous variables

Question

I am working on a binary classification problem having continuous variables (Gene expression Values). My goal is to classify the samples as case or control using gene expression values (from Gene-A, Gene-B and Gene-C) using decision tree classifier. I am using the entropy criteria for node splitting and is implementing the algorithm in python. The classifier is easily able to differentiate the samples.

Below is the sample data,

sample training set with labels

Gene-A    Gene-B    Gene-C    Sample
   1        0         38       Case
   0        7         374      Case
   1        6         572      Case
   0        2         538      Control
   33       5         860      Control

sample testing set labels

Gene-A    Gene-B    Gene-C    Sample
  1         6        394       Case
  13        4        777       Control

I have gone through a lot of resources and have learned, how to mathematically calculate Gini-impurity, entropy and information gain.

I am not able to comprehend how the actual training and testing work. It would be really helpful if someone can show the calculation for training and testing with my sample datasets or provide an online resource?

Answer 1

Of course, it depends on what algorithm you use. Typically, a top-down algorithm is used.

You gather all the training data at the root. The base decision is going to be whatever class you have most of. Now, we see if we can do better.

We consider all possible splits. For categorical variables, every value gets its own node. For continuous variables, we can use any possible midpoint between two values (if the values were sorted). For your example, possible splits are Gene-A < 0.5, Gene-A < 17, Gene-B < 1, Gene-B < 3.5, and so on. There is a total of 10 possible splits.

For each of those candidate splits, we measure how much the entropy decreases (or whatever criterion we selected) and, if this decrease looks significant enough, we introduce this split. For example. Our entropy in the root node is $-0.4 \log_2 0.4 - 0.6 \log_2 0.6 \approx 0.97$. If we introduce the split Gene-A < 0.5, we get one leaf with entropy $1$ (with 2 data points in it), and one leaf with entropy $0.918$ (with 3 data points). The total decrease of entropy is $0.97 - (\frac25 \times 1 + \frac35 \times 0.918) \approx 0.02$. For the split Gene-A < 17 we get a decrease of entropy of about $0.3219$.

The best splits for the root are Gene-B < 5.5 and Gene-C < 456. These both reduce the entropy by about $0.42$, which is a substantial improvement.

When you choose a split, you introduce a leaf for the possible outcomes of the test. Here it's just 2 leaves: "yes, the value is smaller than the threshold" or "no, it is not smaller". In every leaf, we collect the training data from the parent that corresponds to this choice. So, if we select Gene-B < 5.5 as our split, the "yes" leaf will contain the first, fourth and fifth data points, and the "no" leaf will contain the other data points.

Then we continue, by repeating the process for each of the leaves. In our example, the "yes" branch can still be split further. A good split would be Gene-C < 288, which results in pure leaves (they have 0 entropy).

When a leaf is "pure enough" (it has very low entropy) or we don't think we have enough data, or the best split for a leaf is not a significant improvement, or we have reached a maximum depth, you stop the process for that leaf. In this leaf you can store the count for all the classes you have in the training data.

If you have to make a prediction for a new data point (from the test set), you start at the root and look at the test (the splitting criterion). For example, for the first test point, we have that Gene-B < 5.5 is false, so we go to the 'no' branch. You continue until you get to a leaf.

In a leaf, you would predict whatever class you have most of. If the user wants, you can also output a probability by giving the proportion. For the first test point, we go to the "no" branch of the first test, and we end up in a leaf; our prediction would be "Case". For the second test point, we go to the "yes" branch of the first test. Here we test whether 777 < 288, which is false, so we go to the "no" branch, and end up in a leaf. This leaf contains only "Control" cases, so our prediction would be "Control".