(defun difference (list1 list2 &key (measure ‘count))
“Returns the DIFFERENCE (or ERROR) between two lists of things, using one of three measures:
1. Measure type COUNT: the number of times an item in list1 is different from
an item in list2 at the same position. The items don’t have to be numbers.
Example usage: (difference ‘(red blue bob) ‘(blue blue george) :measure ‘count) -> 2
2. Measure type SQUARED: the sum squared difference between items in list1 and list2
Obviously, the items must be numbers of some sort.
Example usage: (difference ‘(1 2 3) ‘(1 3 7) :measure ‘squared) -> 17
3. Measure type MANHATTAN: the sum absolute difference (abs (- a b)) between items
in list1 and list2. Obviously the items must be numbers of some sort.
Example usage: (difference ‘(1 2 3) ‘(1 3 7) :measure ‘manhattan) -> 5”
;;; HINTS: use equalp to test for the given type, and for equality in COUNT
;;; HINTS: ABS is absolute value
;;; HINTS: I used MAPCAR and LAMBDA to make things easy. You might look them up.
;;; HINTS: This is a place where INCF would be reasonable.
;;; HINTS: My code is about 14 (short) lines long
;;;; IMPLEMENT ME
)
;;; I am providing this function for you as an example
(defun most-common (list)
“Returns the most common item in list, breaking ties arbitrarily”
(let ((reduced-elts (mapcar (lambda (elt) (list elt (count elt list)))
(remove-duplicates list))))
(first (first (sort reduced-elts #’> :key #’second)))))
(defun k-nearest-neighbor (examples new-example &key (k 1) (measure ‘count))
“Given a LIST of EXAMPLES, each of the form (list-of-data class), and a NEW-EXAMPLE
of the same form, determines the K EXAMPLES which most closely resemble the NEW-EXAMPLE,
then returns the most common class among them. The MEASURE used to compute similarity
can be provided. Note that the CLASS is a LIST, like (0.9), not 0.9.”
;;; HINTS: use MOST-COMMON to select the most common among N classes.
;;; HINTS: you might use SORT and SUBSEQ
;;; HINTS: I used MAPCAR and LAMBDA to make things easy. You might look them up.
;;; HINTS: My code is about 11 lines long
;;;; IMPLEMENT ME
)
(defun generalization (training-examples test-examples &key (k 1) (measure ‘count))
“Given a list of TRAINING EXAMPLES, each of the form (list-of-data class),
and a set of TEST EXAMPLES, each of the same form, returns the percentage of TEST
EXAMPLES correctly classified when passed to K-NEAREST-NEIGHBOR with the TRAINING
EXAMPLES. Note that the CLASS is a LIST, like (0.9), not 0.9.”
;;; HINTS: use EQUALP to compare classes
;;; HINTS: This is a place where INCF would be reasonable.
;;; HINTS: I used DOLIST
;;; HINTS: My code is about 5 lines long
;;;; IMPLEMENT ME
)