Inlämningsuppgift 4 Maskininlärning

Antag att ett beslutsträd T representeras på följande sätt:
T = class(c)
där c är en klass, eller
T = (A, [(V1,T1), ..., (Vn,Tn)])
där A är ett attribut,
V1, ..., Vn är de möjliga värdena på attributet A
och där T1, ..., Tn är beslutsträd.
Antag att exempel representeras på följande sätt:
E = (c,[(A1,V1), ..., (An,Vn)])
där c är en klass och
(Ai,Vi), 1<=i<=n, är ett par där Ai är ett attribut och Vi är ett värde.
Antag att information om attribut och dess möjliga värden ges av predikatet attribute/2,
där första argumentet är attributnamnet och andra argumentet en lista med värden som attributet kan anta. T.ex.
attribute(size,[large,small]).
attribute(colour,[red,green,blue]).

Uppgift 1

Komplettera nedanstående program med definitioner av följande predikat:
classes(Es,Cs)
som givet en lista med exempel Es returnerar en lista med par [(C1,N1), ..., (Cn,Nn)]
där C1-Cn är samtliga klasser i Es
och Ni, 1<=i<=n, är antalet exempel i Es av klassen Ci.
Listan är sorterad i fallande ordning med avseende på Ni
(dvs. den största klassen motsvaras av det första paret i listan).
Notera att om det endast finns en klass i Es så kommer Cs att endast innehålla ett element.
best_attribute(Es,As,A,AsRest,VEs)
som givet en lista med exempel Es och en lista med attribut As
returnerar det mest informativa attributet A,
en lista AsRest med de övriga attributen
samt en lista VEs som för varje värde Vi på attributet A innehåller ett par på formen
(Vi,Ei) där Ei är den delmängd av Es som på attributet A har värdet Vi.
Notera att för vissa Vi så kan Ei = [].
(Andralogaritmen av ett tal Y erhålls i SICStus med X is log(2,Y).)

decision_tree([],_,D,class(D)) :- !.
decision_tree(Es,_,_,class(C)) :-
        classes(Es,[(C,_)]), !.
decision_tree(Es,[],_,class(C)):- !,
        classes(Es,[(C,_)|_]).
decision_tree(Es,As,_,(A,Trees)) :-
        best_attribute(Es,As,A,AsRest,VEs),
        classes(Es,[(D,_)|_]),
        make_trees(VEs,AsRest,D,Trees).

make_trees([],_,_,[]).
make_trees([(V,Es)|VEs],AsRest,D,[(V,T)|Trees]) :-
        decision_tree(Es, AsRest, D, T),
        make_trees(VEs, AsRest, D, Trees).

Uppgift 2

Definiera ett predikat
classify(E,T,C)
som givet ett oklassificerat exempel E i form av en lista med attribut-värdepar
och ett beslutsträd T returnerar den klass C som beslutsträdet tilldelar exemplet.

Uppgift 3

Applicera programmet i uppgift 1 på träningsmängden som ligger länkad till på kursens hemsida. Redogör för hur många exempel i testmängden som är korrekt klassificerade (detta avgörs med hjälp av predikatet i uppgift 2).