Repository: scikit-learn/scikit-learn
Pull request: [MRG] Adds Minimal Cost-Complexity Pruning to Decision Trees
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/master/CONTRIBUTING.md#pull-request-checklist
-->

#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
Fixes #6557


#### What does this implement/fix? Explain your changes.
This PR implements Minimal Cost-Complexity Pruning based on L. Breiman, J. Friedman, R. Olshen, and C. Stone, "Classification and Regression Trees", Wadsworth, Belmont, CA, 1984.

Most of this implementation is the same as the literature. There are two differences:

1. In Breiman, r(t) is the an estimate of the probability of misclassification. This PR, uses the impurity as r(t).
2. The **weighted** number of samples is used to compute the probability of a point landing on a nodes.

A  cost complexity parameter, `alpha`, was added to `__init__` to control cost complexity pruning. The post pruning is done at the end of `fit`.

The code performing Minimal Cost-Complexity Pruning is mostly done in Python. The Python part produces the node ids that will become the leaves of the new subtree. These leaves are passed to a Cython function called `build_pruned_tree` that builds a tree. This was written in Cython since the tree building API is in Cython.

In Cython, the Stack class is used to go through the tree. Not all the fields of the StackRecord is used. This is a trade off between the code complexity of adding yet another Stack class, and being a little memory inefficient.

Currently, `prune_tree` is public, which allows for the following use case:

```python
clf = DecisionTreeClassifier(alpha=0.0)
clf.fit(X, y)
clf.set_params(alpha=0.1)
clf.prune_tree()
```

If we prefer, we can make `prune_tree` private and not encourage this use case.

Problem statement:
add post-pruning for decision trees
I frequently get asked about post-pruning. Often using single trees is important for interpretability, and post-pruning can help both interpretability and generalization performance.
[I'm surprised there is no open issue on this, but I couldn't find one]

Hints from issue discussion:
I can give this a shot :)

The title of this issue is related https://github.com/scikit-learn/scikit-learn/issues/4630 .

