scikit-learn/scikit-learn — pull request #2131 by glouppe (2013-07-06 13:47:44+00:00)
Title: [WIP] Complete rewrite of the tree module 

Here are some good news for Kaggle competitors... :)

In this PR, I propose a complete rewrite of the core tree module (`_tree.pyx`) and of all tree-dependent estimators. In particular, this new implementation factorizes out the splitting strategy at the core of the construction process of a tree. Such a strategy is now implemented in a `Splitter` object as specified in the new interface in `_tree.pxd`. As of now, this PR provides two splitting strategies, `BestSplitter` for finding the best split in a node (this is CART) and `RandomSplitter` for finding the best random split (this is Extra-Tree).

The PR adresses 3 issues with the module: modularity, space and speed.

1) Modularity: It is now more convenient to write a new Splitting strategy. For example, one could now easily write a splitting strategy based on binning and plug it in the module.

2) Space: no more X_argsorted, no more sample_mask, no more min_density stuff. No more dupplicates of X! A tree is now directly built on the original version of X.

3) Speed: Both Random Forest and Extra-Trees have been speeded up. The most significant improvement benefits to Extra-Trees which are now properly implemented, i.e. without any sorting.

As a small benchmark, I did a little experiment on mnist3vs8 (around ~12000 samples, 784 features, 2 classes):

```
Parameters:
n_estimators=10
max_features=5
bootstrap=False
random_state=0
all other defaults

master
RandomForestClassifier
In [4]: %timeit -n 5 clf.fit(X_train, y_train)
5 loops, best of 3: 22.2 s per loop

ExtraTreesClassifier
In [7]: %timeit -n 5 clf.fit(X_train, y_train)
5 loops, best of 3: 25.8 s per loop

trees-v2
RandomForestClassifier
In [5]: %timeit -n 5 clf.fit(X_train, y_train)
5 loops, best of 3: 1.33 s per loop
=> Speedup = 16.7x

ExtraTreesClassifier
In [9]: %timeit -n 5 clf.fit(X_train, y_train)
5 loops, best of 3: 757 ms per loop
=> Speedup = 34.08x
```

I think the figures speak for themselves... :-)

---

This is still a work in progress and lot of work still needs to be done. However all tests in `test_tree.py` and `test_forest.py` already pass.

On my todo list:
[ ] Fix the GBRT module for the new interface
[ ] Fix the AdaBoost module for the new interface
[ ] Depecrate removed parameters
[ ] Handle negative sample weights (weights are assumed non-negative for now, without any checking)
[ ] PEP8 / Flake

Once all of this is done, I'll call for reviews. My goal is to have this beast merged in during the sprint. I think it is shaping up very well... :)

CC: @pprett @bdholt1 @ndawe @arjoly