private static int pruneReduceError ( TreeNodeVisitor parent , int pathFollowed , TreeNodeVisitor current , ClassificationDataSet 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 < ClassificationDataSet > splits = new ArrayList <> ( numSplits ) ; IntList hadMissing = new IntList ( ) ; double [ ] fracs = new double [ numSplits ] ; double wSum = 0 ; for ( int i = 0 ; i < numSplits ; i ++ ) splits . ( testSet . emptyClone ( ) ) ; for ( int i = 0 ; i < testSet . size ( ) ; i ++ ) { double w_i = testSet . getWeight ( i ) ; int path = current . getPath ( testSet . getDataPoint ( i ) ) ; if ( path >= 0 ) { splits . get ( path ) . addDataPoint ( testSet . getDataPoint ( i ) , testSet . getDataPointCategory ( i ) , w_i ) ; wSum += w_i ; fracs [ path ] += w_i ; } else //missing value hadMissing . add ( i ) ; } //normalize fracs for ( int i = 0 ; i < numSplits ; i ++ ) fracs [ i ] /= wSum + 1e-15 ; if ( ! hadMissing . isEmpty ( ) ) DecisionStump . distributMissing ( splits , fracs , testSet , 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 ( int i = 0 ; i < testSet . size ( ) ; i ++ ) { DataPoint dp = testSet . getDataPoint ( i ) ; int truth = testSet . getDataPointCategory ( i ) ; if ( current . localClassify ( dp ) . mostLikely ( ) == truth ) childCorrect += testSet . getWeight ( i ) ; if ( parent . localClassify ( dp ) . mostLikely ( ) == truth ) parrentCorrect += testSet . getWeight ( i ) ; } 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 ; }
Performs pruning to reduce error on the testing set