This issue [#941](https://github.com/scikit-learn/scikit-learn/pull/941) also seems to be proposing prune method to the tree but the code has considerably changed in the meantime I suppose.

On the topic of interpretability, there has also been published work on creating single decision trees from random forests. As counter-intuitive as this sounds, due to the non-optimality of standard decision tree algorithms, this can apparently give single decisions tree that are both interpretable and also better classifiers/regressors than you would get otherwise.  

@amueller Could you please explain this issue a little bit? I want to work on this.

actually maybe the first thing to do would be to add a stopping criterion based on mutual information...

@lesshaste can you give a citation? (I had been thinking about that recently, damn, obviously it has been done ^^)

@amueller  It has been a long time since I looked at this but:

Section 2.2 of 
"Rule Extraction from Random Forest: the RF+HC Methods" by Morteza Mashayekhi  and  Robin Gras has all the relevant citations I know. Please let me know if you don't have access to this paper.

On an only slightly related note, I remember looking at http://blog.datadive.net/interpreting-random-forests/ with some interest.

> actually maybe the first thing to do would be to add a stopping criterion based on mutual information...

An easy addition would be to stop the construction when `p(t) i(t, s*) < beta`, i.e. when the weighted impurity `p(t) i(t, s*)` for the best split `s*` becomes less than some user-defined threshold `beta`.

> I frequently get asked about post-pruning. Often using single trees is important for interpretability, and post-pruning can help both interpretability and generalization performance.

I think this can also be beneficial for some ensemble algorithms like (gradient) boosting although it's typically not increasing the predictive accuracy for bagging-style ensembles (e.g. random forests).

Pruning might also be useful to save some memory and decrease prediction times a bit.

Commit message: RFC: Less diffs

Patch to review:
diff --git a/doc/whats_new/v0.21.rst b/doc/whats_new/v0.21.rst
index 13a08b9cec4b7..deadbb5438b1d 100644
--- a/doc/whats_new/v0.21.rst
+++ b/doc/whats_new/v0.21.rst
@@ -192,6 +192,11 @@ Support for Python 3.4 and below has been officially dropped.
   and :class:`tree.ExtraTreeRegressor`.
   :issue:`12300` by :user:`Adrin Jalali <adrinjalali>`.
 
+- |Feature| Adds minimal cost complexity pruning to
+  :class:`tree.DecisionTreeClassifier`, :class:`tree.DecisionTreeRegressor`,
+  :class:`tree.ExtraTreeClassifier`, and :class:`tree.ExtraTreeRegressor`.
+  :issue:`6557` by :user:`Thomas Fan <thomasjpfan>`.
+
 - |Fix| Fixed an issue with :class:`tree.BaseDecisionTree`
   and consequently all estimators based
   on it, including :class:`tree.DecisionTreeClassifier`,
diff --git a/examples/tree/plot_cost_complexity_pruning.py b/examples/tree/plot_cost_complexity_pruning.py
new file mode 100644
index 0000000000000..524da4b489d4f
--- /dev/null
+++ b/examples/tree/plot_cost_complexity_pruning.py
@@ -0,0 +1,67 @@
+r"""
+========================================================
+Post pruning decision trees with cost complexity pruning
+========================================================
+
+In this example, decision tree classifiers are trained with a post pruning
+technique called minimal cost complexity pruning. This technique is
+parameterized by the complexity parameter, :math:`\alpha`. Greater values of
+:math:`\alpha` will prune more of the tree, thus creating a smaller trees.
+"""
+
+###############################################################################
+# Train decision tree classifiers
+# -------------------------------
+# Train 40 decision tree classifiers with :math:`\alpha` from 0.00 to
+# 0.40.
+import numpy as np
+from sklearn.model_selection import train_test_split
+from sklearn.datasets import load_breast_cancer
+from sklearn.tree import DecisionTreeClassifier
+
+X, y = load_breast_cancer(return_X_y=True)
+X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
+
+alphas = np.linspace(0, 0.04, 40)
+clfs = []
+for alpha in alphas:
+    clf = DecisionTreeClassifier(random_state=0, alpha=alpha)
+    clf.fit(X_train, y_train)
+    clfs.append(clf)
+
+###############################################################################
+# Plot training and test scores vs alpha
+# --------------------------------------
+# Calcuate and plot the the training scores and test accuracy scores
+# for our classifiers. With :math:`\alpha` equal to 0.0, the decision tree is
+# overfitting with a 1.0 training accuracy score. As the decision tree is
+# pruned the testing accuracy score increases up to a point and then decreases.
+import matplotlib.pyplot as plt
+
+train_scores = []
+test_scores = []
+for clf in clfs:
+    train_scores.append(clf.score(X_train, y_train))
+    test_scores.append(clf.score(X_test, y_test))
+
+fig, ax = plt.subplots()
+ax.set_xlabel("alpha")
+ax.set_ylabel("accuracy")
+ax.set_title("Accuracy vs alpha for training and testing sets")
+ax.plot(alphas, train_scores, label="train")
+ax.plot(alphas, test_scores, label="test")
+ax.legend()
+fig.show()
+
+###############################################################################
+# Plot total number of nodes vs alpha
+# -----------------------------------
+# Plot the total number of nodes for our classifiers. As :math:`\alpha`
+# increases, the number of nodes decreases.
+node_counts = [clf.tree_.node_count for clf in clfs]
+fig, ax = plt.subplots()
+ax.set_xlabel("alpha")
+ax.set_ylabel("number of nodes")
+ax.set_title("Number of nodes vs alpha")
+ax.plot(alphas, node_counts)
+fig.show()
diff --git a/sklearn/tree/_tree.pxd b/sklearn/tree/_tree.pxd
index 14b03103deff0..6f3091729d78d 100644
--- a/sklearn/tree/_tree.pxd
+++ b/sklearn/tree/_tree.pxd
@@ -103,3 +103,13 @@ cdef class TreeBuilder:
                 np.ndarray sample_weight=*,
                 np.ndarray X_idx_sorted=*)
     cdef _check_input(self, object X, np.ndarray y, np.ndarray sample_weight)
