Add get_n_leaves() and get_max_depth() to DesicionTrees #12300

adrinjalali · 2018-10-05T12:57:17Z

See #7613 (it technically fixes the original issue, but more discussion's going on there)

To count the leaves, I'm checking left AND right children of of each node, which should be the case in a general tree. But in most of the tests, only left or right children are checked and not both. I suppose it doesn't happen that only one of the children are set and not the other, but still, it can a potential source of a bug, I think.

I couldn't really come up with a nice test for the two functions, so I've just replaced the equivalent ones in one of the existing tests. We could replace more of those in tests though.

sklearn/tree/tree.py

NicolasHug · 2018-10-05T14:44:26Z

doc/whats_new/v0.21.rst

+  on it, including :class:`tree.DecisionTreeClassifier`,
+  :class:`tree.DecisionTreeRegressor`, :class:`tree.ExtraTreeClassifier`,
+  and :class:`tree.ExtraTreeRegressor`.
+  :issue:`7613` by :user:`Adrin Jalali <adrinjalali>`.


issue should link to your PR #12300, not the actual issue

nah, not really. There seems to be different preferences on this one, and I personally prefer to link to the issues and not the PRs, and if you check v0.20 whats_new page, there are 352 cases of links with "/issue/" in them, and only 1 "/pull/".

And if you click on most of them, those /issue/ links actually lead to a PR. It's misleading and I did the same before (reference an issue number), but was corrected by @glemaitre

Confusing but :issue: link to the PR (The PR will link to the issue)

The advantage of linking to the pr is:

It's easier for us to track the difference between the change log and the commit log

it's easier to find your way to all relevant history

sloria's Sphinx-issues library which we vendor here recently supports a separate :pr: role so we could upgrade and start using that.

So should it be sth like:

- |Feature| :issue:`7613` ``get_n_leaves()`` and ``get_max_depth()`` have been added to :class:`tree.BaseDecisionTree` and consequently all estimators based on it, including :class:`tree.DecisionTreeClassifier`, :class:`tree.DecisionTreeRegressor`, :class:`tree.ExtraTreeClassifier`, and :class:`tree.ExtraTreeRegressor`. :pr:`12300` by :user:`Adrin Jalali <adrinjalali>`.

amueller · 2018-10-05T15:02:48Z

sklearn/tree/tests/test_tree.py

@@ -1233,8 +1232,7 @@ def test_max_leaf_nodes_max_depth():
    k = 4
    for name, TreeEstimator in ALL_TREES.items():
        est = TreeEstimator(max_depth=1, max_leaf_nodes=k).fit(X, y)
-        tree = est.tree_
-        assert_greater(tree.max_depth, 1)
+        assert_greater(est.get_max_depth(), 1)


I don't get this test. Why should it be greater than max_depth?

lol, don't hate me, I just change a test to use the new functions. But I suppose that test is valid because X and y are manually designed in a way that we know the tree will be deeper if allowed, and this makes sure max_depth is ignored by the estimator if max_leaf_nodes is given. At least that's what the comment says.

ohh... I didn't read the comment. That behavior is... unexpected to me? Should we raise a warning in that case? Do we?

Also, there is no test that shows that the depth can be smaller than max_depth, right? We should have some slightly more explicit test, I think.

@amueller, this actually seems a bug to me, which I think can be fixed this way.

On master/this branch, we have the following:

>>> from sklearn.datasets import load_iris >>> from sklearn.tree import DecisionTreeClassifier >>> X, y = load_iris(return_X_y=True) >>> >>> clf = DecisionTreeClassifier(random_state=0, max_depth=1, max_leaf_nodes=100) >>> clf = clf.fit(X, y) >>> clf.get_max_depth() 2 >>> clf.get_n_leaves() 3 >>> >>> clf = DecisionTreeClassifier(random_state=0, max_depth=1) >>> clf = clf.fit(X, y) >>> clf.get_max_depth() 1 >>> clf.get_n_leaves() 2 >>> >>> clf = DecisionTreeClassifier(random_state=0, max_leaf_nodes=100) >>> clf = clf.fit(X, y) >>> clf.get_max_depth() 5 >>> clf.get_n_leaves() 9

Which shows that the max_depth is not actually ignored, it's just an overshoot by 1. And the issue is here:

scikit-learn/sklearn/tree/_tree.pyx

Line 453 in 3804ccd

