% nacteni:
/* ['10.1_16.pl']. */

%:-consult('10.1_16_pocasi_golf.pl').
%:-consult('10.1_16_naradi.pl').
:-consult('10.1_16_restaurace.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)) :- 
    \+ ((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) :- \+ ((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), impurity(Examples, Att, Impurity )), [_MinImpurity/BestAtt|_]).
    
impurity( Exs, Att , Imp) :- attribute( Att , AttVals ), sumv(Att, AttVals, Exs, Rem), Imp is 0 - Rem.

% sumv( +Att, +AttVals, +Exs, -Rem) - "zbytková informace" po testu na vsechny hodnoty atributu Att
sumv( _, [], _, 0).
sumv( Att, [V | Vs], Es, Rem) :-
	setof(Class, X^example(Class,X), Classes),         % množina vsech Class, viz 'help(setof)'
	sumc(Att, V, Classes, S), sumv(Att, Vs, Es, Rem1),
	findall(1, example(Class,_), L), length(L, Nall),  % spočítáme Nall a Nv
	findall(1, (example(_, AVs), member(Att = V, AVs)), L1), length(L1, Nv),
	Pv is Nv / Nall,  % P(v)
	Rem is Pv * S + Rem1.

% sumc(+Att, +V, +Classes, -S) - "vnitřní" suma
sumc(_, _, [], 0).
sumc(Att, V, [C | Classes], S) :-
	findall(1, (example(_, AVs), member(Att = V, AVs)), L1), length(L1, Nv),
	findall(1, (example(C, AVs), member(Att = V, AVs)), L2), length(L2, Ncv),
	sumc(Att, V, Classes, S1),
	((Nv = 0,! ; Ncv = 0), S is S1, ! ;	% P(c|v)
	    Pcv is Ncv / Nv, log2(Pcv, LogPcv), S is Pcv * LogPcv + S1).

% log2(+X, -Y)
log2(X, Y) :- Y is log(X) / log(2).

% ===================================================================

% 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), write('?'), 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).
