MOA 12.03
Real Time Analytics for Data Streams
ASHoeffdingTree.java
Go to the documentation of this file.
00001 /*
00002  *    ASHoeffdingTree.java
00003  *    Copyright (C) 2008 University of Waikato, Hamilton, New Zealand
00004  *    @author Albert Bifet (abifet at cs dot waikato dot ac dot 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 weka.core.Instance;
00023 
00078 public class ASHoeffdingTree extends HoeffdingTree {
00079 
00080     private static final long serialVersionUID = 1L;
00081 
00082     @Override
00083     public String getPurposeString() {
00084         return "Adaptive Size Hoeffding Tree used in Bagging using trees of different size.";
00085     }    
00086     
00087     protected int maxSize = 10000; //EXTENSION TO ASHT
00088 
00089     protected boolean resetTree = false;
00090 
00091     @Override
00092     public void resetLearningImpl() {
00093         this.treeRoot = null;
00094         this.decisionNodeCount = 0;
00095         this.activeLeafNodeCount = 0;
00096         this.inactiveLeafNodeCount = 0;
00097         this.inactiveLeafByteSizeEstimate = 0.0;
00098         this.activeLeafByteSizeEstimate = 0.0;
00099         this.byteSizeEstimateOverheadFraction = 1.0;
00100         this.growthAllowed = true;
00101     }
00102 
00103     @Override
00104     public void trainOnInstanceImpl(Instance inst) {
00105         if (this.treeRoot == null) {
00106             this.treeRoot = newLearningNode();
00107             this.activeLeafNodeCount = 1;
00108         }
00109         FoundNode foundNode = this.treeRoot.filterInstanceToLeaf(inst, null, -1);
00110         Node leafNode = foundNode.node;
00111         if (leafNode == null) {
00112             leafNode = newLearningNode();
00113             foundNode.parent.setChild(foundNode.parentBranch, leafNode);
00114             this.activeLeafNodeCount++;
00115         }
00116         if (leafNode instanceof LearningNode) {
00117             LearningNode learningNode = (LearningNode) leafNode;
00118             learningNode.learnFromInstance(inst, this);
00119             if (this.growthAllowed
00120                     && (learningNode instanceof ActiveLearningNode)) {
00121                 ActiveLearningNode activeLearningNode = (ActiveLearningNode) learningNode;
00122                 double weightSeen = activeLearningNode.getWeightSeen();
00123                 if (weightSeen
00124                         - activeLearningNode.getWeightSeenAtLastSplitEvaluation() >= this.gracePeriodOption.getValue()) {
00125                     attemptToSplit(activeLearningNode, foundNode.parent,
00126                             foundNode.parentBranch);
00127                     //EXTENSION TO ASHT
00128                     // if size too big, resize tree ONLY Split Nodes
00129                     while (this.decisionNodeCount >= this.maxSize && this.treeRoot instanceof SplitNode) {
00130                         if (this.resetTree == false) {
00131                             resizeTree(this.treeRoot, ((SplitNode) this.treeRoot).instanceChildIndex(inst));
00132                             this.treeRoot = ((SplitNode) this.treeRoot).getChild(((SplitNode) this.treeRoot).instanceChildIndex(inst));
00133                         } else {
00134                             resetLearningImpl();
00135                         }
00136                     }
00137                     activeLearningNode.setWeightSeenAtLastSplitEvaluation(weightSeen);
00138                 }
00139             }
00140         }
00141         if (this.trainingWeightSeenByModel
00142                 % this.memoryEstimatePeriodOption.getValue() == 0) {
00143             estimateModelByteSizes();
00144         }
00145     }
00146 
00147     //EXTENSION TO ASHT
00148     public void setMaxSize(int mSize) {
00149         this.maxSize = mSize;
00150     }
00151 
00152     public void setResetTree() {
00153         this.resetTree = true;
00154     }
00155 
00156     public void deleteNode(Node node, int childIndex) {
00157         Node child = ((SplitNode) node).getChild(childIndex);
00158         //if (child != null) {
00159         //}
00160         if (child instanceof SplitNode) {
00161             for (int branch = 0; branch < ((SplitNode) child).numChildren(); branch++) {
00162                 deleteNode(child, branch);
00163             }
00164             this.decisionNodeCount--;
00165         } else if (child instanceof InactiveLearningNode) {
00166             this.inactiveLeafNodeCount--;
00167         } else if (child instanceof ActiveLearningNode) {
00168             this.activeLeafNodeCount--;
00169         }
00170         child = null;
00171     }
00172 
00173     public void resizeTree(Node node, int childIndex) {
00174         //Assume that this is root node
00175         if (node instanceof SplitNode) {
00176             for (int branch = 0; branch < ((SplitNode) node).numChildren(); branch++) {
00177                 if (branch != childIndex) {
00178                     deleteNode(node, branch);
00179                 }
00180             }
00181         }
00182     }
00183 }
 All Classes Namespaces Files Functions Variables Enumerations