is_leaf = (depth > self.max_depth or

After the proposed fix, we'd have:

>>> from sklearn.datasets import load_iris >>> from sklearn.tree import DecisionTreeClassifier >>> X, y = load_iris(return_X_y=True) >>> >>> clf = DecisionTreeClassifier(random_state=0, max_depth=1, max_leaf_nodes=100) >>> clf = clf.fit(X, y) >>> clf.get_max_depth() 1 >>> clf.get_n_leaves() 2 >>> >>> clf = DecisionTreeClassifier(random_state=0, max_depth=1) >>> clf = clf.fit(X, y) >>> clf.get_max_depth() 1 >>> clf.get_n_leaves() 2 >>> >>> clf = DecisionTreeClassifier(random_state=0, max_leaf_nodes=100) >>> clf = clf.fit(X, y) >>> clf.get_max_depth() 5 >>> clf.get_n_leaves() 9

which then makes sense. I think that change needs a Bug Fix entry in whats_new, since it changes the behavior? And should I include it in this PR or create a new one?

sklearn/tree/tree.py

jnothman · 2018-10-08T06:41:08Z

Regarding the "overshoot" can we just be more explicit that the depth excludes the root...?

adrinjalali · 2018-10-08T09:20:19Z

@jnothman, we could, but the issue is that we're not consistent at the moment. The DFS and BFS expansions don't agree with each other. BFS overshoots, DFS doesn't. The output of the following two cases should be the same:

>>> clf = DecisionTreeClassifier(random_state=0, max_depth=1, max_leaf_nodes=100)
>>> clf = clf.fit(X, y)
>>> clf.get_max_depth()
2
>>> clf.get_n_leaves()
3
>>> 
>>> clf = DecisionTreeClassifier(random_state=0, max_depth=1)
>>> clf = clf.fit(X, y)
>>> clf.get_max_depth()
1
>>> clf.get_n_leaves()
2

jnothman · 2018-10-08T13:25:33Z

I see. I'm not sure that there's a neat (i.e. backwards compatible) way to change this behaviour :(

adrinjalali · 2018-10-08T13:29:42Z

I'm not sure how it's done here, but it's arguably a bug, and some bugfixes make things backward incompatible, don't they? We could raise a user warning if they reach that part of the code and tell them it's changed.

jnothman · 2018-10-08T20:20:51Z

Yes, we break for bug fixes, although we still try to limit the damage and alert the user, or else make multiple breaking changes at the same time. Maybe it's not so bad if it's only BFS and most users are getting DFS?

jnothman · 2018-10-08T20:21:31Z

I suppose predictions may not be much affected either, actually.

adrinjalali · 2018-10-09T13:07:16Z

@jnothman:

Yes, we break for bug fixes, although we still try to limit the damage and alert the user, or else make multiple breaking changes at the same time. Maybe it's not so bad if it's only BFS and most users are getting DFS?

I have no idea how people use it. It's the BFS if they set max_leaf_nodes. Anyhow, should we then get this one in since it's not about that issue, and discuss/test the bug on another PR?

amueller · 2018-10-09T15:37:32Z

doc/whats_new/v0.21.rst

@@ -56,6 +56,15 @@ Support for Python 3.4 and below has been officially dropped.
  order for further speed performances. :issue:`12251` by `Tom Dupre la Tour`_.


+:mod:`sklearn.tree`
+...................
+- |Feature| ``get_n_leaves()`` and ``get_max_depth()`` have been added to


amueller · 2018-10-09T15:52:58Z

sklearn/tree/tree.py

@@ -108,6 +108,19 @@ def __init__(self,
        self.class_weight = class_weight
        self.presort = presort

+    def get_depth(self):
+        """Returns the depth of the decision tree, i.e. the maximum


Pep 257:

https://www.python.org/dev/peps/pep-0257/#multi-line-docstrings

No line breaks in first line.

amueller

Looks good apart from docstring nitpick.

jnothman

Otherwise LGTM

jnothman · 2018-10-10T02:12:28Z

sklearn/tree/tree.py

+    def get_depth(self):
+        """Returns the depth of the decision tree.
+
+        The depth of a tree is defined as the maximum depth of its leaves.


Maybe more explicit: "maximum number of nodes between the root and any leaf, inclusive of endpoints."

It's not inclusive of both endpoints though. The depth is correctly reported as 1 for a tree with a root and two leaves.

Good that I clarified then. "The number of branching nodes from the root to the leaf", then?

That may be more confusing, wouldn't it? How about "maximum distance between the root and any leaf"? I had it changed, the push didn't get through, didn't notice.

jnothman · 2018-10-10T11:00:14Z

I guess that is clear enough, thanks

amueller · 2018-10-10T19:35:39Z

yay!

adrinjalali added 3 commits October 5, 2018 11:36

add get_max_depth and get_n_leaves to BaseDecisionTree

d5ad351

use the new functions in a test

bb96ba4

add the whats_new entry in v0.21

cf3a928

NicolasHug reviewed Oct 5, 2018

View reviewed changes

sklearn/tree/tree.py Outdated Show resolved Hide resolved

NicolasHug reviewed Oct 5, 2018

View reviewed changes

amueller reviewed Oct 5, 2018

View reviewed changes

adrinjalali added 4 commits October 5, 2018 17:22

reference the PR and not the issue

3bfc5a6

add docstrings to the two functions

4bfef68

improve the docstring for _tree.max_depth

9098881

rename get_max_depth -> get_depth in DecisionTree

cb6f83c

amueller reviewed Oct 9, 2018

View reviewed changes

whats_new get_max_depth -> get_depth

b205250

amueller reviewed Oct 9, 2018

View reviewed changes

amueller approved these changes Oct 9, 2018

View reviewed changes

no newline in the first line of the docstring

7923fac

jnothman approved these changes Oct 10, 2018

View reviewed changes

improve get_depth docstring

e611960

jnothman merged commit a80bbd9 into scikit-learn:master Oct 10, 2018

adrinjalali deleted the feature/treefuncs branch October 10, 2018 11:46

amueller mentioned this pull request Oct 10, 2018

Tree-based models are very hard to introspect #7613

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add get_n_leaves() and get_max_depth() to DesicionTrees #12300

Add get_n_leaves() and get_max_depth() to DesicionTrees #12300

Add get_n_leaves() and get_max_depth() to DesicionTrees #12300

Add get_n_leaves() and get_max_depth() to DesicionTrees #12300

Conversation

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment