jsat.classifiers.trees

Class DecisionTree

java.lang.Object

jsat.classifiers.trees.DecisionTree

All Implemented Interfaces:

Serializable, Cloneable, Classifier, TreeLearner, Parameterized, Regressor

Direct Known Subclasses:

RandomDecisionTree

public class DecisionTree
extends Object
implements Classifier, Regressor, Parameterized, TreeLearner

Creates a decision tree from DecisionStumps. How this tree performs is controlled by pruning method selected, and the methods used in the stump.
A Decision Tree supports missing values in training and prediction.

Author:

Edward Raff

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	DecisionTree.Node

Constructor Summary

Constructors

Modifier	Constructor and Description
	DecisionTree() Creates a Decision Tree that uses TreePruner.PruningMethod.REDUCED_ERROR pruning on a held out 10% of the data.
protected	DecisionTree(DecisionTree toCopy) Copy constructor
	DecisionTree(int maxDepth) Creates a Decision Tree that does not do any pruning, and is built out only to the specified depth
	DecisionTree(int maxDepth, int minSamples, TreePruner.PruningMethod pruningMethod, double testProportion) Creates a new decision tree classifier

Method Summary

Modifier and Type	Method and Description
CategoricalResults	classify(DataPoint data) Performs classification on the given data point.
DecisionTree	clone()
static DecisionTree	getC45Tree() Returns a Decision Tree with settings initialized so that its behavior is approximately that of the C4.5 decision tree algorithm when used on classification data.
ImpurityScore.ImpurityMeasure	getGainMethod()
int	getMaxDepth() The maximum depth that this classifier may build trees to.
int	getMinResultSplitSize() Returns the minimum result split size that may be considered for use as the attribute to split on.
int	getMinSamples() The minimum number of samples needed at each step in order to continue branching
Parameter	getParameter(String paramName) Returns the parameter with the given name.
List<Parameter>	getParameters() Returns the list of parameters that can be altered for this learner.
TreePruner.PruningMethod	getPruningMethod() Returns the method of pruning used after tree construction
double	getTestProportion() Returns the proportion of the training set that is put aside to perform pruning with
TreeNodeVisitor	getTreeNodeVisitor() Obtains a node visitor for the tree learner that can be used to traverse and predict from the learned tree
protected DecisionTree.Node	makeNodeC(List<DataPointPair<Integer>> dataPoints, Set<Integer> options, int depth, ExecutorService threadPool, ModifiableCountDownLatch mcdl) Makes a new node for classification
protected DecisionTree.Node	makeNodeR(List<DataPointPair<Double>> dataPoints, Set<Integer> options, int depth, ExecutorService threadPool, ModifiableCountDownLatch mcdl) Makes a new node for regression
double	regress(DataPoint data)
void	setGainMethod(ImpurityScore.ImpurityMeasure gainMethod)
void	setMaxDepth(int maxDepth) Sets the maximum depth that this classifier may build trees to.
void	setMinResultSplitSize(int size) When a split is made, it may be that outliers cause the split to segregate a minority of points from the majority.
void	setMinSamples(int minSamples) Sets the minimum number of samples needed at each step in order to continue branching
void	setPruningMethod(TreePruner.PruningMethod pruningMethod) Sets the method of pruning that will be used after tree construction
void	setTestProportion(double testProportion) Sets the proportion of the training set that is put aside to perform pruning with.
boolean	supportsWeightedData() Indicates whether the model knows how to train using weighted data points.
void	train(RegressionDataSet dataSet)
void	train(RegressionDataSet dataSet, ExecutorService threadPool)
void	train(RegressionDataSet dataSet, Set<Integer> options)
void	train(RegressionDataSet dataSet, Set<Integer> options, ExecutorService threadPool)
void	trainC(ClassificationDataSet dataSet) Trains the classifier and constructs a model for classification using the given data set.
void	trainC(ClassificationDataSet dataSet, ExecutorService threadPool) Trains the classifier and constructs a model for classification using the given data set.
void	trainC(ClassificationDataSet dataSet, Set<Integer> options)
protected void	trainC(ClassificationDataSet dataSet, Set<Integer> options, ExecutorService threadPool) Performs exactly the same as trainC(jsat.classifiers.ClassificationDataSet, java.util.concurrent.ExecutorService), but the user can specify a subset of the features to be considered.

