scikit-learn · glemaitre · Feb 7, 2017 · Feb 8, 2017 · Feb 8, 2017 · Feb 8, 2017
diff --git a/sklearn/__init__.py b/sklearn/__init__.py
@@ -143,7 +143,8 @@ def config_context(**new_config):
                'mixture', 'model_selection', 'multiclass', 'multioutput',
                'naive_bayes', 'neighbors', 'neural_network', 'pipeline',
                'preprocessing', 'random_projection', 'semi_supervised',
-               'svm', 'tree', 'discriminant_analysis',
+               'svm', 'tree', 'regression_tree', 'discriminant_analysis',
+               'exact_tree',
                # Non-modules:
                'clone']
 

diff --git a/sklearn/_build_utils/__init__.py b/sklearn/_build_utils/__init__.py
@@ -81,4 +81,4 @@ def maybe_cythonize_extensions(top_path, config):
             exc.args += (message,)
             raise
 
-        config.ext_modules = cythonize(config.ext_modules)
+        config.ext_modules = cythonize(config.ext_modules, annotate=True)
diff --git a/sklearn/ensemble/_gradient_boosting.pyx b/sklearn/ensemble/_gradient_boosting.pyx
@@ -18,12 +18,12 @@ np.import_array()
 from scipy.sparse import issparse
 from scipy.sparse import csr_matrix
 
-from sklearn.tree._tree cimport Node
-from sklearn.tree._tree cimport Tree
+from sklearn.exact_tree._tree cimport Node
+from sklearn.exact_tree._tree cimport Tree
 from sklearn.tree._tree cimport DTYPE_t
 from sklearn.tree._tree cimport SIZE_t
 from sklearn.tree._tree cimport INT32_t
-from sklearn.tree._utils cimport safe_realloc
+from sklearn.exact_tree._utils cimport safe_realloc
 
 ctypedef np.int32_t int32
 ctypedef np.float64_t float64

diff --git a/sklearn/ensemble/gradient_boosting.py b/sklearn/ensemble/gradient_boosting.py
@@ -29,6 +29,7 @@
 from .base import BaseEnsemble
 from ..base import ClassifierMixin
 from ..base import RegressorMixin
+from ..base import clone
 from ..externals import six
 
 from ._gradient_boosting import predict_stages
@@ -47,8 +48,10 @@
 from time import time
 from ..model_selection import train_test_split
 from ..tree.tree import DecisionTreeRegressor
-from ..tree._tree import DTYPE
-from ..tree._tree import TREE_LEAF
+# from ..tree._tree import DTYPE
+# from ..tree._tree import TREE_LEAF
+DTYPE = np.float32
+TREE_LEAF = -1
 
 from ..utils import check_random_state
 from ..utils import check_array
@@ -726,7 +729,7 @@ def __init__(self, loss, learning_rate, n_estimators, criterion,
                  random_state, alpha=0.9, verbose=0, max_leaf_nodes=None,
                  warm_start=False, presort='auto',
                  validation_fraction=0.1, n_iter_no_change=None,
-                 tol=1e-4):
+                 tol=1e-4, estimator=None):
 
         self.n_estimators = n_estimators
         self.learning_rate = learning_rate