+
+
+# =============================================================================
+# Build Pruned Tree
+# =============================================================================
+
+cpdef build_pruned_tree(
+    Tree tree,
+    Tree orig_tree,
+    np.ndarray[np.npy_uint8, ndim=1] leaves_in_subtree)
diff --git a/sklearn/tree/_tree.pyx b/sklearn/tree/_tree.pyx
index ed259c98ac850..9c7c7e2a101c8 100644
--- a/sklearn/tree/_tree.pyx
+++ b/sklearn/tree/_tree.pyx
@@ -1132,3 +1132,101 @@ cdef class Tree:
         Py_INCREF(self)
         arr.base = <PyObject*> self
         return arr
+
+# =============================================================================
+# Build Pruned Tree
+# =============================================================================
+
+cpdef build_pruned_tree(
+    Tree tree,
+    Tree orig_tree,
+    np.ndarray[np.npy_uint8, ndim=1] leaves_in_subtree):
+    """Builds a pruned tree.
+
+    Builds a pruned tree from the original tree. The values and nodes from the
+    original tree are copied into the pruned tree.
+
+    Parameters
+    ----------
+    tree : Tree
+        Location to place the pruned tree
+    orig_tree : Tree
+        Original tree
+    leaves_in_subtree : numpy.ndarray, dtype=np.npy_uint8
+        Original node ids that are leaves in pruned tree
+    """
+
+    cdef SIZE_t capacity = np.sum(leaves_in_subtree)
+    tree._resize(capacity)
+
+    cdef SIZE_t orig_node_id
+    cdef SIZE_t new_node_id
+    cdef SIZE_t depth
+    cdef SIZE_t parent
+    cdef bint is_left
+    cdef bint is_leaf
+
+    # value_stride for original tree and new tree are the same
+    cdef SIZE_t value_stride = orig_tree.value_stride
+    cdef SIZE_t max_depth_seen = -1
+    cdef int rc = 0
+    cdef Node* node
+    cdef double* orig_value_ptr
+    cdef double* new_value_ptr
+
+    # Only uses the start, depth, parent, and is_left variables
+    cdef Stack stack = Stack(INITIAL_STACK_SIZE)
+    cdef StackRecord stack_record
+
+    with nogil:
+        # push root node onto stack
+        rc = stack.push(0, 0, 0, _TREE_UNDEFINED, 0, 0.0, 0)
+        if rc == -1:
+            with gil:
+                raise MemoryError()
+
+        while not stack.is_empty():
+            stack.pop(&stack_record)
+
+            orig_node_id = stack_record.start
+            depth = stack_record.depth
+            parent = stack_record.parent
+            is_left = stack_record.is_left
+
+            is_leaf = leaves_in_subtree[orig_node_id]
+            node = &orig_tree.nodes[orig_node_id]
+
+            new_node_id = tree._add_node(
+                parent, is_left, is_leaf, node.feature, node.threshold,
+                node.impurity, node.n_node_samples,
+                node.weighted_n_node_samples)
+
+            if new_node_id == <SIZE_t>(-1):
+                rc = -1
+                break
+
+            # copy value from original tree to new tree
+            orig_value_ptr = orig_tree.value + value_stride * orig_node_id
+            new_value_ptr = tree.value + value_stride * new_node_id
+            memcpy(new_value_ptr, orig_value_ptr, sizeof(double) * value_stride)
+
+            if not is_leaf:
+                # Push right child on stack
+                rc = stack.push(
+                    node.right_child, 0, depth + 1, new_node_id, 0, 0.0, 0)
+                if rc == -1:
+                    break
+
+                # push left child on stack
+                rc = stack.push(
+                    node.left_child, 0, depth + 1, new_node_id, 1, 0.0, 0)
+                if rc == -1:
+                    break
+
+            if depth > max_depth_seen:
+                max_depth_seen = depth
+
+        if rc >= 0:
+            tree.max_depth = max_depth_seen
+    if rc == -1:
+        raise MemoryError()
diff --git a/sklearn/tree/tests/test_tree.py b/sklearn/tree/tests/test_tree.py
index 7001b7741c4e6..4bf5fbf8f4083 100644
--- a/sklearn/tree/tests/test_tree.py
+++ b/sklearn/tree/tests/test_tree.py
@@ -1828,3 +1828,71 @@ def test_empty_leaf_infinite_threshold():
         infinite_threshold = np.where(~np.isfinite(tree.tree_.threshold))[0]
         assert len(infinite_threshold) == 0
         assert len(empty_leaf) == 0
