#|
This file contains Decision tree learning code to accompany the
textbook "Machine Learning," Tom M. Mitchell, McGraw Hill, 1997.
Copyright 1998 Tom M. Mitchell. This code may be freely distributed
and used for any non-commericial purpose, as long as this copyright
notice is retained. The author assumes absolutely no responsibility
for any harm caused by bugs in the code.
1. OVERVIEW
This file contains a Lisp implementation of the ID3 program for
learning decision trees, as described in Table 3.1 of the textbook
"Machine Learning," Tom Mitchell, McGraw Hill, 1997. It also contains
the set of training examples given in Table 3.2.
The code is simple enough that you should be able to inspect and
modify it for your own use.
The six key functions are:
1. ID3(examples target.attribute attributes)
learns a decision tree, using the algorithm from Table 3.1 in the book
2. Classify(instance tree)
Given a new instance and a previously learned tree, returns the
classification of that instance produced by the tree.
3. Print.tree(tree)
Prints a tree in human readable form
4. Print.entity(instance)
Prints an instance (e.g., one of your training examples)
5. Get.value(attribute instance)
Get the value of some ATTRIBUTE of INSTANCE
6. Put.value(attribute instance value)
Assign VALUE to ATTRIBUTE of INSTANCE
2. EXAMPLE TRACE:
After loading this file into CommonLisp, you should be able to
duplicate the following trace:
;; FIRST LOOK AT THE PROVIDED TRAINING EXAMPLES
>> *training.examples*
(D14 D13 D12 D11 D10 D9 D8 D7 D6 D5 ...)
;; USE THE FUNCTION PRINT.ENTITY TO EXAMINE JUST ONE OF THEM
>> (print.entity 'd6)
(PLAY.TENNIS? NO WIND STRONG HUMIDITY NORMAL TEMPERATURE COOL OUTLOOK RAIN)
;; NOW USE ID3 TO LEARN A TREE
>> (setq tree (id3 *training.examples*