Prune tree

Description

PrunedTree is optimally pruned Tree with respect to estimated classification error using Laplace estimate

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Download

Program source code: prune_tree.pl

Listing

% Solution to Exercise 18.6
 
% prunetree( Tree, PrunedTree): PrunedTree is optimally pruned Tree
%    with respect to estimated classification error using Laplace estimate
%    Assume trees are binary:
%    Tree = leaf( Node, ClassFrequencyList), or
%    Tree = tree( Root, LeftSubtree, RightSubtree)
 
prunetree( Tree, PrunedTree)  :-
   prune( Tree, PrunedTree, Error, FrequencyList).
 
% prune( Tree, PrunedTree, Error, FrequencyList):
%    PrunedTree is optimally pruned Tree with classification Error,
%    FrequencyList is the list of frequencies of classes at root of Tree
 
prune( leaf( Node, FreqList), leaf( Node, FreqList), Error, FreqList)  :-
   static_error( FreqList, Error).
 
prune( tree( Root, Left, Right), PrunedT, Error, FreqList)  :-
   prune( Left, Left1, LeftError, LeftFreq),
   prune( Right, Right1, RightError, RightFreq),
   sumlists( LeftFreq, RightFreq, FreqList),   % Add corresponding elements
   static_error( FreqList, StaticErr),
   sum( LeftFreq, N1),
   sum( RightFreq, N2),
   BackedErr is ( N1*LeftError + N2*RightError) / ( N1 + N2),
   decide( StaticErr, BackedErr, Root, FreqList, Left1, Right1, Error, PrunedT).
 
% Decide to prune or not:
 
decide( StatErr, BackErr, Root, FreqL, _, _, StatErr, leaf( Root, FreqL))  :-
   StatErr =< BackErr, !.      % Static error smaller: prune subtrees 
 
% Otherwise do not prune:
decide( _, BackErr, Root, _, Left, Right, BackErr, tree( Root, Left, Right)).
 
% static_error( ClassFrequencyList, Error): estimated class. error
 
static_error( FreqList, Error)  :-       % Use Laplace estimate
   max( FreqList, Max),                  % Maximum number in FreqList
   sum( FreqList, All),                  % Sum of numbers in FreqList    
   number_of_classes( NumClasses),
   Error is ( All - Max + NumClasses - 1) / ( All + NumClasses).
 
sum( [], 0).
 
sum( [Number | Numbers], Sum)  :-
   sum( Numbers, Sum1),
   Sum is Sum1 + Number.
 
max( [X], X).
 
max( [X,Y | List], Max)  :-
   X > Y, !, max( [X | List], Max)
   ;
   max( [Y | List], Max).
 
sumlists( [], [], []).
 
sumlists( [X1 | L1], [X2 | L2], [X3 | L3])  :-
   X3 is X1 + X2,
   sumlists( L1, L2, L3).
 
% A tree
 
tree1( tree( a,                                           % Root
             tree( b, leaf( e, [3,2]), leaf( f, [1,0])),  % Left subtree    
             tree( c, tree( d, leaf( g, [1,1]), leaf( h,[0,1])), leaf(i,[1,0])))). 
 
number_of_classes( 2).
 
% Test query: ?-  tree1( Tree), prunetree( Tree, PrunedTree).

Comments

pl/prolog/pllib/prune_tree.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0