5
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ but those two points have exactly same feature. Will it do sth? $\endgroup$ – JumpJump Sep 30 '15 at 17:12
  • $\begingroup$ I have already answered the question. If you don't understand the Decision Tree learning algorithm well enough that is a separate issue entirely. $\endgroup$ – Raff.Edward Sep 30 '15 at 17:19
  • $\begingroup$ ah sorry, I will try to study it again. Yea I am just get start in Machine learning, sorry for this non-sense question. $\endgroup$ – JumpJump Sep 30 '15 at 17:21
  • 1
    $\begingroup$ It's not a non-sense question, it's a good question. A good answer would explain why the algorithm would potentially produce a tree of different structure. $\endgroup$ – Matthew Drury Sep 30 '15 at 17:44

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.