# How to split nodes in regression trees

I am looking for a comparison of different regression tree node splitting approaches within the random forest framework. I am looking at the trade-off between ensemble accuracy/reliability (holding forest size constant) and computational complexity of the split since I deal with large datasets.

The standard approach is to minimise $$\sum_{i \in \text{Region}_1} (y_i - \text{mean}(y_i)_{\text{Region}_1})^2 +\sum_{i \in \text{Region}_2} (y_i - \text{mean}(y_i)_{\text{Region}_2})^2$$ But another approach I have seen in a PhD thesis which drastically reduces the computational complexity is to look at the average of $$\frac{(\sum_{i \in \text{Region}_1} y_i)^2}{(\text{Cardinality of Region}_1)}$$ versus the same for $\text{Region}_2$; this allows me to use a running sum of $y_i$.

You can compute variance with the same cost as the averages. Simply put you have to use an on-line version of algorithm for computing variance. It is crystal clear explained on an article of John D. Cook. I used myself this online computing for a regression tree - split numeric method where I use an online computation of variance. I used to compute 2 running statistics, one starting from left and another one starting from right. It is possible to do that in a single step, I considered however that multiplication by a constant, gives also linear time and that does not bother me.