MOA 12.03
Real Time Analytics for Data Streams
RandomHoeffdingTree.java
Go to the documentation of this file.
00001 /*
00002  *    RandomHoeffdingTree.java
00003  *    Copyright (C) 2010 University of Waikato, Hamilton, New Zealand
00004  *    @author Albert Bifet (abifet@cs.waikato.ac.nz)
00005  *
00006  *    This program is free software; you can redistribute it and/or modify
00007  *    it under the terms of the GNU General Public License as published by
00008  *    the Free Software Foundation; either version 3 of the License, or
00009  *    (at your option) any later version.
00010  *
00011  *    This program is distributed in the hope that it will be useful,
00012  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  *    GNU General Public License for more details.
00015  *
00016  *    You should have received a copy of the GNU General Public License
00017  *    along with this program. If not, see <http://www.gnu.org/licenses/>.
00018  *    
00019  */
00020 package moa.classifiers.trees;
00021 
00022 import moa.classifiers.bayes.NaiveBayes;
00023 import moa.classifiers.core.attributeclassobservers.AttributeClassObserver;
00024 import weka.core.Instance;
00025 import weka.core.Utils;
00026 
00033 public class RandomHoeffdingTree extends HoeffdingTree {
00034 
00035     private static final long serialVersionUID = 1L;
00036 
00037     @Override
00038     public String getPurposeString() {
00039         return "Random decision trees for data streams.";
00040     }
00041 
00042     public static class RandomLearningNode extends ActiveLearningNode {
00043 
00044         private static final long serialVersionUID = 1L;
00045 
00046         protected int[] listAttributes;
00047 
00048         protected int numAttributes;
00049 
00050         public RandomLearningNode(double[] initialClassObservations) {
00051             super(initialClassObservations);
00052         }
00053 
00054         @Override
00055         public void learnFromInstance(Instance inst, HoeffdingTree ht) {
00056             this.observedClassDistribution.addToValue((int) inst.classValue(),
00057                     inst.weight());
00058             if (this.listAttributes == null) {
00059                 this.numAttributes = (int) Math.floor(Math.sqrt(inst.numAttributes()));
00060                 this.listAttributes = new int[this.numAttributes];
00061                 for (int j = 0; j < this.numAttributes; j++) {
00062                     boolean isUnique = false;
00063                     while (isUnique == false) {
00064                         this.listAttributes[j] = ht.classifierRandom.nextInt(inst.numAttributes() - 1);
00065                         isUnique = true;
00066                         for (int i = 0; i < j; i++) {
00067                             if (this.listAttributes[j] == this.listAttributes[i]) {
00068                                 isUnique = false;
00069                                 break;
00070                             }
00071                         }
00072                     }
00073 
00074                 }
00075             }
00076             for (int j = 0; j < this.numAttributes - 1; j++) {
00077                 int i = this.listAttributes[j];
00078                 int instAttIndex = modelAttIndexToInstanceAttIndex(i, inst);
00079                 AttributeClassObserver obs = this.attributeObservers.get(i);
00080                 if (obs == null) {
00081                     obs = inst.attribute(instAttIndex).isNominal() ? ht.newNominalClassObserver() : ht.newNumericClassObserver();
00082                     this.attributeObservers.set(i, obs);
00083                 }
00084                 obs.observeAttributeClass(inst.value(instAttIndex), (int) inst.classValue(), inst.weight());
00085             }
00086         }
00087     }
00088 
00089     public static class LearningNodeNB extends RandomLearningNode {
00090 
00091         private static final long serialVersionUID = 1L;
00092 
00093         public LearningNodeNB(double[] initialClassObservations) {
00094             super(initialClassObservations);
00095         }
00096 
00097         @Override
00098         public double[] getClassVotes(Instance inst, HoeffdingTree ht) {
00099             if (getWeightSeen() >= ht.nbThresholdOption.getValue()) {
00100                 return NaiveBayes.doNaiveBayesPrediction(inst,
00101                         this.observedClassDistribution,
00102                         this.attributeObservers);
00103             }
00104             return super.getClassVotes(inst, ht);
00105         }
00106 
00107         @Override
00108         public void disableAttribute(int attIndex) {
00109             // should not disable poor atts - they are used in NB calc
00110         }
00111     }
00112 
00113     public static class LearningNodeNBAdaptive extends LearningNodeNB {
00114 
00115         private static final long serialVersionUID = 1L;
00116 
00117         protected double mcCorrectWeight = 0.0;
00118 
00119         protected double nbCorrectWeight = 0.0;
00120 
00121         public LearningNodeNBAdaptive(double[] initialClassObservations) {
00122             super(initialClassObservations);
00123         }
00124 
00125         @Override
00126         public void learnFromInstance(Instance inst, HoeffdingTree ht) {
00127             int trueClass = (int) inst.classValue();
00128             if (this.observedClassDistribution.maxIndex() == trueClass) {
00129                 this.mcCorrectWeight += inst.weight();
00130             }
00131             if (Utils.maxIndex(NaiveBayes.doNaiveBayesPrediction(inst,
00132                     this.observedClassDistribution, this.attributeObservers)) == trueClass) {
00133                 this.nbCorrectWeight += inst.weight();
00134             }
00135             super.learnFromInstance(inst, ht);
00136         }
00137 
00138         @Override
00139         public double[] getClassVotes(Instance inst, HoeffdingTree ht) {
00140             if (this.mcCorrectWeight > this.nbCorrectWeight) {
00141                 return this.observedClassDistribution.getArrayCopy();
00142             }
00143             return NaiveBayes.doNaiveBayesPrediction(inst,
00144                     this.observedClassDistribution, this.attributeObservers);
00145         }
00146     }
00147 
00148     public RandomHoeffdingTree() {
00149         this.removePoorAttsOption = null;
00150     }
00151 
00152     @Override
00153     protected LearningNode newLearningNode(double[] initialClassObservations) {
00154         LearningNode ret;
00155         int predictionOption = this.leafpredictionOption.getChosenIndex();
00156         if (predictionOption == 0) { //MC
00157             ret = new RandomLearningNode(initialClassObservations);
00158         } else if (predictionOption == 1) { //NB
00159             ret = new LearningNodeNB(initialClassObservations);
00160         } else { //NBAdaptive
00161             ret = new LearningNodeNBAdaptive(initialClassObservations);
00162         }
00163         return ret;
00164     }
00165 
00166     @Override
00167     public boolean isRandomizable() {
00168         return true;
00169     }
00170 }
 All Classes Namespaces Files Functions Variables Enumerations