@@ -750,6 +753,7 @@ def __init__(self, loss, learning_rate, n_estimators, criterion,
         self.validation_fraction = validation_fraction
         self.n_iter_no_change = n_iter_no_change
         self.tol = tol
+        self.estimator = estimator
 
     def _fit_stage(self, i, X, y, y_pred, sample_weight, sample_mask,
                    random_state, X_idx_sorted, X_csc=None, X_csr=None):
@@ -767,19 +771,34 @@ def _fit_stage(self, i, X, y, y_pred, sample_weight, sample_mask,
                                               sample_weight=sample_weight)
 
             # induce regression tree on residuals
-            tree = DecisionTreeRegressor(
-                criterion=self.criterion,
-                splitter='best',
-                max_depth=self.max_depth,
-                min_samples_split=self.min_samples_split,
-                min_samples_leaf=self.min_samples_leaf,
-                min_weight_fraction_leaf=self.min_weight_fraction_leaf,
-                min_impurity_decrease=self.min_impurity_decrease,
-                min_impurity_split=self.min_impurity_split,
-                max_features=self.max_features,
-                max_leaf_nodes=self.max_leaf_nodes,
-                random_state=random_state,
-                presort=self.presort)
+            if self.estimator is None:
+                tree = DecisionTreeRegressor(
+                    criterion=self.criterion,
+                    splitter='best',
+                    max_depth=self.max_depth,
+                    min_samples_split=self.min_samples_split,
+                    min_samples_leaf=self.min_samples_leaf,
+                    min_weight_fraction_leaf=self.min_weight_fraction_leaf,
+                    min_impurity_decrease=self.min_impurity_decrease,
+                    min_impurity_split=self.min_impurity_split,
+                    max_features=self.max_features,
+                    max_leaf_nodes=self.max_leaf_nodes,
+                    random_state=random_state,
+                    presort=self.presort)
+            else:
+                tree = clone(self.estimator)
+                tree.set_params(
+                    criterion=self.criterion,
+                    splitter='best',
+                    max_depth=self.max_depth,
+                    min_samples_split=self.min_samples_split,
+                    min_samples_leaf=self.min_samples_leaf,
+                    min_weight_fraction_leaf=self.min_weight_fraction_leaf,
+                    min_impurity_decrease=self.min_impurity_decrease,
+                    min_impurity_split=self.min_impurity_split,
+                    max_features=self.max_features,
+                    max_leaf_nodes=self.max_leaf_nodes,
+                    random_state=random_state)
 
             if self.subsample < 1.0:
                 # no inplace multiplication!
@@ -1526,7 +1545,7 @@ def __init__(self, loss='deviance', learning_rate=0.1, n_estimators=100,
                  random_state=None, max_features=None, verbose=0,
                  max_leaf_nodes=None, warm_start=False,
                  presort='auto', validation_fraction=0.1,
-                 n_iter_no_change=None, tol=1e-4):
+                 n_iter_no_change=None, tol=1e-4, estimator=None):
 
         super(GradientBoostingClassifier, self).__init__(
             loss=loss, learning_rate=learning_rate, n_estimators=n_estimators,
@@ -1541,7 +1560,7 @@ def __init__(self, loss='deviance', learning_rate=0.1, n_estimators=100,
             min_impurity_split=min_impurity_split,
             warm_start=warm_start, presort=presort,
             validation_fraction=validation_fraction,
-            n_iter_no_change=n_iter_no_change, tol=tol)
+            n_iter_no_change=n_iter_no_change, tol=tol, estimator=estimator)
 
     def _validate_y(self, y):
         check_classification_targets(y)
