package jsat.regression;

import java.util.*;
import java.util.concurrent.*;
import java.util.logging.Level;
import java.util.logging.Logger;

import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.exceptions.FailedToFitException;
import jsat.parameters.*;
import jsat.parameters.Parameter.ParameterHolder;
import jsat.utils.FakeExecutor;
import jsat.utils.IntSet;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * RANSAC is a randomized meta algorithm that is useful for fitting a model to a
 * data set that has a large amount of outliers that do not represent the true 
 * distribution well. 
* RANSAC has the concept of inliers and outliers. An initial number of seed * points is specified. This makes the initial inlier set. The algorithm than * iterates several times, randomly selecting the specified number of points. It * then regresses on all other points, adding all points within a specified * absolute error to the set of inliers. The model is then trained again on the * larger set, and the training error becomes the measure of the strength of the * model. The model that has the lowest error is then the fit model. * * @author Edward Raff */ public class RANSAC implements Regressor, Parameterized { private static final long serialVersionUID = -5015748604828907703L; /** * the minimum number of data required to fit the model */ private int initialTrainSize; /** * the number of iterations performed by the algorithm */ private int iterations; /** * a threshold value for determining when a datum fits a model */ private double maxPointError; /** * the number of close data values required to assert that a model fits well to data */ private int minResultSize; @ParameterHolder private Regressor baseRegressor; /** * True marks that the data point is part of the consensus set. * False indicates it is not. */ private boolean[] consensusSet; private double modelError; /** * Creates a new RANSAC training object. Because RANSAC is sensitive to * parameter settings, which are data and model dependent, no default values * exist for them. * * @param baseRegressor the model to fit using RANSAC * @param iterations the number of iterations of the algorithm to perform * @param initialTrainSize the number of points to seed each iteration of * training with * @param minResultSize the minimum number of inliers to make it into the * model to be considered a possible fit. * @param maxPointError the maximum allowed absolute difference in the * output of the model and the true value for the data point to be added to * the inlier set. */ public RANSAC(Regressor baseRegressor, int iterations, int initialTrainSize, int minResultSize, double maxPointError) { setInitialTrainSize(initialTrainSize); setIterations(iterations); setMaxPointError(maxPointError); setMinResultSize(minResultSize); this.baseRegressor = baseRegressor; } /** * class that does the loop iteration work and returns a reference to * itself. The are sortable based on the lowest error */ private class RANSACWorker implements Callable, Comparable { int maxIterations; RegressionDataSet dataset; Random rand; Regressor baseModel; public RANSACWorker(Regressor baseModel, int maxIterations, RegressionDataSet dataset) { this.baseModel = baseModel; this.maxIterations = maxIterations; this.dataset = dataset; rand = RandomUtil.getRandom(); } //To be determined Regressor bestModel = null; boolean[] bestConsensusSet = null; double bestError = Double.POSITIVE_INFINITY; @Override public RANSACWorker call() throws Exception { bestConsensusSet = new boolean[dataset.getSampleSize()]; boolean[] working_set = new boolean[dataset.getSampleSize()]; Set maybe_inliers = new IntSet(initialTrainSize*2); for(int iter = 0; iter < maxIterations; iter++) { //Create sub data set sample maybe_inliers.clear(); Arrays.fill(working_set, false); while(maybe_inliers.size() < initialTrainSize) maybe_inliers.add(rand.nextInt(working_set.length)); int consensusSize = maybe_inliers.size(); RegressionDataSet subDataSet = new RegressionDataSet(dataset.getNumNumericalVars(), dataset.getCategories()); for(int i : maybe_inliers) { subDataSet.addDataPointPair(dataset.getDataPointPair(i)); working_set[i] = true; } Regressor maybeModel = baseModel.clone(); maybeModel.train(subDataSet); //Build consensus set for(int i = 0; i < working_set.length; i++) { if(working_set[i]) continue;//Already part of the model DataPointPair dpp = dataset.getDataPointPair(i); double guess = maybeModel.regress(dpp.getDataPoint()); double diff = Math.abs(guess - dpp.getPair()); if(diff < maxPointError) { working_set[i] = true;//Add tot he consenus set subDataSet.addDataPointPair(dpp); consensusSize++; } } if(consensusSize < minResultSize ) continue;//We did not fit enough points to be considered //Build final model maybeModel.train(subDataSet); //Copmute final model error on the consenus set double thisError = 0; for(int i = 0; i < working_set.length; i++) { if(!working_set[i]) continue; DataPointPair dpp = dataset.getDataPointPair(i); double guess = maybeModel.regress(dpp.getDataPoint()); double diff = Math.abs(guess - dpp.getPair()); thisError += diff; } if(thisError < bestError)//New best model { bestError = thisError; bestModel = maybeModel; System.arraycopy(working_set, 0, bestConsensusSet, 0, working_set.length); } } return this; } @Override public int compareTo(RANSACWorker o) { return Double.compare(this.bestError, o.bestError); } } /** * Returns the number of data points to be sampled from the training set to * create initial models. * * @return the number of data points used to first create models */ public int getInitialTrainSize() { return initialTrainSize; } /** * Sets the number of data points to be sampled from the training set to * create initial models. * * @param initialTrainSize the number of data points to use to create models */ public void setInitialTrainSize(int initialTrainSize) { if(initialTrainSize < 1) throw new RuntimeException("Can not train on an empty data set"); this.initialTrainSize = initialTrainSize; } /** * Returns the number models that will be tested on the data set. * * @return the number of algorithm iterations */ public int getIterations() { return iterations; } /** * Sets the number models that will be tested on the data set. * @param iterations the number of iterations to perform */ public void setIterations(int iterations) { if(iterations < 1) throw new RuntimeException("Must perform a positive number of iterations"); this.iterations = iterations; } /** * Each data point not in the initial training set will be tested against. * If a data points error is sufficiently small, it will be added to the set * of inliers. * * @return the maximum error any one point may have to be an inliner */ public double getMaxPointError() { return maxPointError; } /** * Each data point not in the initial training set will be tested against. * If a data points error is sufficiently small, it will be added to the set * of inliers. * * @param maxPointError the new maximum error a data point may have to be * considered an inlier. */ public void setMaxPointError(double maxPointError) { if(maxPointError < 0 || Double.isInfinite(maxPointError) || Double.isNaN(maxPointError)) throw new ArithmeticException("The error must be a positive value, not " + maxPointError ); this.maxPointError = maxPointError; } /** * RANSAC requires an initial model to be accurate enough to include a * minimum number of inliers before being considered as a potentially good * model. This is the number of points that must make it into the inlier set * for a model to be considered. * * @return the minimum number of inliers to be considered */ public int getMinResultSize() { return minResultSize; } /** * RANSAC requires an initial model to be accurate enough to include a * minimum number of inliers before being considered as a potentially good * model. This is the number of points that must make it into the inlier set * for a model to be considered. * * @param minResultSize the minimum number of inliers to be considered */ public void setMinResultSize(int minResultSize) { if(minResultSize < getInitialTrainSize()) throw new RuntimeException("The min result size must be larger than the intial train size"); this.minResultSize = minResultSize; } @Override public double regress(DataPoint data) { return baseRegressor.regress(data); } @Override public void train(RegressionDataSet dataSet, boolean parallel) { try { int workSize = iterations/SystemInfo.LogicalCores; int leftOver = iterations%SystemInfo.LogicalCores; List> futures = new ArrayList<>(SystemInfo.LogicalCores+1); ExecutorService threadPool = parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor(); if(leftOver != 0) futures.add(threadPool.submit(new RANSACWorker(baseRegressor, leftOver, dataSet))); for(int i = 0; i < SystemInfo.LogicalCores; i++) futures.add(threadPool.submit(new RANSACWorker(baseRegressor, workSize, dataSet))); PriorityQueue results = new PriorityQueue<>(SystemInfo.LogicalCores+1); for( Future futureWorker : futures ) results.add(futureWorker.get()); RANSACWorker bestResult = results.peek(); modelError = bestResult.bestError; if(Double.isInfinite(modelError)) throw new FailedToFitException("Model could not be fit, inlier set never reach minimum size"); baseRegressor = bestResult.bestModel; consensusSet = bestResult.bestConsensusSet; } catch (InterruptedException | ExecutionException ex) { Logger.getLogger(RANSAC.class.getName()).log(Level.SEVERE, null, ex); throw new FailedToFitException(ex); } } @Override public boolean supportsWeightedData() { return baseRegressor.supportsWeightedData(); } @Override public RANSAC clone() { RANSAC clone = new RANSAC(baseRegressor.clone(), iterations, initialTrainSize, minResultSize, maxPointError); return clone; } /** * Once RANSAC is complete, it maintains its trained version of the * finalized regressor. A clone of it may be retrieved from this method. * @return a clone of the learned regressor */ public Regressor getBaseRegressorClone() { return baseRegressor.clone(); } /** * Returns an boolean array where the indices correspond to data points in * the original training set. true indicates that the data point * was apart of the final consensus set. false indicates that it * was not. * * @return a boolean array indicating which points made it into the * consensus set */ public boolean[] getConsensusSet() { return Arrays.copyOf(consensusSet, consensusSet.length); } /** * Returns the model error, which is the average absolute difference between * the model and all points in the set of inliers. * * @return the error for the learned model. Returns * {@link Double#POSITIVE_INFINITY} if the model has not been trained or * failed to fit. */ public double getModelError() { return modelError; } }

Ads help maintain this website.