We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Tree Doesn't Work With Sparse Data
<!--
This is an issue template. Please fill in the relevant details in the
sections below.
-->

##### Orange version
<!-- From menu _Help→About→Version_ or code `Orange.version.full_version` -->
3.5.0.dev0+ccbdbba

##### Expected behavior
Tree works with sparse data.


##### Actual behavior
It doesn't due to `np.isnan`


##### Steps to reproduce the behavior
Pass any sparse data to Tree.


##### Additional info (worksheets, data, screenshots, ...)
![screen shot 2017-06-02 at 14 15 43](https://cloud.githubusercontent.com/assets/713026/26725268/fccae160-479d-11e7-9e67-e518adf6a6fe.png)




--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `Orange/classification/tree.py`
Content:
```
1 """Tree inducers: SKL and Orange's own inducer"""
2 import numpy as np
3 import sklearn.tree as skl_tree
4 
5 from Orange.base import TreeModel as TreeModelInterface
6 from Orange.classification import SklLearner, SklModel, Learner
7 from Orange.classification import _tree_scorers
8 from Orange.statistics import distribution, contingency
9 from Orange.tree import Node, DiscreteNode, MappedDiscreteNode, \
10     NumericNode, TreeModel
11 
12 __all__ = ["SklTreeLearner", "TreeLearner"]
13 
14 
15 class TreeLearner(Learner):
16     """
17     Tree inducer with proper handling of nominal attributes and binarization.
18 
19     The inducer can handle missing values of attributes and target.
20     For discrete attributes with more than two possible values, each value can
21     get a separate branch (`binarize=False`), or values can be grouped into
22     two groups (`binarize=True`, default).
23 
24     The tree growth can be limited by the required number of instances for
25     internal nodes and for leafs, the sufficient proportion of majority class,
26     and by the maximal depth of the tree.
27 
28     If the tree is not binary, it can contain zero-branches.
29 
30     Args:
31         binarize (bool):
32             if `True` the inducer will find optimal split into two
33             subsets for values of discrete attributes. If `False` (default),
34             each value gets its branch.
35 
36         min_samples_leaf (float):
37             the minimal number of data instances in a leaf
38 
39         min_samples_split (float):
40             the minimal nubmer of data instances that is
41             split into subgroups
42 
43         max_depth (int): the maximal depth of the tree
44 
45         sufficient_majority (float):
46             a majority at which the data is not split
47             further
48 
49     Returns:
50         instance of OrangeTreeModel
51     """
52     __returns__ = TreeModel
53 
54     # Binarization is exhaustive, so we set a limit on the number of values
55     MAX_BINARIZATION = 16
56 
57     def __init__(
58             self, *args, binarize=False, max_depth=None,
59             min_samples_leaf=1, min_samples_split=2, sufficient_majority=0.95,
60             **kwargs):
61         super().__init__(*args, **kwargs)
62         self.params = {}
63         self.binarize = self.params['binarize'] = binarize
64         self.min_samples_leaf = self.params['min_samples_leaf'] = min_samples_leaf
65         self.min_samples_split = self.params['min_samples_split'] = min_samples_split
66         self.sufficient_majority = self.params['sufficient_majority'] = sufficient_majority
67         self.max_depth = self.params['max_depth'] = max_depth
68 
69     def _select_attr(self, data):
70         """Select the attribute for the next split.
71 
72         Returns:
73             tuple with an instance of Node and a numpy array indicating
74             the branch index for each data instance, or -1 if data instance
75             is dropped
76         """
77         # Prevent false warnings by pylint
78         attr = attr_no = None
79         REJECT_ATTRIBUTE = 0, None, None, 0
80 
81         def _score_disc():
82             """Scoring for discrete attributes, no binarization
83 
84             The class computes the entropy itself, not by calling other
85             functions. This is to make sure that it uses the same
86             definition as the below classes that compute entropy themselves
87             for efficiency reasons."""
88             n_values = len(attr.values)
89             if n_values < 2:
90                 return REJECT_ATTRIBUTE
91 
92             x = data.X[:, attr_no].flatten()
93             cont = _tree_scorers.contingency(x, len(data.domain.attributes[attr_no].values),
94                                              data.Y, len(data.domain.class_var.values))
95             attr_distr = np.sum(cont, axis=0)
96             null_nodes = attr_distr <= self.min_samples_leaf
97             # This is just for speed. If there is only a single non-null-node,
98             # entropy wouldn't decrease anyway.
99             if sum(null_nodes) >= n_values - 1:
100                 return REJECT_ATTRIBUTE
101             cont[:, null_nodes] = 0
102             attr_distr = np.sum(cont, axis=0)
103             cls_distr = np.sum(cont, axis=1)
104             n = np.sum(attr_distr)
105             # Avoid log(0); <= instead of == because we need an array
106             cls_distr[cls_distr <= 0] = 1
107             attr_distr[attr_distr <= 0] = 1
108             cont[cont <= 0] = 1
109             class_entr = n * np.log(n) - np.sum(cls_distr * np.log(cls_distr))
110             attr_entr = np.sum(attr_distr * np.log(attr_distr))
111             cont_entr = np.sum(cont * np.log(cont))
112             score = (class_entr - attr_entr + cont_entr) / n / np.log(2)
113             score *= n / len(data)  # punishment for missing values
114             branches = x
115             branches[np.isnan(branches)] = -1
116             if score == 0:
117                 return REJECT_ATTRIBUTE
118             node = DiscreteNode(attr, attr_no, None)
119             return score, node, branches, n_values
120 
121         def _score_disc_bin():
122             """Scoring for discrete attributes, with binarization"""
123             n_values = len(attr.values)
124             if n_values <= 2:
125                 return _score_disc()
126             cont = contingency.Discrete(data, attr)
127             attr_distr = np.sum(cont, axis=0)
128             # Skip instances with missing value of the attribute
129             cls_distr = np.sum(cont, axis=1)
130             if np.sum(attr_distr) == 0:  # all values are missing
131                 return REJECT_ATTRIBUTE
132             best_score, best_mapping = _tree_scorers.find_binarization_entropy(
133                 cont, cls_distr, attr_distr, self.min_samples_leaf)
134             if best_score <= 0:
135                 return REJECT_ATTRIBUTE
136             best_score *= 1 - np.sum(cont.unknowns) / len(data)
137             mapping, branches = MappedDiscreteNode.branches_from_mapping(
138                 data.X[:, attr_no], best_mapping, n_values)
139             node = MappedDiscreteNode(attr, attr_no, mapping, None)
140             return best_score, node, branches, 2
141 
142         def _score_cont():
143             """Scoring for numeric attributes"""
144             col_x = data.X[:, attr_no]
145             nans = np.sum(np.isnan(col_x))
146             non_nans = len(col_x) - nans
147             arginds = np.argsort(col_x)[:non_nans]
148             best_score, best_cut = _tree_scorers.find_threshold_entropy(
149                 col_x, data.Y, arginds,
150                 len(class_var.values), self.min_samples_leaf)
151             if best_score == 0:
152                 return REJECT_ATTRIBUTE
153             best_score *= non_nans / len(col_x)
154             branches = np.full(len(col_x), -1, dtype=int)
155             mask = ~np.isnan(col_x)
156             branches[mask] = (col_x[mask] > best_cut).astype(int)
157             node = NumericNode(attr, attr_no, best_cut, None)
158             return best_score, node, branches, 2
159 
160         #######################################
161         # The real _select_attr starts here
162         domain = data.domain
163         class_var = domain.class_var
164         best_score, *best_res = REJECT_ATTRIBUTE
165         best_res = [Node(None, None, None)] + best_res[1:]
166         disc_scorer = _score_disc_bin if self.binarize else _score_disc
167         for attr_no, attr in enumerate(domain.attributes):
168             sc, *res = disc_scorer() if attr.is_discrete else _score_cont()
169             if res[0] is not None and sc > best_score:
170                 best_score, best_res = sc, res
171         best_res[0].value = distribution.Discrete(data, class_var)
172         return best_res
173 
174     def build_tree(self, data, active_inst, level=1):
175         """Induce a tree from the given data
176 
177         Returns:
178             root node (Node)"""
179         node_insts = data[active_inst]
180         distr = distribution.Discrete(node_insts, data.domain.class_var)
181         if len(node_insts) < self.min_samples_leaf:
182             return None
183         if len(node_insts) < self.min_samples_split or \
184                 max(distr) >= sum(distr) * self.sufficient_majority or \
185                 self.max_depth is not None and level > self.max_depth:
186             node, branches, n_children = Node(None, None, distr), None, 0
187         else:
188             node, branches, n_children = self._select_attr(node_insts)
189         node.subset = active_inst
190         if branches is not None:
191             node.children = [
192                 self.build_tree(data, active_inst[branches == br], level + 1)
193                 for br in range(n_children)]
194         return node
195 
196     def fit_storage(self, data):
197         if self.binarize and any(
198                 attr.is_discrete and len(attr.values) > self.MAX_BINARIZATION
199                 for attr in data.domain.attributes):
200             # No fallback in the script; widgets can prevent this error
201             # by providing a fallback and issue a warning about doing so
202             raise ValueError("Exhaustive binarization does not handle "
203                              "attributes with more than {} values".
204                              format(self.MAX_BINARIZATION))
205 
206         active_inst = np.nonzero(~np.isnan(data.Y))[0].astype(np.int32)
207         root = self.build_tree(data, active_inst)
208         if root is None:
209             distr = distribution.Discrete(data, data.domain.class_var)
210             if np.sum(distr) == 0:
211                 distr[:] = 1
212             root = Node(None, 0, distr)
213         root.subset = active_inst
214         model = TreeModel(data, root)
215         return model
216 
217 
218 class SklTreeClassifier(SklModel, TreeModelInterface):
219     """Wrapper for SKL's tree classifier with the interface API for
220     visualizations"""
221     def __init__(self, *args, **kwargs):
222         SklModel.__init__(self, *args, **kwargs)
223         self._cached_sample_assignments = None
224 
225 
226 class SklTreeLearner(SklLearner):
227     """Wrapper for SKL's tree inducer"""
228     __wraps__ = skl_tree.DecisionTreeClassifier
229     __returns__ = SklTreeClassifier
230     name = 'tree'
231 
232     def __init__(self, criterion="gini", splitter="best", max_depth=None,
233                  min_samples_split=2, min_samples_leaf=1,
234                  max_features=None,
235                  random_state=None, max_leaf_nodes=None,
236                  preprocessors=None):
237         super().__init__(preprocessors=preprocessors)
238         self.params = vars()
239
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/Orange/classification/tree.py b/Orange/classification/tree.py
--- a/Orange/classification/tree.py
+++ b/Orange/classification/tree.py
@@ -1,5 +1,6 @@
 """Tree inducers: SKL and Orange's own inducer"""
 import numpy as np
+import scipy.sparse as sp
 import sklearn.tree as skl_tree
 
 from Orange.base import TreeModel as TreeModelInterface
@@ -76,6 +77,7 @@
         """
         # Prevent false warnings by pylint
         attr = attr_no = None
+        col_x = None
         REJECT_ATTRIBUTE = 0, None, None, 0
 
         def _score_disc():
@@ -89,8 +91,7 @@
             if n_values < 2:
                 return REJECT_ATTRIBUTE
 
-            x = data.X[:, attr_no].flatten()
-            cont = _tree_scorers.contingency(x, len(data.domain.attributes[attr_no].values),
+            cont = _tree_scorers.contingency(col_x, len(data.domain.attributes[attr_no].values),
                                              data.Y, len(data.domain.class_var.values))
             attr_distr = np.sum(cont, axis=0)
             null_nodes = attr_distr <= self.min_samples_leaf
@@ -111,7 +112,7 @@
             cont_entr = np.sum(cont * np.log(cont))
             score = (class_entr - attr_entr + cont_entr) / n / np.log(2)
             score *= n / len(data)  # punishment for missing values
-            branches = x
+            branches = col_x
             branches[np.isnan(branches)] = -1
             if score == 0:
                 return REJECT_ATTRIBUTE
@@ -135,13 +136,12 @@
                 return REJECT_ATTRIBUTE
             best_score *= 1 - np.sum(cont.unknowns) / len(data)
             mapping, branches = MappedDiscreteNode.branches_from_mapping(
-                data.X[:, attr_no], best_mapping, n_values)
+                col_x, best_mapping, n_values)
             node = MappedDiscreteNode(attr, attr_no, mapping, None)
             return best_score, node, branches, 2
 
         def _score_cont():
             """Scoring for numeric attributes"""
-            col_x = data.X[:, attr_no]
             nans = np.sum(np.isnan(col_x))
             non_nans = len(col_x) - nans
             arginds = np.argsort(col_x)[:non_nans]
@@ -159,12 +159,17 @@
 
         #######################################
         # The real _select_attr starts here
+        is_sparse = sp.issparse(data.X)
         domain = data.domain
         class_var = domain.class_var
         best_score, *best_res = REJECT_ATTRIBUTE
         best_res = [Node(None, None, None)] + best_res[1:]
         disc_scorer = _score_disc_bin if self.binarize else _score_disc
         for attr_no, attr in enumerate(domain.attributes):
+            col_x = data.X[:, attr_no]
+            if is_sparse:
+                col_x = col_x.toarray()
+                col_x = col_x.flatten()
             sc, *res = disc_scorer() if attr.is_discrete else _score_cont()
             if res[0] is not None and sc > best_score:
                 best_score, best_res = sc, res

{"golden_diff": "diff --git a/Orange/classification/tree.py b/Orange/classification/tree.py\n--- a/Orange/classification/tree.py\n+++ b/Orange/classification/tree.py\n@@ -1,5 +1,6 @@\n \"\"\"Tree inducers: SKL and Orange's own inducer\"\"\"\n import numpy as np\n+import scipy.sparse as sp\n import sklearn.tree as skl_tree\n \n from Orange.base import TreeModel as TreeModelInterface\n@@ -76,6 +77,7 @@\n         \"\"\"\n         # Prevent false warnings by pylint\n         attr = attr_no = None\n+        col_x = None\n         REJECT_ATTRIBUTE = 0, None, None, 0\n \n         def _score_disc():\n@@ -89,8 +91,7 @@\n             if n_values < 2:\n                 return REJECT_ATTRIBUTE\n \n-            x = data.X[:, attr_no].flatten()\n-            cont = _tree_scorers.contingency(x, len(data.domain.attributes[attr_no].values),\n+            cont = _tree_scorers.contingency(col_x, len(data.domain.attributes[attr_no].values),\n                                              data.Y, len(data.domain.class_var.values))\n             attr_distr = np.sum(cont, axis=0)\n             null_nodes = attr_distr <= self.min_samples_leaf\n@@ -111,7 +112,7 @@\n             cont_entr = np.sum(cont * np.log(cont))\n             score = (class_entr - attr_entr + cont_entr) / n / np.log(2)\n             score *= n / len(data)  # punishment for missing values\n-            branches = x\n+            branches = col_x\n             branches[np.isnan(branches)] = -1\n             if score == 0:\n                 return REJECT_ATTRIBUTE\n@@ -135,13 +136,12 @@\n                 return REJECT_ATTRIBUTE\n             best_score *= 1 - np.sum(cont.unknowns) / len(data)\n             mapping, branches = MappedDiscreteNode.branches_from_mapping(\n-                data.X[:, attr_no], best_mapping, n_values)\n+                col_x, best_mapping, n_values)\n             node = MappedDiscreteNode(attr, attr_no, mapping, None)\n             return best_score, node, branches, 2\n \n         def _score_cont():\n             \"\"\"Scoring for numeric attributes\"\"\"\n-            col_x = data.X[:, attr_no]\n             nans = np.sum(np.isnan(col_x))\n             non_nans = len(col_x) - nans\n             arginds = np.argsort(col_x)[:non_nans]\n@@ -159,12 +159,17 @@\n \n         #######################################\n         # The real _select_attr starts here\n+        is_sparse = sp.issparse(data.X)\n         domain = data.domain\n         class_var = domain.class_var\n         best_score, *best_res = REJECT_ATTRIBUTE\n         best_res = [Node(None, None, None)] + best_res[1:]\n         disc_scorer = _score_disc_bin if self.binarize else _score_disc\n         for attr_no, attr in enumerate(domain.attributes):\n+            col_x = data.X[:, attr_no]\n+            if is_sparse:\n+                col_x = col_x.toarray()\n+                col_x = col_x.flatten()\n             sc, *res = disc_scorer() if attr.is_discrete else _score_cont()\n             if res[0] is not None and sc > best_score:\n                 best_score, best_res = sc, res\n", "issue": "Tree Doesn't Work With Sparse Data\n<!--\r\nThis is an issue template. Please fill in the relevant details in the\r\nsections below.\r\n-->\r\n\r\n##### Orange version\r\n<!-- From menu _Help\u2192About\u2192Version_ or code `Orange.version.full_version` -->\r\n3.5.0.dev0+ccbdbba\r\n\r\n##### Expected behavior\r\nTree works with sparse data.\r\n\r\n\r\n##### Actual behavior\r\nIt doesn't due to `np.isnan`\r\n\r\n\r\n##### Steps to reproduce the behavior\r\nPass any sparse data to Tree.\r\n\r\n\r\n##### Additional info (worksheets, data, screenshots, ...)\r\n![screen shot 2017-06-02 at 14 15 43](https://cloud.githubusercontent.com/assets/713026/26725268/fccae160-479d-11e7-9e67-e518adf6a6fe.png)\r\n\r\n\r\n\n", "before_files": [{"content": "\"\"\"Tree inducers: SKL and Orange's own inducer\"\"\"\nimport numpy as np\nimport sklearn.tree as skl_tree\n\nfrom Orange.base import TreeModel as TreeModelInterface\nfrom Orange.classification import SklLearner, SklModel, Learner\nfrom Orange.classification import _tree_scorers\nfrom Orange.statistics import distribution, contingency\nfrom Orange.tree import Node, DiscreteNode, MappedDiscreteNode, \\\n    NumericNode, TreeModel\n\n__all__ = [\"SklTreeLearner\", \"TreeLearner\"]\n\n\nclass TreeLearner(Learner):\n    \"\"\"\n    Tree inducer with proper handling of nominal attributes and binarization.\n\n    The inducer can handle missing values of attributes and target.\n    For discrete attributes with more than two possible values, each value can\n    get a separate branch (`binarize=False`), or values can be grouped into\n    two groups (`binarize=True`, default).\n\n    The tree growth can be limited by the required number of instances for\n    internal nodes and for leafs, the sufficient proportion of majority class,\n    and by the maximal depth of the tree.\n\n    If the tree is not binary, it can contain zero-branches.\n\n    Args:\n        binarize (bool):\n            if `True` the inducer will find optimal split into two\n            subsets for values of discrete attributes. If `False` (default),\n            each value gets its branch.\n\n        min_samples_leaf (float):\n            the minimal number of data instances in a leaf\n\n        min_samples_split (float):\n            the minimal nubmer of data instances that is\n            split into subgroups\n\n        max_depth (int): the maximal depth of the tree\n\n        sufficient_majority (float):\n            a majority at which the data is not split\n            further\n\n    Returns:\n        instance of OrangeTreeModel\n    \"\"\"\n    __returns__ = TreeModel\n\n    # Binarization is exhaustive, so we set a limit on the number of values\n    MAX_BINARIZATION = 16\n\n    def __init__(\n            self, *args, binarize=False, max_depth=None,\n            min_samples_leaf=1, min_samples_split=2, sufficient_majority=0.95,\n            **kwargs):\n        super().__init__(*args, **kwargs)\n        self.params = {}\n        self.binarize = self.params['binarize'] = binarize\n        self.min_samples_leaf = self.params['min_samples_leaf'] = min_samples_leaf\n        self.min_samples_split = self.params['min_samples_split'] = min_samples_split\n        self.sufficient_majority = self.params['sufficient_majority'] = sufficient_majority\n        self.max_depth = self.params['max_depth'] = max_depth\n\n    def _select_attr(self, data):\n        \"\"\"Select the attribute for the next split.\n\n        Returns:\n            tuple with an instance of Node and a numpy array indicating\n            the branch index for each data instance, or -1 if data instance\n            is dropped\n        \"\"\"\n        # Prevent false warnings by pylint\n        attr = attr_no = None\n        REJECT_ATTRIBUTE = 0, None, None, 0\n\n        def _score_disc():\n            \"\"\"Scoring for discrete attributes, no binarization\n\n            The class computes the entropy itself, not by calling other\n            functions. This is to make sure that it uses the same\n            definition as the below classes that compute entropy themselves\n            for efficiency reasons.\"\"\"\n            n_values = len(attr.values)\n            if n_values < 2:\n                return REJECT_ATTRIBUTE\n\n            x = data.X[:, attr_no].flatten()\n            cont = _tree_scorers.contingency(x, len(data.domain.attributes[attr_no].values),\n                                             data.Y, len(data.domain.class_var.values))\n            attr_distr = np.sum(cont, axis=0)\n            null_nodes = attr_distr <= self.min_samples_leaf\n            # This is just for speed. If there is only a single non-null-node,\n            # entropy wouldn't decrease anyway.\n            if sum(null_nodes) >= n_values - 1:\n                return REJECT_ATTRIBUTE\n            cont[:, null_nodes] = 0\n            attr_distr = np.sum(cont, axis=0)\n            cls_distr = np.sum(cont, axis=1)\n            n = np.sum(attr_distr)\n            # Avoid log(0); <= instead of == because we need an array\n            cls_distr[cls_distr <= 0] = 1\n            attr_distr[attr_distr <= 0] = 1\n            cont[cont <= 0] = 1\n            class_entr = n * np.log(n) - np.sum(cls_distr * np.log(cls_distr))\n            attr_entr = np.sum(attr_distr * np.log(attr_distr))\n            cont_entr = np.sum(cont * np.log(cont))\n            score = (class_entr - attr_entr + cont_entr) / n / np.log(2)\n            score *= n / len(data)  # punishment for missing values\n            branches = x\n            branches[np.isnan(branches)] = -1\n            if score == 0:\n                return REJECT_ATTRIBUTE\n            node = DiscreteNode(attr, attr_no, None)\n            return score, node, branches, n_values\n\n        def _score_disc_bin():\n            \"\"\"Scoring for discrete attributes, with binarization\"\"\"\n            n_values = len(attr.values)\n            if n_values <= 2:\n                return _score_disc()\n            cont = contingency.Discrete(data, attr)\n            attr_distr = np.sum(cont, axis=0)\n            # Skip instances with missing value of the attribute\n            cls_distr = np.sum(cont, axis=1)\n            if np.sum(attr_distr) == 0:  # all values are missing\n                return REJECT_ATTRIBUTE\n            best_score, best_mapping = _tree_scorers.find_binarization_entropy(\n                cont, cls_distr, attr_distr, self.min_samples_leaf)\n            if best_score <= 0:\n                return REJECT_ATTRIBUTE\n            best_score *= 1 - np.sum(cont.unknowns) / len(data)\n            mapping, branches = MappedDiscreteNode.branches_from_mapping(\n                data.X[:, attr_no], best_mapping, n_values)\n            node = MappedDiscreteNode(attr, attr_no, mapping, None)\n            return best_score, node, branches, 2\n\n        def _score_cont():\n            \"\"\"Scoring for numeric attributes\"\"\"\n            col_x = data.X[:, attr_no]\n            nans = np.sum(np.isnan(col_x))\n            non_nans = len(col_x) - nans\n            arginds = np.argsort(col_x)[:non_nans]\n            best_score, best_cut = _tree_scorers.find_threshold_entropy(\n                col_x, data.Y, arginds,\n                len(class_var.values), self.min_samples_leaf)\n            if best_score == 0:\n                return REJECT_ATTRIBUTE\n            best_score *= non_nans / len(col_x)\n            branches = np.full(len(col_x), -1, dtype=int)\n            mask = ~np.isnan(col_x)\n            branches[mask] = (col_x[mask] > best_cut).astype(int)\n            node = NumericNode(attr, attr_no, best_cut, None)\n            return best_score, node, branches, 2\n\n        #######################################\n        # The real _select_attr starts here\n        domain = data.domain\n        class_var = domain.class_var\n        best_score, *best_res = REJECT_ATTRIBUTE\n        best_res = [Node(None, None, None)] + best_res[1:]\n        disc_scorer = _score_disc_bin if self.binarize else _score_disc\n        for attr_no, attr in enumerate(domain.attributes):\n            sc, *res = disc_scorer() if attr.is_discrete else _score_cont()\n            if res[0] is not None and sc > best_score:\n                best_score, best_res = sc, res\n        best_res[0].value = distribution.Discrete(data, class_var)\n        return best_res\n\n    def build_tree(self, data, active_inst, level=1):\n        \"\"\"Induce a tree from the given data\n\n        Returns:\n            root node (Node)\"\"\"\n        node_insts = data[active_inst]\n        distr = distribution.Discrete(node_insts, data.domain.class_var)\n        if len(node_insts) < self.min_samples_leaf:\n            return None\n        if len(node_insts) < self.min_samples_split or \\\n                max(distr) >= sum(distr) * self.sufficient_majority or \\\n                self.max_depth is not None and level > self.max_depth:\n            node, branches, n_children = Node(None, None, distr), None, 0\n        else:\n            node, branches, n_children = self._select_attr(node_insts)\n        node.subset = active_inst\n        if branches is not None:\n            node.children = [\n                self.build_tree(data, active_inst[branches == br], level + 1)\n                for br in range(n_children)]\n        return node\n\n    def fit_storage(self, data):\n        if self.binarize and any(\n                attr.is_discrete and len(attr.values) > self.MAX_BINARIZATION\n                for attr in data.domain.attributes):\n            # No fallback in the script; widgets can prevent this error\n            # by providing a fallback and issue a warning about doing so\n            raise ValueError(\"Exhaustive binarization does not handle \"\n                             \"attributes with more than {} values\".\n                             format(self.MAX_BINARIZATION))\n\n        active_inst = np.nonzero(~np.isnan(data.Y))[0].astype(np.int32)\n        root = self.build_tree(data, active_inst)\n        if root is None:\n            distr = distribution.Discrete(data, data.domain.class_var)\n            if np.sum(distr) == 0:\n                distr[:] = 1\n            root = Node(None, 0, distr)\n        root.subset = active_inst\n        model = TreeModel(data, root)\n        return model\n\n\nclass SklTreeClassifier(SklModel, TreeModelInterface):\n    \"\"\"Wrapper for SKL's tree classifier with the interface API for\n    visualizations\"\"\"\n    def __init__(self, *args, **kwargs):\n        SklModel.__init__(self, *args, **kwargs)\n        self._cached_sample_assignments = None\n\n\nclass SklTreeLearner(SklLearner):\n    \"\"\"Wrapper for SKL's tree inducer\"\"\"\n    __wraps__ = skl_tree.DecisionTreeClassifier\n    __returns__ = SklTreeClassifier\n    name = 'tree'\n\n    def __init__(self, criterion=\"gini\", splitter=\"best\", max_depth=None,\n                 min_samples_split=2, min_samples_leaf=1,\n                 max_features=None,\n                 random_state=None, max_leaf_nodes=None,\n                 preprocessors=None):\n        super().__init__(preprocessors=preprocessors)\n        self.params = vars()\n", "path": "Orange/classification/tree.py"}], "after_files": [{"content": "\"\"\"Tree inducers: SKL and Orange's own inducer\"\"\"\nimport numpy as np\nimport scipy.sparse as sp\nimport sklearn.tree as skl_tree\n\nfrom Orange.base import TreeModel as TreeModelInterface\nfrom Orange.classification import SklLearner, SklModel, Learner\nfrom Orange.classification import _tree_scorers\nfrom Orange.statistics import distribution, contingency\nfrom Orange.tree import Node, DiscreteNode, MappedDiscreteNode, \\\n    NumericNode, TreeModel\n\n__all__ = [\"SklTreeLearner\", \"TreeLearner\"]\n\n\nclass TreeLearner(Learner):\n    \"\"\"\n    Tree inducer with proper handling of nominal attributes and binarization.\n\n    The inducer can handle missing values of attributes and target.\n    For discrete attributes with more than two possible values, each value can\n    get a separate branch (`binarize=False`), or values can be grouped into\n    two groups (`binarize=True`, default).\n\n    The tree growth can be limited by the required number of instances for\n    internal nodes and for leafs, the sufficient proportion of majority class,\n    and by the maximal depth of the tree.\n\n    If the tree is not binary, it can contain zero-branches.\n\n    Args:\n        binarize (bool):\n            if `True` the inducer will find optimal split into two\n            subsets for values of discrete attributes. If `False` (default),\n            each value gets its branch.\n\n        min_samples_leaf (float):\n            the minimal number of data instances in a leaf\n\n        min_samples_split (float):\n            the minimal nubmer of data instances that is\n            split into subgroups\n\n        max_depth (int): the maximal depth of the tree\n\n        sufficient_majority (float):\n            a majority at which the data is not split\n            further\n\n    Returns:\n        instance of OrangeTreeModel\n    \"\"\"\n    __returns__ = TreeModel\n\n    # Binarization is exhaustive, so we set a limit on the number of values\n    MAX_BINARIZATION = 16\n\n    def __init__(\n            self, *args, binarize=False, max_depth=None,\n            min_samples_leaf=1, min_samples_split=2, sufficient_majority=0.95,\n            **kwargs):\n        super().__init__(*args, **kwargs)\n        self.params = {}\n        self.binarize = self.params['binarize'] = binarize\n        self.min_samples_leaf = self.params['min_samples_leaf'] = min_samples_leaf\n        self.min_samples_split = self.params['min_samples_split'] = min_samples_split\n        self.sufficient_majority = self.params['sufficient_majority'] = sufficient_majority\n        self.max_depth = self.params['max_depth'] = max_depth\n\n    def _select_attr(self, data):\n        \"\"\"Select the attribute for the next split.\n\n        Returns:\n            tuple with an instance of Node and a numpy array indicating\n            the branch index for each data instance, or -1 if data instance\n            is dropped\n        \"\"\"\n        # Prevent false warnings by pylint\n        attr = attr_no = None\n        col_x = None\n        REJECT_ATTRIBUTE = 0, None, None, 0\n\n        def _score_disc():\n            \"\"\"Scoring for discrete attributes, no binarization\n\n            The class computes the entropy itself, not by calling other\n            functions. This is to make sure that it uses the same\n            definition as the below classes that compute entropy themselves\n            for efficiency reasons.\"\"\"\n            n_values = len(attr.values)\n            if n_values < 2:\n                return REJECT_ATTRIBUTE\n\n            cont = _tree_scorers.contingency(col_x, len(data.domain.attributes[attr_no].values),\n                                             data.Y, len(data.domain.class_var.values))\n            attr_distr = np.sum(cont, axis=0)\n            null_nodes = attr_distr <= self.min_samples_leaf\n            # This is just for speed. If there is only a single non-null-node,\n            # entropy wouldn't decrease anyway.\n            if sum(null_nodes) >= n_values - 1:\n                return REJECT_ATTRIBUTE\n            cont[:, null_nodes] = 0\n            attr_distr = np.sum(cont, axis=0)\n            cls_distr = np.sum(cont, axis=1)\n            n = np.sum(attr_distr)\n            # Avoid log(0); <= instead of == because we need an array\n            cls_distr[cls_distr <= 0] = 1\n            attr_distr[attr_distr <= 0] = 1\n            cont[cont <= 0] = 1\n            class_entr = n * np.log(n) - np.sum(cls_distr * np.log(cls_distr))\n            attr_entr = np.sum(attr_distr * np.log(attr_distr))\n            cont_entr = np.sum(cont * np.log(cont))\n            score = (class_entr - attr_entr + cont_entr) / n / np.log(2)\n            score *= n / len(data)  # punishment for missing values\n            branches = col_x\n            branches[np.isnan(branches)] = -1\n            if score == 0:\n                return REJECT_ATTRIBUTE\n            node = DiscreteNode(attr, attr_no, None)\n            return score, node, branches, n_values\n\n        def _score_disc_bin():\n            \"\"\"Scoring for discrete attributes, with binarization\"\"\"\n            n_values = len(attr.values)\n            if n_values <= 2:\n                return _score_disc()\n            cont = contingency.Discrete(data, attr)\n            attr_distr = np.sum(cont, axis=0)\n            # Skip instances with missing value of the attribute\n            cls_distr = np.sum(cont, axis=1)\n            if np.sum(attr_distr) == 0:  # all values are missing\n                return REJECT_ATTRIBUTE\n            best_score, best_mapping = _tree_scorers.find_binarization_entropy(\n                cont, cls_distr, attr_distr, self.min_samples_leaf)\n            if best_score <= 0:\n                return REJECT_ATTRIBUTE\n            best_score *= 1 - np.sum(cont.unknowns) / len(data)\n            mapping, branches = MappedDiscreteNode.branches_from_mapping(\n                col_x, best_mapping, n_values)\n            node = MappedDiscreteNode(attr, attr_no, mapping, None)\n            return best_score, node, branches, 2\n\n        def _score_cont():\n            \"\"\"Scoring for numeric attributes\"\"\"\n            nans = np.sum(np.isnan(col_x))\n            non_nans = len(col_x) - nans\n            arginds = np.argsort(col_x)[:non_nans]\n            best_score, best_cut = _tree_scorers.find_threshold_entropy(\n                col_x, data.Y, arginds,\n                len(class_var.values), self.min_samples_leaf)\n            if best_score == 0:\n                return REJECT_ATTRIBUTE\n            best_score *= non_nans / len(col_x)\n            branches = np.full(len(col_x), -1, dtype=int)\n            mask = ~np.isnan(col_x)\n            branches[mask] = (col_x[mask] > best_cut).astype(int)\n            node = NumericNode(attr, attr_no, best_cut, None)\n            return best_score, node, branches, 2\n\n        #######################################\n        # The real _select_attr starts here\n        is_sparse = sp.issparse(data.X)\n        domain = data.domain\n        class_var = domain.class_var\n        best_score, *best_res = REJECT_ATTRIBUTE\n        best_res = [Node(None, None, None)] + best_res[1:]\n        disc_scorer = _score_disc_bin if self.binarize else _score_disc\n        for attr_no, attr in enumerate(domain.attributes):\n            col_x = data.X[:, attr_no]\n            if is_sparse:\n                col_x = col_x.toarray()\n                col_x = col_x.flatten()\n            sc, *res = disc_scorer() if attr.is_discrete else _score_cont()\n            if res[0] is not None and sc > best_score:\n                best_score, best_res = sc, res\n        best_res[0].value = distribution.Discrete(data, class_var)\n        return best_res\n\n    def build_tree(self, data, active_inst, level=1):\n        \"\"\"Induce a tree from the given data\n\n        Returns:\n            root node (Node)\"\"\"\n        node_insts = data[active_inst]\n        distr = distribution.Discrete(node_insts, data.domain.class_var)\n        if len(node_insts) < self.min_samples_leaf:\n            return None\n        if len(node_insts) < self.min_samples_split or \\\n                max(distr) >= sum(distr) * self.sufficient_majority or \\\n                self.max_depth is not None and level > self.max_depth:\n            node, branches, n_children = Node(None, None, distr), None, 0\n        else:\n            node, branches, n_children = self._select_attr(node_insts)\n        node.subset = active_inst\n        if branches is not None:\n            node.children = [\n                self.build_tree(data, active_inst[branches == br], level + 1)\n                for br in range(n_children)]\n        return node\n\n    def fit_storage(self, data):\n        if self.binarize and any(\n                attr.is_discrete and len(attr.values) > self.MAX_BINARIZATION\n                for attr in data.domain.attributes):\n            # No fallback in the script; widgets can prevent this error\n            # by providing a fallback and issue a warning about doing so\n            raise ValueError(\"Exhaustive binarization does not handle \"\n                             \"attributes with more than {} values\".\n                             format(self.MAX_BINARIZATION))\n\n        active_inst = np.nonzero(~np.isnan(data.Y))[0].astype(np.int32)\n        root = self.build_tree(data, active_inst)\n        if root is None:\n            distr = distribution.Discrete(data, data.domain.class_var)\n            if np.sum(distr) == 0:\n                distr[:] = 1\n            root = Node(None, 0, distr)\n        root.subset = active_inst\n        model = TreeModel(data, root)\n        return model\n\n\nclass SklTreeClassifier(SklModel, TreeModelInterface):\n    \"\"\"Wrapper for SKL's tree classifier with the interface API for\n    visualizations\"\"\"\n    def __init__(self, *args, **kwargs):\n        SklModel.__init__(self, *args, **kwargs)\n        self._cached_sample_assignments = None\n\n\nclass SklTreeLearner(SklLearner):\n    \"\"\"Wrapper for SKL's tree inducer\"\"\"\n    __wraps__ = skl_tree.DecisionTreeClassifier\n    __returns__ = SklTreeClassifier\n    name = 'tree'\n\n    def __init__(self, criterion=\"gini\", splitter=\"best\", max_depth=None,\n                 min_samples_split=2, min_samples_leaf=1,\n                 max_features=None,\n                 random_state=None, max_leaf_nodes=None,\n                 preprocessors=None):\n        super().__init__(preprocessors=preprocessors)\n        self.params = vars()\n", "path": "Orange/classification/tree.py"}]}