+
+
+@pytest.mark.parametrize("criterion", CLF_CRITERIONS)
+@pytest.mark.parametrize(
+    "dataset", set(DATASETS.keys()) - {"reg_small", "boston"})
+@pytest.mark.parametrize(
+    "tree_cls", [DecisionTreeClassifier, ExtraTreeClassifier])
+def test_prune_tree_clf_are_subtrees(criterion, dataset, tree_cls):
+    dataset = DATASETS[dataset]
+    X, y = dataset["X"], dataset["y"]
+    assert_pruning_creates_subtree(tree_cls, X, y)
+
+
+@pytest.mark.parametrize("criterion", REG_CRITERIONS)
+@pytest.mark.parametrize("dataset", DATASETS.keys())
+@pytest.mark.parametrize(
+    "tree_cls", [DecisionTreeRegressor, ExtraTreeRegressor])
+def test_prune_tree_reg_are_subtrees(criterion, dataset, tree_cls):
+    dataset = DATASETS[dataset]
+    X, y = dataset["X"], dataset["y"]
+    assert_pruning_creates_subtree(tree_cls, X, y)
+
+
+def assert_pruning_creates_subtree(estimator_cls, X, y):
+    estimators = []
+    for alpha in np.linspace(0.0, 0.2, 11):
+        est = estimator_cls(
+            max_leaf_nodes=20, alpha=alpha, random_state=0).fit(X, y)
+        estimators.append(est)
+
+    for prev_est, next_est in zip(estimators[:-1], estimators[1:]):
+        assert_is_subtree(prev_est.tree_, next_est.tree_)
+
+
+def assert_is_subtree(tree, subtree):
+    assert tree.node_count >= subtree.node_count
+    assert tree.max_depth >= subtree.max_depth
+
+    tree_c_left = tree.children_left
+    tree_c_right = tree.children_right
+    subtree_c_left = subtree.children_left
+    subtree_c_right = subtree.children_right
+
+    stack = [(0, 0)]
+    while len(stack) > 0:
+        tree_n_idx, subtree_n_idx = stack.pop()
+        assert_array_almost_equal(
+            tree.value[tree_n_idx], subtree.value[subtree_n_idx])
+        assert_almost_equal(
+            tree.impurity[tree_n_idx], subtree.impurity[subtree_n_idx])
+        assert_almost_equal(
+            tree.n_node_samples[tree_n_idx],
+            subtree.n_node_samples[subtree_n_idx])
+        assert_almost_equal(
+            tree.weighted_n_node_samples[tree_n_idx],
+            subtree.weighted_n_node_samples[subtree_n_idx])
+
+        if (subtree_c_left[subtree_n_idx] == subtree_c_right[subtree_n_idx]):
+            # is a leaf
+            assert_almost_equal(-2, subtree.threshold[subtree_n_idx])
+        else:
+            # not a leaf
+            assert_almost_equal(
+                tree.threshold[tree_n_idx], subtree.threshold[subtree_n_idx])
+            stack.append(
+                (tree_c_left[tree_n_idx], subtree_c_left[subtree_n_idx]))
+            stack.append(
+                (tree_c_right[tree_n_idx], subtree_c_right[subtree_n_idx]))
diff --git a/sklearn/tree/tree.py b/sklearn/tree/tree.py
index faa83efbb7703..65a83f7ad6ed8 100644
--- a/sklearn/tree/tree.py
+++ b/sklearn/tree/tree.py
@@ -42,6 +42,7 @@
 from ._tree import DepthFirstTreeBuilder
 from ._tree import BestFirstTreeBuilder
 from ._tree import Tree
+from ._tree import build_pruned_tree
 from . import _tree, _splitter, _criterion
 
 __all__ = ["DecisionTreeClassifier",
@@ -93,7 +94,8 @@ def __init__(self,
                  min_impurity_decrease,
                  min_impurity_split,
                  class_weight=None,
-                 presort=False):
+                 presort=False,
+                 alpha=0.0):
         self.criterion = criterion
         self.splitter = splitter
         self.max_depth = max_depth
