4
$\begingroup$

I read about the time complexity of Decision Tree Algorithms like CART, and understand why the time complexity, with sorting, can be approximated as $O(m n^2 \log n)$.

I will try to go through the calculation by my own words, which might help down the road of answering my main question.

Sorting $n$ elements, in general takes $O(n\log{n})$, assume we have $m$ features in our dataset, overall sorting at the root node takes $O(m n\log{n})$. The depth of a balanced binary tree can be computed as $\log n$, which gives us $2^{\log{n}}=n$ leaf nodes, where no further splitting is done. Since we have overall $2n -1$ nodes, we have $2n-1-n=n-1$ nodes where actually look for the best split. This leads overall to $O(m n^2 \log n)$. Let me know, if I am mistaken here already.

But, why exactly do we sort in the first place? We have to consider every feature and the corresponding unique values anyways, to find the maximum gain. I found a source that argued:

"It can be shown that optimal binary split on continuous features is on the boundary between adjacent examples with different class labels . This means that sorting the values of continuous features helps with determining a decision threshold efficiently" (https://sebastianraschka.com/pdf/lecture-notes/stat451fs20/06-trees__notes.pdf).

However, I cannot figure out why this lets us determine the threshold more efficiently.

$\endgroup$

1 Answer 1

1
$\begingroup$

The algorithms needs to sort to do it efficiently. The decision tree is trying to find a threshold $\tau$ for a specific feature to split the samples into two nodes. When you have $n$ different values for a given feature, e.g. $x_1, x_2, ... x_n$, the best way to find a threshold is sorting these values, and trying each boundary (that is the mid-point between the two adjacent samples). There are theoretically $n-1$ different boundaries to try, but w/o sorting the features, you won't be able to see efficiently which boundary values you need to try.

$\endgroup$
8
  • 1
    $\begingroup$ The point being that the splits are determined based on the mid-point between the two closest points, that's why there are n-1 possible splits and why sorting is a good idea. $\endgroup$ Jan 6, 2023 at 12:06
  • $\begingroup$ splitting on mid points only holds for continuous values though, right? Why would we split on mid points of categorical features? $\endgroup$
    – kklaw
    Jan 6, 2023 at 12:08
  • $\begingroup$ @kklaw Categorical variables are transformed before training, usually into dummy variables - 0 and 1's. In that case the mid-point is 0.5, which then either includes or excludes this class. $\endgroup$ Jan 6, 2023 at 12:14
  • $\begingroup$ What if there are more than 2 categorical variables? like color: red, green, blue? We can also easily include or exclude a class without the mid point, can't we? Moreover, we will never encounter values like $0.7$ in one of our categorical features, where the mid point would help, since we transform them to numerical values explicitly. $\endgroup$
    – kklaw
    Jan 6, 2023 at 12:27
  • 1
    $\begingroup$ @gunes some implementations handle categorical features by making bipartitions of the categories, sometimes using mean responses to reduce the number of candidates: datascience.stackexchange.com/a/52103/55122 According to this answer, that was already part of the original CART paper: datascience.stackexchange.com/a/64760/55122 $\endgroup$ Jan 6, 2023 at 14:41

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.