@@ -1969,7 +1988,7 @@ def __init__(self, loss='ls', learning_rate=0.1, n_estimators=100,
                  min_impurity_split=None, init=None, random_state=None,
                  max_features=None, alpha=0.9, verbose=0, max_leaf_nodes=None,
                  warm_start=False, presort='auto', validation_fraction=0.1,
-                 n_iter_no_change=None, tol=1e-4):
+                 n_iter_no_change=None, tol=1e-4, estimator=None):
 
         super(GradientBoostingRegressor, self).__init__(
             loss=loss, learning_rate=learning_rate, n_estimators=n_estimators,
@@ -1983,7 +2002,7 @@ def __init__(self, loss='ls', learning_rate=0.1, n_estimators=100,
             random_state=random_state, alpha=alpha, verbose=verbose,
             max_leaf_nodes=max_leaf_nodes, warm_start=warm_start,
             presort=presort, validation_fraction=validation_fraction,
-            n_iter_no_change=n_iter_no_change, tol=tol)
+            n_iter_no_change=n_iter_no_change, tol=tol, estimator=estimator)
 
     def predict(self, X):
         """Predict regression target for X.

diff --git a/sklearn/exact_tree/__init__.py b/sklearn/exact_tree/__init__.py
@@ -0,0 +1,4 @@
+from .tree import RegressionTree
+
+
+__all__ = ['RegressionTree']
diff --git a/sklearn/exact_tree/_criterion.pxd b/sklearn/exact_tree/_criterion.pxd
@@ -0,0 +1,38 @@
+#cython: cdivision=True
+from ._stats_node cimport StatsNode
+
+
+cdef inline double _impurity_mse(StatsNode* stats_node):
+    cdef double impurity
+    impurity = (stats_node[0].sum_sq_y /
+                stats_node[0].sum_weighted_samples)
+    impurity -= ((stats_node[0].sum_y /
+                  stats_node[0].sum_weighted_samples) ** 2)
+
+    return impurity
+
+
+cdef inline double impurity_improvement(StatsNode* c_stats,
+                                        StatsNode* l_stats,
+                                        StatsNode* r_stats,
+                                        double sum_total_weighted_samples):
+    # FIXME: only using MSE for the moment
+    c_impurity = _impurity_mse(c_stats)
+    l_impurity = _impurity_mse(l_stats)
+    r_impurity = _impurity_mse(r_stats)
+
+    return ((c_stats[0].sum_weighted_samples /
+             sum_total_weighted_samples) *
+            (c_impurity -
+             (l_stats[0].sum_weighted_samples /
+              sum_total_weighted_samples * l_impurity) -
+             (r_stats[0].sum_weighted_samples /
+              sum_total_weighted_samples * r_impurity)))
+
+
+cdef inline double proxy_impurity_improvement(StatsNode* l_stats,
+                                              StatsNode* r_stats):
+    return ((l_stats[0].sum_y * l_stats[0].sum_y) /
+            l_stats[0].sum_weighted_samples +
+            (r_stats[0].sum_y * r_stats[0].sum_y) /
+            r_stats[0].sum_weighted_samples)
diff --git a/sklearn/exact_tree/_criterion.pyx b/sklearn/exact_tree/_criterion.pyx
diff --git a/sklearn/exact_tree/_split_record.pxd b/sklearn/exact_tree/_split_record.pxd
@@ -0,0 +1,60 @@
+from libc.math cimport NAN, INFINITY
+
+from ._stats_node cimport StatsNode
+from ._stats_node cimport stats_node_copy_to
+from ._stats_node cimport stats_node_clear
+
+from ._criterion cimport _impurity_mse
+
+
+cdef struct SplitRecord:
+    int feature
+    int pos
+    float threshold
+    float impurity
+    float impurity_improvement
+    int nid
+    StatsNode c_stats
+    StatsNode l_stats
+    StatsNode r_stats
+
+
+cdef void split_record_reset(SplitRecord* split_record, int feature,
+                             int pos, float threshold,
+                             float impurity,
+                             float impurity_improvement, int nid,
+                             StatsNode* c_stats, StatsNode* l_stats,
+                             StatsNode* r_stats)
+
+
+cdef inline void split_record_clear(SplitRecord* split_record):
+    split_record[0].feature = 0
+    split_record[0].pos = 0
+    split_record[0].threshold = NAN
+    split_record[0].impurity = INFINITY
+    split_record[0].impurity_improvement = -INFINITY
+    split_record[0].nid = 0
+
+    stats_node_clear(&split_record.c_stats)
+    stats_node_clear(&split_record.l_stats)
+    stats_node_clear(&split_record.r_stats)
+
+
+cdef inline void split_record_expand_record(SplitRecord* split_record,
+                                            SplitRecord* left_split_record,
+                                            SplitRecord* right_split_record):
+    split_record_clear(left_split_record)
+    stats_node_copy_to(&split_record[0].l_stats, &left_split_record[0].c_stats)
+    stats_node_copy_to(&split_record[0].l_stats, &left_split_record[0].r_stats)
+    left_split_record[0].impurity = _impurity_mse(
+        &left_split_record[0].c_stats)
+
+    split_record_clear(right_split_record)
+    stats_node_copy_to(&split_record.r_stats, &right_split_record[0].c_stats)
+    stats_node_copy_to(&split_record.r_stats, &right_split_record[0].r_stats)
+    right_split_record[0].impurity = _impurity_mse(
+        &right_split_record[0].c_stats)
+
+
+cdef void split_record_copy_to(SplitRecord* src_split_record,
+                               SplitRecord* dst_split_record)
diff --git a/sklearn/exact_tree/_split_record.pyx b/sklearn/exact_tree/_split_record.pyx
@@ -0,0 +1,32 @@
+cdef void split_record_reset(SplitRecord* split_record, int feature,
+                                    int pos, float threshold,
+                                    float impurity,
+                                    float impurity_improvement, int nid,
+                                    StatsNode* c_stats, StatsNode* l_stats,
+                                    StatsNode* r_stats):
+    split_record[0].feature = feature
+    split_record[0].pos = pos
+    split_record[0].threshold = threshold
+    split_record[0].impurity = impurity
+    split_record[0].impurity_improvement = impurity_improvement
+
+    stats_node_copy_to(c_stats, &split_record.c_stats)
+    stats_node_copy_to(l_stats, &split_record.l_stats)
+    stats_node_copy_to(r_stats, &split_record.r_stats)
+
+
+cdef inline void split_record_copy_to(SplitRecord* src_split_record,
+                                      SplitRecord* dst_split_record):
+    dst_split_record[0].feature = src_split_record[0].feature
+    dst_split_record[0].pos = src_split_record[0].pos
+    dst_split_record[0].threshold = src_split_record[0].threshold
+    dst_split_record[0].impurity = src_split_record[0].impurity
+    dst_split_record[0].impurity_improvement = src_split_record[0].impurity_improvement
+    dst_split_record[0].nid = src_split_record[0].nid
+
+    stats_node_copy_to(&src_split_record[0].c_stats,
+                       &dst_split_record[0].c_stats)
+    stats_node_copy_to(&src_split_record[0].l_stats,
+                       &dst_split_record[0].l_stats)
+    stats_node_copy_to(&src_split_record[0].r_stats,
+                       &dst_split_record[0].r_stats)
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,4 @@
		from .tree import RegressionTree


		__all__ = ['RegressionTree']