/*------------------------------------------------------*/ /* Induction of Decision Trees */ /*------------------------------------------------------*/ /* (C) 1994 Zdravko Markov */ /* Updated: Sping-2005 */ /*------------------------------------------------------*/ /* Example format: example(ID, Class, [A=V,...]). */ /* Use: */ /* Create a decision tree: ?- id3(Threshold). */ /* Print tree: ?- show. */ /* Print rules: ?- listing(if). */ /*------------------------------------------------------*/ /* Additional procedures for experimenting: */ /* ?- entropy(List_of_example_IDs, Entropy). */ /* ?- distr(List_of_example_IDs, [C1/N1, C2/N2,...]). */ /* (where Ni is the number of occurences of Ci) */ /* Get the set of attributes: ?- attr(L). */ /* Get the set of values for attr. A: ?- vals(A,L). */ /*------------------------------------------------------*/ /*------------------------------------------------------*/ ?- op(100,fx,if). ?- op(99,xfy,then). /*------------------------------------------------------*/ id3 :- id3(1). % for compatibility with old versions id3(Tr) :- retractall(node(_,_,_)), retractall(if _ then _), findall(N,example(N,_,_),E), example(_,_,L), !, get_attributes(L,A), idt(E,root,A,Tr), assert_rules, !. idt(E,Parent,_,Tr) :- length(E,Len), Len= '),write(Class). showtree(Parent,Pos) :- findall(Son,node(Son,_,Parent),L), Pos1 is Pos+2, show_list(L,Pos1). show_list([],_) :- !. show_list([N|T],Pos) :- node(N,Label,_), nl, tab(Pos), write(Label), showtree(N,Pos), show_list(T,Pos). /*------------------- Auxiliary --------------------------*/ gen_name(M) :- retract(nam(N)), M is N+1, assert(nam(M)), !. gen_name(1) :- assert(nam(1)). efface(X,[X|T],T) :- !. efface(X,[Y|T],[Y|Z]) :- efface(X,T,Z). subset([],_) :- !. subset([X|T],L) :- member(X,L), !, subset(T,L). maximum([X],X) :- !. maximum([X/M|T],Y/N) :- maximum(T,Z/K), (M>K,Y/N=X/M ; Y/N=Z/K), !. /*------------------- For experimenting------------------------*/ model(C,M) :- atom(C), C\=[], !, setof(N,H^L^W^U^(if H then [C/U],example(N,W,L),covers(H,L)),M). model(H,M) :- findall(N,(example(N,_,L),covers(H,L)),M). covers(H1,H2) :- subset(H1,H2). sem_covers(H1,H2) :- model(H1,M1), model(H2,M2), subset(M2,M1). entropy(E,I) :- length(E,N), information_content(E,N,I). attr(As) :- setof(A,X^C^L^V^(example(X,C,L),member(A=V,L)),As). vals(A,AVs) :- setof(A=V,X^C^L^(example(X,C,L),member(A=V,L)),AVs). /*------------------- End id3.pl --------------------------*/