moa.classifiers.trees

Class ASHoeffdingTree

java.lang.Object

moa.AbstractMOAObject

moa.options.AbstractOptionHandler

moa.classifiers.AbstractClassifier

moa.classifiers.trees.HoeffdingTree

moa.classifiers.trees.ASHoeffdingTree

All Implemented Interfaces:

Serializable, Classifier, AWTRenderable, MOAObject, OptionHandler

public class ASHoeffdingTree
extends HoeffdingTree

Adaptive Size Hoeffding Tree used in Bagging using trees of different size. The Adaptive-Size Hoeffding Tree (ASHT) is derived from the Hoeffding Tree algorithm with the following differences:

• it has a maximum number of split nodes, or size
• after one node splits, if the number of split nodes of the ASHT tree is higher than the maximum value, then it deletes some nodes to reduce its size

The intuition behind this method is as follows: smaller trees adapt more quickly to changes, and larger trees do better during periods with no or little change, simply because they were built on more data. Trees limited to size s will be reset about twice as often as trees with a size limit of 2s. This creates a set of different reset-speeds for an ensemble of such trees, and therefore a subset of trees that are a good approximation for the current rate of change. It is important to note that resets will happen all the time, even for stationary datasets, but this behaviour should not have a negative impact on the ensemble’s predictive performance. When the tree size exceeds the maximun size value, there are two different delete options:

• delete the oldest node, the root, and all of its children except the one where the split has been made. After that, the root of the child not deleted becomes the new root
• delete all the nodes of the tree, i.e., restart from a new root.

The maximum allowed size for the n-th ASHT tree is twice the maximum allowed size for the (n-1)-th tree. Moreover, each tree has a weight proportional to the inverse of the square of its error, and it monitors its error with an exponential weighted moving average (EWMA) with alpha = .01. The size of the first tree is 2.

With this new method, it is attempted to improve bagging performance by increasing tree diversity. It has been observed that boosting tends to produce a more diverse set of classifiers than bagging, and this has been cited as a factor in increased performance.
See more details in:

Albert Bifet, Geoff Holmes, Bernhard Pfahringer, Richard Kirkby, and Ricard Gavaldà. New ensemble methods for evolving data streams. In 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009.

The learner must be ASHoeffdingTree, a Hoeffding Tree with a maximum size value.

Example:

OzaBagASHT -l ASHoeffdingTree -s 10 -u -r Parameters:

• Same parameters as OzaBag
• -f : the size of first classifier in the bag.
• -u : Enable weight classifiers
• -r : Reset trees when size is higher than the max

Version:

$Revision: 7 $

Author:

Albert Bifet (abifet at cs dot waikato dot ac dot nz)

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class moa.classifiers.trees.HoeffdingTree

HoeffdingTree.ActiveLearningNode, HoeffdingTree.FoundNode, HoeffdingTree.InactiveLearningNode, HoeffdingTree.LearningNode, HoeffdingTree.LearningNodeNB, HoeffdingTree.LearningNodeNBAdaptive, HoeffdingTree.Node, HoeffdingTree.SplitNode

Field Summary

Fields

Modifier and Type	Field and Description
protected int	maxSize
protected boolean	resetTree

Fields inherited from class moa.classifiers.trees.HoeffdingTree

activeLeafByteSizeEstimate, activeLeafNodeCount, binarySplitsOption, byteSizeEstimateOverheadFraction, decisionNodeCount, gracePeriodOption, growthAllowed, inactiveLeafByteSizeEstimate, inactiveLeafNodeCount, leafpredictionOption, maxByteSizeOption, memoryEstimatePeriodOption, nbThresholdOption, nominalEstimatorOption, noPrePruneOption, numericEstimatorOption, removePoorAttsOption, splitConfidenceOption, splitCriterionOption, stopMemManagementOption, tieThresholdOption, treeRoot

Fields inherited from class moa.classifiers.AbstractClassifier

