Method pruneErrorBased

JSAT/src/jsat/classifiers/trees/TreePruner.java:166–269

@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

(TreeNodeVisitor parent, int pathFollowed, TreeNodeVisitor current, List<DataPointPair<Integer>> testSet, double alpha)

     * @return expected upperbound on errors
     */
    private static double pruneErrorBased(TreeNodeVisitor parent, int pathFollowed, TreeNodeVisitor current, List<DataPointPair<Integer>> 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<Integer> dpp : testSet)
            {
                if(current.localClassify(dpp.getDataPoint()).mostLikely() != dpp.getPair())
                    errors+=dpp.getDataPoint().getWeight();
                N+=dpp.getDataPoint().getWeight();
            }
            return computeBinomialUpperBound(N, alpha, errors);
        }
        List<List<DataPointPair<Integer>>> splitSet = new ArrayList<List<DataPointPair<Integer>>>(current.childrenCount());
        List<DataPointPair<Integer>> hadMissing = new ArrayList<DataPointPair<Integer>>(0);
        for(int i = 0; i < current.childrenCount(); i++)
            splitSet.add(new ArrayList<DataPointPair<Integer>>());
        
        int localErrors = 0;
        double subTreeScore = 0;
        
        double N = 0.0;
        for(DataPointPair<Integer> 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;
                }
            }