weka.classifiers.trees
Class ADTree

java.lang.Object
  |
  +--weka.classifiers.Classifier
        |
        +--weka.classifiers.trees.ADTree

All Implemented Interfaces:

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

public class ADTree

extends Classifier

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

Version:

$Revision: 1.1 $

Author:

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

See Also:

Serialized Form

Field Summary

static int	SEARCHPATH_ALL The search modes
static int	SEARCHPATH_HEAVIEST
static int	SEARCHPATH_RANDOM
static int	SEARCHPATH_ZPURE
static Tag[]	TAGS_SEARCHPATH

Fields inherited from interface weka.core.Drawable

BayesNet, NOT_DRAWABLE, TREE

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.
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() Returns a string describing classifier
java.lang.String	graph() Returns graph describing the tree.
int	graphType() Returns the type of graph this classifier represents.
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.
java.lang.String	numOfBoostingIterationsTipText()
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.

Methods inherited from class weka.classifiers.Classifier

classifyInstance, debugTipText, forName, getDebug, makeCopies, setDebug

Methods inherited from class java.lang.Object

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

Field Detail

SEARCHPATH_ALL

public static final int SEARCHPATH_ALL

The search modes

See Also:

Constant Field Values

SEARCHPATH_HEAVIEST

public static final int SEARCHPATH_HEAVIEST

See Also:

Constant Field Values

SEARCHPATH_ZPURE

public static final int SEARCHPATH_ZPURE

See Also:

Constant Field Values

SEARCHPATH_RANDOM

public static final int SEARCHPATH_RANDOM

See Also:

Constant Field Values

TAGS_SEARCHPATH

public static final Tag[] TAGS_SEARCHPATH

Constructor Detail

ADTree

public ADTree()

Method Detail

globalInfo

public java.lang.String globalInfo()

Returns a string describing classifier

Returns:

a description suitable for displaying in the explorer/experimenter gui

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 Classifier

Parameters:

instance - the instance to be classified

Returns:

the distribution the tree generates for the instance

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

graphType

public int graphType()

Returns the type of graph this classifier represents.

Specified by:

graphType in interface Drawable

Returns:

Drawable.TREE

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

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

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.

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.

listOptions

public java.util.Enumeration listOptions()

Returns an enumeration describing the available options..

Specified by:

listOptions in interface OptionHandler

Overrides:

listOptions in class Classifier

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

Overrides:

setOptions in class Classifier

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

Overrides:

getOptions in class Classifier

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:

additionalMeasureName - 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

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.

Specified by:

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

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