% nacteni:
/* ['10.1_16.pl']. */

:-consult('10.1_16_pocasi_golf.pl').
%:-consult('10.1_16_naradi.pl').

% převod z faktů na parametry
induce_tree( Tree)  :-
    findall( example( Class, Obj), example( Class, Obj), Examples),
    findall( Att, attribute( Att, _ ), Attributes),
    induce_tree( Attributes, Examples, Tree).

% induce_tree( Attributes , Examples, Tree)
induce_tree(_,[], null ) :- !.
induce_tree(_,[example( Class,_) | Examples], leaf( Class)) :- 
    not((member(example( ClassX,_), Examples), ClassX \== Class)), !. % priklady stejne klasifikace
induce_tree(Attributes , Examples, tree( Attribute , SubTrees)) :-
    choose_attribute( Attributes , Examples, Attribute), ! ,
    del( Attribute , Attributes , RestAtts),
    attribute( Attribute , Values),
    induce_trees( Attribute , Values, RestAtts, Examples, SubTrees).
induce_tree(_, Examples, leaf( ExClasses)) :- % zadny uzitecny atribut, list s stribuci klasifikaci
    findall(Class, member( example( Class, _), Examples), ExClasses).
    
% induce_trees( Att, Values, RestAtts, Examples, SubTrees):
% najdi podstromy SubTrees pro podmnoziny prikladu Examples podle hodnot (Values) atributu Att
induce_trees(_, [],_,_, [] ). % No attributes, no subtrees
induce_trees( Att , [Val1 | Vals ], RestAtts, Exs, [Val1 : Tree1 | Trees]) :-
    attval_subset( Att = Val1, Exs, ExampleSubset),
    induce_tree( RestAtts, ExampleSubset, Tree1),
    induce_trees( Att , Vals, RestAtts, Exs, Trees).
    
% attval_subset(Attribute = Value, Examples, Subset):
% Subset je podmnozina prikladu z Examples, ktere splnuji podminku Attribute = Value
attval_subset( AttributeValue, Examples, ExampleSubset) :-
    findall(example(Class, Obj),
        (member( example( Class, Obj), Examples), satisfy( Obj, [ AttributeValue ])),
        ExampleSubset).

% slide 17

% satisfy( Object, Description)
satisfy( Object, Conj) :- not((member( Att = Val, Conj), member( Att = ValX, Object), ValX \== Val)).

% vybirame atribut podle "cistoty" mnozin, na ktere rozdeli priklady, setof je setridi podle Impurity
choose_attribute( Atts, Examples, BestAtt) :-
    setof( Impurity/Att , (member( Att, Atts), impurity1(Examples, Att, Impurity )), [_MinImpurity/BestAtt|_]).
    
impurity1( Exs, Att , Imp) :- attribute( Att , AttVals ), term_sum( Exs, Att, AttVals, 0, Imp).

% term_sum( Exs, Att, AttVals, PartialSum, Sum) - vazena suma "cistoty" pres vsechny hodnoty atributu Att
term_sum(_,_, [], Sum, Sum).
term_sum( Exs, Att, [Val | Vals ], PartSum, Sum) :- length( Exs, N),
    findall( C, (member( example(C,Desc), Exs), satisfy( Desc, [Att=Val])), ExClasses),
    % ExClasses = seznam klasifikaci (s opakovanim) vsech prikladu s Att=Val
    length( ExClasses, NV), NV > 0, !,
    findall( P, (bagof( 1, member( _Class, ExClasses), L), length( L, NVC), P is NVC/NV), ClassDistribution),
    gini( ClassDistribution , GiniI ),
    NewPartSum is PartSum + GiniI*NV/N,
    term_sum( Exs, Att, Vals, NewPartSum, Sum)
    ; term_sum( Exs, Att, Vals, PartSum, Sum). % zadne priklady nesplnuji Att = Val
    
% gini( ProbabilityList , GiniIndex) - mira "cistoty"
gini( Probs, Index) :- square_sum( Probs, 0, SquareSum), Index is 1 - SquareSum.
square_sum( [], S, S).
square_sum( [P | Ps], PartS, S) :- NewPartS is PartS + P*P, square_sum( Ps, NewPartS, S).

% ===================================================================

% show(+X,+L,-L1)
del(A,[A|T],T).
del(A,[H|T1],[H|T2]) :- del(A,T1,T2).

% show(+Tree)
show(Tree) :-
	show(Tree, 0).

% show(+Tree, +Ind)
show(leaf(Class), Ind) :-
    tab(Ind), write(Class), nl.
show(tree(A, SubTrees), Ind) :-
    tab(Ind), write(A), nl,
    NI is Ind+2, show(SubTrees, NI).
show([], _).
show([_ : null | SubTrees], Ind) :- !, show(SubTrees, Ind).
show([V1 : ST1 | SubTrees], Ind) :-
    tab(Ind), write('= '), write(V1), nl,
    NI is Ind+2, show(ST1, NI),
    show(SubTrees, Ind).

:-induce_tree(T),show(T).
