% File: decision.pl
% includes: support predicates for implementing 
%           decision tree learning algorithm.  

% decision trees are represented by terms of the form:
%
%   Class name - for a leaf node
%   t(Attr,List) - for a non-leaf node, where Attr is the attribute
%     splitting the tree and List is a list of items of the form
%      Value-Subtree, with Subtree the subtree corresponding to
%      the value Value.

%------------------------------------------------------------------

pretty_pr(T) :- pretty_pr(0,T).

pretty_pr(D,t(Att,L)) :- pretty_pr_L(D,Att,L).

pretty_pr_L(_,_,[]).

pretty_pr_L(D,Att,[V-t(A2,L2) | L]) :- !,
   writesp(D),write(Att),write('='),write(V),nl,
   D1 is D+1,
   pretty_pr(D1,t(A2,L2)),
   pretty_pr_L(D,Att,L).

pretty_pr_L(D,Att,[V-Class | L]) :- !,
   writesp(D),write(Att),write('='),write(V), write(': '),write(Class),nl,
   pretty_pr_L(D,Att,L).


writesp(0) :- !.

writesp(N) :- N>0, N1 is N-1, write('  '), writesp(N1).

%----------------------------------------------------------------------

all_have_class([],_).
all_have_class([Ex|Exs],C) :- class(Ex,C), all_have_class(Exs,C).

%----------------------------------------------------------------------

majority_value(Ex,Class) :-
   classes(Classes),
   largest(C,N,
       (member(C,Classes),number((member(X,Ex),class(X,C)),N)),Class).

%----------------------------------------------------------------------

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

%----------------------------------------------------------------------

delete(_,[],[]) :- !.
delete(Item,[Item|T],Rest)  :- !,delete(Item,T,Rest).
delete(Item,[H|T],[H|Rest]) :- !, \+ Item = H, delete(Item,T,Rest).
         
%----------------------------------------------------------------------

val_split(Attr,V,Examples,SExamples) :- 
    findall(Ex,(member(Ex,Examples),attr_value(Attr,Ex,V)),SExamples).

%----------------------------------------------------------------------

class_split(Examples,PosEx,NegEx) :- 
    classes([L1,L2]),
    findall(Ex,(member(Ex,Examples),class(Ex,L1)),PosEx),
    findall(Ex,(member(Ex,Examples),class(Ex,L2)),NegEx).

%----------------------------------------------------------------------

% Assumes only two classes
entropy(Examples,I) :- class_split(Examples,PosEx,NegEx),
                       length(PosEx,LP), length(NegEx,LN),
                       ((LP=0;LN=0) -> I=0;
                          (LP=LN -> I=1;
                            Both is LN + LP,
                            V1 is LP/Both,
                            V2 is LN/Both,
                            IV1 is Both/LP,
                            IV2 is Both/LN,
                            I1 is V1 * log(2,IV1),
                            I2 is V2 * log(2,IV2),
                            I is I1 + I2
                        )).

%----------------------------------------------------------------------

largest(X,N,Goal,Res) :-
   findall(N-X,Goal,List),
   select_largest(List,Res).

   select_largest([N-X|L],Res) :-
      select_largest1(L,N,X,Res).

   select_largest1([],_,X,X).
   select_largest1([N-X|L],N1,_,Res) :-
      N>N1, !,
      select_largest1(L,N,X,Res).
   select_largest1([_|L],N,X,Res) :-
      select_largest1(L,N,X,Res).

%----------------------------------------------------------------------

number(Goal,N) :-
   findall(a,Goal,L),
   length(L,N).

%----------------------------------------------------------------------
