% Computational Intelligence: a logical approach. % Prolog Code. % Decision-tree learner % binary attributes, myopic max information split, no noise % Copyright (c) 1998, Poole, Mackworth, Goebel and Oxford University Press. % dtlearn(Goal, Examples, Attributes, DT) % Given Examples and Attributes induces a decision tree DT for Goal. % Splits on the maximum information gain split % Works for noise-free features, with binary attributes. dtlearn(Goal, Examples, _ , Val) :- all_examples_agree(Goal, Examples, Val). dtlearn(Goal, Examples, Atts, if(Cond=YesVal,YT,NT)) :- \+ all_examples_agree(Goal, Examples, _), select_split(Goal, Examples, Atts, Cond, Rem_Atts), split(Examples, Cond, YesVal, Yes, No), dtlearn(Goal, Yes, Rem_Atts, YT), dtlearn(Goal, No, Rem_Atts, NT). % all_examples_agree(Goal, Examples, Val) is true if all examples agree that % Val is the value of attribute Goal. all_examples_agree(_,[],_). all_examples_agree(Att,[Obj|Rest],Val) :- val(Obj,Att,Val), all_examples_agree(Att,Rest,Val). % split(Examples,Att,YesVal,T,F) is true if T is % the examples in Examples with attribute Att % having value YesVal and F is the examples with % attribute Att having the other value. split([],_,_,[],[]). split([Obj|Rest],Cond,YesVal,[Obj|Yes],No) :- val(Obj,Cond,YesVal), split(Rest,Cond,YesVal, Yes,No). split([Obj|Rest],Cond,YesVal,Yes,[Obj|No]) :- val(Obj,Cond,NoVal), \+ NoVal = YesVal, split(Rest,Cond,YesVal,Yes,No). select_split(Goal, Examples, [A1|RAtts], Cond, Rem_Atts) :- % here is where we really want maximum information, but it % is too early in the book. This is defined using max information here. split_info(Goal,Examples,A1,I1), select_max_info_gain(Goal, Examples, RAtts, A1, I1, Cond, [], Rem_Atts). % select_max_info_gain(Goal, Examples, Atts, BestC, BestIG, % Cond, Rej_Atts, Rem_Atts) % This selects the attribute with the minimum expected information after the split. select_max_info_gain(_, _, [], BestC, _, BestC, Rem_Atts, Rem_Atts). select_max_info_gain(Goal, Exs, [Att|R], BestC, BestIG,Cond, Rej_Atts, Rem_Atts) :- split_info(Goal,Exs,Att,Info), ( Info > BestIG -> select_max_info_gain(Goal, Exs, R, BestC, BestIG,Cond, [Att|Rej_Atts], Rem_Atts) ; select_max_info_gain(Goal, Exs, R, Att, Info ,Cond, [BestC|Rej_Atts], Rem_Atts) ). % split_info(Goal,Examples,Att,Info) is true if Info is the expected % information about Goal in Examples given a test for Att split_info(Goal,Examples,Att,Info) :- split(Examples,Att,_,T,F), information(Goal,T,IT), information(Goal,F,IF), length(T,NT), length(F,NF), Info is (NT*IT + NF*IF)/(NT+NF). % information(Goal,Examples,I) is true if I is the amount of information % in Examples with respect to Goal information(Goal,Examples,I) :- count(Goal,_,Examples,True,False), ( (True=0 ; False=0) -> I=0 ; Total is True + False, I is - True/Total * log(2,True/Total) - False/Total * log(2,False/Total) ). % count(Att,TrueVal,Examples,T,F) is true if there are T examples in Examples % with attribute Att true and F examples with attribute Att false. count(_,_,[],0,0). count(Att,TrueVal,[Ex|R],T1,F) :- val(Ex,Att,TrueVal), count(Att,TrueVal,R,T,F), T1 is T+1. count(Att,TrueVal,[Ex|R],T,F1) :- val(Ex,Att,FalseVal), \+ TrueVal=FalseVal, count(Att,TrueVal,R,T,F), F1 is F+1.