% Computational Intelligence: a logical approach. % Prolog Code. % Decision-tree learner % binary attributes, myopic max info split, noise allowed. % 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. % Stochastic (gives probabilities at leaves), myopic (only looks one % step ahead), maximum information split, for Boolean attributes without % solving overfitting. dtlearn(Goal, Examples, Atts, if(Cond,YT,NT)) :- select_split(Goal, Examples, Atts, Cond), split(Examples, Cond, Yes, No), remove(Cond, Atts, Rem_Atts), dtlearn(Goal, Yes, Rem_Atts, YT), dtlearn(Goal, No, Rem_Atts, NT). dtlearn(Goal, Examples, Atts, Val) :- \+ select_split(Goal, Examples, Atts, _), count(Goal,Examples,T,F), Val is T / (T+F). % split(Examples,Att,T,F) is true if T is the examples in Examples % with attribute Att true and F is the examples with attribute Att false. split([],_,[],[]). split([Obj|Rest],Cond,[Obj|Yes],No) :- val(Obj,Cond,true), split(Rest,Cond,Yes,No). split([Obj|Rest],Cond,Yes,[Obj|No]) :- val(Obj,Cond,false), split(Rest,Cond,Yes,No). % count(Att,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,[Ex|R],T1,F) :- val(Ex,Att,true), count(Att,R,T,F), T1 is T+1. count(Att,[Ex|R],T,F1) :- val(Ex,Att,false), count(Att,R,T,F), F1 is F+1. select_split(Goal, Examples, Atts, Cond) :- % is true if Cond is the best attribute in Atts to determine Goal from % Examples. It fails if there are no splits that give a gain in information. information(Goal,Examples,I1), select_max_info_gain(Goal, Examples, Atts, none , I1, Cond). % select_max_info_gain(Goal, Examples, Atts, BestC, BestI, Cond) % is true if Cond is the attribute that gives the maximum information gain % where the information gain is positive (i.e., the information after the % split is less than without splitting). BestC is the current best condition % (or is "none" if no previous attribute gave any information gain), % and BestI is the information after splitting on BestC. select_max_info_gain(_, _, [], BestC, _, BestC) :- dif(BestC, none). select_max_info_gain(Goal, Exs, [Att|R], BestC, BestI,Cond) :- split_info(Goal,Exs,Att,Info), ( Info >= BestI -> select_max_info_gain(Goal, Exs, R, BestC, BestI,Cond) ; select_max_info_gain(Goal, Exs, R, Att, Info ,Cond) ). % 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) ). % remove(E,L,R) removes one occurrence of element E from list L resulting in R remove(A,[A|R],R). remove(A,[B|C],[B|R]) :- remove(A,C,R).