weka.classifiers.adtree
Class ADTree

java.lang.Object
  |
  +--weka.classifiers.Classifier
        |
        +--weka.classifiers.DistributionClassifier
              |
              +--weka.classifiers.adtree.ADTree

All Implemented Interfaces:

AdditionalMeasureProducer, java.lang.Cloneable, Drawable, IterativeClassifier, OptionHandler, java.io.Serializable, WeightedInstancesHandler

public class ADTree

extends DistributionClassifier

implements OptionHandler, Drawable, AdditionalMeasureProducer, WeightedInstancesHandler, IterativeClassifier

Class for generating an alternating decision tree. The basic algorithm is based on:

Freund, Y., Mason, L.: The alternating decision tree learning algorithm. Proceeding of the Sixteenth International Conference on Machine Learning, Bled, Slovenia, (1999) 124-133.

This version currently only supports two-class problems. The number of boosting iterations needs to be manually tuned to suit the dataset and the desired complexity/accuracy tradeoff. Induction of the trees has been optimized, and heuristic search methods have been introduced to speed learning.

Valid options are:

-B num
Set the number of boosting iterations (default 10)

-E num
Set the nodes to expand: -3(all), -2(weight), -1(z_pure), >=0 seed for random walk (default -3)

-D
Save the instance data with the model

Author:

Richard Kirkby (rkirkby@cs.waikato.ac.nz), Bernhard Pfahringer (bernhard@cs.waikato.ac.nz)

See Also:

Serialized Form

Field Summary

protected int	m_boostingIterations Option - the number of boosting iterations o perform
protected int	m_examplesCounted Statistics - the number of instances processed during search
protected int	m_lastAddedSplitNum The number of the last splitter added to the tree
protected ReferenceInstances	m_negTrainInstances The training instances with negative class - referencing the training dataset
protected int	m_nodesExpanded Statistics - the number of prediction nodes investigated during search
protected int[]	m_nominalAttIndices An array containing the inidices to the nominal attributes in the data
protected int[]	m_numericAttIndices An array containing the inidices to the numeric attributes in the data
protected ReferenceInstances	m_posTrainInstances The training instances with positive class - referencing the training dataset
protected java.util.Random	m_random The random number generator - used for the random search heuristic
protected int	m_randomSeed Option - the seed to use for a random search
protected PredictionNode	m_root The root of the tree
protected boolean	m_saveInstanceData Option - whether the tree should remember the instance data
protected PredictionNode	m_search_bestInsertionNode The best node to insert under, as found so far by the latest search
protected Instances	m_search_bestPathNegInstances The negative instances that apply to the best path found so far
protected Instances	m_search_bestPathPosInstances The positive instances that apply to the best path found so far
protected Splitter	m_search_bestSplitter The best splitter to insert, as found so far by the latest search
protected double	m_search_smallestZ The smallest Z value found so far by the latest search
protected int	m_searchPath Option - the search mode
protected Instances	m_trainInstances The instances used to train the tree
protected double	m_trainTotalWeight The total weight of the instances - used to speed Z calculations
static int	SEARCHPATH_ALL The search modes
static int	SEARCHPATH_HEAVIEST
static int	SEARCHPATH_RANDOM
static int	SEARCHPATH_ZPURE
static Tag[]	TAGS_SEARCHPATH

Constructor Summary

ADTree()

Method Summary

