DSFromScratch/Chap13/072-NaiveBayes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Chap 13 Naive Bayes\n",
    "\n",
    "#### A Really Dumb Spam Filter\n",
    "\n",
    "Let `S` be the event \"the message is spam\" and `V` be the event \"the message contains the word *viagra*.\". \n",
    "`P(S/V) = P(message is spam and contains viagra/ probability that message contains viagra)`\n",
    "\n",
    "If we have a large collection of messages we know are spam, and a large collection we know are not spam, we can estimate `P(V|S)` and `P(V|¬S)`. If we further assume that any message is equally likely to be spam or not-spam (so that `P(S) = P(¬S) = 0.5`), then:\n",
    "\n",
    "`P(S|V) = P(V|S) / P(V|S) + P(V|¬S)`\n",
    "\n",
    "E.g if 50% of spam messages have the word *viagra*, but only 1% of nonspam messages do, then the probability that any given *viagra*-containing email is spam is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9803921568627451"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(0.5/(0.5 +0.01)) # 98%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implimentation\n",
    "\n",
    "Building the classifier. First, we will make a function to tokenize messages into distinct words. We'll first convert each message to lowercase; use `re.findall()` to extract \"words\" consisting of letters, numbers and apostrophes; finally use `set()` to get just the distinct words:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tokenize(message):\n",
    "    message = message.lower() # convert to lowercase\n",
    "    all_words = re.findall(\"[a-z0-9]+\", message) # extract the words\n",
    "    return set(all_words) # remove duplicates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next function will count the words in a labeled training set of messages. We'll have to return a dictionary whose keys are words, and whose values are two-element lists[spam_count, non_spam_count] corresponding to how many times we saw that word in both spam and nonspam messages:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def count_words(training_set):\n",
    "    \"\"\"training set consists of pairs (message, is_spam)\"\"\"\n",
    "    counts = defaultdict(lambda:[0, 0])\n",
    "    for message, is_spam in training_set:\n",
    "        for word in tokenize(message):\n",
    "            counts[word][0 if is_spam else 1] += 1 # does dict[][] reference?\n",
    "    return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def word_probabilities(counts, total_spams, total_non_spams, k=0.5):\n",
    "    \"\"\"turn the word_counts into a list of triplets\n",
    "    w,(p(w | spam) and p(w | ~spam))\"\"\"\n",
    "    return[(w,(spam + k) / (total_spams + 2 * k),\n",
    "           (non_spam + k) / (total_non_spams + 2 * k)) for w, (spam, non_spam) in counts.items()]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next method uses our `word_probs` classification, determined with the training set, and applies it to a new message to be tested: `message`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def spam_probability(word_probs, message):\n",
    "    message_words = tokenize(message) # split the message up into each word\n",
    "    log_prob_if_spam = log_prob_if_not_spam = 0.0\n",
    "    \n",
    "    \n",
    "    # iterate through each word in our vocabulary dict\n",
    "    for word, prob_if_spam, prob_if_not_spam in word_probs:\n",
    "        \n",
    "        # if *word* appears in the message, add the log probability of seeing it\n",
    "        if word in message_words:\n",
    "            log_prob_if_spam += math.log(prob_if_spam)\n",
    "            log_prob_if_not_spam += math.log(prob_if_spam)\n",
    "            \n",
    "        # if *word* doesnt sppear in the message add the log probability of _not_\n",
    "        # seeing it which is log(1 - probability of seeing it)\n",
    "        else:\n",
    "            log_prob_if_spam += math.log(1.0 - prob_if_spam)\n",
    "            log_prob_if_not_spam += math.log(1.0 - prob_if_not_spam)\n",
    "        \n",
    "        prob_if_spam = math.exp(log_prob_if_spam)\n",
    "        prob_if_not_spam = math.exp(log_prob_if_not_spam)\n",
    "        return prob_if_spam / (prob_if_spam + prob_if_not_spam)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Put all of this together into a Naive Bayes Classifier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NaiveBayesClassifier:\n",
    "    \n",
    "    def __init__(self, k=0.5): # k is the psuedo count for smoothing\n",
    "        self.k = k\n",
    "        self.words_probs = []\n",
    "        \n",
    "    def train(self, training_set):\n",
    "        \n",
    "        # count spam and non-spam messages\n",
    "        num_spams = len([is_spam for message, is_spam in training_set if is_spam])\n",
    "        num_non_spams = len(training_set) - num_spams\n",
    "        \n",
    "        # run training data through our \"pipeline\"\n",
    "        word_counts = count_words(training_set)\n",
    "        self.word_probs = word_probabilities(word_counts, num_spams, num_non_spams, self.k)\n",
    "        print(list(self.word_probs)[0:10])\n",
    "        \n",
    "    def classify(self, message):\n",
    "        return spam_probability(self.word_probs, message) # when called only need to give it the message to be tested"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Testing Our Model\n",
    "\n",
    "How do we identify the subject line? Looking through the files, they all seem to start with \"Subject\" - so we'll look for that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import Counter, defaultdict\n",
    "from machine_learning import split_data\n",
    "import math, random, re, glob\n",
    "\n",
    "# path for the files\n",
    "path = r\"/home/sophie/projects/DS_fromScratch/*/*\"\n",
    "\n",
    "data = []\n",
    "\n",
    "# regex for stripping out the leading \"Subject:\" and any spaces after it\n",
    "subject_regex = re.compile(r\"^Subject:\\s+\")\n",
    "\n",
    "# glob.glob returns every filename that matches the wildcarded path\n",
    "# loops over each file in path\n",
    "for fn in glob.glob(path):\n",
    "    #print(\"fn=%s\"%fn)\n",
    "    is_spam = \"ham\" not in fn # if \"ham\" is not in the filename, sets it True\n",
    "\n",
    "    with open(fn,'r',encoding='ISO-8859-1') as file:\n",
    "        for line in file:\n",
    "            if line.startswith(\"Subject:\"):\n",
    "                subject = subject_regex.sub(\"\", line).strip()\n",
    "                data.append((subject, is_spam))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can split the data into a training data and test data, and then we're ready to build a classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "num_spams = 369\n",
      "num_non_spams = 2178\n",
      "counts =  ['kissinger', 'truck', 'orgns']\n",
      "[('kissinger', 0.0013513513513513514, 0.0006883891693437356), ('truck', 0.0013513513513513514, 0.0011473152822395595), ('orgns', 0.0013513513513513514, 0.0006883891693437356), ('delivers', 0.0013513513513513514, 0.002065167508031207), ('angry', 0.0013513513513513514, 0.0029830197338228544), ('newby', 0.0013513513513513514, 0.0011473152822395595), ('zone', 0.0013513513513513514, 0.0006883891693437356), ('tiling', 0.0013513513513513514, 0.0006883891693437356), ('university', 0.004054054054054054, 0.0002294630564479119), ('interviews', 0.0013513513513513514, 0.0011473152822395595)]\n"
     ]
    }
   ],
   "source": [
    "random.seed(0)  # to check answers with the example I am following\n",
    "train_data, test_data = split_data(data, 0.75)\n",
    "\n",
    "classifier = NaiveBayesClassifier()\n",
    "classifier.train(train_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then we can check how our model does:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# triplets (subject, actual is_spam, predicted spam probability)\n",
    "# Here we are feeding the classifier object test data.\n",
    "classified = [(subject, is_spam, classifier.classify(subject)) for subject, is_spam in test_data]\n",
    "\n",
    "# assume that spam_probability > 0.5 corresponds to spam prediction and count the \n",
    "# combinations of (actual is_spam, predicted is_spam)\n",
    "counts = Counter((is_spam, spam_probability > 0.5) for _,  is_spam, spam_probability in \n",
    "                 classified)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({(False, False): 742, (True, False): 134})\n"
     ]
    }
   ],
   "source": [
    "print(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's also look at the most misclassified:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# sort by spam_probability from smallest to largest\n",
    "classified.sort(key=lambda row: row[2])\n",
    "\n",
    "# the highest predicted spam probabilities among the non-spams\n",
    "# row[1]= True/False is_spam. If False, then not False is True and it is stored in spammiest_hams\n",
    "spammiest_hams = list(filter(lambda row: not row[1], classified))[-5:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# the lowest predicted spam probabilities among the actual spams\n",
    "hammiest_spams = list(filter(lambda row: row[1], classified))[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Core Java Technologies Tech Tips, September 10, 2002 (ArrayList vs. LinkedList, Zero-Length Arrays)', False, 0.49983409024807623), ('F2M - Ihre kostenlose Faxnummer - Newsletter', False, 0.49983409024807623), (\"Market Can't Find Its Bottom With Both Hands\", False, 0.49983409024807623), ('[Lockergnome Apple Core]  Skip Content', False, 0.49983409024807623), (\"Re: Hi! I'm new here.\", False, 0.49983409024807623)]\n",
      "------------\n",
      "[('New Version 7: Uncover the TRUTH about ANYONE!', True, 0.49983409024807623), ('Low Price Smokes', True, 0.49983409024807623), ('Dont waste your TIME!!! Why?', True, 0.49983409024807623), ('Toners and inkjet cartridges for less....               NOAZ', True, 0.49983409024807623), ('zzzz,All New! Breast Enhancement', True, 0.49983409024807623)]\n"
     ]
    }
   ],
   "source": [
    "print(spammiest_hams) # the messages found in ham which had a high % probability of being spam\n",
    "print(\"------------\")\n",
    "print(hammiest_spams) # the messages in spam which have the highest probability of not being spam."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly we can look at the spammiest *words*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def p_spam_given_word(word_prob):\n",
    "    \"\"\"uses bayes's theorem to compute p(spam | message contains word)\"\"\"\n",
    "    \n",
    "    # word_prob is one of the triplets produced by word_probabilities\n",
    "    word, prob_if_spam, prob_if_not_spam = word_prob\n",
    "    return prob_if_spam / (prob_if_spam + prob_if_not_spam) # calculating bayes theorem here.\n",
    "\n",
    "# This is sorted by applying bayes theorem to each \n",
    "words = sorted(classifier.word_probs, key=p_spam_given_word) # classifier.word_probs = self.word_probs is a class \n",
    "                                                             # attribute.\n",
    "spammiest_words = words[-5:]\n",
    "hammiest_words = words[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('clearance', 0.022972972972972974, 0.0002294630564479119), ('sale', 0.02837837837837838, 0.0002294630564479119), ('systemworks', 0.033783783783783786, 0.0002294630564479119), ('money', 0.03918918918918919, 0.0002294630564479119), ('adv', 0.041891891891891894, 0.0002294630564479119)]\n",
      "---------------\n",
      "[('satalk', 0.0013513513513513514, 0.0502524093620927), ('spambayes', 0.0013513513513513514, 0.047957778797613586), ('users', 0.0013513513513513514, 0.03832033042680129), ('was', 0.0013513513513513514, 0.037402478201009635), ('razor', 0.0013513513513513514, 0.032354290959155575)]\n"
     ]
    }
   ],
   "source": [
    "# words most likely to sppear in spam\n",
    "print(spammiest_words) # this prints out word_probs triplets, sorted by application of bayes theorem to the 2nd and 3rd\n",
    "                       # elements\n",
    "print(\"---------------\")\n",
    "\n",
    "# words most likely to appear in ham\n",
    "print(hammiest_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How could we get better performance? 1) Get more data to train on. 2) improve the model. Some ways to do this:\n",
    "\n",
    "- Look at message content, not just the subject line.\n",
    "- Modify the classifier to accept an optional `min_count` threshold and ignore tokens that don't appear at least that many times\n",
    "- The tokenizer has no notion of similar words (e.g. \"cheap\" and \"cheapest\"). Modify the classifer to take an optional stemmer function that converts words to `equivalence classes` of words. For example, a really simple stemmer function might be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def drop_final_s(word):\n",
    "    return re.sub(\"S$\", \"\", word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Creating a good stemmer function is hard. People frequently use the [`Porter Stemmer`](http://tartarus.org/martin/PorterStemmer/)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}