source: src/main/java/weka/classifiers/misc/VFI.java @ 28

Last change on this file since 28 was 4, checked in by gnappo, 14 years ago

Import di weka.

File size: 19.4 KB
Line 
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 *    VFI.java
19 *    Copyright (C) 2000 University of Waikato, Hamilton, New Zealand
20 *
21 */
22
23package weka.classifiers.misc;
24
25import weka.classifiers.Classifier;
26import weka.classifiers.AbstractClassifier;
27import weka.core.Capabilities;
28import weka.core.Instance;
29import weka.core.Instances;
30import weka.core.Option;
31import weka.core.OptionHandler;
32import weka.core.RevisionUtils;
33import weka.core.TechnicalInformation;
34import weka.core.TechnicalInformationHandler;
35import weka.core.Utils;
36import weka.core.WeightedInstancesHandler;
37import weka.core.Capabilities.Capability;
38import weka.core.TechnicalInformation.Field;
39import weka.core.TechnicalInformation.Type;
40
41import java.util.Enumeration;
42import java.util.Vector;
43
44/**
45 <!-- globalinfo-start -->
46 * Classification by voting feature intervals. Intervals are constucted around each class for each attribute (basically discretization). Class counts are recorded for each interval on each attribute. Classification is by voting. For more info see:<br/>
47 * <br/>
48 * G. Demiroz, A. Guvenir: Classification by voting feature intervals. In: 9th European Conference on Machine Learning, 85-92, 1997.<br/>
49 * <br/>
50 * Have added a simple attribute weighting scheme. Higher weight is assigned to more confident intervals, where confidence is a function of entropy:<br/>
51 * weight (att_i) = (entropy of class distrib att_i / max uncertainty)^-bias
52 * <p/>
53 <!-- globalinfo-end -->
54 *
55 <!-- technical-bibtex-start -->
56 * BibTeX:
57 * <pre>
58 * &#64;inproceedings{Demiroz1997,
59 *    author = {G. Demiroz and A. Guvenir},
60 *    booktitle = {9th European Conference on Machine Learning},
61 *    pages = {85-92},
62 *    publisher = {Springer},
63 *    title = {Classification by voting feature intervals},
64 *    year = {1997}
65 * }
66 * </pre>
67 * <p/>
68 <!-- technical-bibtex-end -->
69 *
70 * Faster than NaiveBayes but slower than HyperPipes. <p><p>
71 *
72 * <pre>
73 *  Confidence: 0.01 (two tailed)
74 *
75 * Dataset                   (1) VFI '-B  | (2) Hyper (3) Naive
76 *                         ------------------------------------
77 * anneal.ORIG               (10)   74.56 |   97.88 v   74.77
78 * anneal                    (10)   71.83 |   97.88 v   86.51 v
79 * audiology                 (10)   51.69 |   66.26 v   72.25 v
80 * autos                     (10)   57.63 |   62.79 v   57.76
81 * balance-scale             (10)   68.72 |   46.08 *   90.5  v
82 * breast-cancer             (10)   67.25 |   69.84 v   73.12 v
83 * wisconsin-breast-cancer   (10)   95.72 |   88.31 *   96.05 v
84 * horse-colic.ORIG          (10)   66.13 |   70.41 v   66.12
85 * horse-colic               (10)   78.36 |   62.07 *   78.28
86 * credit-rating             (10)   85.17 |   44.58 *   77.84 *
87 * german_credit             (10)   70.81 |   69.89 *   74.98 v
88 * pima_diabetes             (10)   62.13 |   65.47 v   75.73 v
89 * Glass                     (10)   56.82 |   50.19 *   47.43 *
90 * cleveland-14-heart-diseas (10)   80.01 |   55.18 *   83.83 v
91 * hungarian-14-heart-diseas (10)   82.8  |   65.55 *   84.37 v
92 * heart-statlog             (10)   79.37 |   55.56 *   84.37 v
93 * hepatitis                 (10)   83.78 |   63.73 *   83.87
94 * hypothyroid               (10)   92.64 |   93.33 v   95.29 v
95 * ionosphere                (10)   94.16 |   35.9  *   82.6  *
96 * iris                      (10)   96.2  |   91.47 *   95.27 *
97 * kr-vs-kp                  (10)   88.22 |   54.1  *   87.84 *
98 * labor                     (10)   86.73 |   87.67     93.93 v
99 * lymphography              (10)   78.48 |   58.18 *   83.24 v
100 * mushroom                  (10)   99.85 |   99.77 *   95.77 *
101 * primary-tumor             (10)   29    |   24.78 *   49.35 v
102 * segment                   (10)   77.42 |   75.15 *   80.1  v
103 * sick                      (10)   65.92 |   93.85 v   92.71 v
104 * sonar                     (10)   58.02 |   57.17     67.97 v
105 * soybean                   (10)   86.81 |   86.12 *   92.9  v
106 * splice                    (10)   88.61 |   41.97 *   95.41 v
107 * vehicle                   (10)   52.94 |   32.77 *   44.8  *
108 * vote                      (10)   91.5  |   61.38 *   90.19 *
109 * vowel                     (10)   57.56 |   36.34 *   62.81 v
110 * waveform                  (10)   56.33 |   46.11 *   80.02 v
111 * zoo                       (10)   94.05 |   94.26     95.04 v
112 *                          ------------------------------------
113 *                                (v| |*) |  (9|3|23)  (22|5|8)
114 * </pre>                                       
115 * <p>
116 *
117 <!-- options-start -->
118 * Valid options are: <p/>
119 *
120 * <pre> -C
121 *  Don't weight voting intervals by confidence</pre>
122 *
123 * <pre> -B &lt;bias&gt;
124 *  Set exponential bias towards confident intervals
125 *  (default = 1.0)</pre>
126 *
127 <!-- options-end -->
128 *
129 * @author Mark Hall (mhall@cs.waikato.ac.nz)
130 * @version $Revision: 5928 $
131 */
132public class VFI 
133  extends AbstractClassifier
134  implements OptionHandler, WeightedInstancesHandler, TechnicalInformationHandler {
135
136  /** for serialization */
137  static final long serialVersionUID = 8081692166331321866L;
138 
139  /** The index of the class attribute */
140  protected int m_ClassIndex;
141
142  /** The number of classes */
143  protected int m_NumClasses;
144
145  /** The training data */
146  protected Instances m_Instances = null;
147
148  /** The class counts for each interval of each attribute */
149  protected double [][][] m_counts;
150
151  /** The global class counts */
152  protected double [] m_globalCounts;
153
154  /** The lower bounds for each attribute */
155  protected double [][] m_intervalBounds;
156
157  /** The maximum entropy for the class */
158  protected double m_maxEntrop;
159
160  /** Exponentially bias more confident intervals */
161  protected boolean m_weightByConfidence = true;
162
163  /** Bias towards more confident intervals */
164  protected double m_bias = -0.6;
165
166  private double TINY = 0.1e-10;
167
168  /**
169   * Returns a string describing this search method
170   * @return a description of the search method suitable for
171   * displaying in the explorer/experimenter gui
172   */
173  public String globalInfo() {
174    return "Classification by voting feature intervals. Intervals are "
175      +"constucted around each class for each attribute ("
176      +"basically discretization). Class counts are "
177      +"recorded for each interval on each attribute. Classification is by "
178      +"voting. For more info see:\n\n"
179      + getTechnicalInformation().toString() + "\n\n"
180      +"Have added a simple attribute weighting scheme. Higher weight is "
181      +"assigned to more confident intervals, where confidence is a function "
182      +"of entropy:\nweight (att_i) = (entropy of class distrib att_i / "
183      +"max uncertainty)^-bias";
184  }
185
186  /**
187   * Returns an instance of a TechnicalInformation object, containing
188   * detailed information about the technical background of this class,
189   * e.g., paper reference or book this class is based on.
190   *
191   * @return the technical information about this class
192   */
193  public TechnicalInformation getTechnicalInformation() {
194    TechnicalInformation        result;
195   
196    result = new TechnicalInformation(Type.INPROCEEDINGS);
197    result.setValue(Field.AUTHOR, "G. Demiroz and A. Guvenir");
198    result.setValue(Field.TITLE, "Classification by voting feature intervals");
199    result.setValue(Field.BOOKTITLE, "9th European Conference on Machine Learning");
200    result.setValue(Field.YEAR, "1997");
201    result.setValue(Field.PAGES, "85-92");
202    result.setValue(Field.PUBLISHER, "Springer");
203   
204    return result;
205  }
206
207  /**
208   * Returns an enumeration describing the available options.
209   *
210   * @return an enumeration of all the available options.
211   */
212  public Enumeration listOptions() {
213
214    Vector newVector = new Vector(2);
215
216    newVector.addElement(
217    new Option("\tDon't weight voting intervals by confidence",
218               "C", 0,"-C"));
219    newVector.addElement(
220    new Option("\tSet exponential bias towards confident intervals\n"
221               +"\t(default = 1.0)",
222               "B", 1,"-B <bias>"));
223
224    return newVector.elements();
225  }
226
227  /**
228   * Parses a given list of options. <p/>
229   *
230   <!-- options-start -->
231   * Valid options are: <p/>
232   *
233   * <pre> -C
234   *  Don't weight voting intervals by confidence</pre>
235   *
236   * <pre> -B &lt;bias&gt;
237   *  Set exponential bias towards confident intervals
238   *  (default = 1.0)</pre>
239   *
240   <!-- options-end -->
241   *
242   * @param options the list of options as an array of strings
243   * @throws Exception if an option is not supported
244   */
245  public void setOptions(String[] options) throws Exception {
246    String optionString;
247   
248    setWeightByConfidence(!Utils.getFlag('C', options));
249   
250    optionString = Utils.getOption('B', options);
251    if (optionString.length() != 0) {
252      Double temp = new Double(optionString);
253      setBias(temp.doubleValue());
254    }
255
256    Utils.checkForRemainingOptions(options);
257  }
258
259  /**
260   * Returns the tip text for this property
261   * @return tip text for this property suitable for
262   * displaying in the explorer/experimenter gui
263   */
264  public String weightByConfidenceTipText() {
265    return "Weight feature intervals by confidence";
266  }
267
268  /**
269   * Set weighting by confidence
270   * @param c true if feature intervals are to be weighted by confidence
271   */
272  public void setWeightByConfidence(boolean c) {
273    m_weightByConfidence = c;
274  }
275
276  /**
277   * Get whether feature intervals are being weighted by confidence
278   * @return true if weighting by confidence is selected
279   */
280  public boolean getWeightByConfidence() {
281    return m_weightByConfidence;
282  }
283
284  /**
285   * Returns the tip text for this property
286   * @return tip text for this property suitable for
287   * displaying in the explorer/experimenter gui
288   */
289  public String biasTipText() {
290    return "Strength of bias towards more confident features";
291  }
292
293  /**
294   * Set the value of the exponential bias towards more confident intervals
295   * @param b the value of the bias parameter
296   */
297  public void setBias(double b) {
298    m_bias = -b;
299  }
300
301  /**
302   * Get the value of the bias parameter
303   * @return the bias parameter
304   */
305  public double getBias() {
306    return -m_bias;
307  }
308
309  /**
310   * Gets the current settings of VFI
311   *
312   * @return an array of strings suitable for passing to setOptions()
313   */
314  public String[] getOptions () {
315    String[] options = new String[3];
316    int current = 0;
317   
318    if (!getWeightByConfidence()) {
319      options[current++] = "-C";
320    }
321
322    options[current++] = "-B"; options[current++] = ""+getBias();
323    while (current < options.length) {
324      options[current++] = "";
325    }
326   
327    return options;
328  }
329 
330
331  /**
332   * Returns default capabilities of the classifier.
333   *
334   * @return      the capabilities of this classifier
335   */
336  public Capabilities getCapabilities() {
337    Capabilities result = super.getCapabilities();
338    result.disableAll();
339
340    // attributes
341    result.enable(Capability.NOMINAL_ATTRIBUTES);
342    result.enable(Capability.NUMERIC_ATTRIBUTES);
343    result.enable(Capability.DATE_ATTRIBUTES);
344    result.enable(Capability.STRING_ATTRIBUTES);
345    result.enable(Capability.MISSING_VALUES);
346
347    // class
348    result.enable(Capability.NOMINAL_CLASS);
349    result.enable(Capability.MISSING_CLASS_VALUES);
350
351    // instances
352    result.setMinimumNumberInstances(0);
353   
354    return result;
355  }
356
357  /**
358   * Generates the classifier.
359   *
360   * @param instances set of instances serving as training data
361   * @throws Exception if the classifier has not been generated successfully
362   */
363  public void buildClassifier(Instances instances) throws Exception {
364
365    if (!m_weightByConfidence) {
366      TINY = 0.0;
367    }
368
369    // can classifier handle the data?
370    getCapabilities().testWithFail(instances);
371
372    // remove instances with missing class
373    instances = new Instances(instances);
374    instances.deleteWithMissingClass();
375
376    m_ClassIndex = instances.classIndex();
377    m_NumClasses = instances.numClasses();
378    m_globalCounts = new double [m_NumClasses];
379    m_maxEntrop = Math.log(m_NumClasses) / Math.log(2);
380
381    m_Instances = new Instances(instances, 0); // Copy the structure for ref
382
383    m_intervalBounds = 
384      new double[instances.numAttributes()][2+(2*m_NumClasses)];
385
386    for (int j = 0; j < instances.numAttributes(); j++) {
387      boolean alt = false;
388      for (int i = 0; i < m_NumClasses*2+2; i++) {
389        if (i == 0) {
390          m_intervalBounds[j][i] = Double.NEGATIVE_INFINITY;
391        } else if (i == m_NumClasses*2+1) {
392          m_intervalBounds[j][i] = Double.POSITIVE_INFINITY;
393        } else {
394          if (alt) {
395            m_intervalBounds[j][i] = Double.NEGATIVE_INFINITY;
396            alt = false;
397          } else {
398            m_intervalBounds[j][i] = Double.POSITIVE_INFINITY;
399            alt = true;
400          }
401        }
402      }
403    }
404
405    // find upper and lower bounds for numeric attributes
406    for (int j = 0; j < instances.numAttributes(); j++) {
407      if (j != m_ClassIndex && instances.attribute(j).isNumeric()) {
408        for (int i = 0; i < instances.numInstances(); i++) {
409          Instance inst = instances.instance(i);
410          if (!inst.isMissing(j)) {
411            if (inst.value(j) < 
412                m_intervalBounds[j][((int)inst.classValue()*2+1)]) {
413              m_intervalBounds[j][((int)inst.classValue()*2+1)] = 
414                inst.value(j);
415            }
416            if (inst.value(j) > 
417                m_intervalBounds[j][((int)inst.classValue()*2+2)]) {
418              m_intervalBounds[j][((int)inst.classValue()*2+2)] = 
419                inst.value(j);
420            }
421          }
422        }
423      }
424    }
425
426    m_counts = new double [instances.numAttributes()][][];
427
428    // sort intervals
429    for (int i = 0 ; i < instances.numAttributes(); i++) {
430      if (instances.attribute(i).isNumeric()) {
431        int [] sortedIntervals = Utils.sort(m_intervalBounds[i]);
432        // remove any duplicate bounds
433        int count = 1;
434        for (int j = 1; j < sortedIntervals.length; j++) {
435          if (m_intervalBounds[i][sortedIntervals[j]] != 
436              m_intervalBounds[i][sortedIntervals[j-1]]) {
437            count++;
438          }
439        }
440        double [] reordered = new double [count];
441        count = 1;
442        reordered[0] = m_intervalBounds[i][sortedIntervals[0]];
443        for (int j = 1; j < sortedIntervals.length; j++) {
444           if (m_intervalBounds[i][sortedIntervals[j]] != 
445              m_intervalBounds[i][sortedIntervals[j-1]]) {
446             reordered[count] =  m_intervalBounds[i][sortedIntervals[j]];
447             count++;
448           }
449        }
450        m_intervalBounds[i] = reordered;
451        m_counts[i] = new double [count][m_NumClasses];
452      } else if (i != m_ClassIndex) { // nominal attribute
453        m_counts[i] = 
454          new double [instances.attribute(i).numValues()][m_NumClasses];
455      }
456    }
457
458    // collect class counts
459    for (int i = 0; i < instances.numInstances(); i++) {
460      Instance inst = instances.instance(i);
461      m_globalCounts[(int)instances.instance(i).classValue()] += inst.weight();
462      for (int j = 0; j < instances.numAttributes(); j++) {
463        if (!inst.isMissing(j) && j != m_ClassIndex) {
464          if (instances.attribute(j).isNumeric()) {
465            double val = inst.value(j);
466           
467            int k;
468            for (k = m_intervalBounds[j].length-1; k >= 0; k--) {
469              if (val > m_intervalBounds[j][k]) {
470                m_counts[j][k][(int)inst.classValue()] += inst.weight();
471                break;
472              } else if (val == m_intervalBounds[j][k]) {
473                m_counts[j][k][(int)inst.classValue()] += 
474                  (inst.weight() / 2.0);
475                m_counts[j][k-1][(int)inst.classValue()] += 
476                  (inst.weight() / 2.0);;
477                break;
478              }
479            }
480           
481          } else {
482            // nominal attribute
483            m_counts[j][(int)inst.value(j)][(int)inst.classValue()] += 
484              inst.weight();;
485          }
486        }
487      }
488    }
489  }
490
491  /**
492   * Returns a description of this classifier.
493   *
494   * @return a description of this classifier as a string.
495   */
496  public String toString() {
497    if (m_Instances == null) {
498      return "FVI: Classifier not built yet!";
499    }
500    StringBuffer sb = 
501      new StringBuffer("Voting feature intervals classifier\n");
502
503    /* Output the intervals and class counts for each attribute */
504    /*    for (int i = 0; i < m_Instances.numAttributes(); i++) {
505      if (i != m_ClassIndex) {
506        sb.append("\n"+m_Instances.attribute(i).name()+" :\n");
507         if (m_Instances.attribute(i).isNumeric()) {
508           for (int j = 0; j < m_intervalBounds[i].length; j++) {
509             sb.append(m_intervalBounds[i][j]).append("\n");
510             if (j != m_intervalBounds[i].length-1) {
511               for (int k = 0; k < m_NumClasses; k++) {
512                 sb.append(m_counts[i][j][k]+" ");
513               }
514             }
515             sb.append("\n");
516           }
517         } else {
518           for (int j = 0; j < m_Instances.attribute(i).numValues(); j++) {
519             sb.append(m_Instances.attribute(i).value(j)).append("\n");
520             for (int k = 0; k < m_NumClasses; k++) {
521               sb.append(m_counts[i][j][k]+" ");
522             }
523             sb.append("\n");
524           }
525         }
526      }
527      } */
528    return sb.toString();
529  }
530
531  /**
532   * Classifies the given test instance.
533   *
534   * @param instance the instance to be classified
535   * @return the predicted class for the instance
536   * @throws Exception if the instance can't be classified
537   */
538  public double [] distributionForInstance(Instance instance) 
539    throws Exception {
540    double [] dist = new double[m_NumClasses];
541    double [] temp = new double[m_NumClasses];
542    double weight = 1.0;
543
544
545    for (int i = 0; i < instance.numAttributes(); i++) {
546      if (i != m_ClassIndex && !instance.isMissing(i)) {
547        double val = instance.value(i);
548        boolean ok = false;
549        if (instance.attribute(i).isNumeric()) {
550          int k;
551          for (k = m_intervalBounds[i].length-1; k >= 0; k--) {
552            if (val > m_intervalBounds[i][k]) {
553              for (int j = 0; j < m_NumClasses; j++) {
554                if (m_globalCounts[j] > 0) {
555                  temp[j] = ((m_counts[i][k][j]+TINY) / 
556                             (m_globalCounts[j]+TINY));
557                }
558              }
559              ok = true;
560              break;
561            } else if (val == m_intervalBounds[i][k]) {
562              for (int j = 0; j < m_NumClasses; j++) {
563                if (m_globalCounts[j] > 0) {
564                  temp[j] = ((m_counts[i][k][j] + m_counts[i][k-1][j]) / 2.0) +
565                    TINY;
566                  temp[j] /= (m_globalCounts[j]+TINY);
567                }
568              }
569              ok = true;
570              break;
571            }
572          }
573          if (!ok) {
574            throw new Exception("This shouldn't happen");
575          }
576        } else { // nominal attribute
577          ok = true;
578          for (int j = 0; j < m_NumClasses; j++) {
579            if (m_globalCounts[j] > 0) {
580              temp[j] = ((m_counts[i][(int)val][j]+TINY) / 
581                         (m_globalCounts[j]+TINY));
582            }
583          }       
584        }
585       
586        double sum = Utils.sum(temp);
587        if (sum <= 0) {
588          for (int j = 0; j < temp.length; j++) {
589            temp[j] = 1.0 / (double)temp.length;
590          }
591        } else {
592          Utils.normalize(temp, sum);
593        }
594
595        if (m_weightByConfidence) {
596          weight = weka.core.ContingencyTables.entropy(temp);
597          weight = Math.pow(weight, m_bias);
598          if (weight < 1.0) {
599            weight = 1.0;
600          }
601        }
602
603        for (int j = 0; j < m_NumClasses; j++) {
604          dist[j] += (temp[j] * weight);
605        }
606      }
607    }
608   
609    double sum = Utils.sum(dist);
610    if (sum <= 0) {
611      for (int j = 0; j < dist.length; j++) {
612        dist[j] = 1.0 / (double)dist.length;
613      }
614      return dist;
615    } else {
616      Utils.normalize(dist, sum);
617      return dist;
618    }
619  }
620 
621  /**
622   * Returns the revision string.
623   *
624   * @return            the revision
625   */
626  public String getRevision() {
627    return RevisionUtils.extract("$Revision: 5928 $");
628  }
629       
630  /**
631   * Main method for testing this class.
632   *
633   * @param args should contain command line arguments for evaluation
634   * (see Evaluation).
635   */
636  public static void main(String [] args) {
637    runClassifier(new VFI(), args);
638  }
639}
Note: See TracBrowser for help on using the repository browser.