void	boost() Performs a single boosting iteration, using two-class optimized method.
void	buildClassifier(Instances instances) Builds a classifier for a set of instances.
java.lang.Object	clone() Creates a clone that is identical to the current tree, but is independent.
double[]	distributionForInstance(Instance instance) Returns the class probability distribution for an instance.
void	done() Frees memory that is no longer needed for a final model - will no longer be able to increment the classifier after calling this.
java.util.Enumeration	enumerateMeasures() Returns an enumeration of the additional measure names.
double	getMeasure(java.lang.String additionalMeasureName) Returns the value of the named measure.
int	getNumOfBoostingIterations() Gets the number of boosting iterations.
java.lang.String[]	getOptions() Gets the current settings of ADTree.
protected int	getRandom(int max) Gets the next random value.
int	getRandomSeed() Gets random seed for a random walk.
boolean	getSaveInstanceData() Gets whether the tree is to save instance data.
SelectedTag	getSearchPath() Gets the method of searching the tree for a new insertion.
java.lang.String	globalInfo()
java.lang.String	graph() Returns graph describing the tree.
protected void	graphTraverse(PredictionNode currentNode, java.lang.StringBuffer text, int splitOrder, int predOrder, Instances instances) Traverses the tree, graphing each node.
void	initClassifier(Instances instances) Sets up the tree ready to be trained, using two-class optimized method.
java.lang.String	legend() Returns the legend of the tree, describing how results are to be interpreted.
java.util.Enumeration	listOptions() Returns an enumeration describing the available options.
static void	main(java.lang.String[] argv) Main method for testing this class.
double	measureExamplesProcessed() Returns the number of examples "counted".
double	measureNodesExpanded() Returns the number of nodes expanded.
double	measureNumLeaves() Calls measure function for leaf size - the number of prediction nodes.
double	measureNumPredictionLeaves() Calls measure function for prediction leaf size - the number of prediction nodes without children.
double	measureTreeSize() Calls measure function for tree size - the total number of nodes.
void	merge(ADTree mergeWith) Merges two trees together.
void	next(int iteration) Performs one iteration.
int	nextSplitAddedOrder() Returns the next number in the order that splitter nodes have been added to the tree, and records that a new splitter has been added.
protected int	numOfAllNodes(PredictionNode root) Returns the total number of nodes in a tree.
java.lang.String	numOfBoostingIterationsTipText()
protected int	numOfPredictionLeafNodes(PredictionNode root) Returns the number of leaf nodes in a tree - prediction nodes without children.
protected int	numOfPredictionNodes(PredictionNode root) Returns the number of prediction nodes in a tree.
protected double	predictionValueForInstance(Instance inst, PredictionNode currentNode, double currentValue) Returns the class prediction value (vote) for an instance.
java.lang.String	randomSeedTipText()
java.lang.String	saveInstanceDataTipText()
java.lang.String	searchPathTipText()
void	setNumOfBoostingIterations(int b) Sets the number of boosting iterations.
void	setOptions(java.lang.String[] options) Parses a given list of options.
void	setRandomSeed(int seed) Sets random seed for a random walk.
void	setSaveInstanceData(boolean v) Sets whether the tree is to save instance data.
void	setSearchPath(SelectedTag newMethod) Sets the method of searching the tree for a new insertion.
java.lang.String	toString() Returns a description of the classifier.
protected java.lang.String	toString(PredictionNode currentNode, int level) Traverses the tree, forming a string that describes it.

Methods inherited from class weka.classifiers.DistributionClassifier

classifyInstance

Methods inherited from class weka.classifiers.Classifier

forName, makeCopies

Methods inherited from class java.lang.Object

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

Field Detail

SEARCHPATH_ALL

public static final int SEARCHPATH_ALL

The search modes

SEARCHPATH_HEAVIEST

public static final int SEARCHPATH_HEAVIEST

SEARCHPATH_ZPURE

public static final int SEARCHPATH_ZPURE

SEARCHPATH_RANDOM

public static final int SEARCHPATH_RANDOM

TAGS_SEARCHPATH

public static final Tag[] TAGS_SEARCHPATH

m_trainInstances

protected Instances m_trainInstances

The instances used to train the tree

m_root

protected PredictionNode m_root

The root of the tree

m_random

protected java.util.Random m_random

The random number generator - used for the random search heuristic

m_lastAddedSplitNum

protected int m_lastAddedSplitNum

The number of the last splitter added to the tree

m_numericAttIndices

protected int[] m_numericAttIndices

An array containing the inidices to the numeric attributes in the data

m_nominalAttIndices

protected int[] m_nominalAttIndices

An array containing the inidices to the nominal attributes in the data

m_trainTotalWeight

protected double m_trainTotalWeight

The total weight of the instances - used to speed Z calculations

m_posTrainInstances

protected ReferenceInstances m_posTrainInstances

The training instances with positive class - referencing the training dataset

m_negTrainInstances

protected ReferenceInstances m_negTrainInstances

The training instances with negative class - referencing the training dataset

m_search_bestInsertionNode

protected PredictionNode m_search_bestInsertionNode

The best node to insert under, as found so far by the latest search

m_search_bestSplitter

protected Splitter m_search_bestSplitter

The best splitter to insert, as found so far by the latest search

m_search_smallestZ

protected double m_search_smallestZ

The smallest Z value found so far by the latest search

m_search_bestPathPosInstances

protected Instances m_search_bestPathPosInstances

The positive instances that apply to the best path found so far

m_search_bestPathNegInstances

protected Instances m_search_bestPathNegInstances

The negative instances that apply to the best path found so far

m_nodesExpanded

protected int m_nodesExpanded

Statistics - the number of prediction nodes investigated during search

m_examplesCounted

protected int m_examplesCounted

Statistics - the number of instances processed during search

m_boostingIterations

protected int m_boostingIterations

Option - the number of boosting iterations o perform

m_searchPath

protected int m_searchPath

Option - the search mode

m_randomSeed

protected int m_randomSeed

Option - the seed to use for a random search

m_saveInstanceData

