package jsat.classifiers.trees;
import static java.lang.Math.*;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import jsat.DataSet;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.exceptions.FailedToFitException;
import jsat.math.OnLineStatistics;
import jsat.regression.RegressionDataSet;
import jsat.utils.FakeExecutor;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;
/**
* Extra Randomized Trees (ERTrees) is an ensemble method built on top of
* {@link ExtraTree}. The randomness of the trees provides incredibly high
* variance, yet a low bias. The sum of many randomized trees proves to be
* a powerful and fast learner.
* The default settings are those suggested in the paper. However, the default
* stop size suggested (especially for classification) is often too small. You
* may want to consider increasing it if the accuracy is too low.
* See:
* Geurts, P., Ernst, D.,&Wehenkel, L. (2006). Extremely randomized trees
* . Machine learning, 63(1), 3–42. doi:10.1007/s10994-006-6226-1
*
* @author Edward Raff
*/
public class ERTrees extends ExtraTree
{
private static final long serialVersionUID = 7139392253403373132L;
//NOTE ExtraTrees uses the dynamic reflection, so extening it the new getter/setter paris are automatically picked up
private ExtraTree baseTree = new ExtraTree();
private boolean useDefaultSelectionCount = true;
private boolean useDefaultStopSize = true;
private ExtraTree[] forrest;
private int forrestSize;
/**
* Creates a new Extremely Randomized Trees learner
*/
public ERTrees()
{
this(100);
}
/**
* Creates a new Extremely Randomized Trees learner
* @param forrestSize the number of trees to construct
*/
public ERTrees(int forrestSize)
{
this.forrestSize = forrestSize;
}
/**
* Copy constructor
* @param toCopy the object to copy
*/
public ERTrees(ERTrees toCopy)
{
super(toCopy);
this.forrestSize = toCopy.forrestSize;
this.useDefaultSelectionCount = toCopy.useDefaultSelectionCount;
this.useDefaultStopSize = toCopy.useDefaultStopSize;
this.baseTree = toCopy.baseTree.clone();
if(toCopy.forrest != null)
{
this.forrest = new ExtraTree[toCopy.forrest.length];
for(int i = 0; i < toCopy.forrest.length; i++)
this.forrest[i] = toCopy.forrest[i].clone();
}
}
/**
* Measures the statistics of feature importance from the trees in this
* forest. For classification datasets, the {@link MDI} method with Gini
* impurity will be used. For others, the {@link ImportanceByUses} method
* will be used. This may change in the future.
*
* @param
* @param data the dataset to infer the feature importance from with respect
* to the current model.
* @return an array of statistics, which each index corresponds to a
* specific feature. Numeric features start from the zero index, categorical
* features start from the index equal to the number of numeric features.
*/
public OnLineStatistics[] evaluateFeatureImportance(DataSet data)
{
if(data instanceof ClassificationDataSet)
return evaluateFeatureImportance(data, new MDI(ImpurityScore.ImpurityMeasure.GINI));
else
return evaluateFeatureImportance(data, new ImportanceByUses());
}
/**
* Measures the statistics of feature importance from the trees in this
* forest.
*
* @param
* @param data the dataset to infer the feature importance from with respect
* to the current model.
* @param imp the method of determing the feature importance that will be
* applied to each tree in this model
* @return an array of statistics, which each index corresponds to a
* specific feature. Numeric features start from the zero index, categorical
* features start from the index equal to the number of numeric features.
*/
public OnLineStatistics[] evaluateFeatureImportance(DataSet data, TreeFeatureImportanceInference imp)
{
OnLineStatistics[] importances = new OnLineStatistics[data.getNumFeatures()];
for(int i = 0; i < importances.length; i++)
importances[i] = new OnLineStatistics();
for(ExtraTree tree :forrest)
{
double[] feats = imp.getImportanceStats(tree, data);
for(int i = 0; i < importances.length; i++)
importances[i].add(feats[i]);
}
return importances;
}
/**
* Sets whether or not to use the default heuristic for the number of random
* features to select as candidates for each node. If true the
* value of selectionCount will be modified during training, using sqrt(n)
* features for classification and all features for regression. Otherwise,
* whatever value set before hand will be used.
* @param useDefaultSelectionCount whether or not to use the heuristic
* version
*/
public void setUseDefaultSelectionCount(boolean useDefaultSelectionCount)
{
this.useDefaultSelectionCount = useDefaultSelectionCount;
}
/**
* Returns if the default heuristic for the selection count is used
* @return if the default heuristic for the selection count is used
*/
public boolean getUseDefaultSelectionCount()
{
return useDefaultSelectionCount;
}
/**
* Sets whether or not to us the default heuristic for the number of points
* to force a new node to be a leaf. If true the value for stopSize
* will be altered during training, set to 2 for classification and 5 for
* regression. Otherwise, whatever value set beforehand will be used.
* @param useDefaultStopSize whether or not to use the heuristic version
*/
public void setUseDefaultStopSize(boolean useDefaultStopSize)
{
this.useDefaultStopSize = useDefaultStopSize;
}
/**
* Returns if the default heuristic for the stop size is used
* @return if the default heuristic for the stop size is used
*/
public boolean getUseDefaultStopSize()
{
return useDefaultStopSize;
}
public void setForrestSize(int forrestSize)
{
this.forrestSize = forrestSize;
}
public int getForrestSize()
{
return forrestSize;
}
@Override
public CategoricalResults classify(DataPoint data)
{
CategoricalResults cr = new CategoricalResults(predicting.getNumOfCategories());
for(ExtraTree tree : forrest)
cr.incProb(tree.classify(data).mostLikely(), 1.0);
cr.normalize();
return cr;
}
private void doTraining(boolean parallel, DataSet dataSet) throws FailedToFitException
{
forrest = new ExtraTree[forrestSize];
ParallelUtils.run(parallel, forrestSize, (start, end) ->
{
if (dataSet instanceof ClassificationDataSet)
{
ClassificationDataSet cds = (ClassificationDataSet) dataSet;
for (int i = start; i < end; i++)
{
forrest[i] = baseTree.clone();
forrest[i].train(cds);
}
}
else if (dataSet instanceof RegressionDataSet)
{
RegressionDataSet rds = (RegressionDataSet) dataSet;
for (int i = start; i < end; i++)
{
forrest[i] = baseTree.clone();
forrest[i].train(rds);
}
}
else
throw new RuntimeException("BUG: Please report");
});
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
if(useDefaultSelectionCount)
baseTree.setSelectionCount((int)max(round(sqrt(dataSet.getNumFeatures())), 1));
if(useDefaultStopSize)
baseTree.setStopSize(2);
predicting = dataSet.getPredicting();
doTraining(parallel, dataSet);
}
@Override
public boolean supportsWeightedData()
{
return true;
}
@Override
public double regress(DataPoint data)
{
double mean = 0.0;
for(ExtraTree tree : forrest)
mean += tree.regress(data);
return mean/forrest.length;
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
if(useDefaultSelectionCount)
baseTree.setSelectionCount(dataSet.getNumFeatures());
if(useDefaultStopSize)
baseTree.setStopSize(5);
doTraining(parallel, dataSet);
}
@Override
public ERTrees clone()
{
return new ERTrees(this);
}
@Override
public TreeNodeVisitor getTreeNodeVisitor()
{
throw new UnsupportedOperationException("Can not get the tree node vistor becase ERTrees is really a ensemble");
}
}
Ads help maintain this website.