← Back to branch summary

~ubuntu-branches/ubuntu/precise/weka/precise

« back to all changes in this revision

Viewing changes to weka/classifiers/trees/j48/PruneableClassifierTree.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/classifiers/trees/j48/PruneableClassifierTree.java
 
1
/*
 
2
 *    This program is free software; you can redistribute it and/or modify
 
3
 *    it under the terms of the GNU General Public License as published by
 
4
 *    the Free Software Foundation; either version 2 of the License, or
 
5
 *    (at your option) any later version.
 
6
 *
 
7
 *    This program is distributed in the hope that it will be useful,
 
8
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 *    GNU General Public License for more details.
 
11
 *
 
12
 *    You should have received a copy of the GNU General Public License
 
13
 *    along with this program; if not, write to the Free Software
 
14
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 *    PruneableClassifierTree.java
 
19
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 
20
 *
 
21
 */
 
22
 
 
23
package weka.classifiers.trees.j48;
 
24
 
 
25
import weka.core.Capabilities;
 
26
import weka.core.Instances;
 
27
import weka.core.Utils;
 
28
import weka.core.Capabilities.Capability;
 
29
 
 
30
import java.util.Random;
 
31
 
 
32
/**
 
33
 * Class for handling a tree structure that can
 
34
 * be pruned using a pruning set. 
 
35
 *
 
36
 * @author Eibe Frank (eibe@cs.waikato.ac.nz)
 
37
 * @version $Revision: 1.11 $
 
38
 */
 
39
public class PruneableClassifierTree 
 