Methods inherited from class java.lang.Object

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

Constructor Detail

DecisionTree

public DecisionTree()

Creates a Decision Tree that uses TreePruner.PruningMethod.REDUCED_ERROR pruning on a held out 10% of the data.

DecisionTree

public DecisionTree(int maxDepth)

Creates a Decision Tree that does not do any pruning, and is built out only to the specified depth

Parameters:

maxDepth -

DecisionTree

public DecisionTree(int maxDepth,
                    int minSamples,
                    TreePruner.PruningMethod pruningMethod,
                    double testProportion)

Creates a new decision tree classifier

Parameters:

maxDepth - the maximum depth of the tree to create

minSamples - the minimum number of samples needed to continue branching

pruningMethod - the method of pruning to use after construction

testProportion - the proportion of the data set to put aside to use for pruning

DecisionTree

protected DecisionTree(DecisionTree toCopy)

Copy constructor

Parameters:

toCopy - the object to copy

Method Detail

regress

public double regress(DataPoint data)

Specified by:

regress in interface Regressor

train

public void train(RegressionDataSet dataSet,
                  ExecutorService threadPool)

Specified by:

train in interface Regressor

train

public void train(RegressionDataSet dataSet,
                  Set<Integer> options)

train

public void train(RegressionDataSet dataSet,
                  Set<Integer> options,
                  ExecutorService threadPool)

train

public void train(RegressionDataSet dataSet)

Specified by:

train in interface Regressor

getC45Tree

public static DecisionTree getC45Tree()

Returns a Decision Tree with settings initialized so that its behavior is approximately that of the C4.5 decision tree algorithm when used on classification data. The exact behavior not identical, and certain base cases may not behave in the exact same manner. However, it uses all of the same general algorithms.

The returned tree does not perform or support

• discrete attribute grouping
• windowing
• subsidiary cutpoints (soft boundaries)

Returns:

a decision tree that will behave in a manner similar to C4.5

setGainMethod

public void setGainMethod(ImpurityScore.ImpurityMeasure gainMethod)

getGainMethod

public ImpurityScore.ImpurityMeasure getGainMethod()

setMinResultSplitSize

public void setMinResultSplitSize(int size)

When a split is made, it may be that outliers cause the split to segregate a minority of points from the majority. The min result split size parameter specifies the minimum allowable number of points to end up in one of the splits for it to be admisible for consideration.

Parameters:

size - the minimum result split size to use

getMinResultSplitSize

public int getMinResultSplitSize()

Returns the minimum result split size that may be considered for use as the attribute to split on.

Returns:

the minimum result split size in use

setMaxDepth

public void setMaxDepth(int maxDepth)

Sets the maximum depth that this classifier may build trees to.

Parameters:

maxDepth - the maximum depth of the trained tree

getMaxDepth

public int getMaxDepth()

The maximum depth that this classifier may build trees to.

Returns:

the maximum depth that this classifier may build trees to.

setMinSamples

public void setMinSamples(int minSamples)

Sets the minimum number of samples needed at each step in order to continue branching

Parameters:

minSamples - the minimum number of samples needed to branch

getMinSamples

public int getMinSamples()

The minimum number of samples needed at each step in order to continue branching

Returns:

the minimum number of samples needed at each step in order to continue branching

setPruningMethod

public void setPruningMethod(TreePruner.PruningMethod pruningMethod)

Sets the method of pruning that will be used after tree construction

Parameters:

pruningMethod - the method of pruning that will be used after tree construction

See Also:

TreePruner.PruningMethod

getPruningMethod

public TreePruner.PruningMethod getPruningMethod()

Returns the method of pruning used after tree construction

Returns:

the method of pruning used after tree construction

getTestProportion

public double getTestProportion()

Returns the proportion of the training set that is put aside to perform pruning with

Returns:

the proportion of the training set that is put aside to perform pruning with

setTestProportion

public void setTestProportion(double testProportion)

