Spam Filter

A spam filter

Write a simple spam filter based on naive Bayes probability, following the steps outlined in A plan for Spam by Paul Graham. The article describes the problem and provides an outline of the method to be used. The article provides some Lisp code, and Paul Graham provides more useful Lisp code. You do not need to do this in Lisp, any language will work, but it is particularly simple to write it in Lisp.
Start from the program shown in Figure 8.3 pages 140-141 of the Graham ANSI Common Lisp book (You can get the software from Paul Graham's lisp code page). You'll need the functions read-text and see and the variable punc. The function read-text reads one word at a time, the function see updates the count of how many time a word has been seen, punc specifies pubctuation characters that should be considered as separate words.
To make life easy, I have already made the changes you need to Graham code,

Use the file spam.lisp. Instead of a single hash-table, I have created one hash-table *bad* for the words from the spam file [Paul Graham calls it bad] and one *good* for the words from the good email file [called good by Paul Graham]. I have removed the call to string-downcase in the function read-text since words should be kept with the original case. I have added additional characters to the list in punc since I want them to be stored as separate symbols. You are free to add more characters if needed.
You need to count how many messages you have in each of the two files, the files with spam messages and the file with good messages. This is needed to compute the probability a message is spam.

You need to create a third hash-table where you map each token to the probability that it is from a spam message. This, according to Paul Graham, can be computed as follows:

     ; ngood = number of good messages -- good = hash table of good words
     (let ((g (* 2 (or (gethash word good) 0)))
           (b (or (gethash word bad) 0)))
       (unless (< (+ g b) 5)
	       (max .01
	            (min .99 (float (/ (min 1 (/ b nbad))
				       (+ (min 1 (/ g ngood)) 
				          (min 1 (/ b nbad)))))))))

When you get a new message and you want to see if it is spam, you need to select its 15 most interesting tokens, i.e. the ones with spam probability as far away as possible from .5. Graham suggests you compute this as
```
     ;; call them probs
     (let ((prod (apply #'* probs)))
       (/ prod (+ prod (apply #'* (mapcar #'(lambda (x) (- 1 x)) probs)))))
       
```
Run your program on test data to train it, and then measure how well it performs.