@@ -107,6 +109,7 @@ def __init__(self,
         self.min_impurity_split = min_impurity_split
         self.class_weight = class_weight
         self.presort = presort
+        self.alpha = alpha
 
     def get_depth(self):
         """Returns the depth of the decision tree.
@@ -380,6 +383,8 @@ def fit(self, X, y, sample_weight=None, check_input=True,
 
         builder.build(self.tree_, X, y, sample_weight, X_idx_sorted)
 
+        self.prune_tree()
+
         if self.n_outputs_ == 1:
             self.n_classes_ = self.n_classes_[0]
             self.classes_ = self.classes_[0]
@@ -510,6 +515,110 @@ def decision_path(self, X, check_input=True):
         X = self._validate_X_predict(X, check_input)
         return self.tree_.decision_path(X)
 
+    def prune_tree(self):
+        """Prunes tree using Minimal Cost-Complexity Pruning.
+
+        .. versionadded:: 0.21
+        """
+        check_is_fitted(self, 'tree_')
+
+        if self.alpha == 0.0:
+            return
+
+        n_nodes = self.tree_.node_count
+
+        # prior probability using weighted samples
+        samples = self.tree_.weighted_n_node_samples
+        prior = samples / samples[0]
+
+        # impurity weighted by prior
+        R_node = prior * self.tree_.impurity
+
+        # find parent node ids and leaves
+        child_l = self.tree_.children_left
+        child_r = self.tree_.children_right
+        parents = np.zeros(shape=n_nodes, dtype=np.intp)
+
+        # Uses uint8 to avoid casting when passing to generate_pruned_tree
+        leaves_in_subtree = np.zeros(shape=n_nodes, dtype=np.uint8)
+
+        stack = [(0, -1)]
+        while len(stack) > 0:
+            node_id, parent = stack.pop()
+            parents[node_id] = parent
+            if child_l[node_id] == child_r[node_id]:
+                leaves_in_subtree[node_id] = 1
+            else:
+                stack.append((child_l[node_id], node_id))
+                stack.append((child_r[node_id], node_id))
+
+        # computes number of leaves in all branches and the overall impurity of
+        # the branch. The overall impurity is the sum of R_node in its leaves.
+        N_leaves = np.zeros(shape=n_nodes, dtype=np.int32)
+        leaf_idicies, = np.where(leaves_in_subtree)
+        R_branch = np.zeros(shape=n_nodes, dtype=DTYPE)
+        R_branch[leaf_idicies] = R_node[leaf_idicies]
+
+        # bubble up values to ancestor nodes
+        for idx in leaf_idicies:
+            cur_R = R_node[idx]
+            while idx != 0:
+                par_idx = parents[idx]
+                R_branch[par_idx] += cur_R
+                N_leaves[par_idx] += 1
+                idx = par_idx
+
+        # non-leaves that can be pruned
+        inner_nodes = np.logical_not(leaves_in_subtree)
+        in_subtree = np.ones(shape=n_nodes, dtype=np.bool)
+
+        cur_alpha = 0
+        while cur_alpha < self.alpha:
+            # If root node is a leaf
+            if not inner_nodes[0]:
+                break
+
+            # computes alpha for subtrees
+            g_node = (R_node - R_branch) / (N_leaves - 1)
+            g_node[~inner_nodes] = np.inf
+
+            # smallest value is the weakest link which is pruned
+            cur_idx = np.argmin(g_node)
+            cur_alpha = g_node[cur_idx]
+
+            # descendants of branch are not in subtree
+            stack = [cur_idx]
+            while len(stack) > 0:
+                idx = stack.pop()
+                inner_nodes[idx] = False
+                leaves_in_subtree[idx] = 0
+                in_subtree[idx] = False
+                n_left, n_right = child_l[idx], child_r[idx]
+                if n_left != n_right:
+                    stack.append(n_left)
+                    stack.append(n_right)
+            leaves_in_subtree[cur_idx] = 1
+
+            # updates number of leaves
+            cur_leaves, N_leaves[cur_idx] = N_leaves[cur_idx], 0
+
+            # computes the increase in R_branch to bubble up
+            R_diff = R_node[cur_idx] - R_branch[cur_idx]
+            R_branch[cur_idx] = R_node[cur_idx]
+
+            # bubble up values to ancestors
+            cur_idx = parents[cur_idx]
+            while cur_idx != _tree.TREE_LEAF:
+                N_leaves[cur_idx] -= cur_leaves - 1
+                R_branch[cur_idx] += R_diff
+                cur_idx = parents[cur_idx]
+
+        # build pruned treee
+        pruned_tree = Tree(self.n_features_, self.n_classes_, self.n_outputs_)
+        build_pruned_tree(pruned_tree, self.tree_, leaves_in_subtree)
+
+        self.tree_ = pruned_tree
+
     @property
     def feature_importances_(self):
         """Return the feature importances.
@@ -666,6 +775,9 @@ class DecisionTreeClassifier(BaseDecisionTree, ClassifierMixin):
         When using either a smaller dataset or a restricted depth, this may
         speed up the training.
 
+    alpha : float, optional (default=0.0)
+        Complexity parameter used for Minimal Cost-Complexity Pruning.
+
     Attributes
     ----------
     classes_ : array of shape = [n_classes] or a list of such arrays
@@ -757,7 +869,8 @@ def __init__(self,
                  min_impurity_decrease=0.,
                  min_impurity_split=None,
                  class_weight=None,
-                 presort=False):
+                 presort=False,
+                 alpha=0.0):
         super(DecisionTreeClassifier, self).__init__(
             criterion=criterion,
             splitter=splitter,
@@ -771,7 +884,8 @@ def __init__(self,
             random_state=random_state,
             min_impurity_decrease=min_impurity_decrease,
             min_impurity_split=min_impurity_split,
-            presort=presort)
+            presort=presort,
+            alpha=alpha)
 
     def fit(self, X, y, sample_weight=None, check_input=True,
             X_idx_sorted=None):
