Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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 Region_1} (y_i - mean(y_i)_{Region1})^2$ +$\sum_{i \in Region_2} (y_i - mean(y_i)_{Region2})^2$. But another approach I have seen in a PhD thesis which drastically reduces the computational complexity is to look at the average of $(\sum_{i \in Region_1} y_i)^2/(Cardinality of Region_1)$ versus the same for $Region_2$; this allows me to use a running sum of $y_i$.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

For more information you can take a look on Wikipedia also.

share|improve this answer
Very nice. What do you mean by 'constant time'. Wouldn't it be linear time? –  Jase Feb 5 '14 at 7:34
Sorry, I was meaning multiplication by a constant time, since I compute 2 running statistics. I will correct that in the answer. –  rapaio Feb 5 '14 at 7:39
How do you handle the large amounts of noise in the variance estimate in the first few iterations (whether starting from front or back of the vector)? –  Jase Feb 6 '14 at 15:12
@Jase I do not have an answer. What I usually do in practice is to adjust the parameter which decides the minimum number of instances in a node. If there is plenty of data, then is no problem to have a large value for this minimum. If it is not, then I try to take a look at my data and understand from the underlying distribution which would be a proper value for this parameter. I imagine that one could automate that by trying to estimate a confidence interval for the variance estimation, but I never tried to work on that. –  rapaio Feb 6 '14 at 16:07
The 'regression tree.' link is invalid. –  honeytidy Jan 29 at 3:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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