protected boolean m_saveInstanceData

Option - whether the tree should remember the instance data

Constructor Detail

ADTree

public ADTree()

Method Detail

initClassifier

public void initClassifier(Instances instances)
                    throws java.lang.Exception

Sets up the tree ready to be trained, using two-class optimized method.

Specified by:

initClassifier in interface IterativeClassifier

Parameters:

instances - the instances to train the tree with

Throws:

java.lang.Exception - if training data is unsuitable

next

public void next(int iteration)
          throws java.lang.Exception

Performs one iteration.

Specified by:

next in interface IterativeClassifier

Parameters:

iteration - the index of the current iteration (0-based)

Throws:

java.lang.Exception - if this iteration fails

boost

public void boost()
           throws java.lang.Exception

Performs a single boosting iteration, using two-class optimized method. Will add a new splitter node and two prediction nodes to the tree (unless merging takes place).

Throws:

java.lang.Exception - if try to boost without setting up tree first or there are no instances to train with

distributionForInstance

public double[] distributionForInstance(Instance instance)

Returns the class probability distribution for an instance.

Overrides:

distributionForInstance in class DistributionClassifier

Parameters:

instance - the instance to be classified

Returns:

the distribution the tree generates for the instance

predictionValueForInstance

protected double predictionValueForInstance(Instance inst,
                                            PredictionNode currentNode,
                                            double currentValue)

Returns the class prediction value (vote) for an instance.

Parameters:

inst - the instance

currentNode - the root of the tree to get the values from

currentValue - the current value before adding the value contained in the subtree

Returns:

the class prediction value (vote)

toString

public java.lang.String toString()

Returns a description of the classifier.

Overrides:

toString in class java.lang.Object

Returns:

a string containing a description of the classifier

toString

protected java.lang.String toString(PredictionNode currentNode,
                                    int level)

Traverses the tree, forming a string that describes it.

Parameters:

currentNode - the current node under investigation

level - the current level in the tree

Returns:

the string describing the subtree

graph

public java.lang.String graph()
                       throws java.lang.Exception

Returns graph describing the tree.

Specified by:

graph in interface Drawable

Returns:

the graph of the tree in dotty format

Throws:

java.lang.Exception - if something goes wrong

graphTraverse

protected void graphTraverse(PredictionNode currentNode,
                             java.lang.StringBuffer text,
                             int splitOrder,
                             int predOrder,
                             Instances instances)
                      throws java.lang.Exception

Traverses the tree, graphing each node.

Parameters:

currentNode - the currentNode under investigation

text - the string built so far

splitOrder - the order the parent splitter was added to the tree

predOrder - the order this predictor was added to the split

Throws:

java.lang.Exception - if something goes wrong

legend

public java.lang.String legend()

Returns the legend of the tree, describing how results are to be interpreted.

Returns:

a string containing the legend of the classifier

globalInfo

public java.lang.String globalInfo()

Returns:

a description of the classifier suitable for displaying in the explorer/experimenter gui

numOfBoostingIterationsTipText

public java.lang.String numOfBoostingIterationsTipText()

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

getNumOfBoostingIterations

public int getNumOfBoostingIterations()

Gets the number of boosting iterations.

Returns:

the number of boosting iterations

setNumOfBoostingIterations

public void setNumOfBoostingIterations(int b)

Sets the number of boosting iterations.

Parameters:

b - the number of boosting iterations to use

searchPathTipText

public java.lang.String searchPathTipText()

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

getSearchPath

public SelectedTag getSearchPath()

Gets the method of searching the tree for a new insertion. Will be one of SEARCHPATH_ALL, SEARCHPATH_HEAVIEST, SEARCHPATH_ZPURE, SEARCHPATH_RANDOM.

Returns:

the tree searching mode

setSearchPath

public void setSearchPath(SelectedTag newMethod)

Sets the method of searching the tree for a new insertion. Will be one of SEARCHPATH_ALL, SEARCHPATH_HEAVIEST, SEARCHPATH_ZPURE, SEARCHPATH_RANDOM.

Parameters:

newMethod - the new tree searching mode

randomSeedTipText

public java.lang.String randomSeedTipText()

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

getRandomSeed

public int getRandomSeed()

Gets random seed for a random walk.

Returns:

the random seed

setRandomSeed

public void setRandomSeed(int seed)

Sets random seed for a random walk.

Parameters:

s - the random seed

saveInstanceDataTipText

public java.lang.String saveInstanceDataTipText()

Returns:

tip text for this property suitable for displaying in the explorer/experimenter gui

getSaveInstanceData

public boolean getSaveInstanceData()

Gets whether the tree is to save instance data.

Returns:

the random seed

setSaveInstanceData