@@ -1018,6 +1132,9 @@ class DecisionTreeRegressor(BaseDecisionTree, RegressorMixin):
         When using either a smaller dataset or a restricted depth, this may
         speed up the training.
 
+    alpha : float, optional (default=0.0)
+        Complexity parameter used for Minimal Cost-Complexity Pruning.
+
     Attributes
     ----------
     feature_importances_ : array of shape = [n_features]
@@ -1100,7 +1217,8 @@ def __init__(self,
                  max_leaf_nodes=None,
                  min_impurity_decrease=0.,
                  min_impurity_split=None,
-                 presort=False):
+                 presort=False,
+                 alpha=0.0):
         super(DecisionTreeRegressor, self).__init__(
             criterion=criterion,
             splitter=splitter,
@@ -1113,7 +1231,8 @@ def __init__(self,
             random_state=random_state,
             min_impurity_decrease=min_impurity_decrease,
             min_impurity_split=min_impurity_split,
-            presort=presort)
+            presort=presort,
+            alpha=alpha)
 
     def fit(self, X, y, sample_weight=None, check_input=True,
             X_idx_sorted=None):
@@ -1295,6 +1414,9 @@ class ExtraTreeClassifier(DecisionTreeClassifier):
         Note that these weights will be multiplied with sample_weight (passed
         through the fit method) if sample_weight is specified.
 
+    alpha : float, optional (default=0.0)
+        Complexity parameter used for Minimal Cost-Complexity Pruning.
+
     See also
     --------
     ExtraTreeRegressor, sklearn.ensemble.ExtraTreesClassifier,
@@ -1326,7 +1448,8 @@ def __init__(self,
                  max_leaf_nodes=None,
                  min_impurity_decrease=0.,
                  min_impurity_split=None,
-                 class_weight=None):
+                 class_weight=None,
+                 alpha=0.0):
         super(ExtraTreeClassifier, self).__init__(
             criterion=criterion,
             splitter=splitter,
@@ -1339,7 +1462,8 @@ def __init__(self,
             class_weight=class_weight,
             min_impurity_decrease=min_impurity_decrease,
             min_impurity_split=min_impurity_split,
-            random_state=random_state)
+            random_state=random_state,
+            alpha=alpha)
 
 
 class ExtraTreeRegressor(DecisionTreeRegressor):
