A Common Lisp implementation of the ID3 machine learning algorithm by R. Quinlan.
It generates decision trees from example instances that have discrete variables. Further, it can generate a function that traverses that tree to classify new instances from outside the training data (e.g. where one variable is missing).
Here's an example of how to use it:
CL-USER>
(defpackage #:id3-examples
(:use "ID3" "COMMON-LISP" "CL-USER"))
Package "ID3-EXAMPLES"
CL-USER> (in-package :id3-examples)
Package "ID3-EXAMPLES"
ID3-EXAMPLES>
(defparameter
*examples*
'((:outlook sunny :temp hot :humidity high :wind weak :play-tennis no)
(:outlook sunny :temp hot :humidity high :wind strong :play-tennis no)
(:outlook overcast :temp hot :humidity high :wind weak :play-tennis yes)
(:outlook rain :temp mild :humidity high :wind weak :play-tennis yes)
(:outlook rain :temp cool :humidity normal :wind weak :play-tennis yes)
(:outlook rain :temp cool :humidity normal :wind strong :play-tennis no)
(:outlook overcast :temp cool :humidity normal :wind strong :play-tennis yes)
(:outlook sunny :temp mild :humidity high :wind weak :play-tennis no)
(:outlook sunny :temp cool :humidity normal :wind weak :play-tennis yes)
(:outlook rain :temp mild :humidity normal :wind weak :play-tennis yes)
(:outlook sunny :temp mild :humidity normal :wind strong :play-tennis yes)
(:outlook overcast :temp mild :humidity high :wind strong :play-tennis yes)
(:outlook overcast :temp hot :humidity normal :wind weak :play-tennis yes)
(:outlook rain :temp mild :humidity high :wind strong :play-tennis no))
"Examples for testing. Play tennis or not? That's the question.")
*EXAMPLES*
ID3-EXAMPLES>
(defun example-1 ()
"Build and use a classifier function."
;; Create the classifier function
(setf (symbol-function 'classification-of)
(build-id3-classifier *examples* :play-tennis
:positive-value 'yes :negative-value 'no))
;; Make a couple of test instances
(let ((instances '((:wind strong :outlook sunny :humidity high)
(:outlook sunny :humidity normal :wind weak))))
;; Try to classify them
(loop for instance in instances
do (format t "Adding classification of instance ~A~%" instance)
collect (classification-of instance))))
EXAMPLE-1
ID3-EXAMPLES>
(defun example-2 ()
"Build a tree. Then traverse it with a tree-traverser."
;; Build the tree
(let ((decision-tree (id3 *examples* :play-tennis
:positive-value 'yes :negative-value 'no))
;; Make a couple of test instances
(instances '((:wind strong :outlook sunny :humidity high)
(:outlook sunny :humidity normal :wind weak))))
;; Try to classify the instances using the tree
(loop for instance in instances
do (format t "Adding classification of instance ~A~%" instance)
collect (classify instance decision-tree))))
EXAMPLE-2
ID3-EXAMPLES> (example-1)
Adding classification of instance (WIND STRONG OUTLOOK SUNNY HUMIDITY HIGH)
Adding classification of instance (OUTLOOK SUNNY HUMIDITY NORMAL WIND WEAK)
(NO YES)
ID3-EXAMPLES> (example-2)
Adding classification of instance (WIND STRONG OUTLOOK SUNNY HUMIDITY HIGH)
Adding classification of instance (OUTLOOK SUNNY HUMIDITY NORMAL WIND WEAK)
(NO YES)
ID3-EXAMPLES>