classifierRandom, modelContext, randomSeed, randomSeedOption, trainingWeightSeenByModel

Fields inherited from class moa.options.AbstractOptionHandler

classOptionNamesToPreparedObjects, options

Constructor Summary

Constructors

Constructor and Description
ASHoeffdingTree()

Method Summary

Methods

Modifier and Type	Method and Description
void	deleteNode(HoeffdingTree.Node node, int childIndex)
String	getPurposeString() Gets the purpose of this object
void	resetLearningImpl() Resets this classifier.
void	resizeTree(HoeffdingTree.Node node, int childIndex)
void	setMaxSize(int mSize)
void	setResetTree()
void	trainOnInstanceImpl(weka.core.Instance inst) Trains this classifier incrementally using the given instance. The reason for ...Impl methods: ease programmer burden by not requiring them to remember calls to super in overridden methods.

Methods inherited from class moa.classifiers.trees.HoeffdingTree

activateLearningNode, attemptToSplit, calcByteSize, computeHoeffdingBound, deactivateAllLeaves, deactivateLearningNode, enforceTrackerLimit, estimateModelByteSizes, findLearningNodes, findLearningNodes, getModelDescription, getModelMeasurementsImpl, getVotesForInstance, isRandomizable, measureByteSize, measureTreeDepth, newLearningNode, newLearningNode, newNominalClassObserver, newNumericClassObserver, newSplitNode, newSplitNode

Methods inherited from class moa.classifiers.AbstractClassifier

contextIsCompatible, copy, correctlyClassifies, getAttributeNameString, getAWTRenderer, getClassLabelString, getClassNameString, getDescription, getModelContext, getModelMeasurements, getNominalValueString, getSubClassifiers, modelAttIndexToInstanceAttIndex, modelAttIndexToInstanceAttIndex, prepareForUseImpl, resetLearning, setModelContext, setRandomSeed, trainingHasStarted, trainingWeightSeenByModel, trainOnInstance

Methods inherited from class moa.options.AbstractOptionHandler

discoverOptionsViaReflection, getCLICreationString, getOptions, getPreparedClassOption, getPreparedClassOption, prepareClassOptions, prepareForUse, prepareForUse

Methods inherited from class moa.AbstractMOAObject

copy, measureByteSize, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface moa.options.OptionHandler

getCLICreationString, getOptions, prepareForUse, prepareForUse

Field Detail

maxSize

protected int maxSize

resetTree

protected boolean resetTree

Constructor Detail

ASHoeffdingTree

public ASHoeffdingTree()

Method Detail

getPurposeString

public String getPurposeString()

Description copied from interface: OptionHandler

Gets the purpose of this object

Specified by:

getPurposeString in interface OptionHandler

Overrides:

getPurposeString in class HoeffdingTree

Returns:

the string with the purpose of this object

resetLearningImpl

public void resetLearningImpl()

Description copied from class: AbstractClassifier

Resets this classifier. It must be similar to starting a new classifier from scratch.

The reason for ...Impl methods: ease programmer burden by not requiring them to remember calls to super in overridden methods. Note that this will produce compiler errors if not overridden.

Overrides:

resetLearningImpl in class HoeffdingTree

trainOnInstanceImpl

public void trainOnInstanceImpl(weka.core.Instance inst)

Description copied from class: AbstractClassifier

Trains this classifier incrementally using the given instance.

The reason for ...Impl methods: ease programmer burden by not requiring them to remember calls to super in overridden methods. Note that this will produce compiler errors if not overridden.

Overrides:

trainOnInstanceImpl in class HoeffdingTree

Parameters:

inst - the instance to be used for training

setMaxSize

public void setMaxSize(int mSize)

setResetTree

public void setResetTree()

deleteNode

public void deleteNode(HoeffdingTree.Node node,
              int childIndex)

resizeTree

public void resizeTree(HoeffdingTree.Node node,
              int childIndex)