public void setSaveInstanceData(boolean v)

Sets whether the tree is to save instance data.

Parameters:

s - the random seed

listOptions

public java.util.Enumeration listOptions()

Returns an enumeration describing the available options.

Specified by:

listOptions in interface OptionHandler

Returns:

an enumeration of all the available options

setOptions

public void setOptions(java.lang.String[] options)
                throws java.lang.Exception

Parses a given list of options. Valid options are:

-B num
Set the number of boosting iterations (default 10)

-E num
Set the nodes to expand: -3(all), -2(weight), -1(z_pure), >=0 seed for random walk (default -3)

-D
Save the instance data with the model

Specified by:

setOptions in interface OptionHandler

Parameters:

options - the list of options as an array of strings

Throws:

java.lang.Exception - if an option is not supported

getOptions

public java.lang.String[] getOptions()

Gets the current settings of ADTree.

Specified by:

getOptions in interface OptionHandler

Returns:

an array of strings suitable for passing to setOptions()

measureTreeSize

public double measureTreeSize()

Calls measure function for tree size - the total number of nodes.

Returns:

the tree size

measureNumLeaves

public double measureNumLeaves()

Calls measure function for leaf size - the number of prediction nodes.

Returns:

the leaf size

measureNumPredictionLeaves

public double measureNumPredictionLeaves()

Calls measure function for prediction leaf size - the number of prediction nodes without children.

Returns:

the leaf size

measureNodesExpanded

public double measureNodesExpanded()

Returns the number of nodes expanded.

Returns:

the number of nodes expanded during search

measureExamplesProcessed

public double measureExamplesProcessed()

Returns the number of examples "counted".

Returns:

the number of nodes processed during search

enumerateMeasures

public java.util.Enumeration enumerateMeasures()

Returns an enumeration of the additional measure names.

Specified by:

enumerateMeasures in interface AdditionalMeasureProducer

Returns:

an enumeration of the measure names

getMeasure

public double getMeasure(java.lang.String additionalMeasureName)

Returns the value of the named measure.

Specified by:

getMeasure in interface AdditionalMeasureProducer

Parameters:

measureName - the name of the measure to query for its value

Returns:

the value of the named measure

Throws:

java.lang.IllegalArgumentException - if the named measure is not supported

numOfAllNodes

protected int numOfAllNodes(PredictionNode root)

Returns the total number of nodes in a tree.

Parameters:

root - the root of the tree being measured

Returns:

tree size in number of splitter + prediction nodes

numOfPredictionNodes

protected int numOfPredictionNodes(PredictionNode root)

Returns the number of prediction nodes in a tree.

Parameters:

root - the root of the tree being measured

Returns:

tree size in number of prediction nodes

numOfPredictionLeafNodes

protected int numOfPredictionLeafNodes(PredictionNode root)

Returns the number of leaf nodes in a tree - prediction nodes without children.

Parameters:

root - the root of the tree being measured

Returns:

tree leaf size in number of prediction nodes

getRandom

protected int getRandom(int max)

Gets the next random value.

Parameters:

max - the maximum value (+1) to be returned

Returns:

the next random value (between 0 and max-1)

nextSplitAddedOrder

public int nextSplitAddedOrder()

Returns the next number in the order that splitter nodes have been added to the tree, and records that a new splitter has been added.

Returns:

the next number in the order

buildClassifier

public void buildClassifier(Instances instances)
                     throws java.lang.Exception

Builds a classifier for a set of instances.

Overrides:

buildClassifier in class Classifier

Parameters:

instances - the instances to train the classifier with

Throws:

java.lang.Exception - if something goes wrong

done

public void done()

Frees memory that is no longer needed for a final model - will no longer be able to increment the classifier after calling this.

Specified by:

done in interface IterativeClassifier

Following copied from interface: weka.classifiers.IterativeClassifier

Throws:

java.lang.Exception - if cleanup fails

clone

public java.lang.Object clone()

Creates a clone that is identical to the current tree, but is independent. Deep copies the essential elements such as the tree nodes, and the instances (because the weights change.) Reference copies several elements such as the potential splitter sets, assuming that such elements should never differ between clones.

Specified by:

clone in interface IterativeClassifier

Overrides:

clone in class java.lang.Object

Returns:

the clone

merge

public void merge(ADTree mergeWith)
           throws java.lang.Exception

Merges two trees together. Modifies the tree being acted on, leaving tree passed as a parameter untouched (cloned). Does not check to see whether training instances are compatible - strange things could occur if they are not.

Parameters:

mergeWith - the tree to merge with

Throws:

java.lang.Exception - if merge could not be performed

main

public static void main(java.lang.String[] argv)

Main method for testing this class.

Parameters:

argv - the options