package jsat.classifiers.boosting;

import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.classifiers.*;
import jsat.classifiers.knn.NearestNeighbour;
import jsat.classifiers.trees.DecisionTree;
import jsat.math.OnLineStatistics;
import jsat.parameters.*;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;

/**
 * An implementation of Bootstrap Aggregating, as described by LEO BREIMAN in "Bagging Predictors". 
*
* Bagging is an ensemble learner, it takes a weak learner and trains several to create a better over result. * Bagging is particularly useful when the base classifier has some amount of predictive power, but is hindered * by variance in the output (small change in input causes large change in output), or variances in input * (handles noisy data badly or is has a brittle learning algorithm). It is common to perform bagging on * {@link DecisionTree Decision Trees}, because they meet these strengths and weaknesses.
* Bagging produces little to no improvement when using learners that have low variance and robust learning * methods. {@link NearestNeighbour} is an example of a particularly bad method to bag. *
* Bagging has many similarities to boosting. * @author Edward Raff */ public class Bagging implements Classifier, Regressor, Parameterized { private static final long serialVersionUID = -6566453570170428838L; private Classifier baseClassifier; private Regressor baseRegressor; private CategoricalData predicting; private int extraSamples; private int rounds; private boolean simultaniousTraining; private Random random; private List learners; /** * The number of rounds of bagging that will be used by default in the constructor: {@value #DEFAULT_ROUNDS} */ public static final int DEFAULT_ROUNDS = 20; /** * The number of extra samples to take when bagging in each round used by default in the constructor: {@value #DEFAULT_EXTRA_SAMPLES} */ public static final int DEFAULT_EXTRA_SAMPLES = 0; /** * The default behavior for parallel training, as specified by {@link #setSimultaniousTraining(boolean) } is {@value #DEFAULT_SIMULTANIOUS_TRAINING} */ public static final boolean DEFAULT_SIMULTANIOUS_TRAINING = true; /** * Creates a new Bagger for classification. This can not be changed after construction. * * @param baseClassifier the base learner to use. */ public Bagging(Classifier baseClassifier) { this(baseClassifier, DEFAULT_EXTRA_SAMPLES, DEFAULT_SIMULTANIOUS_TRAINING); } /** * Creates a new Bagger for classification. This can not be changed after construction. * * @param baseClassifier the base learner to use. * @param extraSamples how many extra samples past the training size to take * @param simultaniousTraining controls whether base learners are trained sequentially or simultaneously */ public Bagging(Classifier baseClassifier, int extraSamples, boolean simultaniousTraining) { this(baseClassifier, extraSamples, simultaniousTraining, DEFAULT_ROUNDS, new Random(1)); } /** * Creates a new Bagger for classification. This can not be changed after construction. * * @param baseClassifier the base learner to use. * @param extraSamples how many extra samples past the training size to take * @param simultaniousTraining controls whether base learners are trained sequentially or simultaneously * @param rounds how many rounds of bagging to perform. * @param random the source of randomness for sampling */ public Bagging(Classifier baseClassifier, int extraSamples, boolean simultaniousTraining, int rounds, Random random) { this(extraSamples, simultaniousTraining, rounds, random); this.baseClassifier = baseClassifier; } /** * Creates a new Bagger for regression. This can not be changed after construction. * * @param baseRegressor the base learner to use. */ public Bagging(Regressor baseRegressor) { this(baseRegressor, DEFAULT_EXTRA_SAMPLES, DEFAULT_SIMULTANIOUS_TRAINING); } /** * Creates a new Bagger for regression. This can not be changed after construction. * * @param baseRegressor the base learner to use. * @param extraSamples how many extra samples past the training size to take * @param simultaniousTraining controls whether base learners are trained sequentially or simultaneously */ public Bagging(Regressor baseRegressor, int extraSamples, boolean simultaniousTraining) { this(baseRegressor, extraSamples, simultaniousTraining, DEFAULT_ROUNDS, new Random(1)); } /** * Creates a new Bagger for regression. This can not be changed after construction. * * @param baseRegressor the base learner to use. * @param extraSamples how many extra samples past the training size to take * @param simultaniousTraining controls whether base learners are trained sequentially or simultaneously * @param rounds how many rounds of bagging to perform. * @param random the source of randomness for sampling */ public Bagging(Regressor baseRegressor, int extraSamples, boolean simultaniousTraining, int rounds, Random random) { this(extraSamples, simultaniousTraining, rounds, random); this.baseRegressor = baseRegressor; } //For internal use private Bagging(int extraSamples, boolean simultaniousTraining, int rounds, Random random) { setExtraSamples(extraSamples); setSimultaniousTraining(simultaniousTraining); setRounds(rounds); this.random = random; } /** * 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; } /** * Sets the number of rounds that bagging is done, meaning how many base learners are trained * @param rounds the number of base learners to train * @throws ArithmeticException if the number specified is not a positive value */ public void setRounds(int rounds) { if(rounds <= 0) throw new ArithmeticException("Must train a positive number of learners"); this.rounds = rounds; } /** * 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 getRounds() { return rounds; } /** * Bagging produces multiple base learners. These can all be trained at the same time, using more memory, * or sequentially using the base learner's parallel training method. If set to true, the base learners * will be trained simultaneously. * * @param simultaniousTraining true to train all learners at the same time, false to train them sequentially */ public void setSimultaniousTraining(boolean simultaniousTraining) { this.simultaniousTraining = simultaniousTraining; } @Override public CategoricalResults classify(DataPoint data) { if(baseClassifier == null) throw new RuntimeException("Bagging instance created for regression, not classification"); else if(learners == null || learners.isEmpty()) throw new RuntimeException("Classifier has not yet been trained"); CategoricalResults totalResult = new CategoricalResults(predicting.getNumOfCategories()); for(int i = 0; i < learners.size(); i++) { CategoricalResults result = ((Classifier) learners.get(i)).classify(data); totalResult.incProb(result.mostLikely(), 1.0); } totalResult.normalize(); return totalResult; } @Override public void train(final ClassificationDataSet dataSet, final boolean parallel) { predicting = dataSet.getPredicting(); learners = new ArrayList(rounds); //Used to make the main thread wait for the working threads to finish before submiting a new job so we dont waist too much memory then we can use at once final Semaphore waitForThread = new Semaphore(SystemInfo.LogicalCores); //Used to make the main thread wait for the working threads to finish before returning final CountDownLatch waitForFinish = new CountDownLatch(rounds); //Creat a synchrnozied view so we can add safely final List synchronizedLearners = Collections.synchronizedList(learners); final int[] sampleCounts = new int[dataSet.getSampleSize()]; ExecutorService threadPool = ParallelUtils.getNewExecutor(parallel); for(int i = 0; i < rounds; i++) { sampleWithReplacement(sampleCounts, sampleCounts.length+extraSamples, random); final ClassificationDataSet sampleSet = getSampledDataSet(dataSet, sampleCounts); final Classifier learner = baseClassifier.clone(); if(simultaniousTraining && parallel) { try { //Wait for an available thread waitForThread.acquire(); threadPool.submit(() -> { learner.train(sampleSet); synchronizedLearners.add(learner); waitForThread.release();//Finish, allow another one to pass through waitForFinish.countDown(); }); } catch (InterruptedException ex) { Logger.getLogger(Bagging.class.getName()).log(Level.SEVERE, null, ex); System.err.println(ex.getMessage()); } } else { learner.train(sampleSet, parallel); learners.add(learner); } } if (simultaniousTraining && parallel) try { waitForFinish.await(); } catch (InterruptedException ex) { Logger.getLogger(Bagging.class.getName()).log(Level.SEVERE, null, ex); System.err.println(ex.getMessage()); } threadPool.shutdownNow(); } /** * Creates a new data set from the given sample counts. Points sampled * multiple times will have multiple entries in the data set. * @param dataSet the data set that was sampled from * @param sampledCounts the sampling values obtained from * {@link #sampleWithReplacement(int[], int, java.util.Random) } * @return a new sampled classification data set */ public static ClassificationDataSet getSampledDataSet(ClassificationDataSet dataSet, int[] sampledCounts) { ClassificationDataSet destination = new ClassificationDataSet(dataSet.getNumNumericalVars(), dataSet.getCategories(), dataSet.getPredicting()); for (int i = 0; i < sampledCounts.length; i++) for(int j = 0; j < sampledCounts[i]; j++) { DataPoint dp = dataSet.getDataPoint(i); destination.addDataPoint(dp.getNumericalValues(), dp.getCategoricalValues(), dataSet.getDataPointCategory(i)); } return destination; } /** * Creates a new data set from the given sample counts. Points sampled * multiple times will be added once to the data set with their weight * multiplied by the number of times it was sampled. * @param dataSet the data set that was sampled from * @param sampledCounts the sampling values obtained from * {@link #sampleWithReplacement(int[], int, java.util.Random) } * @return a new sampled classification data set */ public static ClassificationDataSet getWeightSampledDataSet(ClassificationDataSet dataSet, int[] sampledCounts) { ClassificationDataSet destination = new ClassificationDataSet(dataSet.getNumNumericalVars(), dataSet.getCategories(), dataSet.getPredicting()); for (int i = 0; i < sampledCounts.length; i++) { if(sampledCounts[i] <= 0) continue; DataPoint dp = dataSet.getDataPoint(i); destination.addDataPoint(dp.getNumericalValues(), dp.getCategoricalValues(), dataSet.getDataPointCategory(i), dp.getWeight()*sampledCounts[i]); } return destination; } /** * Creates a new data set from the given sample counts. Points sampled * multiple times will have multiple entries in the data set. * @param dataSet the data set that was sampled from * @param sampledCounts the sampling values obtained from * {@link #sampleWithReplacement(int[], int, java.util.Random) } * @return a new sampled classification data set */ public static RegressionDataSet getSampledDataSet(RegressionDataSet dataSet, int[] sampledCounts) { RegressionDataSet destination = new RegressionDataSet(dataSet.getNumNumericalVars(), dataSet.getCategories()); for (int i = 0; i < sampledCounts.length; i++) for (int j = 0; j < sampledCounts[i]; j++) { DataPoint dp = dataSet.getDataPoint(i); destination.addDataPoint(dp, dataSet.getTargetValue(i)); } return destination; } /** * Creates a new data set from the given sample counts. Points sampled * multiple times will be added once to the data set with their weight * multiplied by the number of times it was sampled. * @param dataSet the data set that was sampled from * @param sampledCounts the sampling values obtained from * {@link #sampleWithReplacement(int[], int, java.util.Random) } * @return a new sampled classification data set */ public static RegressionDataSet getWeightSampledDataSet(RegressionDataSet dataSet, int[] sampledCounts) { RegressionDataSet destination = new RegressionDataSet(dataSet.getNumNumericalVars(), dataSet.getCategories()); for (int i = 0; i < sampledCounts.length; i++) { if(sampledCounts[i] <= 0) continue; DataPoint dp = dataSet.getDataPoint(i); DataPoint reWeighted = new DataPoint(dp.getNumericalValues(), dp.getCategoricalValues(), dp.getCategoricalData(), dp.getWeight()*sampledCounts[i]); destination.addDataPoint(reWeighted, dataSet.getTargetValue(i)); } return destination; } /** * Performs the sampling based on the number of data points, storing the * counts in an array to be constructed from XXXX * @param sampleCounts an array to keep count of how many times each data * point was sampled. The array will be filled with zeros before sampling * starts * @param samples the number of samples to take from the data set * @param rand the source of randomness */ static public void sampleWithReplacement(int[] sampleCounts, int samples, Random rand) { Arrays.fill(sampleCounts, 0); for(int i = 0; i < samples; i++) sampleCounts[rand.nextInt(sampleCounts.length)]++; } @Override public boolean supportsWeightedData() { return false; } @Override public double regress(DataPoint data) { if(baseRegressor == null) throw new RuntimeException("Bagging instance created for classification, not regression"); else if(learners == null || learners.isEmpty()) throw new RuntimeException("Regressor has not yet been trained"); OnLineStatistics stats = new OnLineStatistics(); for(int i = 0; i < learners.size(); i++) { double x = ((Regressor) learners.get(i)).regress(data); stats.add(x); } return stats.getMean(); } @Override public void train(RegressionDataSet dataSet, final boolean parallel) { learners = new ArrayList(rounds); //Used to make the main thread wait for the working threads to finish before submiting a new job so we dont waist too much memory then we can use at once final Semaphore waitForThread = new Semaphore(SystemInfo.LogicalCores); //Used to make the main thread wait for the working threads to finish before returning final CountDownLatch waitForFinish = new CountDownLatch(rounds); //Creat a synchrnozied view so we can add safely final List synchronizedLearners = Collections.synchronizedList(learners); final int[] sampleCount = new int[dataSet.getSampleSize()]; ExecutorService threadPool = ParallelUtils.getNewExecutor(parallel); for(int i = 0; i < rounds; i++) { sampleWithReplacement(sampleCount, sampleCount.length+extraSamples, random); final RegressionDataSet sampleSet = getSampledDataSet(dataSet, sampleCount); final Regressor learner = baseRegressor.clone(); if(simultaniousTraining && parallel) { try { //Wait for an available thread waitForThread.acquire(); threadPool.submit(() -> { learner.train(sampleSet); synchronizedLearners.add(learner); waitForThread.release();//Finish, allow another one to pass through waitForFinish.countDown(); }); } catch (InterruptedException ex) { Logger.getLogger(Bagging.class.getName()).log(Level.SEVERE, null, ex); System.err.println(ex.getMessage()); } } else { learner.train(sampleSet, parallel); learners.add(learner); } } if (simultaniousTraining && parallel) try { waitForFinish.await(); } catch (InterruptedException ex) { Logger.getLogger(Bagging.class.getName()).log(Level.SEVERE, null, ex); System.err.println(ex.getMessage()); } threadPool.shutdownNow(); } @Override public Bagging clone() { Bagging clone = new Bagging(extraSamples, simultaniousTraining, rounds, new Random(rounds)); if(baseClassifier != null) clone.baseClassifier = baseClassifier.clone(); if(predicting != null) clone.predicting = this.predicting.clone(); if(baseRegressor != null) clone.baseRegressor = baseRegressor.clone(); if(learners != null && !learners.isEmpty()) { clone.learners = new ArrayList(this.learners.size()); for(Object learner : learners) if(learner instanceof Classifier) clone.learners.add( ((Classifier)learner).clone()); else clone.learners.add( ((Regressor)learner).clone()); } return clone; } }

Ads help maintain this website.