package jsat.classifiers.trees;

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

import jsat.classifiers.*;
import jsat.classifiers.trees.ImpurityScore.ImpurityMeasure;
import jsat.exceptions.FailedToFitException;
import jsat.linear.Vec;
import jsat.math.OnLineStatistics;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.*;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;

/**
 * This class is a 1-rule. It creates one rule that is used to classify all inputs, 
 * making it a decision tree with only one node. It can be used as a weak learner 
 * for ensemble learners, or as the nodes in a true decision tree. 
 * 

* Categorical values are handled similarly under all circumstances.
* During classification, numeric attributes are separated based on most * likely probability into their classes.
* During regression, numeric attributes are done with only binary splits, * finding the split that minimizes the total squared error sum.
*
* The Decision Stump supports missing values in training and prediction. * * @author Edward Raff */ public class DecisionStump implements Classifier, Regressor, Parameterized { private static final long serialVersionUID = -2849268862089019514L; /** * Indicates which attribute to split on */ private int splittingAttribute; /** * Used only when trained for classification. Contains information about the class being predicted */ private CategoricalData predicting; /** * Contains the information about the attributes in the data set */ private CategoricalData[] catAttributes; /** * The number of numeric features in the dataset that this Stump was trained from */ private int numNumericFeatures; /** * Used only in classification. Contains the numeric boundaries to split on */ private List boundries; /** * Used only in classification. Contains the most likely class corresponding to each boundary split */ private List owners; /** * Used only in classification. Contains the results for each of the split options */ private CategoricalResults[] results; /** * How much of the data went to each path */ protected double[] pathRatio; /** * Only used during regression. Contains the averages for each branch in * the first and 2nd index. 3rd index contains the split value. * If no split could be done, the length is zero and it contains only the * return value */ private double[] regressionResults; private ImpurityMeasure gainMethod; private boolean removeContinuousAttributes; /** * The minimum number of points that must be inside the split result for a * split to occur. */ private int minResultSplitSize = 10; /** * Creates a new decision stump */ public DecisionStump() { gainMethod = ImpurityMeasure.INFORMATION_GAIN_RATIO; removeContinuousAttributes = false; } /** * Unlike categorical values, when a continuous attribute is selected to split on, not * all values of the attribute become the same. It can be useful to split on the same * attribute multiple times. If set true, continuous attributes will be removed from * the options list. Else, they will be left in the options list. * * @param removeContinuousAttributes whether or not to remove continuous attributes on a call to {@link #trainC(java.util.List, java.util.Set) } */ public void setRemoveContinuousAttributes(boolean removeContinuousAttributes) { this.removeContinuousAttributes = removeContinuousAttributes; } public void setGainMethod(ImpurityMeasure gainMethod) { this.gainMethod = gainMethod; } public ImpurityMeasure getGainMethod() { return gainMethod; } /** * * @return The number of numeric features in the dataset that this Stump was * trained from */ protected int numNumeric() { return numNumericFeatures; } /** * * @return the number of categorical features in the dataset that this Stump * was trained from. */ protected int numCategorical() { return catAttributes.length; } /** * 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. * * @param minResultSplitSize the minimum result split size to use */ public void setMinResultSplitSize(int minResultSplitSize) { if(minResultSplitSize <= 1) throw new ArithmeticException("Min split size must be a positive value "); this.minResultSplitSize = minResultSplitSize; } /** * Returns the minimum result split size that may be considered for use as * the attribute to split on. * * @return the minimum result split size in use */ public int getMinResultSplitSize() { return minResultSplitSize; } /** * Returns the attribute that this stump has decided to use to compute * results. Numeric features start from 0, and categorical features start * from the number of numeric features. * * @return the attribute that this stump has decided to use to compute results. */ public int getSplittingAttribute() { //TODO refactor the splittingAttribute to just be in this order already if(splittingAttribute < catAttributes.length)//categorical feature return numNumericFeatures+splittingAttribute; //else, is Numerical attribute int numerAttribute = splittingAttribute - catAttributes.length; return numerAttribute; } /** * Sets the DecisionStump's predicting information. This will be set automatically * by calling {@link #train(jsat.classifiers.ClassificationDataSet) } or * {@link #train(jsat.classifiers.ClassificationDataSet, java.util.concurrent.ExecutorService) }, * but it must be called before using {@link #trainC(java.util.List, java.util.Set) }. * * @param predicting the information about the attribute that will be predicted by this classifier */ public void setPredicting(CategoricalData predicting) { this.predicting = predicting; } @Override public double regress(DataPoint data) { if(regressionResults == null) throw new RuntimeException("Decusion stump has not been trained for regression"); int path = whichPath(data); if(path >= 0) return regressionResults[path]; //else, was missing, average double avg = 0; for(int i = 0; i < pathRatio.length; i++) avg += pathRatio[i]*regressionResults[i]; return avg; } @Override public void train(RegressionDataSet dataSet, boolean parallel) { Set options = new IntSet(dataSet.getNumFeatures()); for(int i = 0; i < dataSet.getNumFeatures(); i++) options.add(i); List>> split = trainR(dataSet.getDPPList(), options, parallel); if(split == null) throw new FailedToFitException("Tree could not be fit, make sure your data is good. Potentially file a bug"); } /** * From the score for the original set that is being split, this computes * the gain as the improvement in classification from the original split. * @param origScore the score of the unsplit set * @param aSplit the splitting of the data points * @return the gain score for this split */ protected double getGain(ImpurityScore origScore, List>> aSplit) { ImpurityScore[] scores = getSplitScores(aSplit); return ImpurityScore.gain(origScore, scores); } private ImpurityScore[] getSplitScores(List>> aSplit) { ImpurityScore[] scores = new ImpurityScore[aSplit.size()]; for(int i = 0; i < aSplit.size(); i++) scores[i] = getClassGainScore(aSplit.get(i)); return scores; } /** * A value that is just above zero */ private static final double almost0 = 1e-6; /** * A value that is just below one */ private static final double almost1 = 1.0-almost0; /** * Determines which split path this data point would follow from this decision stump. * Works for both classification and regression. * * @param data the data point in question * @return the integer indicating which path to take. -1 returned if stump is not trained */ public int whichPath(DataPoint data) { int paths = getNumberOfPaths(); if(paths < 0) return paths;//Not trained else if(paths == 1)//ONLY one option, entropy was zero return 0; else if(splittingAttribute < catAttributes.length)//Same for classification and regression return data.getCategoricalValue(splittingAttribute); //else, is Numerical attribute - but regression or classification? int numerAttribute = splittingAttribute - catAttributes.length; double val = data.getNumericalValues().get(numerAttribute); if(Double.isNaN(val)) return -1;//missing if (results != null)//Categorical! { int pos = Collections.binarySearch(boundries, val); pos = pos < 0 ? -pos-1 : pos; return owners.get(pos); } else//Regression! It is trained, it would have been grabed at the top if not { if(regressionResults.length == 1) return 0; else if(val <= regressionResults[2]) return 0; else return 1; } } /** * Returns the number of paths that this decision stump leads to. The stump may not ever * direct a data point on some of the paths. A result of 1 path means that all data points * will be given the same decision, and is generated when the entropy of a set is 0.0. *

* -1 is returned for an untrained stump * * @return the number of paths this decision stump has stored */ public int getNumberOfPaths() { if(results != null)//Categorical! return results.length; else if(catAttributes != null)//Regression! if(regressionResults.length == 1) return 1; else if(splittingAttribute < catAttributes.length)//Categorical return catAttributes[splittingAttribute].getNumOfCategories(); else//Numerical is always binary return 2; return Integer.MIN_VALUE;//Not trained! } @Override public CategoricalResults classify(DataPoint data) { if(results == null) throw new RuntimeException("DecisionStump has not been trained for classification"); int path = whichPath(data); if(path >= 0) return results[path]; else//missing value case, so average { Vec tmp = results[0].getVecView().clone(); tmp.mutableMultiply(pathRatio[0]); for(int i = 1; i < results.length; i++) tmp.mutableAdd(pathRatio[i], results[i].getVecView()); return new CategoricalResults(tmp.arrayCopy()); } } /** * Returns the categorical result of the i'th path. * @param i the path to get the result for * @return the result that would be returned if a data point went down the given path * @throws IndexOutOfBoundsException if an invalid path is given * @throws NullPointerException if the stump has not been trained for classification */ public CategoricalResults result(int i) { if(i < 0 || i >= getNumberOfPaths()) throw new IndexOutOfBoundsException("Invalid path, can to return a result for path " + i); return results[i]; } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { Set splitOptions = new IntSet(dataSet.getNumFeatures()); for(int i = 0; i < dataSet.getNumFeatures(); i++) splitOptions.add(i); this.predicting = dataSet.getPredicting(); trainC(dataSet.getAsDPPList(), splitOptions, parallel); } /** * This is a helper function that does the work of training this stump. It may be * called directly by other classes that are creating decision trees to avoid * redundant repackaging of lists. * * @param dataPoints the lists of datapoint to train on, paired with the true category of each training point * @param options the set of attributes that this classifier may choose from. The attribute it does choose will be removed from the set. * @return the a list of lists, containing all the datapoints that would have followed each path. Useful for training a decision tree */ public List>> trainC(List> dataPoints, Set options) { return trainC(dataPoints, options, false); } public List>> trainC(final List> dataPoints, Set options, boolean parallel) { //TODO remove paths that have zero probability of occuring, so that stumps do not have an inflated branch value if(predicting == null) throw new RuntimeException("Predicting value has not been set"); catAttributes = dataPoints.get(0).getDataPoint().getCategoricalData(); numNumericFeatures = dataPoints.get(0).getVector().length(); final ImpurityScore origScoreObj = getClassGainScore(dataPoints); double origScore = origScoreObj.getScore(); if(origScore == 0.0 || dataPoints.size() < minResultSplitSize*2)//Then all data points belond to the same category! { results = new CategoricalResults[1];//Only one path! results[0] = new CategoricalResults(predicting.getNumOfCategories()); results[0].setProb(dataPoints.get(0).getPair(), 1.0); pathRatio = new double[]{0}; List>> toReturn = new ArrayList>>(); toReturn.add(dataPoints); return toReturn; } /** * The splitting for the split on the attribute with the best gain */ final List>> bestSplit = Collections.synchronizedList(new ArrayList<>()); /** * best gain in information we have seen so far */ final AtomicDouble bestGain = new AtomicDouble(-1); final DoubleList bestRatio = new DoubleList(); /** * The best attribute to split on */ splittingAttribute = -1; final CountDownLatch latch = new CountDownLatch(options.size()); final ThreadLocal>> localList = ThreadLocal.withInitial(()->new ArrayList<>(dataPoints)); ExecutorService ex = parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor(); for(final int attribute_to_consider : options) { ex.submit(() -> { List> DPs = localList.get(); int attribute = attribute_to_consider; final double[] gainRet = new double[]{Double.NaN}; gainRet[0] = Double.NaN; List>> aSplit; PairedReturn, List> tmp = null;//Used on numerical attributes ImpurityScore[] split_scores = null;//used for cat double weightScale = 1.0; if(attribute < catAttributes.length)//Then we are doing a categorical split { //Create a list of lists to hold the split variables aSplit = listOfLists(catAttributes[attribute].getNumOfCategories()); split_scores = new ImpurityScore[aSplit.size()]; for(int i=0; i < split_scores.length; i++) split_scores[i] = new ImpurityScore(predicting.getNumOfCategories(), gainMethod); List> wasMissing = new ArrayList>(0); double missingSum = 0.0; //Now seperate the values in our current list into their proper split bins for(DataPointPair dpp : DPs) { int val = dpp.getDataPoint().getCategoricalValue(attribute); double weight = dpp.getDataPoint().getWeight(); if(val >= 0) { aSplit.get(val).add(dpp); split_scores[val].addPoint(weight, dpp.getPair()); } else { wasMissing.add(dpp); missingSum += weight; } } int pathsTaken = 0; for(List> split : aSplit) if(!split.isEmpty()) pathsTaken++; if(pathsTaken <= 1)//not a good path, avoid looping on this junk. Can be caused by missing data { latch.countDown(); return; } if(missingSum > 0)//move missing values into others { double newSum = (origScoreObj.getSumOfWeights()-missingSum); weightScale = newSum/origScoreObj.getSumOfWeights(); double[] fracs = new double[split_scores.length]; for(int i = 0; i < fracs.length; i++) fracs[i] = split_scores[i].getSumOfWeights()/newSum; distributMissing(aSplit, fracs, wasMissing); } } else//Spliting on a numerical value { attribute -= catAttributes.length; int N = predicting.getNumOfCategories(); //Create a list of lists to hold the split variables aSplit = listOfLists(2);//Size at least 2 split_scores = new ImpurityScore[2]; tmp = createNumericCSplit(DPs, N, attribute, aSplit, origScoreObj, gainRet, split_scores); if(tmp == null) { latch.countDown(); return; } //Fix it back so it can be used below attribute+= catAttributes.length; } //Now everything is seperated! double gain;//= Double.isNaN(gainRet[0]) ? : gainRet[0]; if(!Double.isNaN(gainRet[0])) gain = gainRet[0]; else { if(split_scores == null) split_scores = getSplitScores(aSplit); gain = ImpurityScore.gain(origScoreObj, weightScale, split_scores); } if(gain > bestGain.get()) { synchronized(bestRatio) { if(gain > bestGain.get())//double check incase changed { bestGain.set(gain); splittingAttribute = attribute; bestSplit.clear(); bestSplit.addAll(aSplit); bestRatio.clear(); double sum = 1e-8; for(int i = 0; i < split_scores.length; i++) { sum += split_scores[i].getSumOfWeights(); bestRatio.add(split_scores[i].getSumOfWeights()); } for(int i = 0; i < split_scores.length; i++) bestRatio.set(i, bestRatio.getD(i)/sum); if(attribute >= catAttributes.length) { boundries = tmp.getFirstItem(); owners = tmp.getSecondItem(); } } } } latch.countDown(); }); } try { latch.await(); } catch (InterruptedException ex1) { Logger.getLogger(DecisionStump.class.getName()).log(Level.SEVERE, null, ex1); throw new FailedToFitException(ex1); } if(splittingAttribute == -1)//We could not find a good split at all { bestSplit.clear(); bestSplit.add(dataPoints); CategoricalResults badResult = new CategoricalResults(predicting.getNumOfCategories()); for(DataPointPair dpp : dataPoints) badResult.incProb(dpp.getPair(), 1.0); badResult.normalize(); results = new CategoricalResults[] {badResult}; pathRatio = new double[]{1}; return bestSplit; } if(splittingAttribute < catAttributes.length || removeContinuousAttributes) options.remove(splittingAttribute); results = new CategoricalResults[bestSplit.size()]; pathRatio = bestRatio.getVecView().arrayCopy(); for(int i = 0; i < bestSplit.size(); i++) { results[i] = new CategoricalResults(predicting.getNumOfCategories()); for(DataPointPair dpp : bestSplit.get(i)) results[i].incProb(dpp.getPair(), dpp.getDataPoint().getWeight()); results[i].normalize(); } return bestSplit; } /** * * @param dataPoints the original list of data points * @param N number of predicting target options * @param attribute the numeric attribute to try and find a split on * @param aSplit the list of lists to place the results of splitting in * @param origScore the score value for the data set we are splitting * @param finalGain array used to reference a double that can be returned. * If this method determined the gain in order to find the split, it sets * the value at index zero to the gain it computed. May be null, in which * case it is ignored. * @return A pair of lists of the same size. The list of doubles containing * the split boundaries, and the integers containing the path number. * Multiple splits could go down the same path. */ private PairedReturn, List> createNumericCSplit( List> dataPoints, int N, final int attribute, List>> aSplit, ImpurityScore origScore, double[] finalGain, ImpurityScore[] subScores) { //cache misses are killing us, move data into a double[] to get more juice! double[] vals = new double[dataPoints.size()];//TODO put this in a thread local somewhere and re-use int wasNaN = 0; for(int i = 0; i < dataPoints.size()-wasNaN; i++) { double val = dataPoints.get(i).getVector().get(attribute); if(!Double.isNaN(val)) vals[i] = val; else { Collections.swap(dataPoints, vals.length-wasNaN-1, i); wasNaN++; i--;//go back and do this one again! } } //do what i want! Collection> paired = (Collection> )(Collection )Arrays.asList(dataPoints); QuickSort.sort(vals, 0, vals.length-wasNaN, paired );//sort the numeric values and put our original list of data points in the correct order at the same time double bestGain = Double.NEGATIVE_INFINITY; double bestSplit = Double.NEGATIVE_INFINITY; int splitIndex = -1; ImpurityScore rightSide = origScore.clone(); ImpurityScore leftSide = new ImpurityScore(N, gainMethod); //remove any Missing Value nodes from considering from the start double nanWeightRemoved = 0; for(int i = dataPoints.size()-wasNaN; i < dataPoints.size(); i++) { double weight = dataPoints.get(i).getDataPoint().getWeight(); int truth = dataPoints.get(i).getPair(); nanWeightRemoved += weight; rightSide.removePoint(weight, truth); } double wholeRescale = rightSide.getSumOfWeights()/(rightSide.getSumOfWeights()+nanWeightRemoved); for(int i = 0; i < minResultSplitSize; i++) { if(i >= dataPoints.size()) System.out.println("WHAT?"); double weight = dataPoints.get(i).getDataPoint().getWeight(); int truth = dataPoints.get(i).getPair(); leftSide.addPoint(weight, truth); rightSide.removePoint(weight, truth); } for(int i = minResultSplitSize; i < dataPoints.size()-minResultSplitSize-1-wasNaN; i++) { DataPointPair dpp = dataPoints.get(i); rightSide.removePoint(dpp.getDataPoint(), dpp.getPair()); leftSide.addPoint(dpp.getDataPoint(), dpp.getPair()); double leftVal = vals[i]; double rightVal = vals[i+1]; if( (rightVal-leftVal) < 1e-14 )//Values are too close! continue; double curGain = ImpurityScore.gain(origScore, wholeRescale, leftSide, rightSide); if(curGain >= bestGain) { double curSplit = (leftVal + rightVal) / 2; bestGain = curGain; bestSplit = curSplit; splitIndex = i+1; subScores[0] = leftSide.clone(); subScores[1] = rightSide.clone(); } } if(splitIndex == -1) return null; if(finalGain != null) finalGain[0] = bestGain; aSplit.set(0, new ArrayList<>(dataPoints.subList(0, splitIndex))); aSplit.set(1, new ArrayList<>(dataPoints.subList(splitIndex, dataPoints.size()-wasNaN))); if(wasNaN > 0) { double weightScale = leftSide.getSumOfWeights()/(leftSide.getSumOfWeights() + rightSide.getSumOfWeights()+0.0); distributMissing(aSplit, new double[]{weightScale, 1-weightScale}, dataPoints.subList(dataPoints.size()-wasNaN, dataPoints.size())); } PairedReturn, List> tmp = new PairedReturn<>( Arrays.asList(bestSplit, Double.POSITIVE_INFINITY), Arrays.asList(0, 1)); return tmp; } /** * Distributes a list of datapoints that had missing values to each split, re-weighted by the indicated fractions * @param splits a list of lists, where each inner list is a split * @param hadMissing the list of datapoints that had missing values */ static protected void distributMissing(List>> splits, List> hadMissing) { double[] fracs = new double[splits.size()]; for(int i = 0; i < splits.size(); i++) for(DataPointPair dpp : splits.get(i)) fracs[i] += dpp.getDataPoint().getWeight(); double sum = 0; for(double d : fracs) sum += d; for(int i = 0; i < fracs.length; i++) fracs[i] /= sum; distributMissing(splits, fracs, hadMissing); } /** * Distributes a list of datapoints that had missing values to each split, re-weighted by the indicated fractions * @param splits a list of lists, where each inner list is a split * @param fracs the fraction of weight to each split, should sum to one * @param hadMissing the list of datapoints that had missing values */ static protected void distributMissing(List>> splits, double[] fracs, List> hadMissing) { for (DataPointPair dpp : hadMissing) { DataPoint dp = dpp.getDataPoint(); Vec vec = dp.getNumericalValues(); int[] cats = dp.getCategoricalValues(); CategoricalData[] lab = dp.getCategoricalData(); for (int i = 0; i < fracs.length; i++) { double nw = fracs[i] * dp.getWeight(); if(Double.isNaN(nw))//happens when no weight is available continue; if(nw <= 1e-13) continue; DataPointPair dp_i = new DataPointPair(new DataPoint(vec, cats, lab, nw), dpp.getPair()); splits.get(i).add(dp_i); } } } public List>> trainR(final List> dataPoints, Set options) { return trainR(dataPoints, options, false); } public List>> trainR(final List> dataPoints, Set options, boolean parallel) { catAttributes = dataPoints.get(0).getDataPoint().getCategoricalData(); numNumericFeatures = dataPoints.get(0).getVector().length(); //Not enough points for a split to occur if(dataPoints.size() <= minResultSplitSize*2) { splittingAttribute = catAttributes.length; regressionResults = new double[1]; double avg = 0.0; double sum = 0.0; for(DataPointPair dpp : dataPoints ) { double weight = dpp.getDataPoint().getWeight(); avg += dpp.getPair()*weight; sum += weight; } regressionResults[0] = avg/sum; List>> toRet = new ArrayList<>(1); toRet.add(dataPoints); return toRet; } final List>> bestSplit = new ArrayList<>(); final AtomicDouble lowestSplitSqrdError = new AtomicDouble(Double.MAX_VALUE); final ThreadLocal>> localList = ThreadLocal.withInitial(()->new ArrayList<>(dataPoints)); ExecutorService ex = parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor(); final CountDownLatch latch = new CountDownLatch(options.size()); for(int attribute_to_consider : options) { final int attribute = attribute_to_consider; ex.submit(() -> { final List> DPs = localList.get(); List>> thisSplit = null; //The squared error for this split double thisSplitSqrdErr = Double.MAX_VALUE; //Contains the means of each split double[] thisMeans = null; double[] thisRatio; if(attribute < catAttributes.length) { thisSplit = listOfListsD(catAttributes[attribute].getNumOfCategories()); OnLineStatistics[] stats = new OnLineStatistics[thisSplit.size()]; thisRatio = new double[thisSplit.size()]; for(int i = 0; i < thisSplit.size(); i++) stats[i] = new OnLineStatistics(); //Now seperate the values in our current list into their proper split bins List> wasMissing = new ArrayList>(0); for(DataPointPair dpp : DPs) { int category = dpp.getDataPoint().getCategoricalValue(attribute); if(category >= 0) { thisSplit.get(category).add(dpp); stats[category].add(dpp.getPair(), dpp.getDataPoint().getWeight()); } else//was negative, missing value { wasMissing.add(dpp); } } thisMeans = new double[stats.length]; thisSplitSqrdErr = 0.0; double sum = 0; for(int i = 0; i < stats.length; i++) { sum += (thisRatio[i] = stats[i].getSumOfWeights()); thisSplitSqrdErr += stats[i].getVarance()*stats[i].getSumOfWeights(); thisMeans[i] = stats[i].getMean(); } for(int i = 0; i < stats.length; i++) thisRatio[i] /= sum; if(!wasMissing.isEmpty()) distributMissing(thisSplit, thisRatio, wasMissing); } else//Findy a binary split that reduces the variance! { final int numAttri = attribute - catAttributes.length; //We need our list in sorted order by attribute! Comparator> dppDoubleSorter = new Comparator>() { @Override public int compare(DataPointPair o1, DataPointPair o2) { return Double.compare(o1.getVector().get(numAttri), o2.getVector().get(numAttri)); } }; Collections.sort(DPs, dppDoubleSorter);//this will put nans to the right //2 passes, first to sum up the right side, 2nd to move down the grow the left side OnLineStatistics rightSide = new OnLineStatistics(); OnLineStatistics leftSide = new OnLineStatistics(); int nans = 0; for(DataPointPair dpp : DPs) if(!Double.isNaN(dpp.getVector().get(numAttri))) rightSide.add(dpp.getPair(), dpp.getDataPoint().getWeight()); else nans++; int bestS = 0; thisSplitSqrdErr = Double.POSITIVE_INFINITY; final double allWeight = rightSide.getSumOfWeights(); thisMeans = new double[3]; thisRatio = new double[2]; for(int i = 0; i < DPs.size()-nans; i++) { DataPointPair dpp = DPs.get(i); double weight = dpp.getDataPoint().getWeight(); double val = dpp.getPair(); rightSide.remove(val, weight); leftSide.add(val, weight); if(i < minResultSplitSize) continue; else if(i > DPs.size()-minResultSplitSize-nans) break; double tmpSVariance = rightSide.getVarance()*rightSide.getSumOfWeights() + leftSide.getVarance()*leftSide.getSumOfWeights(); if(tmpSVariance < thisSplitSqrdErr && !Double.isInfinite(tmpSVariance))//Infinity can occur once the weights get REALY small { thisSplitSqrdErr = tmpSVariance; bestS = i; thisMeans[0] = leftSide.getMean(); thisMeans[1] = rightSide.getMean(); //Third spot contains the split value! thisMeans[2] = (DPs.get(bestS).getVector().get(numAttri) + DPs.get(bestS+1).getVector().get(numAttri))/2.0; thisRatio[0] = leftSide.getSumOfWeights()/allWeight; thisRatio[1] = rightSide.getSumOfWeights()/allWeight; } } if(DPs.size() - nans >= minResultSplitSize) { //Now we have the binary split that minimizes the variances of the 2 sets, thisSplit = listOfListsD(2); thisSplit.get(0).addAll(DPs.subList(0, bestS+1)); thisSplit.get(1).addAll(DPs.subList(bestS+1, DPs.size()-nans)); if(nans > 0) distributMissing(thisSplit, thisRatio, DPs.subList(DPs.size()-nans, DPs.size())); } else//not a good split, we can't trust it thisSplitSqrdErr = Double.NEGATIVE_INFINITY; } //numerical issue check. When we get a REALLy good split, error can be a tiny negative value due to numerical instability. Check and swap sign if small if(Math.abs(thisSplitSqrdErr) < 1e-13)//no need to check sign, make simpler thisSplitSqrdErr = Math.abs(thisSplitSqrdErr); //Now compare what weve done if(thisSplitSqrdErr >= 0 && thisSplitSqrdErr < lowestSplitSqrdError.get())//how did we get -Inf? { synchronized(bestSplit) { if(thisSplitSqrdErr < lowestSplitSqrdError.get()) { lowestSplitSqrdError.set(thisSplitSqrdErr); bestSplit.clear(); bestSplit.addAll(thisSplit); splittingAttribute = attribute; regressionResults = thisMeans; pathRatio = thisRatio; } } } latch.countDown(); }); } try { latch.await(); } catch (InterruptedException ex1) { Logger.getLogger(DecisionStump.class.getName()).log(Level.SEVERE, null, ex1); throw new FailedToFitException(ex1); } //Removal of attribute from list if needed if(splittingAttribute < catAttributes.length || removeContinuousAttributes) options.remove(splittingAttribute); if(bestSplit.size() == 0)//no good option selected. Keep old behavior, return null in that case return null; return bestSplit; } private static List>> listOfLists(int n ) { List>> aSplit = new ArrayList<>(n); for (int i = 0; i < n; i++) aSplit.add(new ArrayList<>()); return aSplit; } private static List>> listOfListsD(int n ) { List>> aSplit = new ArrayList<>(n); for (int i = 0; i < n; i++) aSplit.add(new ArrayList<>()); return aSplit; } @Override public boolean supportsWeightedData() { return true; } private ImpurityScore getClassGainScore(List> dataPoints) { ImpurityScore cgs = new ImpurityScore(predicting.getNumOfCategories(), gainMethod); for(DataPointPair dpp : dataPoints) cgs.addPoint(dpp.getDataPoint(), dpp.getPair()); return cgs; } @Override public DecisionStump clone() { DecisionStump copy = new DecisionStump(); if(this.catAttributes != null) copy.catAttributes = CategoricalData.copyOf(catAttributes); if(this.results != null) { copy.results = new CategoricalResults[this.results.length]; for(int i = 0; i < this.results.length; i++ ) copy.results[i] = this.results[i].clone(); } copy.removeContinuousAttributes = this.removeContinuousAttributes; copy.splittingAttribute = this.splittingAttribute; if(this.boundries != null) copy.boundries = new DoubleList(this.boundries); if(this.owners != null) copy.owners = new IntList(this.owners); if(this.predicting != null) copy.predicting = this.predicting.clone(); if(regressionResults != null) copy.regressionResults = Arrays.copyOf(this.regressionResults, this.regressionResults.length); if(pathRatio != null) copy.pathRatio = Arrays.copyOf(this.pathRatio, this.pathRatio.length); copy.minResultSplitSize = this.minResultSplitSize; copy.gainMethod = this.gainMethod; copy.numNumericFeatures = this.numNumericFeatures; return copy; } }

Ads help maintain this website.