;;;  Additional ID3 functions for artificially adding noise to data and testing results on
;;;  pruned and unpruned decision-trees.

(defun id3-noise-test (examples train# feature-noise-level category-noise-level)  
;;; Run and test id3 on the examples after adding noise. Using train# training examples splitting the rest
;;; 50/50 for a pruning test set and a performance test set.  Feature and category noise levels should
;;; be between 0 and 1.  Shows original and pruned tree and their results on the test set.
  (setf examples (mix-up examples))  ; First randomize order of elements
  (let* ((training-examples (add-feature-and-category-noise (subseq examples 0 train#)
							    feature-noise-level category-noise-level))
	 (rest-examples  (subseq examples train#))
	 (num-prune-test (round (* 0.5 (length rest-examples))))
	 (prune-test-examples (add-feature-and-category-noise (subseq rest-examples 0 num-prune-test) 
							      feature-noise-level category-noise-level))
	 (testing-examples (add-feature-noise (subseq rest-examples num-prune-test) feature-noise-level))
	 (start-time (get-internal-run-time)))
    (format t "~%~%Training Set: ~A; Pruning Test Set: ~A; Performance Test Set: ~A"
	    train# num-prune-test (length testing-examples))
    (let* ((decision-tree (id3 training-examples)) pruned-tree)
      (format t "~%~%Run time: ~,2Fs" (seconds-since start-time))
      (format t "~%Decision tree: ~%~A" decision-tree)
      (test-examples testing-examples decision-tree)
      (setf pruned-tree (prune-decision-tree decision-tree prune-test-examples))
      (format t "~%~%Pruned Decision tree: ~%~A" pruned-tree)
      (test-examples testing-examples pruned-tree))))


(defun add-feature-and-category-noise (examples feature-noise-level category-noise-level)
;;; Add both feature and category noise to the examples at the given levels.
;;; That is, with the given probability replace a value with a random value
  (setf examples (copy-tree examples))
  (dolist (example examples examples)
    (if (>  category-noise-level (random 1.0))
	(setf (first example) (pick-one '(+ -))))
    (add-feature-noise-to-instance (second example) feature-noise-level)))

(defun add-feature-noise (examples probability)
;;; Add just feature noise to the examples
  (setf examples (copy-tree examples))
  (dolist (example examples examples)
    (add-feature-noise-to-instance (second example) probability)))

(defun add-feature-noise-to-instance (instance probability)
;;; Add feature noise to the instance by replacing each feature with random
;;; value from domain with the given probability
      (dotimes (i (length instance) instance)
	(if (>  probability (random 1.0))
	    (setf (nth i instance)
		  (pick-one (nth i *domains*))))))

(defun pick-one (list)
  "Pick an item randomly from the list"
  (nth (random (length list)) list))

(defun mix-up (list)
  "Randomize the order of elements in this list."
  (mapcar #'(lambda (pair) (rest pair))
	  (sort (mapcar #'(lambda (item) (cons (random 1.0) item)) list)
		#'(lambda (a b) (> (first a) (first b))))))