0
$\begingroup$

I know there is a partial answer here but my question is slightly different. I have implemented a decision tree in sklearn. Say I have $2^n$ different values for a feature, with just one feature. I was expecting that a good decision tree should be able to keep the depth at or below $n$. Let's say the $2^n$ values for the features are indexed ($1 \dots 2^n$), if I make a split in the middle, that is the most effective way, and I can get a leaf with just one element at the end of a a n-deep tree.

Of course, it could be less, if, for example, I only have two categories, and all the elements below $2^{n-1}$ are in one class, and the other elements in the other class. But, in the worst case, I thought I should have depth $n$. However, when I implemented a solution for just around 1 million examples with one feature that has about 100,000 values, I got a tree with depth 125! (and I was expecting about 17).

Why is that?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

There is an assumption in the statement if I make a split in the middle. The assumption is the tree will always split at the middle value = the median value so half the values go right and the other half go left. The split could be anywhere. And importantly the split focuses on the number of records at each value (think histogram).

Lets take the 100K values and 1m records. The root split could be, the records with the max value goes right, all other records go left. Then the next split on the left says the records with the max value of those 99,999 values go right, all other records go left. And so on. In this case it peels off one value, and all records with that value, at each split.

That is an extreme example but it illustrates the point. The split could be the min, max or anywhere in between. The number of records at each value is what is important.

You can research the answer to your tree by exporting the tree which will show you the splits and the split statistic for each node.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Of course, I know that, but that would be a stupid way to do it. I am assuming the implementation is smarter than that, any implementation should optimise things, not make them worse. $\endgroup$
    – user
    Oct 13, 2017 at 20:50
  • $\begingroup$ The decision tree is trying to optimise classification accuracy, not tree depth. This means sometimes you will end up with very unbalanced trees. The only case where the split points would be at the median is when this maximises the information gain at that split node. $\endgroup$
    – timleathart
    Oct 13, 2017 at 21:03

Your Answer

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

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