We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Unnecessary slow down on DecisionTreeClassifier
Just a minor unnecessary calculation that might become huge on large trees.

https://github.com/nltk/nltk/blob/develop/nltk/classify/decisiontree.py#L269

Even if verbose is false you are building that description string. Wouldn't it be a good idea to have that string building inside the if condition of verbose?


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `nltk/classify/decisiontree.py`
Content:
```
1 # Natural Language Toolkit: Decision Tree Classifiers
2 #
3 # Copyright (C) 2001-2017 NLTK Project
4 # Author: Edward Loper <edloper@gmail.com>
5 # URL: <http://nltk.org/>
6 # For license information, see LICENSE.TXT
7 
8 """
9 A classifier model that decides which label to assign to a token on
10 the basis of a tree structure, where branches correspond to conditions
11 on feature values, and leaves correspond to label assignments.
12 """
13 from __future__ import print_function, unicode_literals, division
14 
15 from collections import defaultdict
16 
17 from nltk.probability import FreqDist, MLEProbDist, entropy
18 from nltk.classify.api import ClassifierI
19 from nltk.compat import python_2_unicode_compatible
20 
21 @python_2_unicode_compatible
22 class DecisionTreeClassifier(ClassifierI):
23     def __init__(self, label, feature_name=None, decisions=None, default=None):
24         """
25         :param label: The most likely label for tokens that reach
26             this node in the decision tree.  If this decision tree
27             has no children, then this label will be assigned to
28             any token that reaches this decision tree.
29         :param feature_name: The name of the feature that this
30             decision tree selects for.
31         :param decisions: A dictionary mapping from feature values
32             for the feature identified by ``feature_name`` to
33             child decision trees.
34         :param default: The child that will be used if the value of
35             feature ``feature_name`` does not match any of the keys in
36             ``decisions``.  This is used when constructing binary
37             decision trees.
38         """
39         self._label = label
40         self._fname = feature_name
41         self._decisions = decisions
42         self._default = default
43 
44     def labels(self):
45         labels = [self._label]
46         if self._decisions is not None:
47             for dt in self._decisions.values():
48                 labels.extend(dt.labels())
49         if self._default is not None:
50             labels.extend(self._default.labels())
51         return list(set(labels))
52 
53     def classify(self, featureset):
54         # Decision leaf:
55         if self._fname is None:
56             return self._label
57 
58         # Decision tree:
59         fval = featureset.get(self._fname)
60         if fval in self._decisions:
61             return self._decisions[fval].classify(featureset)
62         elif self._default is not None:
63             return self._default.classify(featureset)
64         else:
65             return self._label
66 
67     def error(self, labeled_featuresets):
68         errors = 0
69         for featureset, label in labeled_featuresets:
70             if self.classify(featureset) != label:
71                 errors += 1
72         return errors/len(labeled_featuresets)
73 
74     def pretty_format(self, width=70, prefix='', depth=4):
75         """
76         Return a string containing a pretty-printed version of this
77         decision tree.  Each line in this string corresponds to a
78         single decision tree node or leaf, and indentation is used to
79         display the structure of the decision tree.
80         """
81         # [xx] display default!!
82         if self._fname is None:
83             n = width-len(prefix)-15
84             return '{0}{1} {2}\n'.format(prefix, '.'*n, self._label)
85         s = ''
86         for i, (fval, result) in enumerate(sorted(self._decisions.items())):
87             hdr = '{0}{1}={2}? '.format(prefix, self._fname, fval)
88             n = width-15-len(hdr)
89             s += '{0}{1} {2}\n'.format(hdr, '.'*(n), result._label)
90             if result._fname is not None and depth>1:
91                 s += result.pretty_format(width, prefix+'  ', depth-1)
92         if self._default is not None:
93             n = width-len(prefix)-21
94             s += '{0}else: {1} {2}\n'.format(prefix, '.'*n, self._default._label)
95             if self._default._fname is not None and depth>1:
96                 s += self._default.pretty_format(width, prefix+'  ', depth-1)
97         return s
98 
99     def pseudocode(self, prefix='', depth=4):
100         """
101         Return a string representation of this decision tree that
102         expresses the decisions it makes as a nested set of pseudocode
103         if statements.
104         """
105         if self._fname is None:
106             return "{0}return {1!r}\n".format(prefix, self._label)
107         s = ''
108         for (fval, result) in sorted(self._decisions.items()):
109             s += '{0}if {1} == {2!r}: '.format(prefix, self._fname, fval)
110             if result._fname is not None and depth>1:
111                 s += '\n'+result.pseudocode(prefix+'  ', depth-1)
112             else:
113                 s += 'return {0!r}\n'.format(result._label)
114         if self._default is not None:
115             if len(self._decisions) == 1:
116                 s += '{0}if {1} != {2!r}: '.format(prefix, self._fname,
117                                          list(self._decisions.keys())[0])
118             else:
119                 s += '{0}else: '.format(prefix)
120             if self._default._fname is not None and depth>1:
121                 s += '\n'+self._default.pseudocode(prefix+'  ', depth-1)
122             else:
123                 s += 'return {0!r}\n'.format(self._default._label)
124         return s
125 
126     def __str__(self):
127         return self.pretty_format()
128 
129     @staticmethod
130     def train(labeled_featuresets, entropy_cutoff=0.05, depth_cutoff=100,
131               support_cutoff=10, binary=False, feature_values=None,
132               verbose=False):
133         """
134         :param binary: If true, then treat all feature/value pairs as
135             individual binary features, rather than using a single n-way
136             branch for each feature.
137         """
138         # Collect a list of all feature names.
139         feature_names = set()
140         for featureset, label in labeled_featuresets:
141             for fname in featureset:
142                 feature_names.add(fname)
143 
144         # Collect a list of the values each feature can take.
145         if feature_values is None and binary:
146             feature_values = defaultdict(set)
147             for featureset, label in labeled_featuresets:
148                 for fname, fval in featureset.items():
149                     feature_values[fname].add(fval)
150 
151         # Start with a stump.
152         if not binary:
153             tree = DecisionTreeClassifier.best_stump(
154                 feature_names, labeled_featuresets, verbose)
155         else:
156             tree = DecisionTreeClassifier.best_binary_stump(
157                 feature_names, labeled_featuresets, feature_values, verbose)
158 
159         # Refine the stump.
160         tree.refine(labeled_featuresets, entropy_cutoff, depth_cutoff-1,
161                     support_cutoff, binary, feature_values, verbose)
162 
163         # Return it
164         return tree
165 
166     @staticmethod
167     def leaf(labeled_featuresets):
168         label = FreqDist(label for (featureset, label)
169                          in labeled_featuresets).max()
170         return DecisionTreeClassifier(label)
171 
172     @staticmethod
173     def stump(feature_name, labeled_featuresets):
174         label = FreqDist(label for (featureset, label)
175                          in labeled_featuresets).max()
176 
177         # Find the best label for each value.
178         freqs = defaultdict(FreqDist) # freq(label|value)
179         for featureset, label in labeled_featuresets:
180             feature_value = featureset.get(feature_name)
181             freqs[feature_value][label] += 1
182 
183         decisions = dict((val, DecisionTreeClassifier(freqs[val].max()))
184                          for val in freqs)
185         return DecisionTreeClassifier(label, feature_name, decisions)
186 
187     def refine(self, labeled_featuresets, entropy_cutoff, depth_cutoff,
188                support_cutoff, binary=False, feature_values=None,
189                verbose=False):
190         if len(labeled_featuresets) <= support_cutoff: return
191         if self._fname is None: return
192         if depth_cutoff <= 0: return
193         for fval in self._decisions:
194             fval_featuresets = [(featureset, label) for (featureset, label)
195                                 in labeled_featuresets
196                                 if featureset.get(self._fname) == fval]
197 
198             label_freqs = FreqDist(label for (featureset, label)
199                                    in fval_featuresets)
200             if entropy(MLEProbDist(label_freqs)) > entropy_cutoff:
201                 self._decisions[fval] = DecisionTreeClassifier.train(
202                     fval_featuresets, entropy_cutoff, depth_cutoff,
203                     support_cutoff, binary, feature_values, verbose)
204         if self._default is not None:
205             default_featuresets = [(featureset, label) for (featureset, label)
206                                    in labeled_featuresets
207                                    if featureset.get(self._fname) not in
208                                    self._decisions]
209             label_freqs = FreqDist(label for (featureset, label)
210                                    in default_featuresets)
211             if entropy(MLEProbDist(label_freqs)) > entropy_cutoff:
212                 self._default = DecisionTreeClassifier.train(
213                     default_featuresets, entropy_cutoff, depth_cutoff,
214                     support_cutoff, binary, feature_values, verbose)
215 
216     @staticmethod
217     def best_stump(feature_names, labeled_featuresets, verbose=False):
218         best_stump = DecisionTreeClassifier.leaf(labeled_featuresets)
219         best_error = best_stump.error(labeled_featuresets)
220         for fname in feature_names:
221             stump = DecisionTreeClassifier.stump(fname, labeled_featuresets)
222             stump_error = stump.error(labeled_featuresets)
223             if stump_error < best_error:
224                 best_error = stump_error
225                 best_stump = stump
226         if verbose:
227             print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \
228                    (len(labeled_featuresets), best_stump._fname, best_error)))
229         return best_stump
230 
231     @staticmethod
232     def binary_stump(feature_name, feature_value, labeled_featuresets):
233         label = FreqDist(label for (featureset, label)
234                          in labeled_featuresets).max()
235 
236         # Find the best label for each value.
237         pos_fdist = FreqDist()
238         neg_fdist = FreqDist()
239         for featureset, label in labeled_featuresets:
240             if featureset.get(feature_name) == feature_value:
241                 pos_fdist[label] += 1
242             else:
243                 neg_fdist[label] += 1
244 
245 
246         decisions = {}
247         default = label
248         # But hopefully we have observations!
249         if pos_fdist.N() > 0:
250             decisions = {feature_value: DecisionTreeClassifier(pos_fdist.max())}
251         if neg_fdist.N() > 0:
252             default = DecisionTreeClassifier(neg_fdist.max())
253 
254         return DecisionTreeClassifier(label, feature_name, decisions, default)
255 
256     @staticmethod
257     def best_binary_stump(feature_names, labeled_featuresets, feature_values,
258                           verbose=False):
259         best_stump = DecisionTreeClassifier.leaf(labeled_featuresets)
260         best_error = best_stump.error(labeled_featuresets)
261         for fname in feature_names:
262             for fval in feature_values[fname]:
263                 stump = DecisionTreeClassifier.binary_stump(
264                     fname, fval, labeled_featuresets)
265                 stump_error = stump.error(labeled_featuresets)
266                 if stump_error < best_error:
267                     best_error = stump_error
268                     best_stump = stump
269         if best_stump._decisions:
270             descr = '{0}={1}'.format(best_stump._fname,
271                                list(best_stump._decisions.keys())[0])
272         else:
273             descr = '(default)'
274         if verbose:
275             print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \
276                    (len(labeled_featuresets), descr, best_error)))
277         return best_stump
278 
279 ##//////////////////////////////////////////////////////
280 ##  Demo
281 ##//////////////////////////////////////////////////////
282 
283 def f(x):
284     return DecisionTreeClassifier.train(x, binary=True, verbose=True)
285 
286 def demo():
287     from nltk.classify.util import names_demo, binary_names_demo_features
288     classifier = names_demo(f, #DecisionTreeClassifier.train,
289                             binary_names_demo_features)
290     print(classifier.pp(depth=7))
291     print(classifier.pseudocode(depth=7))
292 
293 if __name__ == '__main__':
294     demo()
295 
296
```
--- 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/nltk/classify/decisiontree.py b/nltk/classify/decisiontree.py
--- a/nltk/classify/decisiontree.py
+++ b/nltk/classify/decisiontree.py
@@ -266,12 +266,12 @@
                 if stump_error < best_error:
                     best_error = stump_error
                     best_stump = stump
