;;;; Author: Steve Wolfman
;;;;
;;;; This file contains code to help you when running your
;;;; decision tree.

;;; This simple program just runs a classifier on the given
;;; data-point.  At each node of the classifier tree, it checks for
;;; the feature value in the data point, and, if that value has not
;;; been calculated, it calculates it using the feature's extractor.

;; classifier is a properly constructed decision tree
;; data-point is a data point to be classified.
;; returns T if the classifier answers YES for the point;
;; returns NIL otherwise.
(defun run-dectree (classifier data-point)
  (if (not (consp classifier))
      (progn
        (assert (or (eq classifier T)
                    (eq classifier NIL)) 
                (classifier)
                "Improperly formed decision tree in run-dectree (leaf node is neither T nor NIL")
        classifier)
    (progn
      (assert (feature-p (first classifier)) ((first classifier))
              "car of tree is not a feature in run-dectree")
      (let ((field (cdr (assoc (feature-name (first classifier)) data-point))))
        (when (null field)
              (assert (not (null (feature-extractor (first classifier))))
                      ((first classifier))
                      "No extractor for unlabeled feature ~S in run-dectree"
                      (feature-name (first classifier)))
              (setf field (funcall (feature-extractor (first classifier)) data-point))
              (assert (not (null field)) (field)
                      "Feature extractor failed to extract value in run-dectree"))
        ;; Should have a check here to make sure the branch is non-empty.
        (run-dectree (cdr (assoc field (rest classifier))) data-point)))))
  
;; This is something like what we will use to grade your projects. It
;; calculates error rates over a set of data points for a given
;; decision tree builder.

;; Finds the error rate. Returns three values: error rate, false
;; positive rate, false negative rate.
(defun test-decision-tree (dec-tree test-set key-attr 
                                    &optional (fp 0) (fn 0) (count 0))
  (if (null test-set)
      (if (= count 0)
          (values 0 0 0)
        (values (/ (+ fp fn) count) (/ fp count) (/ fn count)))
    (let ((true-answer (cdr (assoc key-attr (first test-set))))
          (answer      (run-dectree dec-tree (first test-set))))
      (test-decision-tree dec-tree (rest test-set) key-attr
                          (if (and answer
                                   (not true-answer))
                              (+ fp 1)
                            fp)
                          (if (and (not answer)
                                   true-answer)
                              (+ fn 1)
                            fn)
                          (+ count 1)))))

;; This will allow you to take random subsets of your data-points to
;; test your decision tree builder (take a random subset, build your
;; decision tree with it, test on the other examples).

;; Given a data set, returns a random partition (two disjoint random
;; subsets) of the data set with one of the given size.
(defun rand-subset (new-size data-set)
  (rand-subset-helper new-size data-set (length data-set)))

(defun rand-subset-helper (new-size data-set old-size 
                                    &optional (new-set1 nil)
                                              (new-set2 nil))
  (cond ((= old-size 0) (values new-set1 new-set2))
        (T (let ((rand-num (random old-size)))
             (if (< rand-num new-size)
                 (rand-subset-helper 
                  (- new-size 1) 
                  (rest data-set) 
                  (- old-size 1) 
                  (cons (first data-set) new-set1)
                  new-set2)
               (rand-subset-helper
                new-size
                (rest data-set)
                (- old-size 1)
                new-set1
                (cons (first data-set) new-set2)))))))