package jsat.classifiers.trees;

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

import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.classifiers.trees.ImpurityScore.ImpurityMeasure;
import static jsat.classifiers.trees.TreePruner.*;
import jsat.classifiers.trees.TreePruner.PruningMethod;
import jsat.exceptions.FailedToFitException;
import jsat.exceptions.ModelMismatchException;
import jsat.parameters.Parameter;
import jsat.parameters.Parameterized;
import jsat.regression.RegressionDataSet;
import jsat.regression.Regressor;
import jsat.utils.*;
import jsat.utils.concurrent.ParallelUtils;

/**
 * Creates a decision tree from {@link DecisionStump DecisionStumps}. How this
 * tree performs is controlled by pruning method selected, and the methods used
 * in the stump.
* A Decision Tree supports missing values in training and prediction. * * @author Edward Raff */ public class DecisionTree implements Classifier, Regressor, Parameterized, TreeLearner { private static final long serialVersionUID = 9220980056440500214L; private int maxDepth; private int minSamples; private Node root; private CategoricalData predicting; private PruningMethod pruningMethod; /** * What portion of the training data will be set aside for pruning. */ private double testProportion; /** * Base decision stump used to clone so that we can keep certain features * inside the stump instead of duplicating them here. */ private DecisionStump baseStump = new DecisionStump(); @Override public double regress(DataPoint data) { if(data.numNumericalValues() != root.stump.numNumeric() || data.numCategoricalValues() != root.stump.numCategorical()) throw new ModelMismatchException("Tree expected " + root.stump.numNumeric() + " numeric and " + root.stump.numCategorical() + " categorical features, instead received data with " + data.numNumericalValues() + " and " + data.numCategoricalValues() + " features respectively"); return root.regress(data); } @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); train(dataSet, options, parallel); } public void train(RegressionDataSet dataSet, Set options) { train(dataSet, options, false); } public void train(RegressionDataSet dataSet, Set options, boolean parallel) { ModifiableCountDownLatch mcdl = new ModifiableCountDownLatch(1); root = makeNodeR(dataSet.getDPPList(), options, 0, parallel, mcdl); try { mcdl.await(); } catch (InterruptedException ex) { Logger.getLogger(DecisionTree.class.getName()).log(Level.SEVERE, null, ex); } if(root == null)//fitting issure, most likely too few datums. try just a stump { DecisionStump stump = new DecisionStump(); stump.train(dataSet, parallel); root = new Node(stump); } //TODO add pruning for regression } /** * Creates a Decision Tree that uses {@link PruningMethod#REDUCED_ERROR} * pruning on a held out 10% of the data. */ public DecisionTree() { this(Integer.MAX_VALUE, 10, PruningMethod.REDUCED_ERROR, 0.1); } /** * Creates a Decision Tree that does not do any pruning, and is built out only to the specified depth * @param maxDepth */ public DecisionTree(int maxDepth) { this(maxDepth, 10, PruningMethod.NONE, 0.00001); } /** * Creates a new decision tree classifier * * @param maxDepth the maximum depth of the tree to create * @param minSamples the minimum number of samples needed to continue branching * @param pruningMethod the method of pruning to use after construction * @param testProportion the proportion of the data set to put aside to use for pruning */ public DecisionTree(int maxDepth, int minSamples, PruningMethod pruningMethod, double testProportion) { setMaxDepth(maxDepth); setMinSamples(minSamples); setPruningMethod(pruningMethod); setTestProportion(testProportion); } /** * Copy constructor * @param toCopy the object to copy */ protected DecisionTree(DecisionTree toCopy) { this.maxDepth = toCopy.maxDepth; this.minSamples = toCopy.minSamples; if(toCopy.root != null) this.root = toCopy.root.clone(); if(toCopy.predicting != null) this.predicting = toCopy.predicting.clone(); this.pruningMethod = toCopy.pruningMethod; this.testProportion = toCopy.testProportion; this.baseStump = toCopy.baseStump.clone(); } /** * Returns a Decision Tree with settings initialized so that its behavior is * approximately that of the C4.5 decision tree algorithm when used on * classification data. The exact behavior not identical, and certain * base cases may not behave in the exact same manner. However, it uses all * of the same general algorithms.

* The returned tree does not perform or support *
    *
  • discrete attribute grouping
  • *
  • windowing
  • *
  • subsidiary cutpoints (soft boundaries)
  • *
* * @return a decision tree that will behave in a manner similar to C4.5 */ public static DecisionTree getC45Tree() { DecisionTree tree = new DecisionTree(); tree.setMinResultSplitSize(2); tree.setMinSamples(3); tree.setMinResultSplitSize(2); tree.setTestProportion(1.0); tree.setPruningMethod(PruningMethod.ERROR_BASED); tree.baseStump.setGainMethod(ImpurityMeasure.INFORMATION_GAIN_RATIO); return tree; } public void setGainMethod(ImpurityMeasure gainMethod) { baseStump.setGainMethod(gainMethod); } public ImpurityMeasure getGainMethod() { return baseStump.getGainMethod(); } /** * 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 size the minimum result split size to use */ public void setMinResultSplitSize(int size) { baseStump.setMinResultSplitSize(size); } /** * 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 baseStump.getMinResultSplitSize(); } /** * Sets the maximum depth that this classifier may build trees to. * @param maxDepth the maximum depth of the trained tree */ public void setMaxDepth(int maxDepth) { if(maxDepth < 0) throw new RuntimeException("The maximum depth must be a positive number"); this.maxDepth = maxDepth; } /** * The maximum depth that this classifier may build trees to. * @return the maximum depth that this classifier may build trees to. */ public int getMaxDepth() { return maxDepth; } /** * Sets the minimum number of samples needed at each step in order to continue branching * @param minSamples the minimum number of samples needed to branch */ public void setMinSamples(int minSamples) { this.minSamples = minSamples; } /** * The minimum number of samples needed at each step in order to continue branching * @return the minimum number of samples needed at each step in order to continue branching */ public int getMinSamples() { return minSamples; } /** * Sets the method of pruning that will be used after tree construction * @param pruningMethod the method of pruning that will be used after tree construction * @see PruningMethod */ public void setPruningMethod(PruningMethod pruningMethod) { this.pruningMethod = pruningMethod; } /** * Returns the method of pruning used after tree construction * @return the method of pruning used after tree construction */ public PruningMethod getPruningMethod() { return pruningMethod; } /** * Returns the proportion of the training set that is put aside to perform pruning with * @return the proportion of the training set that is put aside to perform pruning with */ public double getTestProportion() { return testProportion; } /** * Sets the proportion of the training set that is put aside to perform pruning with. *
NOTE: The values 0 and 1 are special cases.
* 0 indicates that no pruning will occur regardless of the set pruning method
* 1 indicates that the training set will be used as the testing set. This is * valid for some pruning methods. * @param testProportion the proportion, must be in the range [0, 1] */ public void setTestProportion(double testProportion) { if(testProportion < 0 || testProportion > 1 || Double.isInfinite(testProportion) || Double.isNaN(testProportion)) throw new ArithmeticException("Proportion must be in the range [0, 1], not " + testProportion); this.testProportion = testProportion; } @Override public CategoricalResults classify(DataPoint data) { if(data.numNumericalValues() != root.stump.numNumeric() || data.numCategoricalValues() != root.stump.numCategorical()) throw new ModelMismatchException("Tree expected " + root.stump.numNumeric() + " numeric and " + root.stump.numCategorical() + " categorical features, instead received data with " + data.numNumericalValues() + " and " + data.numCategoricalValues() + " features respectively"); return root.classify(data); } @Override public void train(ClassificationDataSet dataSet, boolean parallel) { Set options = new IntSet(dataSet.getNumFeatures()); for(int i = 0; i < dataSet.getNumFeatures(); i++) options.add(i); trainC(dataSet, options, parallel); } /** * Performs exactly the same as * {@link #train(jsat.classifiers.ClassificationDataSet, java.util.concurrent.ExecutorService) }, * but the user can specify a subset of the features to be considered. * * @param dataSet the data set to train from * @param options the subset of features to split on * @param parallel whether or not to use multiple cores in training */ protected void trainC(ClassificationDataSet dataSet, Set options, boolean parallel) { if(dataSet.getSampleSize() < minSamples) throw new FailedToFitException("There are only " + dataSet.getSampleSize() + " data points in the sample set, at least " + minSamples + " are needed to make a tree"); this.predicting = dataSet.getPredicting(); ModifiableCountDownLatch mcdl = new ModifiableCountDownLatch(1); List> dataPoints = dataSet.getAsDPPList(); List> testPoints = new ArrayList<>(); if(pruningMethod != PruningMethod.NONE && testProportion != 0.0)//Then we need to set aside a testing set { if(testProportion != 1) { int testSize = (int) (dataPoints.size()*testProportion); Random rand = new Random(testSize); for(int i = 0; i < testSize; i++) testPoints.add(dataPoints.remove(rand.nextInt(dataPoints.size()))); } else testPoints.addAll(dataPoints); } this.root = makeNodeC(dataPoints, options, 0, parallel, mcdl); try { mcdl.await(); } catch (InterruptedException ex) { System.err.println(ex.getMessage()); Logger.getLogger(DecisionTree.class.getName()).log(Level.SEVERE, null, ex); } if(root == null)//fitting issure, most likely too few datums. try just a stump { DecisionStump stump = new DecisionStump(); stump.train(dataSet, parallel); root = new Node(stump); } else prune(root, pruningMethod, testPoints); } /** * Makes a new node for classification * @param dataPoints the list of data points paired with their class * @param options the attributes that this tree may select from * @param depth the current depth of the tree * @param parallel whether or not to use multiple threads when training * @param mcdl count down latch * @return the node created, or null if no node was created */ protected Node makeNodeC(List> dataPoints, final Set options, final int depth, final boolean parallel, final ModifiableCountDownLatch mcdl) { //figure out what level of parallelism we are going to use, feature wise or depth wise boolean mePara = (1L<= SystemInfo.LogicalCores*2;//should the NEXT node use the stump parallelism if(depth > maxDepth || options.isEmpty() || dataPoints.size() < minSamples || dataPoints.isEmpty()) { mcdl.countDown(); return null; } DecisionStump stump = baseStump.clone(); stump.setPredicting(this.predicting); final List>> splits; if(mePara) splits = stump.trainC(dataPoints, options, parallel); else splits = stump.trainC(dataPoints, options); final Node node = new Node(stump); if(stump.getNumberOfPaths() > 1)//If there is 1 path, we are perfectly classifier - nothing more to do for(int i = 0; i < node.paths.length; i++) { final int ii = i; final List> splitI = splits.get(i); mcdl.countUp(); if(depthPara) { (parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor()).submit(() -> { node.paths[ii] = makeNodeC(splitI, new IntSet(options), depth+1, parallel, mcdl); }); } else node.paths[ii] = makeNodeC(splitI, new IntSet(options), depth+1, parallel, mcdl); } mcdl.countDown(); return node; } /** * Makes a new node for regression * @param dataPoints the list of data points paired with their associated real value * @param options the attributes that this tree may select from * @param depth the current depth of the tree * @param parallel whether or not to perform parallel computation * @param mcdl count down latch * @return the node created, or null if no node was created */ protected Node makeNodeR(List> dataPoints, final Set options, final int depth, final boolean parallel, final ModifiableCountDownLatch mcdl) { //figure out what level of parallelism we are going to use, feature wise or depth wise boolean mePara = (1L<= SystemInfo.LogicalCores*2;//should the NEXT node use the stump parallelism if(depth > maxDepth || options.isEmpty() || dataPoints.size() < minSamples || dataPoints.isEmpty()) { mcdl.countDown(); return null; } DecisionStump stump = baseStump.clone(); final List>> splits; if(mePara) splits = stump.trainR(dataPoints, options, parallel); else splits = stump.trainR(dataPoints, options); if(splits == null)//an error occured, probably not enough data for many categorical values { mcdl.countDown(); return null; } final Node node = new Node(stump); if(stump.getNumberOfPaths() > 1)//If there is 1 path, we are perfectly classifier - nothing more to do for(int i = 0; i < node.paths.length; i++) { final int ii = i; final List> splitI = splits.get(i); mcdl.countUp(); if(depthPara) { (parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor()) .submit(() -> { node.paths[ii] = makeNodeR(splitI, new IntSet(options), depth+1, parallel, mcdl); }); } else node.paths[ii] = makeNodeR(splitI, new IntSet(options), depth+1, parallel, mcdl); } mcdl.countDown(); return node; } public void trainC(ClassificationDataSet dataSet, Set options) { trainC(dataSet, options, false); } @Override public boolean supportsWeightedData() { return true; } @Override public DecisionTree clone() { DecisionTree copy = new DecisionTree(maxDepth, minSamples, pruningMethod, testProportion); if(this.predicting != null) copy.predicting = this.predicting.clone(); if(this.root != null) copy.root = this.root.clone(); copy.baseStump = this.baseStump.clone(); return copy; } @Override public TreeNodeVisitor getTreeNodeVisitor() { return root; } protected static class Node extends TreeNodeVisitor { private static final long serialVersionUID = -7507748424627088734L; final protected DecisionStump stump; protected Node[] paths; public Node(DecisionStump stump) { this.stump = stump; paths = new Node[stump.getNumberOfPaths()]; } @Override public double getPathWeight(int path) { return stump.pathRatio[path]; } @Override public boolean isLeaf() { if(paths == null ) return true; for(int i = 0; i < paths.length; i++) if(paths[i] != null) return false; return true; } @Override public int childrenCount() { return paths.length; } @Override public CategoricalResults localClassify(DataPoint dp) { return stump.classify(dp); } @Override public double localRegress(DataPoint dp) { return stump.regress(dp); } @Override public Node clone() { Node copy = new Node( (DecisionStump)this.stump.clone()); for(int i = 0; i < this.paths.length; i++) copy.paths[i] = this.paths[i] == null ? null : this.paths[i].clone(); return copy; } @Override public TreeNodeVisitor getChild(int child) { if(isLeaf()) return null; else return paths[child]; } @Override public void setPath(int child, TreeNodeVisitor node) { if(node instanceof Node) paths[child] = (Node) node; else super.setPath(child, node); } @Override public void disablePath(int child) { paths[child] = null; } @Override public int getPath(DataPoint dp) { return stump.whichPath(dp); } @Override public boolean isPathDisabled(int child) { if(isLeaf()) return true; return paths[child] == null; } @Override public Collection featuresUsed() { IntList used = new IntList(1); used.add(stump.getSplittingAttribute()); return used; } } @Override public List getParameters() { List toRet = new ArrayList<>(Parameter.getParamsFromMethods(this)); for (Parameter param : baseStump.getParameters())//We kno the two setGainMethods will colide if(!param.getName().contains("Gain Method") && !param.getName().contains("Numeric Handling")) toRet.add(param); return Collections.unmodifiableList(toRet); } }

Ads help maintain this website.