spam-classifier.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Language model\n",
    "\n",
    "Language model is a probability distribution over sequences of word.\n",
    "In this lab we will apply laguage model for a classification problem. The task is to implement a filter for spam documents."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dataset\n",
    "Download this https://www.kaggle.com/uciml/sms-spam-collection-dataset dataset.\n",
    "Here we normalize the text and split it by sentences using nltk library. Then sentences are splitted to the terms. For simplicity we will lose the punctuation and characters register."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import re\n",
    "import string\n",
    "import nltk\n",
    "import random\n",
    "from nltk.tokenize import sent_tokenize, word_tokenize\n",
    "from sklearn import metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize(text):\n",
    "    text = text.lower()\n",
    "    text = re.sub('\\W+',' ', text)\n",
    "    text = text.encode(\"ascii\", errors=\"ignore\").decode()\n",
    "    text = text.translate(str.maketrans('', '', string.punctuation))\n",
    "    text = text.strip()\n",
    "    return text\n",
    "\n",
    "def tokenize(text):\n",
    "    sentences = sent_tokenize(text)\n",
    "    words = []\n",
    "    for sent in sentences:\n",
    "        words.append(word_tokenize(normalize(sent)))\n",
    "    return words                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>category</th>\n",
       "      <th>text</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>ham</td>\n",
       "      <td>Go until jurong point, crazy.. Available only ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>ham</td>\n",
       "      <td>Ok lar... Joking wif u oni...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>spam</td>\n",
       "      <td>Free entry in 2 a wkly comp to win FA Cup fina...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>ham</td>\n",
       "      <td>U dun say so early hor... U c already then say...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>ham</td>\n",
       "      <td>Nah I don't think he goes to usf, he lives aro...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>spam</td>\n",
       "      <td>FreeMsg Hey there darling it's been 3 week's n...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>ham</td>\n",
       "      <td>Even my brother is not like to speak with me. ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>ham</td>\n",
       "      <td>As per your request 'Melle Melle (Oru Minnamin...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>spam</td>\n",
       "      <td>WINNER!! As a valued network customer you have...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>spam</td>\n",
       "      <td>Had your mobile 11 months or more? U R entitle...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  category                                               text\n",
       "0      ham  Go until jurong point, crazy.. Available only ...\n",
       "1      ham                      Ok lar... Joking wif u oni...\n",
       "2     spam  Free entry in 2 a wkly comp to win FA Cup fina...\n",
       "3      ham  U dun say so early hor... U c already then say...\n",
       "4      ham  Nah I don't think he goes to usf, he lives aro...\n",
       "5     spam  FreeMsg Hey there darling it's been 3 week's n...\n",
       "6      ham  Even my brother is not like to speak with me. ...\n",
       "7      ham  As per your request 'Melle Melle (Oru Minnamin...\n",
       "8     spam  WINNER!! As a valued network customer you have...\n",
       "9     spam  Had your mobile 11 months or more? U R entitle..."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "messages = pd.read_csv('spam.csv', encoding=\"latin1\")\n",
    "messages = messages.drop(labels = [\"Unnamed: 2\", \"Unnamed: 3\", \"Unnamed: 4\"], axis = 1)\n",
    "messages.columns = [\"category\", \"text\"]\n",
    "display(messages.head(n = 10))\n",
    "\n",
    "spam_messages = messages[messages[\"category\"] == \"spam\"][\"text\"]\n",
    "ham_messages = messages[messages[\"category\"] == \"ham\"][\"text\"]\n",
    "\n",
    "spam_sentences = []\n",
    "ham_sentences = [] \n",
    "\n",
    "for message in spam_messages:\n",
    "    spam_sentences.extend(tokenize(message))\n",
    "    \n",
    "for message in ham_messages:\n",
    "    ham_sentences.extend(tokenize(message)) \n",
    "\n",
    "#list of sentences, each sentence represented as a list of terms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate the average length and average number of sentences in spam message."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "average length of a spam message:  27.70682730923695\n",
      "average length of a sentence in spam message:  9.174202127659575\n",
      "average number of sentences in spam message:  3.0200803212851404\n"
     ]
    }
   ],
   "source": [
    "message_count = len(spam_messages)\n",
    "message_length = 0\n",
    "sentence_number = 0\n",
    "sentence_length = 0\n",
    "\n",
    "for spam in spam_messages:\n",
    "    sentences = sent_tokenize(spam)\n",
    "    for sent in sentences:\n",
    "        sentence_length += len(word_tokenize(sent))\n",
    "    sentence_number += len(sentences)\n",
    "    message_length += len(word_tokenize(spam))\n",
    "    \n",
    "spam_message_length = round(message_length/message_count)\n",
    "spam_message_sentence_length = round(sentence_length/sentence_number)\n",
    "spam_message_sentence_number = round(sentence_number/message_count)\n",
    "\n",
    "print('average length of a spam message: ', message_length/message_count)\n",
    "print('average length of a sentence in spam message: ', sentence_length/sentence_number)\n",
    "print('average number of sentences in spam message: ', sentence_number/message_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Unigram model\n",
    "\n",
    "Calculate the number of occurancies of each term separately for spam and ham messages and the total number of terms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_dict(sentences):\n",
    "    terms = dict()\n",
    "    for sent in sentences:\n",
    "        for word in sent:\n",
    "            count = terms.get(word, 0)\n",
    "            terms.update({word: count + 1})\n",
    "    return terms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2886 6851\n"
     ]
    }
   ],
   "source": [
    "spam_term_c = build_dict(spam_sentences)\n",
    "spam_N = len(spam_term_c)\n",
    "ham_term_c = build_dict(ham_sentences)\n",
    "ham_N = len(ham_term_c)\n",
    "\n",
    "print(spam_N, ham_N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Print 10 most popular words in spam messages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('to', 688) ('a', 378) ('call', 355) ('you', 297) ('your', 264) ('free', 224) ('2', 206) ('the', 206) ('for', 204) ('now', 199)\n"
     ]
    }
   ],
   "source": [
    "spam_sorted = sorted(spam_term_c.items(), key=lambda x: x[1], reverse=True)\n",
    "\n",
    "print(*spam_sorted[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bigram model\n",
    "\n",
    "We use sentence begining and sentence ending as a special terms (\"<s\" and \"/s>\" respectively). \n",
    "\n",
    "Calculate the number of occuracnies for bigrams (as a key in dictionary we use words, separated by the space symbol) - **build_bigram_dict**.\n",
    "\n",
    "Also, for using in a generative model, for each term we will need a list of next term, found in the dataset - **build_next_term**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_bigram_dict(sentences):\n",
    "    terms = dict()\n",
    "    for sent in sentences:\n",
    "        sent.insert(0, '<s') \n",
    "        sent.append('/s>')\n",
    "        for i in range(len(sent) - 1):\n",
    "            word1 = sent[i]\n",
    "            word2 = sent[i+1]\n",
    "            bigram = word1 + ' ' + word2\n",
    "            count = terms.get(bigram, 0)\n",
    "            terms.update({bigram: count + 1})\n",
    "            \n",
    "    return terms\n",
    "\n",
    "def build_next_term(spam_dict, spam_bigram_dict):\n",
    "    next_term = dict()\n",
    "    for word in spam_dict:\n",
    "        terms = []\n",
    "        for bigram in spam_bigram_dict:\n",
    "            if bigram.startswith(word+\" \"):\n",
    "                length = len(word) + 1\n",
    "                next_word = bigram[length:]\n",
    "                count = spam_bigram_dict[bigram]\n",
    "                terms.append((next_word, count))\n",
    "        terms = sorted(terms, key=lambda x: x[1], reverse=True)\n",
    "        next_term[word] = terms\n",
    "    return next_term "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_term_c[\"<s\"] = len(spam_sentences)\n",
    "spam_term_c[\"/s>\"] = len(spam_sentences)\n",
    "\n",
    "ham_term_c[\"<s\"] = len(ham_sentences)\n",
    "ham_term_c[\"/s>\"] = len(ham_sentences)\n",
    "\n",
    "spam_bigram_c = build_bigram_dict(spam_sentences)\n",
    "spam_next_words = build_next_term(spam_term_c, spam_bigram_c)\n",
    "\n",
    "ham_bigram_c = build_bigram_dict(ham_sentences)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('be', 25), ('b', 4), ('blow', 2), ('go', 2), ('not', 1), ('u', 1), ('recieve', 1), ('receive', 1), ('arrive', 1), ('the', 1), ('smith', 1), ('/s>', 1), ('ignore', 1), ('enter', 1), ('give', 1)]\n"
     ]
    }
   ],
   "source": [
    "print(spam_next_words[\"will\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which bigrams are the most popular in spam messages?\n",
    "\n",
    "From which words spam sentence usually begins?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "most popular bigrams in spam messages are:\n",
      "('<s <s', 2256) ('/s> /s>', 2256) ('<s call', 149) ('now /s>', 98) ('<s you', 83) ('you have', 73) ('<s your', 67) ('<s to', 66) ('<s txt', 61) ('have won', 54) \n",
      "\n",
      "most popular starting words in spam messages are:\n",
      "('<s', 2256) ('call', 149) ('you', 83) ('your', 67) ('to', 66) ('txt', 61) ('urgent', 53) ('free', 39) ('text', 39) ('this', 37)\n"
     ]
    }
   ],
   "source": [
    "spam_bigram_sorted = sorted(spam_bigram_c.items(), key=lambda x: x[1], reverse=True)\n",
    "\n",
    "print(\"most popular bigrams in spam messages are:\")\n",
    "print(*spam_bigram_sorted[:10], \"\\n\")\n",
    "\n",
    "print(\"most popular starting words in spam messages are:\")\n",
    "startings = [(bigram[0][3:], bigram[1]) for bigram in spam_bigram_sorted if '<s' in bigram[0]] \n",
    "print(*startings[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Genetative model\n",
    "\n",
    "Now using out language model let's generate a spam message. \n",
    "\n",
    "We use the calculated values for average sentence number in message and an average sentence length.\n",
    "Just start with a random sentence beginning ```random.choice(spam_next_words['<s'])[0]``` and go through dictionary of bigrams, choosing randomly next word of ```randomness``` most popular to follow."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_spam(start_word=\"\", randomness = 5):\n",
    "    message = \"\"\n",
    "    for _ in range(spam_message_sentence_number):\n",
    "        if len(start_word) == 0:\n",
    "            start_word = random.choice(spam_next_words['<s'])[0]\n",
    "        message += start_word[:1].upper() + start_word[1:]\n",
    "        for _ in range(spam_message_sentence_length):\n",
    "            next_possible = spam_next_words[start_word]\n",
    "            next_word = random.choice(next_possible[:min(randomness, len(next_possible))])[0]\n",
    "            \n",
    "            if next_word == \"/s>\":\n",
    "                message += \". \"\n",
    "                break\n",
    "                \n",
    "            message += \" \" + next_word\n",
    "            start_word = next_word  \n",
    "        if not next_word == \"/s>\":\n",
    "            message += \". \"\n",
    "        start_word = \"\"\n",
    "    return message"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "I have 1 new mobiles with u. Hard live operator. Pushbutton 2 contact u u know u can win our. \n"
     ]
    }
   ],
   "source": [
    "print(generate_spam())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 302,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hungry gay chat to claim call now. Wow. Claire here http www ldew com1win150ppmx3age16. \n"
     ]
    }
   ],
   "source": [
    "print(generate_spam())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 397,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Urgent message. Call 08000930705 for free entry into 121 chat to 86688. Text messages by a 2000 gift. \n"
     ]
    }
   ],
   "source": [
    "print(generate_spam(\"urgent\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 346,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello from your mobile update for a new voicemail. This message waiting for free entry std text back if. This week. \n"
     ]
    }
   ],
   "source": [
    "print(generate_spam(\"hello\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Smoothing\n",
    "\n",
    "The problem is that if the bigram $t_1 t_2$ occuted $0$ times in the corpus, the conditional probability $P(t_2|t_1) = 0$\n",
    "\n",
    "The solution is smoothing. Read this document https://nlp.stanford.edu/~wcmac/papers/20050421-smoothing-tutorial.pdf\n",
    "\n",
    "Here we implement the Jelinek-Mercer smoothing (interpolation) and a functions (smoothing_prob_spam & smoothing_prob_ham), that return the conditional probability $P(t_2 | t_1)$ with a smoothing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "def smoothing_prob_spam(x, s, l=0.8):\n",
    "    if s + \" \" + x in spam_bigram_c:\n",
    "        prob_xs = spam_bigram_c[s + \" \" + x] / spam_term_c[s]\n",
    "    else: \n",
    "        prob_xs = 0\n",
    "    if x in spam_term_c:\n",
    "        prob_x = spam_term_c[x] / sum(spam_term_c.values())\n",
    "    else: \n",
    "        prob_x = 0\n",
    "    return l * prob_xs + (1 - l) * prob_x\n",
    "\n",
    "def smoothing_prob_ham(x, s, l=0.8):\n",
    "    if s + \" \" + x in ham_bigram_c:\n",
    "        prob_xs = ham_bigram_c[s + \" \" + x] / ham_term_c[s]\n",
    "    else: \n",
    "        prob_xs = 0\n",
    "    if x in ham_term_c:\n",
    "        prob_x = ham_term_c[x] / sum(ham_term_c.values())\n",
    "    else: \n",
    "        prob_x = 0\n",
    "    return l * prob_xs + (1 - l) * prob_x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classification\n",
    "\n",
    "Now, let's implement a Bayesian Classifier for the sentence and test one of our generated sentences on it.\n",
    "\n",
    "The Bayesian Classifier returns, which probability is higher: $P(spam|t_1, \\dots , t_k)$ or $P(ham|t_1, \\dots , t_k)$, where:\n",
    "\n",
    "$$P(spam|t_1, \\dots , t_k) = \\frac{P(t_1, \\dots , t_k|spam)P(spam)}{P(t_1, \\dots , t_k)} \\sim P(t_1, \\dots , t_k|spam)P(spam)$$ \n",
    "$$\\sim P(t_1 | BEGIN, spam) \\cdot \\sim P(t_2 | t_1, spam) \\cdot \\dots \\cdot \\sim P(END | t_k, spam)$$\n",
    "\n",
    "(and the same for ham)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(sentence):\n",
    "    sentence = word_tokenize(normalize(sentence))\n",
    "    sentence.insert(0, '<s') \n",
    "    sentence.append('/s>')\n",
    "    prob_spam = 1\n",
    "    prob_ham = 1\n",
    "    for i in range(len(sentence) - 1):\n",
    "        word1 = sentence[i]\n",
    "        word2 = sentence[i+1]\n",
    "        prob_spam = prob_spam * smoothing_prob_spam(word2, word1)\n",
    "        prob_ham = prob_ham * smoothing_prob_ham(word2, word1)\n",
    "    if prob_spam > prob_ham: return 1\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the sentence is spam\n"
     ]
    }
   ],
   "source": [
    "spam = classify(\"Hello from your mobile update for a new voicemail\")\n",
    "if spam: print(\"the sentence is spam\")\n",
    "else: print(\"the sentence is ham\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing\n",
    "Let's now evaluate the classifier using sklearn metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_sentences_raw = []\n",
    "for message in spam_messages:\n",
    "    spam_sentences_raw.extend(sent_tokenize(message))\n",
    "    \n",
    "ham_sentences_raw = []\n",
    "for message in ham_messages:\n",
    "    ham_sentences_raw.extend(sent_tokenize(message))\n",
    "\n",
    "\n",
    "X = spam_sentences_raw + ham_sentences_raw\n",
    "y = [1] * len(spam_sentences_raw) + [0] * len(ham_sentences_raw)\n",
    "y_pred = []\n",
    "for sentence in X:\n",
    "    y_pred.append(classify(sentence))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy: 0.9957646210687573\n"
     ]
    }
   ],
   "source": [
    "print(\"Accuracy:\",metrics.accuracy_score(y, y_pred))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              precision    recall  f1-score   support\n",
      "\n",
      "           0       1.00      1.00      1.00      8841\n",
      "           1       0.98      0.99      0.99      2256\n",
      "\n",
      "    accuracy                           1.00     11097\n",
      "   macro avg       0.99      1.00      0.99     11097\n",
      "weighted avg       1.00      1.00      1.00     11097\n",
      "\n",
      "0: ham\n",
      "1: spam\n"
     ]
    }
   ],
   "source": [
    "print(metrics.classification_report(y, y_pred))\n",
    "print(\"0: ham\")\n",
    "print(\"1: spam\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}