@@ -1463,6 +1587,8 @@ class ExtraTreeRegressor(DecisionTreeRegressor):
         Best nodes are defined as relative reduction in impurity.
         If None then unlimited number of leaf nodes.
 
+    alpha : float, optional (default=0.0)
+        Complexity parameter used for Minimal Cost-Complexity Pruning.
 
     See also
     --------
@@ -1494,7 +1620,8 @@ def __init__(self,
                  random_state=None,
                  min_impurity_decrease=0.,
                  min_impurity_split=None,
-                 max_leaf_nodes=None):
+                 max_leaf_nodes=None,
+                 alpha=0.0):
         super(ExtraTreeRegressor, self).__init__(
             criterion=criterion,
             splitter=splitter,
@@ -1506,4 +1633,5 @@ def __init__(self,
             max_leaf_nodes=max_leaf_nodes,
             min_impurity_decrease=min_impurity_decrease,
             min_impurity_split=min_impurity_split,
-            random_state=random_state)
+            random_state=random_state,
+            alpha=alpha)


Code review comments:
diff_hunk: @@ -510,6 +515,110 @@ def decision_path(self, X, check_input=True):
         X = self._validate_X_predict(X, check_input)
         return self.tree_.decision_path(X)
 
+    def prune_tree(self):
path: sklearn/tree/tree.py
text: @user1:
I think this needs to be called after fit automatically to facilitate cross validation etc.

I wonder if this should instead be a public function?

@author:
Currently, `prune_tree` is a public function that is called at the end of `fit`. It should work with our cross validation classes/functions.

diff_hunk: @@ -1018,6 +1132,9 @@ class DecisionTreeRegressor(BaseDecisionTree, RegressorMixin):
         When using either a smaller dataset or a restricted depth, this may
         speed up the training.
 
+    alpha : float, optional (default=0.0)
path: sklearn/tree/tree.py
text: @user1:
This is not a sufficiently descriptive parameter name.

@author:
Agreed. It would need a prefix to describe it, maybe `cost_complexity_alpha`?

diff_hunk: @@ -510,6 +515,110 @@ def decision_path(self, X, check_input=True):
         X = self._validate_X_predict(X, check_input)
         return self.tree_.decision_path(X)
 
+    def prune_tree(self):
+        """Prunes tree using Minimal Cost-Complexity Pruning.
+
+        .. versionadded:: 0.21
+        """
+        check_is_fitted(self, 'tree_')
+
+        if self.alpha == 0.0:
+            return
+
+        n_nodes = self.tree_.node_count
+
+        # prior probability using weighted samples
+        samples = self.tree_.weighted_n_node_samples
+        prior = samples / samples[0]
+
+        # impurity weighted by prior
+        R_node = prior * self.tree_.impurity
+
+        # find parent node ids and leaves
+        child_l = self.tree_.children_left
+        child_r = self.tree_.children_right
+        parents = np.zeros(shape=n_nodes, dtype=np.intp)
+
+        # Uses uint8 to avoid casting when passing to generate_pruned_tree
+        leaves_in_subtree = np.zeros(shape=n_nodes, dtype=np.uint8)
+
+        stack = [(0, -1)]
+        while len(stack) > 0:
+            node_id, parent = stack.pop()
+            parents[node_id] = parent
+            if child_l[node_id] == child_r[node_id]:
+                leaves_in_subtree[node_id] = 1
+            else:
+                stack.append((child_l[node_id], node_id))
+                stack.append((child_r[node_id], node_id))
+
+        # computes number of leaves in all branches and the overall impurity of
+        # the branch. The overall impurity is the sum of R_node in its leaves.
+        N_leaves = np.zeros(shape=n_nodes, dtype=np.int32)
path: sklearn/tree/tree.py
text: @user1:
why big N?

@author:
Good point. This and `R_node` would be more pythonic as lowercase.