2
$\begingroup$

I am studying decision tree and I would like to know if this case is possible:

We have 2 features, each does not decrease the Gini of the previous node (=> not choose), but their combination (two decisions one after another) decrease the Gini over the previous one (=> loose information)

Possible or not?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes, it is possible. XOR problem is a simple example for this case. The dataset is $$C_1=(0,1),(1,0), C_2=(1,1),(0,0)$$ where $C_i$ is class $i$. In the root, the class distribution is $1/2-1/2$. Any split (e.g. $x\lessgtr 0.5$, $y\lessgtr0.5$, ...) will result in the same class distribution, so information gain is 0 or gini-index will not decrease. But, the in next step, we'll perfectly classify the samples.

So, a decision tree implementation with strict improvement condition on one level won't be able to learn this dataset.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you very much for your answer. So we can conclude: "The CART algorithm [...] does not check whether or not the split will lead to the lowest possible impurity several levels down. [...] often produces a solution that’s reasonably good but not guaranteed to be optimal." Keras, and TensorFlow by Aurelien Geron $\endgroup$
    – Lucas Bensaid
    Commented Jan 17, 2021 at 11:54
  • 1
    $\begingroup$ Yes, of course. Finding the optimal decision tree is np-complete, and the current algorithms follow the greedy approach. See the following: people.csail.mit.edu/rivest/… $\endgroup$
    – gunes
    Commented Jan 17, 2021 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.