-        if best_stump._decisions:
-            descr = '{0}={1}'.format(best_stump._fname,
-                               list(best_stump._decisions.keys())[0])
-        else:
-            descr = '(default)'
         if verbose:
+            if best_stump._decisions:
+                descr = '{0}={1}'.format(best_stump._fname,
+                                         list(best_stump._decisions.keys())[0])
+            else:
+                descr = '(default)'
             print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \
                    (len(labeled_featuresets), descr, best_error)))
         return best_stump

{"golden_diff": "diff --git a/nltk/classify/decisiontree.py b/nltk/classify/decisiontree.py\n--- a/nltk/classify/decisiontree.py\n+++ b/nltk/classify/decisiontree.py\n@@ -266,12 +266,12 @@\n                 if stump_error < best_error:\n                     best_error = stump_error\n                     best_stump = stump\n-        if best_stump._decisions:\n-            descr = '{0}={1}'.format(best_stump._fname,\n-                               list(best_stump._decisions.keys())[0])\n-        else:\n-            descr = '(default)'\n         if verbose:\n+            if best_stump._decisions:\n+                descr = '{0}={1}'.format(best_stump._fname,\n+                                         list(best_stump._decisions.keys())[0])\n+            else:\n+                descr = '(default)'\n             print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \\\n                    (len(labeled_featuresets), descr, best_error)))\n         return best_stump\n", "issue": "Unnecessary slow down on DecisionTreeClassifier\nJust a minor unnecessary calculation that might become huge on large trees.\r\n\r\nhttps://github.com/nltk/nltk/blob/develop/nltk/classify/decisiontree.py#L269\r\n\r\nEven if verbose is false you are building that description string. Wouldn't it be a good idea to have that string building inside the if condition of verbose?\r\n\n", "before_files": [{"content": "# Natural Language Toolkit: Decision Tree Classifiers\n#\n# Copyright (C) 2001-2017 NLTK Project\n# Author: Edward Loper <edloper@gmail.com>\n# URL: <http://nltk.org/>\n# For license information, see LICENSE.TXT\n\n\"\"\"\nA classifier model that decides which label to assign to a token on\nthe basis of a tree structure, where branches correspond to conditions\non feature values, and leaves correspond to label assignments.\n\"\"\"\nfrom __future__ import print_function, unicode_literals, division\n\nfrom collections import defaultdict\n\nfrom nltk.probability import FreqDist, MLEProbDist, entropy\nfrom nltk.classify.api import ClassifierI\nfrom nltk.compat import python_2_unicode_compatible\n\n@python_2_unicode_compatible\nclass DecisionTreeClassifier(ClassifierI):\n    def __init__(self, label, feature_name=None, decisions=None, default=None):\n        \"\"\"\n        :param label: The most likely label for tokens that reach\n            this node in the decision tree.  If this decision tree\n            has no children, then this label will be assigned to\n            any token that reaches this decision tree.\n        :param feature_name: The name of the feature that this\n            decision tree selects for.\n        :param decisions: A dictionary mapping from feature values\n            for the feature identified by ``feature_name`` to\n            child decision trees.\n        :param default: The child that will be used if the value of\n            feature ``feature_name`` does not match any of the keys in\n            ``decisions``.  This is used when constructing binary\n            decision trees.\n        \"\"\"\n        self._label = label\n        self._fname = feature_name\n        self._decisions = decisions\n        self._default = default\n\n    def labels(self):\n        labels = [self._label]\n        if self._decisions is not None:\n            for dt in self._decisions.values():\n                labels.extend(dt.labels())\n        if self._default is not None:\n            labels.extend(self._default.labels())\n        return list(set(labels))\n\n    def classify(self, featureset):\n        # Decision leaf:\n        if self._fname is None:\n            return self._label\n\n        # Decision tree:\n        fval = featureset.get(self._fname)\n        if fval in self._decisions:\n            return self._decisions[fval].classify(featureset)\n        elif self._default is not None:\n            return self._default.classify(featureset)\n        else:\n            return self._label\n\n    def error(self, labeled_featuresets):\n        errors = 0\n        for featureset, label in labeled_featuresets:\n            if self.classify(featureset) != label:\n                errors += 1\n        return errors/len(labeled_featuresets)\n\n    def pretty_format(self, width=70, prefix='', depth=4):\n        \"\"\"\n        Return a string containing a pretty-printed version of this\n        decision tree.  Each line in this string corresponds to a\n        single decision tree node or leaf, and indentation is used to\n        display the structure of the decision tree.\n        \"\"\"\n        # [xx] display default!!\n        if self._fname is None:\n            n = width-len(prefix)-15\n            return '{0}{1} {2}\\n'.format(prefix, '.'*n, self._label)\n        s = ''\n        for i, (fval, result) in enumerate(sorted(self._decisions.items())):\n            hdr = '{0}{1}={2}? '.format(prefix, self._fname, fval)\n            n = width-15-len(hdr)\n            s += '{0}{1} {2}\\n'.format(hdr, '.'*(n), result._label)\n            if result._fname is not None and depth>1:\n                s += result.pretty_format(width, prefix+'  ', depth-1)\n        if self._default is not None:\n            n = width-len(prefix)-21\n            s += '{0}else: {1} {2}\\n'.format(prefix, '.'*n, self._default._label)\n            if self._default._fname is not None and depth>1:\n                s += self._default.pretty_format(width, prefix+'  ', depth-1)\n        return s\n\n    def pseudocode(self, prefix='', depth=4):\n        \"\"\"\n        Return a string representation of this decision tree that\n        expresses the decisions it makes as a nested set of pseudocode\n        if statements.\n        \"\"\"\n        if self._fname is None:\n            return \"{0}return {1!r}\\n\".format(prefix, self._label)\n        s = ''\n        for (fval, result) in sorted(self._decisions.items()):\n            s += '{0}if {1} == {2!r}: '.format(prefix, self._fname, fval)\n            if result._fname is not None and depth>1:\n                s += '\\n'+result.pseudocode(prefix+'  ', depth-1)\n            else:\n                s += 'return {0!r}\\n'.format(result._label)\n        if self._default is not None:\n            if len(self._decisions) == 1:\n                s += '{0}if {1} != {2!r}: '.format(prefix, self._fname,\n                                         list(self._decisions.keys())[0])\n            else:\n                s += '{0}else: '.format(prefix)\n            if self._default._fname is not None and depth>1:\n                s += '\\n'+self._default.pseudocode(prefix+'  ', depth-1)\n            else:\n                s += 'return {0!r}\\n'.format(self._default._label)\n        return s\n\n    def __str__(self):\n        return self.pretty_format()\n\n    @staticmethod\n    def train(labeled_featuresets, entropy_cutoff=0.05, depth_cutoff=100,\n              support_cutoff=10, binary=False, feature_values=None,\n              verbose=False):\n        \"\"\"\n        :param binary: If true, then treat all feature/value pairs as\n            individual binary features, rather than using a single n-way\n            branch for each feature.\n        \"\"\"\n        # Collect a list of all feature names.\n        feature_names = set()\n        for featureset, label in labeled_featuresets:\n            for fname in featureset:\n                feature_names.add(fname)\n\n        # Collect a list of the values each feature can take.\n        if feature_values is None and binary:\n            feature_values = defaultdict(set)\n            for featureset, label in labeled_featuresets:\n                for fname, fval in featureset.items():\n                    feature_values[fname].add(fval)\n\n        # Start with a stump.\n        if not binary:\n            tree = DecisionTreeClassifier.best_stump(\n                feature_names, labeled_featuresets, verbose)\n        else:\n            tree = DecisionTreeClassifier.best_binary_stump(\n                feature_names, labeled_featuresets, feature_values, verbose)\n\n        # Refine the stump.\n        tree.refine(labeled_featuresets, entropy_cutoff, depth_cutoff-1,\n                    support_cutoff, binary, feature_values, verbose)\n\n        # Return it\n        return tree\n\n    @staticmethod\n    def leaf(labeled_featuresets):\n        label = FreqDist(label for (featureset, label)\n                         in labeled_featuresets).max()\n        return DecisionTreeClassifier(label)\n\n    @staticmethod\n    def stump(feature_name, labeled_featuresets):\n        label = FreqDist(label for (featureset, label)\n                         in labeled_featuresets).max()\n\n        # Find the best label for each value.\n        freqs = defaultdict(FreqDist) # freq(label|value)\n        for featureset, label in labeled_featuresets:\n            feature_value = featureset.get(feature_name)\n            freqs[feature_value][label] += 1\n\n        decisions = dict((val, DecisionTreeClassifier(freqs[val].max()))\n                         for val in freqs)\n        return DecisionTreeClassifier(label, feature_name, decisions)\n\n    def refine(self, labeled_featuresets, entropy_cutoff, depth_cutoff,\n               support_cutoff, binary=False, feature_values=None,\n               verbose=False):\n        if len(labeled_featuresets) <= support_cutoff: return\n        if self._fname is None: return\n        if depth_cutoff <= 0: return\n        for fval in self._decisions:\n            fval_featuresets = [(featureset, label) for (featureset, label)\n                                in labeled_featuresets\n                                if featureset.get(self._fname) == fval]\n\n            label_freqs = FreqDist(label for (featureset, label)\n                                   in fval_featuresets)\n            if entropy(MLEProbDist(label_freqs)) > entropy_cutoff:\n                self._decisions[fval] = DecisionTreeClassifier.train(\n                    fval_featuresets, entropy_cutoff, depth_cutoff,\n                    support_cutoff, binary, feature_values, verbose)\n        if self._default is not None:\n            default_featuresets = [(featureset, label) for (featureset, label)\n                                   in labeled_featuresets\n                                   if featureset.get(self._fname) not in\n                                   self._decisions]\n            label_freqs = FreqDist(label for (featureset, label)\n                                   in default_featuresets)\n            if entropy(MLEProbDist(label_freqs)) > entropy_cutoff:\n                self._default = DecisionTreeClassifier.train(\n                    default_featuresets, entropy_cutoff, depth_cutoff,\n                    support_cutoff, binary, feature_values, verbose)\n\n    @staticmethod\n    def best_stump(feature_names, labeled_featuresets, verbose=False):\n        best_stump = DecisionTreeClassifier.leaf(labeled_featuresets)\n        best_error = best_stump.error(labeled_featuresets)\n        for fname in feature_names:\n            stump = DecisionTreeClassifier.stump(fname, labeled_featuresets)\n            stump_error = stump.error(labeled_featuresets)\n            if stump_error < best_error:\n                best_error = stump_error\n                best_stump = stump\n        if verbose:\n            print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \\\n                   (len(labeled_featuresets), best_stump._fname, best_error)))\n        return best_stump\n\n    @staticmethod\n    def binary_stump(feature_name, feature_value, labeled_featuresets):\n        label = FreqDist(label for (featureset, label)\n                         in labeled_featuresets).max()\n\n        # Find the best label for each value.\n        pos_fdist = FreqDist()\n        neg_fdist = FreqDist()\n        for featureset, label in labeled_featuresets:\n            if featureset.get(feature_name) == feature_value:\n                pos_fdist[label] += 1\n            else:\n                neg_fdist[label] += 1\n\n\n        decisions = {}\n        default = label\n        # But hopefully we have observations!\n        if pos_fdist.N() > 0:\n            decisions = {feature_value: DecisionTreeClassifier(pos_fdist.max())}\n        if neg_fdist.N() > 0:\n            default = DecisionTreeClassifier(neg_fdist.max())\n\n        return DecisionTreeClassifier(label, feature_name, decisions, default)\n\n    @staticmethod\n    def best_binary_stump(feature_names, labeled_featuresets, feature_values,\n                          verbose=False):\n        best_stump = DecisionTreeClassifier.leaf(labeled_featuresets)\n        best_error = best_stump.error(labeled_featuresets)\n        for fname in feature_names:\n            for fval in feature_values[fname]:\n                stump = DecisionTreeClassifier.binary_stump(\n                    fname, fval, labeled_featuresets)\n                stump_error = stump.error(labeled_featuresets)\n                if stump_error < best_error:\n                    best_error = stump_error\n                    best_stump = stump\n        if best_stump._decisions:\n            descr = '{0}={1}'.format(best_stump._fname,\n                               list(best_stump._decisions.keys())[0])\n        else:\n            descr = '(default)'\n        if verbose:\n            print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \\\n                   (len(labeled_featuresets), descr, best_error)))\n        return best_stump\n\n##//////////////////////////////////////////////////////\n##  Demo\n##//////////////////////////////////////////////////////\n\ndef f(x):\n    return DecisionTreeClassifier.train(x, binary=True, verbose=True)\n\ndef demo():\n    from nltk.classify.util import names_demo, binary_names_demo_features\n    classifier = names_demo(f, #DecisionTreeClassifier.train,\n                            binary_names_demo_features)\n    print(classifier.pp(depth=7))\n    print(classifier.pseudocode(depth=7))\n\nif __name__ == '__main__':\n    demo()\n\n", "path": "nltk/classify/decisiontree.py"}], "after_files": [{"content": "# Natural Language Toolkit: Decision Tree Classifiers\n#\n# Copyright (C) 2001-2017 NLTK Project\n# Author: Edward Loper <edloper@gmail.com>\n# URL: <http://nltk.org/>\n# For license information, see LICENSE.TXT\n\n\"\"\"\nA classifier model that decides which label to assign to a token on\nthe basis of a tree structure, where branches correspond to conditions\non feature values, and leaves correspond to label assignments.\n\"\"\"\nfrom __future__ import print_function, unicode_literals, division\n\nfrom collections import defaultdict\n\nfrom nltk.probability import FreqDist, MLEProbDist, entropy\nfrom nltk.classify.api import ClassifierI\nfrom nltk.compat import python_2_unicode_compatible\n\n@python_2_unicode_compatible\nclass DecisionTreeClassifier(ClassifierI):\n    def __init__(self, label, feature_name=None, decisions=None, default=None):\n        \"\"\"\n        :param label: The most likely label for tokens that reach\n            this node in the decision tree.  If this decision tree\n            has no children, then this label will be assigned to\n            any token that reaches this decision tree.\n        :param feature_name: The name of the feature that this\n            decision tree selects for.\n        :param decisions: A dictionary mapping from feature values\n            for the feature identified by ``feature_name`` to\n            child decision trees.\n        :param default: The child that will be used if the value of\n            feature ``feature_name`` does not match any of the keys in\n            ``decisions``.  This is used when constructing binary\n            decision trees.\n        \"\"\"\n        self._label = label\n        self._fname = feature_name\n        self._decisions = decisions\n        self._default = default\n\n    def labels(self):\n        labels = [self._label]\n        if self._decisions is not None:\n            for dt in self._decisions.values():\n                labels.extend(dt.labels())\n        if self._default is not None:\n            labels.extend(self._default.labels())\n        return list(set(labels))\n\n    def classify(self, featureset):\n        # Decision leaf:\n        if self._fname is None:\n            return self._label\n\n        # Decision tree:\n        fval = featureset.get(self._fname)\n        if fval in self._decisions:\n            return self._decisions[fval].classify(featureset)\n        elif self._default is not None:\n            return self._default.classify(featureset)\n        else:\n            return self._label\n\n    def error(self, labeled_featuresets):\n        errors = 0\n        for featureset, label in labeled_featuresets:\n            if self.classify(featureset) != label:\n                errors += 1\n        return errors/len(labeled_featuresets)\n\n    def pretty_format(self, width=70, prefix='', depth=4):\n        \"\"\"\n        Return a string containing a pretty-printed version of this\n        decision tree.  Each line in this string corresponds to a\n        single decision tree node or leaf, and indentation is used to\n        display the structure of the decision tree.\n        \"\"\"\n        # [xx] display default!!\n        if self._fname is None:\n            n = width-len(prefix)-15\n            return '{0}{1} {2}\\n'.format(prefix, '.'*n, self._label)\n        s = ''\n        for i, (fval, result) in enumerate(sorted(self._decisions.items())):\n            hdr = '{0}{1}={2}? '.format(prefix, self._fname, fval)\n            n = width-15-len(hdr)\n            s += '{0}{1} {2}\\n'.format(hdr, '.'*(n), result._label)\n            if result._fname is not None and depth>1:\n                s += result.pretty_format(width, prefix+'  ', depth-1)\n        if self._default is not None:\n            n = width-len(prefix)-21\n            s += '{0}else: {1} {2}\\n'.format(prefix, '.'*n, self._default._label)\n            if self._default._fname is not None and depth>1:\n                s += self._default.pretty_format(width, prefix+'  ', depth-1)\n        return s\n\n    def pseudocode(self, prefix='', depth=4):\n        \"\"\"\n        Return a string representation of this decision tree that\n        expresses the decisions it makes as a nested set of pseudocode\n        if statements.\n        \"\"\"\n        if self._fname is None:\n            return \"{0}return {1!r}\\n\".format(prefix, self._label)\n        s = ''\n        for (fval, result) in sorted(self._decisions.items()):\n            s += '{0}if {1} == {2!r}: '.format(prefix, self._fname, fval)\n            if result._fname is not None and depth>1:\n                s += '\\n'+result.pseudocode(prefix+'  ', depth-1)\n            else:\n                s += 'return {0!r}\\n'.format(result._label)\n        if self._default is not None:\n            if len(self._decisions) == 1:\n                s += '{0}if {1} != {2!r}: '.format(prefix, self._fname,\n                                         list(self._decisions.keys())[0])\n            else:\n                s += '{0}else: '.format(prefix)\n            if self._default._fname is not None and depth>1:\n                s += '\\n'+self._default.pseudocode(prefix+'  ', depth-1)\n            else:\n                s += 'return {0!r}\\n'.format(self._default._label)\n        return s\n\n    def __str__(self):\n        return self.pretty_format()\n\n    @staticmethod\n    def train(labeled_featuresets, entropy_cutoff=0.05, depth_cutoff=100,\n              support_cutoff=10, binary=False, feature_values=None,\n              verbose=False):\n        \"\"\"\n        :param binary: If true, then treat all feature/value pairs as\n            individual binary features, rather than using a single n-way\n            branch for each feature.\n        \"\"\"\n        # Collect a list of all feature names.\n        feature_names = set()\n        for featureset, label in labeled_featuresets:\n            for fname in featureset:\n                feature_names.add(fname)\n\n        # Collect a list of the values each feature can take.\n        if feature_values is None and binary:\n            feature_values = defaultdict(set)\n            for featureset, label in labeled_featuresets:\n                for fname, fval in featureset.items():\n                    feature_values[fname].add(fval)\n\n        # Start with a stump.\n        if not binary:\n            tree = DecisionTreeClassifier.best_stump(\n                feature_names, labeled_featuresets, verbose)\n        else:\n            tree = DecisionTreeClassifier.best_binary_stump(\n                feature_names, labeled_featuresets, feature_values, verbose)\n\n        # Refine the stump.\n        tree.refine(labeled_featuresets, entropy_cutoff, depth_cutoff-1,\n                    support_cutoff, binary, feature_values, verbose)\n\n        # Return it\n        return tree\n\n    @staticmethod\n    def leaf(labeled_featuresets):\n        label = FreqDist(label for (featureset, label)\n                         in labeled_featuresets).max()\n        return DecisionTreeClassifier(label)\n\n    @staticmethod\n    def stump(feature_name, labeled_featuresets):\n        label = FreqDist(label for (featureset, label)\n                         in labeled_featuresets).max()\n\n        # Find the best label for each value.\n        freqs = defaultdict(FreqDist) # freq(label|value)\n        for featureset, label in labeled_featuresets:\n            feature_value = featureset.get(feature_name)\n            freqs[feature_value][label] += 1\n\n        decisions = dict((val, DecisionTreeClassifier(freqs[val].max()))\n                         for val in freqs)\n        return DecisionTreeClassifier(label, feature_name, decisions)\n\n    def refine(self, labeled_featuresets, entropy_cutoff, depth_cutoff,\n               support_cutoff, binary=False, feature_values=None,\n               verbose=False):\n        if len(labeled_featuresets) <= support_cutoff: return\n        if self._fname is None: return\n        if depth_cutoff <= 0: return\n        for fval in self._decisions:\n            fval_featuresets = [(featureset, label) for (featureset, label)\n                                in labeled_featuresets\n                                if featureset.get(self._fname) == fval]\n\n            label_freqs = FreqDist(label for (featureset, label)\n                                   in fval_featuresets)\n            if entropy(MLEProbDist(label_freqs)) > entropy_cutoff:\n                self._decisions[fval] = DecisionTreeClassifier.train(\n                    fval_featuresets, entropy_cutoff, depth_cutoff,\n                    support_cutoff, binary, feature_values, verbose)\n        if self._default is not None:\n            default_featuresets = [(featureset, label) for (featureset, label)\n                                   in labeled_featuresets\n                                   if featureset.get(self._fname) not in\n                                   self._decisions]\n            label_freqs = FreqDist(label for (featureset, label)\n                                   in default_featuresets)\n            if entropy(MLEProbDist(label_freqs)) > entropy_cutoff:\n                self._default = DecisionTreeClassifier.train(\n                    default_featuresets, entropy_cutoff, depth_cutoff,\n                    support_cutoff, binary, feature_values, verbose)\n\n    @staticmethod\n    def best_stump(feature_names, labeled_featuresets, verbose=False):\n        best_stump = DecisionTreeClassifier.leaf(labeled_featuresets)\n        best_error = best_stump.error(labeled_featuresets)\n        for fname in feature_names:\n            stump = DecisionTreeClassifier.stump(fname, labeled_featuresets)\n            stump_error = stump.error(labeled_featuresets)\n            if stump_error < best_error:\n                best_error = stump_error\n                best_stump = stump\n        if verbose:\n            print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \\\n                   (len(labeled_featuresets), best_stump._fname, best_error)))\n        return best_stump\n\n    @staticmethod\n    def binary_stump(feature_name, feature_value, labeled_featuresets):\n        label = FreqDist(label for (featureset, label)\n                         in labeled_featuresets).max()\n\n        # Find the best label for each value.\n        pos_fdist = FreqDist()\n        neg_fdist = FreqDist()\n        for featureset, label in labeled_featuresets:\n            if featureset.get(feature_name) == feature_value:\n                pos_fdist[label] += 1\n            else:\n                neg_fdist[label] += 1\n\n\n        decisions = {}\n        default = label\n        # But hopefully we have observations!\n        if pos_fdist.N() > 0:\n            decisions = {feature_value: DecisionTreeClassifier(pos_fdist.max())}\n        if neg_fdist.N() > 0:\n            default = DecisionTreeClassifier(neg_fdist.max())\n\n        return DecisionTreeClassifier(label, feature_name, decisions, default)\n\n    @staticmethod\n    def best_binary_stump(feature_names, labeled_featuresets, feature_values,\n                          verbose=False):\n        best_stump = DecisionTreeClassifier.leaf(labeled_featuresets)\n        best_error = best_stump.error(labeled_featuresets)\n        for fname in feature_names:\n            for fval in feature_values[fname]:\n                stump = DecisionTreeClassifier.binary_stump(\n                    fname, fval, labeled_featuresets)\n                stump_error = stump.error(labeled_featuresets)\n                if stump_error < best_error:\n                    best_error = stump_error\n                    best_stump = stump\n        if verbose:\n            if best_stump._decisions:\n                descr = '{0}={1}'.format(best_stump._fname,\n                                         list(best_stump._decisions.keys())[0])\n            else:\n                descr = '(default)'\n            print(('best stump for {:6d} toks uses {:20} err={:6.4f}'.format \\\n                   (len(labeled_featuresets), descr, best_error)))\n        return best_stump\n\n##//////////////////////////////////////////////////////\n##  Demo\n##//////////////////////////////////////////////////////\n\ndef f(x):\n    return DecisionTreeClassifier.train(x, binary=True, verbose=True)\n\ndef demo():\n    from nltk.classify.util import names_demo, binary_names_demo_features\n    classifier = names_demo(f, #DecisionTreeClassifier.train,\n                            binary_names_demo_features)\n    print(classifier.pp(depth=7))\n    print(classifier.pseudocode(depth=7))\n\nif __name__ == '__main__':\n    demo()\n\n", "path": "nltk/classify/decisiontree.py"}]}