package jsat.classifiers.trees;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.boosting.Bagging;
import jsat.classifiers.trees.ImpurityScore.ImpurityMeasure;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.FakeExecutor;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.AtomicDoubleArray;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
/**
* Random Forest is an extension of {@link Bagging} that is applied only to
* {@link DecisionTree DecisionTrees}. It works in a similar manner, but also
* only uses a random sub set of the features for each tree trained. This
* provides increased performance in accuracy of predictions, and reduced
* training time over just Bagging.
*
* This class supports learning and predicting with missing values.
*
* @author Edward Raff
* @see Bagging
*/
public class RandomForest implements Classifier, Regressor, Parameterized
{
//TODO implement Out of Bag estimates of proximity, importance, and outlier detection
private static final long serialVersionUID = 2725020584282958141L;
/**
* Only used when training for a classification problem
*/
private CategoricalData predicting;
private int extraSamples;
/**
* Setting the number of features to use. Default value is -1, indicating the heuristic
* of sqrt(N) or N/3 should be used for classification and regression respectively. This
* value should be set away from -1 before training work begins, and set back if it
* was not set explicitly by the used
*/
private int featureSamples;
private int maxForestSize;
private boolean useOutOfBagError = false;
private boolean useOutOfBagImportance = false;
private TreeFeatureImportanceInference importanceMeasure = new MDI();
private OnLineStatistics[] feature_importance = null;
private double outOfBagError;
private RandomDecisionTree baseLearner;
private List forest;
public RandomForest()
{
this(100);
}
public RandomForest(int maxForestSize)
{
setExtraSamples(0);
setMaxForestSize(maxForestSize);
autoFeatureSample();
baseLearner = new RandomDecisionTree(1, Integer.MAX_VALUE, 3, TreePruner.PruningMethod.NONE, 1e-15);
baseLearner.setGainMethod(ImpurityMeasure.GINI);
}
/**
* RandomForest performs Bagging. Bagging samples from the training set with replacement, and draws
* a sampleWithReplacement at least as large as the training set. This controls how many extra samples are
* taken. If negative, fewer samples will be taken. Using negative values is not recommended.
*
* @param i how many extra samples to take
*/
public void setExtraSamples(int i)
{
extraSamples = i;
}
public int getExtraSamples()
{
return extraSamples;
}
/**
* Instead of using a heuristic, the exact number of features to sample is provided.
* If equal to or larger then the number of features in one of the training data sets,
* RandomForest degrades to {@link Bagging} performed on {@link DecisionTree}.
*
* To re-enable the heuristic mode, call {@link #autoFeatureSample() }
*
* @param featureSamples the number of features to randomly select for each tree in the forest.
* @throws ArithmeticException if the number given is less then or equal to zero
* @see #autoFeatureSample()
* @see Bagging
*/
public void setFeatureSamples(int featureSamples)
{
if(featureSamples <= 0)
throw new ArithmeticException("A positive number of features must be given");
this.featureSamples = featureSamples;
}
/**
* Tells the class to automatically select the number of features to use. For
* classification problems, this is the square root of the number of features.
* For regression, the number of features divided by 3 is used.
*/
public void autoFeatureSample()
{
featureSamples = -1;
}
/**
* Returns true if heuristics are currently in use for the number of features, or false if the number has been specified.
* @return true if heuristics are currently in use for the number of features, or false if the number has been specified.
*/
public boolean isAutoFeatureSample()
{
return featureSamples == -1;
}
/**
* Sets the maximum number of trees to create for the forest.
* @param maxForestSize the number of base learners to train
* @throws ArithmeticException if the number specified is not a positive value
*/
public void setMaxForestSize(int maxForestSize)
{
if(maxForestSize <= 0)
throw new ArithmeticException("Must train a positive number of learners");
this.maxForestSize = maxForestSize;
}
/**
* Returns the number of rounds of boosting that will be done, which is also the number of base learners that will be trained
* @return the number of rounds of boosting that will be done, which is also the number of base learners that will be trained
*/
public int getMaxForestSize()
{
return maxForestSize;
}
/**
* Sets whether or not to compute the out of bag error during training
* @param useOutOfBagError true to compute the out of bag error, false to skip it
*/
public void setUseOutOfBagError(boolean useOutOfBagError)
{
this.useOutOfBagError = useOutOfBagError;
}
/**
* Indicates if the out of bag error rate will be computed during training
* @return true if the out of bag error will be computed, false otherwise
*/
public boolean isUseOutOfBagError()
{
return useOutOfBagError;
}
/**
* Random Forest can obtain an unbiased estimate of feature importance using
* a {@link TreeFeatureImportanceInference} method on the out-of-bag samples
* during training. Since each tree will produce a different importance
* score, we also get a set of statistics for each feature rather than just
* a single score value. These are only computed if {@link #setUseOutOfBagImportance(boolean)
* } is set to true.
* @return an array of size equal to the number of features, each
* {@link OnLineStatistics} describing the statistics for the importance of
* each feature. Numeric features start from index 0, and categorical
* features start from the index equal to the number of numeric features.
*/
public OnLineStatistics[] getFeatureImportance()
{
return feature_importance;
}
/**
* Sets whether or not to compute the out of bag importance of each feature
* during training.
*
* @param useOutOfBagImportance true to compute the out of bag
* feature importance, false to skip it
*/
public void setUseOutOfBagImportance(boolean useOutOfBagImportance)
{
this.useOutOfBagImportance = useOutOfBagImportance;
}
/**
* Indicates if the out of bag feature importance will be computed during
* training
*
* @return true if the out of bag importance will be computed,
* false otherwise
*/
public boolean isUseOutOfBagImportance()
{
return useOutOfBagImportance;
}
/**
* If {@link #isUseOutOfBagError() } is false, then this method will return
* 0 after training. Otherwise, it will return the out of bag error estimate
* after training has completed. For classification problems, this is the 0/1
* loss error rate. Regression problems return the mean squared error.
* @return the out of bag error estimate for this predictor
*/
public double getOutOfBagError()
{
return outOfBagError;
}
@Override
public CategoricalResults classify(DataPoint data)
{
if(forest == null || forest.isEmpty())
throw new RuntimeException("Classifier has not yet been trained");
else if(predicting == null)
throw new RuntimeException("Classifier has been trained for regression");
CategoricalResults totalResult = new CategoricalResults(predicting.getNumOfCategories());
for(DecisionTree tree : forest)
totalResult.incProb(tree.classify(data).mostLikely(), 1.0);
totalResult.normalize();
return totalResult;
}
@Override
public void train(ClassificationDataSet dataSet, boolean parallel)
{
this.predicting = dataSet.getPredicting();
this.forest = new ArrayList(maxForestSize);
trainStep(dataSet, parallel);
}
@Override
public boolean supportsWeightedData()
{
return true;
}
@Override
public double regress(DataPoint data)
{
if(forest == null || forest.isEmpty())
throw new RuntimeException("Classifier has not yet been trained");
else if(predicting != null)
throw new RuntimeException("Classifier has been trained for classification");
OnLineStatistics stats = new OnLineStatistics();
for(DecisionTree tree : forest)
stats.add(tree.regress(data));
return stats.getMean();
}
@Override
public void train(RegressionDataSet dataSet, boolean parallel)
{
this.predicting = null;
this.forest = new ArrayList(maxForestSize);
trainStep(dataSet, parallel);
}
/**
* Does the actual set up and training. {@link #predicting } and {@link #forest} should be
* set up appropriately first. Everything else is handled by this and {@link LearningWorker}
*
* @param dataSet the data set, classification or regression
* @param threadPool the source of threads
*/
private void trainStep(DataSet dataSet, boolean parallel)
{
boolean autoLearners = isAutoFeatureSample();//We will need to set it back after, so remember if we need to
if(autoLearners)
baseLearner.setRandomFeatureCount(Math.max((int)Math.sqrt(dataSet.getNumFeatures()), 1));
else
baseLearner.setRandomFeatureCount(featureSamples);
int roundsToDistribut = maxForestSize;
int roundShare = roundsToDistribut / SystemInfo.LogicalCores;//The number of rounds each thread gets
int extraRounds = roundsToDistribut % SystemInfo.LogicalCores;//The number of extra rounds that need to get distributed
if(!parallel)//No point in duplicatin recources
roundShare = roundsToDistribut;//All the rounds get shoved onto one thread
ExecutorService threadPool = parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor();
//Random used for creating more random objects, faster to duplicate such a small recourse then share and lock
Random rand = RandomUtil.getRandom();
List> futures = new ArrayList<>(SystemInfo.LogicalCores);
int[][] counts = null;
AtomicDoubleArray pred = null;
if(dataSet instanceof RegressionDataSet)
{
pred = new AtomicDoubleArray(dataSet.getSampleSize());
counts = new int[pred.length()][1];//how many predictions are in this?
}
else
{
counts = new int[dataSet.getSampleSize()][((ClassificationDataSet)dataSet).getClassSize()];
}
while (roundsToDistribut > 0)
{
int extra = (extraRounds-- > 0) ? 1 : 0;
Future future = threadPool.submit(new LearningWorker(dataSet, roundShare + extra, new Random(rand.nextInt()), counts, pred));
roundsToDistribut -= (roundShare + extra);
futures.add(future);
}
outOfBagError = 0;
try
{
List workers = ListUtils.collectFutures(futures);
for (LearningWorker worker : workers)
forest.addAll(worker.learned);
if (useOutOfBagError)
{
if (dataSet instanceof ClassificationDataSet)
{
ClassificationDataSet cds = (ClassificationDataSet) dataSet;
for (int i = 0; i < counts.length; i++)
{
int max = 0;
for (int j = 1; j < counts[i].length; j++)
if(counts[i][j] > counts[i][max])
max = j;
if(max != cds.getDataPointCategory(i))
outOfBagError++;
}
}
else
{
RegressionDataSet rds = (RegressionDataSet) dataSet;
for (int i = 0; i < counts.length; i++)
outOfBagError += Math.pow(pred.get(i)/counts[i][0]-rds.getTargetValue(i), 2);
}
outOfBagError /= dataSet.getSampleSize();
}
if(useOutOfBagImportance)//collect feature importance stats from each worker
{
feature_importance = new OnLineStatistics[dataSet.getNumFeatures()];
for(int j = 0; j < dataSet.getNumFeatures(); j++)
feature_importance[j] = new OnLineStatistics();
for(LearningWorker worker : workers)
for(int j = 0; j < dataSet.getNumFeatures(); j++)
feature_importance[j].add(worker.fi[j]);
}
}
catch (Exception ex)
{
Logger.getLogger(RandomForest.class.getName()).log(Level.SEVERE, null, ex);
}
}
@Override
public RandomForest clone()
{
RandomForest clone = new RandomForest(maxForestSize);
clone.extraSamples = this.extraSamples;
clone.featureSamples = this.featureSamples;
if(this.predicting != null)
clone.predicting = this.predicting.clone();
if(this.forest != null)
{
clone.forest = new ArrayList(this.forest.size());
for(DecisionTree tree : this.forest)
clone.forest.add(tree.clone());
}
clone.baseLearner = this.baseLearner.clone();
clone.useOutOfBagImportance = this.useOutOfBagImportance;
clone.useOutOfBagError = this.useOutOfBagError;
if(this.feature_importance != null)
{
clone.feature_importance = new OnLineStatistics[this.feature_importance.length];
for(int i = 0; i < this.feature_importance.length; i++)
clone.feature_importance[i] = this.feature_importance[i].clone();
}
return clone;
}
private class LearningWorker implements Callable
{
int toLearn;
List learned;
DataSet dataSet;
Random random;
OnLineStatistics[] fi;
/**
* For regression: sum of predictions
*/
private AtomicDoubleArray votes;
private int[][] counts;
public LearningWorker(DataSet dataSet, int toLearn, Random random, int[][] counts, AtomicDoubleArray pred)
{
this.dataSet = dataSet;
this.toLearn = toLearn;
this.random = random;
this.learned = new ArrayList(toLearn);
if(useOutOfBagError)
{
votes = pred;
this.counts = counts;
}
if(useOutOfBagImportance)
{
this.fi = new OnLineStatistics[dataSet.getNumFeatures()];
for(int i = 0; i < fi.length; i++)
fi[i] = new OnLineStatistics();
}
}
@Override
public LearningWorker call() throws Exception
{
Set features = new IntSet(baseLearner.getRandomFeatureCount());
int[] sampleCounts = new int[dataSet.getSampleSize()];
for(int i = 0; i < toLearn; i++)
{
//Sample to get the training points
Bagging.sampleWithReplacement(sampleCounts, sampleCounts.length+extraSamples, random);
//Sample to select the feature subset
features.clear();
while(features.size() < Math.min(baseLearner.getRandomFeatureCount(), dataSet.getNumFeatures()))//The user could have specified too many
features.add(random.nextInt(dataSet.getNumFeatures()));
RandomDecisionTree learner = baseLearner.clone();
if(dataSet instanceof ClassificationDataSet)
learner.trainC(Bagging.getWeightSampledDataSet((ClassificationDataSet)dataSet, sampleCounts), features);
else //It must be regression!
learner.train(Bagging.getWeightSampledDataSet((RegressionDataSet)dataSet, sampleCounts), features);
learned.add(learner);
if(useOutOfBagError)
{
for(int j = 0; j < sampleCounts.length; j++)
{
if(sampleCounts[j] != 0)
continue;
DataPoint dp = dataSet.getDataPoint(j);
if(dataSet instanceof ClassificationDataSet)
{
int pred = learner.classify(dp).mostLikely();
synchronized(counts[j])
{
counts[j][pred]++;
}
}
else
{
votes.getAndAdd(j, learner.regress(dp));
synchronized(counts[j])
{
counts[j][0]++;
}
}
}
}
if(useOutOfBagImportance)
{
DataSet oob;
if(dataSet instanceof ClassificationDataSet)
{
ClassificationDataSet cds = (ClassificationDataSet)dataSet;
ClassificationDataSet oob_ = new ClassificationDataSet(cds.getNumNumericalVars(), cds.getCategories(), cds.getPredicting());
for(int j = 0; j < sampleCounts.length; j++)
if(sampleCounts[j] == 0)
oob_.addDataPoint(cds.getDataPoint(j), cds.getDataPointCategory(j));
oob = oob_;
}
else//regression
{
RegressionDataSet rds = (RegressionDataSet)dataSet;
RegressionDataSet oob_ = new RegressionDataSet(rds.getNumNumericalVars(), rds.getCategories());
for(int j = 0; j < sampleCounts.length; j++)
if(sampleCounts[j] == 0)
oob_.addDataPoint(rds.getDataPoint(j), rds.getTargetValue(j));
oob = oob_;
}
double[] oob_import = importanceMeasure.getImportanceStats(learner, oob);
for(int j = 0; j < fi.length; j++)
fi[j].add(oob_import[j]);
}
}
return this;
}
}
}
Ads help maintain this website.