Class ADTree

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable, IterativeClassifier, AdditionalMeasureProducer, CapabilitiesHandler, Drawable, OptionHandler, RevisionHandler, TechnicalInformationHandler, WeightedInstancesHandler

    public class ADTree
    extends Classifier
    implements OptionHandler, Drawable, AdditionalMeasureProducer, WeightedInstancesHandler, IterativeClassifier, TechnicalInformationHandler
    Class for generating an alternating decision tree. The basic algorithm is based on:

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

    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.

    BibTeX:

     @inproceedings{Freund1999,
        address = {Bled, Slovenia},
        author = {Freund, Y. and Mason, L.},
        booktitle = {Proceeding of the Sixteenth International Conference on Machine Learning},
        pages = {124-133},
        title = {The alternating decision tree learning algorithm},
        year = {1999}
     }
     

    Valid options are:

     -B <number of boosting iterations>
      Number of boosting iterations.
      (Default = 10)
     -E <-3|-2|-1|>=0>
      Expand nodes: -3(all), -2(weight), -1(z_pure), >=0 seed for random walk
      (Default = -3)
     -D
      Save the instance data with the model
    Version:
    $Revision: 10290 $
    Author:
    Richard Kirkby (rkirkby@cs.waikato.ac.nz), Bernhard Pfahringer (bernhard@cs.waikato.ac.nz)
    See Also:
    Serialized Form
    • Field Detail

      • SEARCHPATH_ALL

        public static final int SEARCHPATH_ALL
        search mode: Expand all paths
        See Also:
        Constant Field Values
      • SEARCHPATH_HEAVIEST

        public static final int SEARCHPATH_HEAVIEST
        search mode: Expand the heaviest path
        See Also:
        Constant Field Values
      • SEARCHPATH_ZPURE

        public static final int SEARCHPATH_ZPURE
        search mode: Expand the best z-pure path
        See Also:
        Constant Field Values
      • SEARCHPATH_RANDOM

        public static final int SEARCHPATH_RANDOM
        search mode: Expand a random path
        See Also:
        Constant Field Values
      • TAGS_SEARCHPATH

        public static final Tag[] TAGS_SEARCHPATH
        The search modes
    • 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
      • getTechnicalInformation

        public TechnicalInformation getTechnicalInformation()
        Returns an instance of a TechnicalInformation object, containing detailed information about the technical background of this class, e.g., paper reference or book this class is based on.
        Specified by:
        getTechnicalInformation in interface TechnicalInformationHandler
        Returns:
        the technical information about this class
      • 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.
        Parameters:
        seed - 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:
        v - true then the tree saves 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
        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