40
  extends ClassifierTree {
 
41
  
 
42
  /** for serialization */
 
43
  static final long serialVersionUID = -555775736857600201L;
 
44
 
 
45
  /** True if the tree is to be pruned. */
 
46
  private boolean pruneTheTree = false;
 
47
 
 
48
  /** How many subsets of equal size? One used for pruning, the rest for training. */
 
49
  private int numSets = 3;
 
50
 
 
51
  /** Cleanup after the tree has been built. */
 
52
  private boolean m_cleanup = true;
 
53
 
 
54
  /** The random number seed. */
 
55
  private int m_seed = 1;
 
56
 
 
57
  /**
 
58
   * Constructor for pruneable tree structure. Stores reference
 
59
   * to associated training data at each node.
 
60
   *
 
61
   * @param toSelectLocModel selection method for local splitting model
 
62
   * @param pruneTree true if the tree is to be pruned
 
63
   * @param num number of subsets of equal size
 
64
   * @param cleanup
 
65
   * @param seed the seed value to use
 
66
   * @throws Exception if something goes wrong
 
67
   */
 
68
  public PruneableClassifierTree(ModelSelection toSelectLocModel,
 
69
                                 boolean pruneTree, int num, boolean cleanup,
 
70
                                 int seed)
 
71
       throws Exception {
 
72
 
 
73
    super(toSelectLocModel);
 
74
 
 
75
    pruneTheTree = pruneTree;
 
76
    numSets = num;
 
77
    m_cleanup = cleanup;
 
78
    m_seed = seed;
 
79
  }
 
80
 
 
81
  /**
 
82
   * Returns default capabilities of the classifier tree.
 
83
   *
 
84
   * @return      the capabilities of this classifier tree
 
85
   */
 
86
  public Capabilities getCapabilities() {
 
87
    Capabilities result = super.getCapabilities();
 
88
 
 
89
    // attributes
 
90
    result.enable(Capability.NOMINAL_ATTRIBUTES);
 
91
    result.enable(Capability.NUMERIC_ATTRIBUTES);
 
92
    result.enable(Capability.DATE_ATTRIBUTES);
 
93
    result.enable(Capability.MISSING_VALUES);
 
94
 
 
95
    // class
 
96
    result.enable(Capability.NOMINAL_CLASS);
 
97
    result.enable(Capability.MISSING_CLASS_VALUES);
 
98
 
 
99
    // instances
 
100
    result.setMinimumNumberInstances(0);
 
101
    
 
102
    return result;
 
103
  }
 
104
 
 
105
  /**
 
106
   * Method for building a pruneable classifier tree.
 
107
   *
 
108
   * @param data the data to build the tree from 
 
109
   * @throws Exception if tree can't be built successfully
 
110
   */
 
111
  public void buildClassifier(Instances data) 
 
112
       throws Exception {
 
113
 
 
114
    // can classifier tree handle the data?
 
115
    getCapabilities().testWithFail(data);
 
116
 
 
117
    // remove instances with missing class
 
118
    data = new Instances(data);
 
119
    data.deleteWithMissingClass();
 
120
    
 
121
   Random random = new Random(m_seed);
 
122
   data.stratify(numSets);
 
123
   buildTree(data.trainCV(numSets, numSets - 1, random),
 
124
             data.testCV(numSets, numSets - 1), false);
 
125
   if (pruneTheTree) {
 
126
     prune();
 
127
   }
 
128
   if (m_cleanup) {
 
129
     cleanup(new Instances(data, 0));
 
130
   }
 
131
  }
 
132
 
 
133
  /**
 
134
   * Prunes a tree.
 
135
   *
 
136
   * @throws Exception if tree can't be pruned successfully
 
137
   */
 
138
  public void prune() throws Exception {
 
139
  
 
140
    if (!m_isLeaf) {
 
141
      
 
142
      // Prune all subtrees.
 
143
      for (int i = 0; i < m_sons.length; i++)
 
144
        son(i).prune();
 
145
      
 
146
      // Decide if leaf is best choice.
 
147
      if (Utils.smOrEq(errorsForLeaf(),errorsForTree())) {
 
148
        
 
149
        // Free son Trees
 
150
        m_sons = null;
 
151
        m_isLeaf = true;
 
152
        
 
153
        // Get NoSplit Model for node.
 
154
        m_localModel = new NoSplit(localModel().distribution());
 
155
      }
 
156
    }
 
157
  }
 
158
 
 
159
  /**
 
160
   * Returns a newly created tree.
 
161
   *
 
162
   * @param train the training data
 
163
   * @param test the test data
 
164
   * @return the generated tree
 
165
   * @throws Exception if something goes wrong
 
166
   */
 
167
  protected ClassifierTree getNewTree(Instances train, Instances test) 
 
168
       throws Exception {
 
169
 
 
170
    PruneableClassifierTree newTree = 
 
171
      new PruneableClassifierTree(m_toSelectModel, pruneTheTree, numSets, m_cleanup,
 
172
                                  m_seed);
 
173
    newTree.buildTree(train, test, false);
 
174
    return newTree;
 
175
  }
 
176
 
 
177
  /**
 
178
   * Computes estimated errors for tree.
 
179
   *
 
180
   * @return the estimated errors
 
181
   * @throws Exception if error estimate can't be computed
 
182
   */
 
183
  private double errorsForTree() throws Exception {
 
184
 
 
185
    double errors = 0;
 
186
 
 
187
    if (m_isLeaf)
 
188
      return errorsForLeaf();
 
189
    else{
 
190
      for (int i = 0; i < m_sons.length; i++)
 
191
        if (Utils.eq(localModel().distribution().perBag(i), 0)) {
 
192
          errors += m_test.perBag(i)-
 
193
            m_test.perClassPerBag(i,localModel().distribution().
 
194
                                maxClass());
 
195
        } else
 
196
          errors += son(i).errorsForTree();
 
197
 
 
198
      return errors;
 
199
    }
 
200
  }
 
201
 
 
202
  /**
 
203
   * Computes estimated errors for leaf.
 
204
   *
 
205
   * @return the estimated errors
 
206
   * @throws Exception if error estimate can't be computed
 
207
   */
 
208
  private double errorsForLeaf() throws Exception {
 
209
 
 
210
    return m_test.total()-
 
211
      m_test.perClass(localModel().distribution().maxClass());
 
212
  }
 
213
 
 
214
  /**
 
215
   * Method just exists to make program easier to read.
 
216
   */
 
217
  private ClassifierSplitModel localModel() {
 
218
    
 
219
    return (ClassifierSplitModel)m_localModel;
 
220
  }
 
221
 
 
222
  /**
 
223
   * Method just exists to make program easier to read.
 
224
   */
 
225
  private PruneableClassifierTree son(int index) {
 
226
 
 
227
    return (PruneableClassifierTree)m_sons[index];
 
228
  }
 
229
}
 
230
 
 
231
 
 
232
 
 
233
 
 
234
 
 
235
 
 
236