Sets the proportion of the training set that is put aside to perform pruning with.
NOTE: The values 0 and 1 are special cases.
0 indicates that no pruning will occur regardless of the set pruning method
1 indicates that the training set will be used as the testing set. This is valid for some pruning methods.

Parameters:

testProportion - the proportion, must be in the range [0, 1]

classify

public CategoricalResults classify(DataPoint data)

Description copied from interface: Classifier

Performs classification on the given data point.

Specified by:

classify in interface Classifier

Parameters:

data - the data point to classify

Returns:

the results of the classification.

trainC

public void trainC(ClassificationDataSet dataSet,
                   ExecutorService threadPool)

Description copied from interface: Classifier

Trains the classifier and constructs a model for classification using the given data set. If the training method knows how, it will used the threadPool to conduct training in parallel. This method will block until the training has completed.

Specified by:

trainC in interface Classifier

Parameters:

dataSet - the data set to train on

threadPool - the source of threads to use.

trainC

protected void trainC(ClassificationDataSet dataSet,
                      Set<Integer> options,
                      ExecutorService threadPool)

Performs exactly the same as trainC(jsat.classifiers.ClassificationDataSet, java.util.concurrent.ExecutorService), but the user can specify a subset of the features to be considered.

Parameters:

dataSet - the data set to train from

options - the subset of features to split on

threadPool - the source of threads for training.

makeNodeC

protected DecisionTree.Node makeNodeC(List<DataPointPair<Integer>> dataPoints,
                                      Set<Integer> options,
                                      int depth,
                                      ExecutorService threadPool,
                                      ModifiableCountDownLatch mcdl)

Makes a new node for classification

Parameters:

dataPoints - the list of data points paired with their class

options - the attributes that this tree may select from

depth - the current depth of the tree

threadPool - the source of threads

mcdl - count down latch

Returns:

the node created, or null if no node was created

makeNodeR

protected DecisionTree.Node makeNodeR(List<DataPointPair<Double>> dataPoints,
                                      Set<Integer> options,
                                      int depth,
                                      ExecutorService threadPool,
                                      ModifiableCountDownLatch mcdl)

Makes a new node for regression

Parameters:

dataPoints - the list of data points paired with their associated real value

options - the attributes that this tree may select from

depth - the current depth of the tree

threadPool - the source of threads

mcdl - count down latch

Returns:

the node created, or null if no node was created

trainC

public void trainC(ClassificationDataSet dataSet)

Description copied from interface: Classifier

Trains the classifier and constructs a model for classification using the given data set.

Specified by:

trainC in interface Classifier

Parameters:

dataSet - the data set to train on

trainC

public void trainC(ClassificationDataSet dataSet,
                   Set<Integer> options)

supportsWeightedData

public boolean supportsWeightedData()

Description copied from interface: Classifier

Indicates whether the model knows how to train using weighted data points. If it does, the model will train assuming the weights. The values returned by this method may change depending on the parameters set for the model.

Specified by:

supportsWeightedData in interface Classifier

Specified by:

supportsWeightedData in interface Regressor

Returns:

true if the model supports weighted data, false otherwise

clone

public DecisionTree clone()

Specified by:

clone in interface Classifier

Specified by:

clone in interface Regressor

Overrides:

clone in class Object

getTreeNodeVisitor

public TreeNodeVisitor getTreeNodeVisitor()

Description copied from interface: TreeLearner

Obtains a node visitor for the tree learner that can be used to traverse and predict from the learned tree

Specified by:

getTreeNodeVisitor in interface TreeLearner

Returns:

the root node visitor for the learned tree

getParameters

public List<Parameter> getParameters()

Description copied from interface: Parameterized

Returns the list of parameters that can be altered for this learner.

Specified by:

getParameters in interface Parameterized

Returns:

the list of parameters that can be altered for this learner.

getParameter

public Parameter getParameter(String paramName)

Description copied from interface: Parameterized

Returns the parameter with the given name. Two different strings may map to a single Parameter object. An ASCII only string, and a Unicode style string.

Specified by:

getParameter in interface Parameterized

Parameters:

paramName - the name of the parameter to obtain

Returns:

the Parameter in question, or null if no such named Parameter exists.