@ May 1993, Luis Torgo - LIACC

ID3 a decision tree learner

This program implements the original ID3 algorithm as it is described by Quinlan.

This is a rather naive implementation used only for teaching purposes.

Contents

# HOW TO RUN IT

You need to run YAP-prolog and afterwards load the id3 learner

	?- [-id3].
To learn some problem you first need a file describing both the attributes of the problem as well as the examples being learned (bellow you have a more detailed description of these files, but you can also have a look at the given example file named "golf").

The predicate used to learn a file of examples is run/1.

	Ex :

	?- run(golf_id3).
This learns the examples contained in the file and outputs the resulting decision tree.

# THE OUTPUT

As it was said the system outputs in a kind of graphical way the resulting decision tree. nevertheless the tree is also internally stored as a set of Prolog terms. Their form is the following :

node(NodeId,AttributeName or "leaf",ListOfDescendents or ClassLabel)

where

ListOfDescendents is a list of triplets of the form (ValueOfAttribute,DescendentNodeId,ExsPartition)

Exs: node(1,color,[(red,2,[4,5,10,23]),(blue,3,[2])]) 
node(15,leaf,dog)

# THE INPUT FILE

The file on which ID3 is to be runned should contain a list of facts each describing an example.

Each example is stored as a Prolog fact with the following format ex(ExID,ListOfAttributeValuePairs,ClassLabel).

	Ex:

	ex(1,[color=red,shape=circular],x).