Decision tree with equal points

Question

Suppose I have a decision tree built, and in the training set there are two points, say $x_1$ and $x_2$, which are completely equal. What happens if I remove exactly one of them from the training data? Will the decision tree be changed?

Answer 1

The decision tree might or might not change depending on your dataset. The decision tree is likely to change if your dataset has a small number of points.

For example, let $T$ be a training set with one continuous attribute $A$ and a binary target class $C$. Let us use the Gini gain $\Delta$ as splitting criterion - see an example here. Let's say you have two duplicated points $x_1$ and $x_2$ with $x_1 = x_2$.

If your dataset is:

A C
1 +
1 +
2 -

Then there will be no difference by removing one duplicated point (e.g. the first one). The dataset will be split in two sets according to the cut-off $1$ for $A$ anyway.

If your dataset is:

A  C
1 +
1 +
2 -
3 +
4 +
5 -

The split induced on this dataset will be different from the split induced on the dataset where we remove the duplicated point (e.g. the first one).

• The split induced on this dataset will be found by optimizing $\Delta$ on all possible cut-offs for $A$. If you do it, you will see that the best $\Delta$ is obtained with $1$ as cut-off for $A$. ($\Delta = 0.11$);
• If we remove the first point, the optimization procedure will select the cut-off $4$ for $A$. The cut-off $1$ has $\Delta = 0.08$, the cut-off on $2$ has $\Delta = 0.013$, and the cut-off $4$ has $\Delta = 0.18$.

The two examples above are both related to a small number of points. You can imagine that what happened in the second example is more likely to happen if the number of data points is small. Therefore, it is more likely that the nodes at the bottom of your decision tree change rather than the nose at the top, i.e. it is very difficult that the root node of a decision tree changes.

Answer 2

The splitting points may or may not be changed at all, the decision splits are dependent on all the data at a node - not just 2 points. Even if they did change, the change from the removal of any 1 point is likely to be very minimal. At least 1 leaf node's probability scores will be changed very slightly since there is one less data point.