Literature on the algorithm for optimal splitting in the growing of classification trees

Question

In ESL, Section 9.7, there is a paragraph stating that the computation time of a split in the growing of a classification (or regression) tree typically scales like $p N \log N$ where $p$ is the number of predictors and $N$ is the number of samples.

A naive approach results in a $pN^2$ scaling, and I haven't been able to find any references to the literature that explains the details for the splitting part of the algorithm and how one achieves a typical $p N \log N$ scaling.

In the naive approach the optimal split for a given variable, after an initial ordering of the observed values, is sought among the $N-1$ midpoints between the observed values, and computing the loss for each split can be done in time that scales like $N$.

I could (and will probably) study the source code for some of the implementations I know, but a literature reference would be nice $-$ in particular regarding the time complexity.

Answer 1

I will give a different answer, since is too much for a comment and it treats a more general approach.

So, in ESL, they describe indeed the computation time for a branch-and-bound (more precisely it looks like a divide and conquer to me).

We denote with $N$ the number of observations and with $K$ the number of children nodes, when we grow a tree. I assume we do not loose in generality if we consider $K$ to be fixed. Also, we can denote with $f(N)$ the processing time for computing split points at a given node.

Thus, we can write recursively the formula for the execution time like: $$T(N) = f(N) + K * T(N/K) $$ we considered here that the child nodes split the input data set of size $N$ in $K$ subsets of equal size $N/K$. We know that tis is the best case.

However, we can see that this is a well-know application of Master Theorem. This is well documented in CLRS book. I have the 3rd edition and the details are at section 4.5 and proof is at the next section. I do not remember well the details, but I remember is not too complicated if one expands the recursion and group some terms together.

However, what is important for this case is than when $f(N)=O(N)$ - linear time, the resulting time of the algorithm is $T(N) = O(N logN)$. This time is computed for a single input variable, thus, our total time for $P$ variables would be $O(P N logN)$

This time is achievable for tree growing, if all the inputs are initially sorted in $O(P N logN)$, and finding the splitting value takes linear time on this sorted inputs. Here we can apply the on-line variance algorithm, as I mentioned in my previous answer for $L_2 = \frac{1}{N}(y-\hat{y})^2$ . For $L_1 = \frac{1}{N}|y-\hat{y}|$ is even easier to find median. I confess I never tried out some other loss function for trees.

Note however that the Master Theorem applies for the best case if the splits are equal in size. The worst case is when the split is very unbalanced. There, one can apply a different case of Master Theorem and the time will become $O(P N^2)$.

As a conclusion I assume that ESL authors use the term typically in a way that is used for describing the quick-sort algorithm. Typically quick sort gives $O(N logN)$ running time, having worst case $O(N^2)$, for some specific data setups.

I hope it helps.

Answer 2

See my answer from another question here. While I do not have paper references, you can trivially find yourself that for $p$ numeric inputs of length $N$ you have to:

• iterate over all $p$ inputs - $O(p)$
• sort ascending each input - $O(N log(N))$
• compute 2 running variances one starting from left and one starting from right in linear time - $O(N)$

The dominant time for each attribute is the sorting time, thus we have $O(p N log(N))$.