package jsat.classifiers.trees;
import java.util.ArrayList;
import java.util.List;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.math.SpecialMath;
/**
* Provides post-pruning algorithms for any decision tree that can be altered
* using the {@link TreeNodeVisitor}. Pruning is done with a held out testing
* set
*
* All pruning methods handle missing values
*
* NOTE: API still under work, expect changes
*
* @author Edward Raff
*/
public class TreePruner
{
private TreePruner()
{
}
/**
* The method of pruning to use
*/
public static enum PruningMethod
{
/**
* The tree will be left as generated, no pruning will occur.
*/
NONE,
/**
* The tree will be pruned in a bottom up fashion, removing
* leaf nodes if the removal does not reduce the accuracy on the testing
* set
*/
REDUCED_ERROR,
/**
* Bottom-Up pessimistic pruning using Error based Pruning from the
* C4.5 algorithm. If the node visitor supports
* {@link TreeNodeVisitor#setPath(int, jsat.classifiers.trees.TreeNodeVisitor) }
* it will perform sub tree replacement for the maximal sub tree.
* The default Confidence (CF) is 0.25, as used in the C4.5 algorithm.
*
* NOTE: For the one case where the root would be pruned by taking the sub tree
* with the most nodes, this implementation will not perform that step. However,
* this is incredibly rare - and otherwise performs the same.
*/
ERROR_BASED
};
/**
* Performs pruning starting from the root node of a tree
* @param root the root node of a decision tree
* @param method the pruning method to use
* @param testSet the test set of data points to use for pruning
*/
public static void prune(TreeNodeVisitor root, PruningMethod method, ClassificationDataSet testSet)
{
prune(root, method, testSet.getAsDPPList());
}
/**
* Performs pruning starting from the root node of a tree
* @param root the root node of a decision tree
* @param method the pruning method to use
* @param testSet the test set of data points to use for pruning
*/
public static void prune(TreeNodeVisitor root, PruningMethod method, List> testSet)
{
//TODO add vargs for extra arguments that may be used by pruning methods
if(method == PruningMethod.NONE )
return;
else if(method == PruningMethod.REDUCED_ERROR)
pruneReduceError(null, -1, root, testSet);
else if(method == PruningMethod.ERROR_BASED)
pruneErrorBased(null, -1, root, testSet, 0.25);
else
throw new RuntimeException("BUG: please report");
}
/**
* Performs pruning to reduce error on the testing set
* @param parent the parent of the current node, may be null
* @param pathFollowed the path from the parent that lead to the current node
* @param current the current node being considered
* @param testSet the set of testing points to apply to this node
* @return the number of nodes pruned from the tree
*/
private static int pruneReduceError(TreeNodeVisitor parent, int pathFollowed, TreeNodeVisitor current, List> testSet)
{
if(current == null)
return 0;
int nodesPruned = 0;
//If we are not a leaf, prune our children
if(!current.isLeaf())
{
//Each child should only be given testing points that would decend down that path
int numSplits = current.childrenCount();
List>> splits = new ArrayList>>(numSplits);
List> hadMissing = new ArrayList>(0);
//TODO if splits = 2, reorder the original array and use subList to return memory efficent references
for (int i = 0; i < numSplits; i++)
splits.add(new ArrayList>());
for (DataPointPair dpp : testSet)
{
int path = current.getPath(dpp.getDataPoint());
if(path >= 0)
splits.get(path).add(dpp);
else//missing value
hadMissing.add(dpp);
}
if(!hadMissing.isEmpty())
DecisionStump.distributMissing(splits, hadMissing);
for (int i = numSplits - 1; i >= 0; i--)//Go backwards so child removals dont affect indices
nodesPruned += pruneReduceError(current, i, current.getChild(i), splits.get(i));
}
//If we pruned all our children, we may have become a leaf! Should we prune ourselves?
if(current.isLeaf() && parent != null)//Compare this nodes accuracy vs its parrent
{
double childCorrect = 0;
double parrentCorrect = 0;
for(DataPointPair dpp : testSet)
{
DataPoint dp = dpp.getDataPoint();
int truth = dpp.getPair();
if(current.localClassify(dp).mostLikely() == truth)
childCorrect += dp.getWeight();
if(parent.localClassify(dp).mostLikely() == truth)
parrentCorrect += dp.getWeight();
}
if(parrentCorrect >= childCorrect)//We use >= b/c if they are the same, we assume smaller trees are better
{
parent.disablePath(pathFollowed);
return nodesPruned+1;//We prune our children and ourselves
}
return nodesPruned;
}
return nodesPruned;
}
/**
*
* @param parent the parent node, or null if there is no parent
* @param pathFollowed the path from the parent node to the current node
* @param current the current node to evaluate
* @param testSet the set of points to estimate error from
* @param alpha the Confidence
* @return expected upperbound on errors
*/
private static double pruneErrorBased(TreeNodeVisitor parent, int pathFollowed, TreeNodeVisitor current, List> testSet, double alpha)
{
//TODO this does a lot of redundant computation. Re-write this code to keep track of where datapoints came from to avoid redudancy.
if(current == null || testSet.isEmpty())
return 0;
else if(current.isLeaf())//return number of errors
{
int errors = 0;
double N = 0;
for(DataPointPair dpp : testSet)
{
if(current.localClassify(dpp.getDataPoint()).mostLikely() != dpp.getPair())
errors+=dpp.getDataPoint().getWeight();
N+=dpp.getDataPoint().getWeight();
}
return computeBinomialUpperBound(N, alpha, errors);
}
List>> splitSet = new ArrayList>>(current.childrenCount());
List> hadMissing = new ArrayList>(0);
for(int i = 0; i < current.childrenCount(); i++)
splitSet.add(new ArrayList>());
int localErrors = 0;
double subTreeScore = 0;
double N = 0.0;
for(DataPointPair dpp : testSet)
{
DataPoint dp = dpp.getDataPoint();
if(current.localClassify(dp).mostLikely() != dpp.getPair())
localErrors+=dp.getWeight();
N += dp.getWeight();
int path = current.getPath(dp);
if(path >= 0)
splitSet.get(path).add(dpp);
else
hadMissing.add(dpp);
}
if(!hadMissing.isEmpty())
DecisionStump.distributMissing(splitSet, hadMissing);
//Find child wich gets the most of the test set as the candidate for sub-tree replacement
int maxChildCount = 0;
int maxChild = -1;
for(int path = 0; path < splitSet.size(); path++)
if(!current.isPathDisabled(path))
{
subTreeScore += pruneErrorBased(current, path, current.getChild(path), splitSet.get(path), alpha);
if(maxChildCount < splitSet.get(path).size())
{
maxChildCount = splitSet.get(path).size();
maxChild = path;
}
}
/* Original uses normal approximation of p + Z_alpha * sqrt(p (1-p) / n).
* Instead, just compute exact using inverse beta
* Upper Bound = 1.0 - BetaInv(alpha, n-k, k+1)
*/
final double prunedTreeScore = computeBinomialUpperBound(N, alpha, localErrors);
double maxChildTreeScore;
if(maxChild == -1)
maxChildTreeScore = Double.POSITIVE_INFINITY;
else
{
TreeNodeVisitor maxChildNode = current.getChild(maxChild);
int otherE = 0;
for (int path = 0; path < splitSet.size(); path++)
for (DataPointPair dpp : splitSet.get(path))
if (maxChildNode.classify(dpp.getDataPoint()).mostLikely() != dpp.getPair())
otherE+=dpp.getDataPoint().getWeight();
maxChildTreeScore = computeBinomialUpperBound(N, alpha, otherE);
}
if(maxChildTreeScore < prunedTreeScore && maxChildTreeScore < subTreeScore && parent != null)
{
try//NodeVisitor may not support setPath method, which is optional
{
parent.setPath(pathFollowed, current.getChild(maxChild));
return maxChildTreeScore;
}
catch(UnsupportedOperationException ex)
{
//fall out to others, this is ok
}
}
//MaxChildTreeScore is not the min, or it was not supported - so we do not compare against it any more
if(prunedTreeScore < subTreeScore )
{
for(int i = 0; i < current.childrenCount(); i++)
current.disablePath(i);
return prunedTreeScore;
}
else//no change
return subTreeScore;
}
private static double computeBinomialUpperBound(final double N, double alpha, double errors)
{
return N * (1.0 - SpecialMath.invBetaIncReg(alpha, N - errors+1e-9, errors + 1.0));
}
}
Ads help maintain this website.