% id3skel.pl - am
% - benoetigt bei Quintus: library(math)
% - Kann mit animals_ex.pl als Datenbasis getestet werden.
% - Testaufruf:  :- make_tree(T), show_tree(T,O),   und ggfs.
%                   make_rules(T,L), show_rules(L).
% - nicht vergessen: Division durch Null abzufangen
% Datei besteht aus der 'entkernten' 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ID3-Implementation nach Bratko
%% Christian Franzel Feb 95
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% make_tree induziert einen Entscheidungsbaum (ID3) anhand der als Fakten
%%           gegebenen Beispiele [ example( Class, Objektbeschreibung ) ].
%%           Zunaechst werden diese Fakten aufgesammelt und dann induce_tree aufgerufen.

make_tree( Tree ):-
	findall( example( Obj_L ), example( Obj_L ), Examples_L ),
	findall( A, attribute( A, _ ), Attributes_L ),
	induce_tree( Attributes_L, Examples_L, Tree ).


% ... induce_tree ist die Kernaufgabe 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Transformation eines ID3-Baumes in eine Regelmenge
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ... ist die Aufgabe



%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Visualisierung des Baumes
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% show_tree visualisiert einen mit make_tree erzeugten Baum ab der X-Pos Pos.

show_tree( null, Pos ):-
	tab( Pos ),
	write( null ),
	nl, !.

show_tree( leaf( Class ), Pos ):-
	tab( Pos ),
	write( '-> ' ),
	write( Class ), 
	nl, !.

show_tree( set( Ex_L ), Pos ):-
	tab( Pos ),
	write( 'nicht unterscheidbar: ' ),
	writeList( Ex_L, Pos ), 
	nl, !.

show_tree( tree( Att, Subtrees ), Pos ):-
	tab( Pos ),
	write( Att ),
	nl,
	Pos2 is Pos + 2,
	show_trees( Subtrees, Pos2 ).

show_trees( [], _ ):- !.

show_trees( [ Val: Tree1 | Trees ], Pos ):-
	tab( Pos ),
	write( '= ' ),
	write( Val ),
	nl,
	Pos2 is Pos + 2,
	show_tree( Tree1, Pos2 ),
	show_trees( Trees, Pos ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Visualisierung der Regelmenge
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

show_rules( [] ):- !.

show_rules( [ First | Rest ] ):-
	show_rule( First ),
	nl,
	show_rules( Rest ).

show_rule( [] ):- !.



show_rule( [ Att : Value | Rest ] ):-
	write( '[ ' ), 
	write( Att ),
	write( ' = ' ),
	write( Value ),
	write( ' ]'),
	write( ' '),
	show_rule( Rest ).


show_rule( [f( Class )] ):-
	write( ' --> ' ),
	write( Class ).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Hilfsprozeduren:

%% gen_arg ermittelt den Wert des Attributs Att des angegebenen Beipiels

gen_arg( Att, example( Obj_L ), Value ):-
	vector( List ),
	nth( X, List, Att ),!,
	nth( X, Obj_L, Value ).


%% class bestimmt die Klasse des Beispiels (= Wert des Klassifikationsattributes )

class( Example, Class ):-
	classific( ClassAtt, _ ),
	gen_arg( ClassAtt, Example, Class ).
	

%% sameclass stellt fest, ob es sich bei den Bsp. nur um eine Klasse handelt.

sameclass( _, [] ).

sameclass( Class, [ Example | Rest ] ):-
	class( Example, Class2 ),
	Class == Class2,
	sameclass( Class, Rest ).


%% number_ex_4_class bestimmt die Anzahl N der Bsp. in Ex_L fuer die Klasse Class.

number_ex_4_class( Class, Ex_L, N ):-
	findall( Class, 
	         ( member( example( Obj_L ), Ex_L ),
		   class( example( Obj_L ), Class ) ),
		 Ex4Cl_L ),
	length( Ex4Cl_L, N ).	


%% attvalsubset filtert aus der Liste Exs_L die Bsp. heraus, die nicht AttVal genuegen.

attvalsubset( Att, Val, Exs_L, Subset_L ):-
	findall( example( Obj_L ), 
	         ( member( example( Obj_L ), Exs_L ),
		 satisfy( Att, Val, example( Obj_L ) ) ),
		 Subset_L ).


%% satisfy ueberprueft, ob das Objekt der Bedingung Att = Val genuegt

satisfy( Att, Val, Example ):-
	gen_arg( Att, Example, Val ).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Hilfsprozeduren (unterste Stufe):

log2( X, Result ):-
	log( 2, N ),           %% log_a( X ) = ( log( X ) / log( a ) )
	log( X, Z ),
	Result is Z / N.


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


del( X, [ X | Rest ], Rest ).
del( X, [ Y | Rest ], [ Y | L ] ):-
	del( X, Rest, L ).


nth( 1, [ First | _ ], First ).
nth( N, [ _ | Rest ], X ):-
	nth( N1, Rest, X ),
	N is N1 + 1.


%%%%%% nur fuer die Ausgabe:

writeList( [], _ ):- !.

writeList( [ First | Rest ], Pos ):-
	nl,
	tab( Pos ),
	write( First ),
	writeList( Rest, Pos ).