Email_Spam_Classifier.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Importing Packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 326,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "from nltk.stem import PorterStemmer, WordNetLemmatizer\n",
    "from stemming.porter2 import stem\n",
    "import glob\n",
    "from random import shuffle\n",
    "import pandas as pd\n",
    "import re\n",
    "import operator\n",
    "import numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 413,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk import pos_tag\n",
    "from nltk.tokenize import word_tokenize\n",
    "from nltk.corpus import wordnet\n",
    "from math import floor\n",
    "import numpy as np\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "stemmer = PorterStemmer()\n",
    "lemmatiser = WordNetLemmatizer()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# General Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 698,
   "metadata": {},
   "outputs": [],
   "source": [
    "def randomize_files(file_list):\n",
    "    shuffle(file_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 699,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_training_and_testing_sets(file_list, split):\n",
    "\n",
    "    split_index = floor(len(file_list) * split)\n",
    "    training = file_list[:split_index]\n",
    "    testing = file_list[split_index:]\n",
    "    return training, testing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 700,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reading_files_to_list(file_name_list):\n",
    "    storing_list = list()\n",
    "    for file in file_name_list:                      # iterate over the list getting each file \n",
    "        with open(file, encoding=\"latin-1\") as f:\n",
    "            text = f.read()\n",
    "            storing_list.append(text)\n",
    "    return storing_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 701,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to return correct positional argument as per wordnet for lemmatiser function in the next block     \n",
    "def get_wordnet_pos(treebank_tag):\n",
    "    if treebank_tag.startswith('J'):\n",
    "        return wordnet.ADJ\n",
    "    elif treebank_tag.startswith('V'):\n",
    "        return wordnet.VERB\n",
    "    elif treebank_tag.startswith('N'):\n",
    "        return wordnet.NOUN\n",
    "    elif treebank_tag.startswith('R'):\n",
    "        return wordnet.ADV\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 702,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cleaning_stemming(email_list):\n",
    "    # Removing special cahracters like !,@, ., %, etc and keeping only alphabets and numbers\n",
    "    clean_email = list()\n",
    "    for email in email_list:\n",
    "        string = email\n",
    "        string = re.sub(\"\\.(?!$\\d)\",'', str(string))\n",
    "        string = re.sub(\"[^A-Za-z0-9]+\", ' ', str(string))\n",
    "        clean_email.append(string)\n",
    "\n",
    "    tokenized_email = list()\n",
    "    for email in clean_email:\n",
    "        tokens = word_tokenize(email)\n",
    "        tokens_pos = pos_tag(tokens)\n",
    "        tokenized_email.append(tokens_pos)\n",
    "        \n",
    "    email_lemma = list()\n",
    "    for token in tokenized_email:\n",
    "        temp_word = list()\n",
    "        for word in token:\n",
    "            try:\n",
    "                temp_word.append(lemmatiser.lemmatize(word[0].lower(), pos = get_wordnet_pos(word[1]))) #used the above function\n",
    "            except:\n",
    "                continue\n",
    "        email_lemma.append(temp_word)\n",
    "    return email_lemma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 703,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_email_str(test_clean):\n",
    "    temp_list = []\n",
    "    for item in test_clean:\n",
    "        temp_str = ' '.join(item)\n",
    "        temp_list.append(temp_str)\n",
    "    return temp_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 704,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bag_of_words(email_lemma):\n",
    "    clean_dict = {}\n",
    "    for i in email_lemma:\n",
    "        for word in i:\n",
    "            if word not in clean_dict:\n",
    "                clean_dict[word] = 1\n",
    "            else:\n",
    "                clean_dict[word] = clean_dict[word] + 1\n",
    "    \n",
    "    word_bag = {}\n",
    "    for i in sorted(clean_dict.keys()):\n",
    "        word_bag[i] = clean_dict[i]\n",
    "    return word_bag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 705,
   "metadata": {},
   "outputs": [],
   "source": [
    "def probab_word_given_spam_or_ham(email_words, word_bag):\n",
    "    probability = 1.0\n",
    "    for word in email_words:\n",
    "        if word in list(set(word_bag)):\n",
    "            numerator = word_bag[word] + 1           # 1 is Laplace Smoothing\n",
    "            denominator = sum(word_bag.values()) + len(word_bag.keys())    #Again, Laplace Smoothing\n",
    "            prob_temp = float(numerator) / float(denominator)\n",
    "            probability = probability * prob_temp\n",
    "        else:\n",
    "            numerator = 1\n",
    "            denominator = sum(word_bag.values()) + len(word_bag.keys())    #Again, Laplace Smoothing\n",
    "            prob_temp = float(numerator) / float(denominator)\n",
    "            probability = probability * prob_temp\n",
    "    return probability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 706,
   "metadata": {},
   "outputs": [],
   "source": [
    "def probab_word(email_words):\n",
    "    probability = 1.0\n",
    "    denominator = len(email_words)\n",
    "    for word in list(set(email_words)):\n",
    "        numerator = email_words.count(word)\n",
    "        prob_temp = float(numerator) + 1 / float(denominator)\n",
    "        probability = probability * prob_temp\n",
    "    return probability\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 707,
   "metadata": {},
   "outputs": [],
   "source": [
    "def spam_given_email(email_words, spam_word_bag, spam_train_list, ham_train_list):\n",
    "    probab_spam = float(len(spam_train_list) / (len(spam_train_list) + len(ham_train_list)))\n",
    "    probability = (probab_word_given_spam_or_ham(email_words, spam_word_bag) * probab_spam) / probab_word(email_words)\n",
    "    return probability\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 708,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ham_given_email(email_words, ham_word_bag, spam_train_list, ham_train_list):\n",
    "    probab_ham = float(len(ham_train_list) / (len(spam_train_list) + len(ham_train_list)))\n",
    "    probability = (probab_word_given_spam_or_ham(email_words, ham_word_bag) * probab_ham) / probab_word(email_words)\n",
    "    return probability\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 709,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classifier(email_words, spam_word_bag, ham_word_bag, spam_train_list, ham_train_list):\n",
    "    p_Spam = spam_given_email(email_words, spam_word_bag, spam_train_list, ham_train_list)\n",
    "    p_Ham = ham_given_email(email_words, ham_word_bag, spam_train_list, ham_train_list)\n",
    "    \n",
    "    if p_Spam > p_Ham:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 741,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Reading the SPAM email files and dividing it into the train and test\n",
    "\n",
    "path = '/Users/sumeetkotaria/Desktop/Machine Learning/HW1/Dataset/spam/*.txt'\n",
    "spam_files = glob.glob(path)\n",
    "randomize_files(spam_files)\n",
    "spam_train_file, spam_test_file = get_training_and_testing_sets(spam_files,0.75)    #Spliting SPAM files to Train and Test\n",
    "\n",
    "# Reading spam emails to list\n",
    "spam_train_list = reading_files_to_list(spam_train_file)\n",
    "spam_test_list = reading_files_to_list(spam_test_file)\n",
    "\n",
    "# Reading the HAM email files and dividing it into the train and test\n",
    "path = '/Users/sumeetkotaria/Desktop/Machine Learning/HW1/Dataset/ham/*.txt'\n",
    "ham_files = glob.glob(path)\n",
    "randomize_files(ham_files)\n",
    "ham_train_file, ham_test_file = get_training_and_testing_sets(ham_files,0.75)    #Splitting HAM files to Train and Test\n",
    "\n",
    "# Reading ham emails to list\n",
    "ham_train_list = reading_files_to_list(ham_train_file)\n",
    "ham_test_list = reading_files_to_list(ham_test_file)\n",
    "\n",
    "\n",
    "# Setting test data\n",
    "spam_test_clean = cleaning_stemming(spam_test_list)\n",
    "ham_test_clean = cleaning_stemming(ham_test_list)\n",
    "\n",
    "spam_test_str = test_email_str(spam_test_clean)\n",
    "ham_test_str = test_email_str(ham_test_clean)\n",
    "\n",
    "# Cleaning train_data\n",
    "spam_train_clean = cleaning_stemming(spam_train_list)\n",
    "ham_train_clean = cleaning_stemming(ham_train_list)\n",
    "\n",
    "\n",
    "# Bag of words for train and test\n",
    "spam_word_bag = bag_of_words(spam_train_clean)\n",
    "ham_word_bag = bag_of_words(ham_train_clean)\n",
    "\n",
    "df_spam_test = pd.DataFrame(spam_test_str, columns = ['Email'])\n",
    "df_spam_test['Actual Spam / No Spam'] = 1\n",
    "df_spam_test['predict'] = 0\n",
    "df_ham_test = pd.DataFrame(ham_test_str, columns = ['Email'])\n",
    "df_ham_test['Actual Spam / No Spam'] = 0\n",
    "df_ham_test['predict'] = 0\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 711,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_data = pd.concat([df_spam_test,df_ham_test], ignore_index = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 712,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/sumeetkotaria/anaconda3/lib/python3.6/site-packages/ipykernel_launcher.py:4: SettingWithCopyWarning: \n",
      "A value is trying to be set on a copy of a slice from a DataFrame\n",
      "\n",
      "See the caveats in the documentation: http://pandas.pydata.org/pandas-docs/stable/indexing.html#indexing-view-versus-copy\n",
      "  after removing the cwd from sys.path.\n"
     ]
    }
   ],
   "source": [
    "for index, row in test_data.iterrows():\n",
    "    email_str = row['Email']\n",
    "    email_words = email_str.split()\n",
    "    test_data['predict'][index] = classifier(email_words, spam_word_bag, ham_word_bag, spam_train_list, ham_train_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 713,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8739365815931941"
      ]
     },
     "execution_count": 713,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = np.sum(test_data['Actual Spam / No Spam'] == test_data['predict'])\n",
    "b = np.sum(test_data['Actual Spam / No Spam'] != test_data['predict'])\n",
    "a/(a+b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The accaracy of Naive Bayes Classifer is 87.39%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nearest Neighbour"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 742,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vectorize(email_list, dictionary):     #email_list is list of list of words in email\n",
    "    vector = []\n",
    "    for email in email_list:\n",
    "        email_vector = []\n",
    "        for key in dictionary:\n",
    "            temp = email.count(dictionary[key])\n",
    "            email_vector.append(temp)\n",
    "        vector.append(email_vector)\n",
    "    \n",
    "    return vector\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 743,
   "metadata": {},
   "outputs": [],
   "source": [
    "def creating_dictionary(clean_train_list):\n",
    "    \n",
    "    list_of_words = [item for subitem in clean_train_list for item in subitem]\n",
    "    dict_temp = list(set(list_of_words))\n",
    "    main_dictionary = dict(enumerate(dict_temp))\n",
    "    \n",
    "    return main_dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 744,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_list = spam_train_list + ham_train_list\n",
    "clean_train_list = cleaning_stemming(train_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 745,
   "metadata": {},
   "outputs": [],
   "source": [
    "dictionary = creating_dictionary(clean_train_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 746,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 'undermine',\n",
       " 1: 'tentative',\n",
       " 2: 'bdtydnd',\n",
       " 3: 'vor',\n",
       " 4: 'horton',\n",
       " 5: 'roose',\n",
       " 6: 'quetzal',\n",
       " 7: 'granada',\n",
       " 8: 'agitation',\n",
       " 9: 'ejya',\n",
       " 10: 'bassinet',\n",
       " 11: 'l',\n",
       " 12: 'orebody',\n",
       " 13: 'prose',\n",
       " 14: 'hdr',\n",
       " 15: 'thereto',\n",
       " 16: 'colorate',\n",
       " 17: 'polach',\n",
       " 18: 'creosote',\n",
       " 19: 'pieasantly',\n",
       " 20: 'consummate',\n",
       " 21: 'hesitate',\n",
       " 22: 'spill',\n",
       " 23: 'iekouqi',\n",
       " 24: 'marsh',\n",
       " 25: 'lesson',\n",
       " 26: 'sullivan',\n",
       " 27: 'fly',\n",
       " 28: 'wigging',\n",
       " 29: 'shake',\n",
       " 30: 'dawn',\n",
       " 31: 'ameliorate',\n",
       " 32: 'ple',\n",
       " 33: 'klement',\n",
       " 34: 'pre',\n",
       " 35: 'banking',\n",
       " 36: 'cecilia',\n",
       " 37: 'unitholders',\n",
       " 38: 'colloidal',\n",
       " 39: 'pull',\n",
       " 40: 'sri',\n",
       " 41: 'ocean',\n",
       " 42: 'vega',\n",
       " 43: 'passionvalhalla',\n",
       " 44: 'nico',\n",
       " 45: 'uscriabin',\n",
       " 46: 'orig',\n",
       " 47: 'potter',\n",
       " 48: 'wwwkbhbbbzn',\n",
       " 49: 'jepson',\n",
       " 50: 'wean',\n",
       " 51: 'stock',\n",
       " 52: 'bring',\n",
       " 53: 'palindrome',\n",
       " 54: 'asteroidal',\n",
       " 55: 'dvd',\n",
       " 56: 'ppo',\n",
       " 57: 'hdp',\n",
       " 58: 'wbukxoirements',\n",
       " 59: 'symbo',\n",
       " 60: 'tkm',\n",
       " 61: 'dissolve',\n",
       " 62: 'jlnyjxfp',\n",
       " 63: 'basically',\n",
       " 64: 'diving',\n",
       " 65: 'coral',\n",
       " 66: 'following',\n",
       " 67: 'fbpzunusw',\n",
       " 68: 'comc',\n",
       " 69: 'delinvest',\n",
       " 70: 'treasurer',\n",
       " 71: 'dungeon',\n",
       " 72: 'winter',\n",
       " 73: 'axisymmetric',\n",
       " 74: 'demagogue',\n",
       " 75: 'olympics',\n",
       " 76: 'disneyland',\n",
       " 77: 'dchdpo',\n",
       " 78: 'grosvenor',\n",
       " 79: 'builetin',\n",
       " 80: 'alvina',\n",
       " 81: 'nesi',\n",
       " 82: 'lunar',\n",
       " 83: 'bridgeback',\n",
       " 84: 'inefficacy',\n",
       " 85: 'asltom',\n",
       " 86: 'goughary',\n",
       " 87: 'rebel',\n",
       " 88: 'mcbeath',\n",
       " 89: 'lute',\n",
       " 90: 'tamc',\n",
       " 91: 'tiiiiiiighten',\n",
       " 92: 'excellence',\n",
       " 93: 'sioma',\n",
       " 94: 'fucker',\n",
       " 95: 'landowner',\n",
       " 96: 'excrescent',\n",
       " 97: 'lamphier',\n",
       " 98: 'gross',\n",
       " 99: 'longhand',\n",
       " 100: 'evoke',\n",
       " 101: 'malicious',\n",
       " 102: 'uvdc',\n",
       " 103: 'opmjpv',\n",
       " 104: 'healthy',\n",
       " 105: 'embroil',\n",
       " 106: 'huntington',\n",
       " 107: 'stoff',\n",
       " 108: 'gmtaualvu',\n",
       " 109: 'disc',\n",
       " 110: 'xelbbjllk',\n",
       " 111: 'phy',\n",
       " 112: 'flickz',\n",
       " 113: 'lebanese',\n",
       " 114: 'tmmkr',\n",
       " 115: 'gljpf',\n",
       " 116: 'mttrqc',\n",
       " 117: 'glare',\n",
       " 118: 'iwqbq',\n",
       " 119: 'turkey',\n",
       " 120: 'dmxpp',\n",
       " 121: 'avaiiabie',\n",
       " 122: 'dll',\n",
       " 123: 'weygandt',\n",
       " 124: 'pete',\n",
       " 125: 'sandbag',\n",
       " 126: 'collaboration',\n",
       " 127: 'jederzeit',\n",
       " 128: 'passlink',\n",
       " 129: 'holeable',\n",
       " 130: 'marji',\n",
       " 131: 'parakeet',\n",
       " 132: 'exeter',\n",
       " 133: 'orleans',\n",
       " 134: 'obispo',\n",
       " 135: 'mbag',\n",
       " 136: 'soignet',\n",
       " 137: 'guuaarantee',\n",
       " 138: 'protract',\n",
       " 139: 'jafry',\n",
       " 140: 'phentermlne',\n",
       " 141: 'faraday',\n",
       " 142: 'sprechen',\n",
       " 143: 'forgiveness',\n",
       " 144: 'wider',\n",
       " 145: 'specifyplease',\n",
       " 146: 'diatribe',\n",
       " 147: 'fuse',\n",
       " 148: 'messagelogin',\n",
       " 149: 'intially',\n",
       " 150: 'olvmll',\n",
       " 151: 'invitation',\n",
       " 152: 'egas',\n",
       " 153: 'designation',\n",
       " 154: 'tanisha',\n",
       " 155: 'mheffner',\n",
       " 156: 'lls',\n",
       " 157: 'fasciculate',\n",
       " 158: 'coarsen',\n",
       " 159: 'lunch',\n",
       " 160: 'attention',\n",
       " 161: 'osteopathic',\n",
       " 162: 'nba',\n",
       " 163: 'expensive',\n",
       " 164: 'balky',\n",
       " 165: 'penny',\n",
       " 166: 'iayngheyp',\n",
       " 167: 'parkfield',\n",
       " 168: 'intelligence',\n",
       " 169: 'educable',\n",
       " 170: 'gebiet',\n",
       " 171: 'equilibrate',\n",
       " 172: 'ndrsr',\n",
       " 173: 'upbringcoexist',\n",
       " 174: 'hydrology',\n",
       " 175: 'jockstrap',\n",
       " 176: 'avktla',\n",
       " 177: 'fontr',\n",
       " 178: 'rinehart',\n",
       " 179: 'tpfcesai',\n",
       " 180: 'llqwzg',\n",
       " 181: 'lebensgeschichte',\n",
       " 182: 'pumper',\n",
       " 183: 'partial',\n",
       " 184: 'bauble',\n",
       " 185: 'kayebeatty',\n",
       " 186: 'pvaovu',\n",
       " 187: 'border',\n",
       " 188: 'oiy',\n",
       " 189: 'cobo',\n",
       " 190: 'lipitor',\n",
       " 191: 'drag',\n",
       " 192: 'ertagacha',\n",
       " 193: 'kiowa',\n",
       " 194: 'vf',\n",
       " 195: 'fontbrhl',\n",
       " 196: 'morris',\n",
       " 197: 'posiprods',\n",
       " 198: 'liverpool',\n",
       " 199: 'diffract',\n",
       " 200: 'quelle',\n",
       " 201: 'cheeky',\n",
       " 202: 'stoop',\n",
       " 203: 'fjvytcs',\n",
       " 204: 'aggravate',\n",
       " 205: 'neptune',\n",
       " 206: 'vances',\n",
       " 207: 'laredo',\n",
       " 208: 'teiecommunications',\n",
       " 209: 'twic',\n",
       " 210: 'sly',\n",
       " 211: 'cinnabar',\n",
       " 212: 'wawiezhllctdchhg',\n",
       " 213: 'leslie',\n",
       " 214: 'indirect',\n",
       " 215: 'roadster',\n",
       " 216: 'clalls',\n",
       " 217: 'wt',\n",
       " 218: 'mutterer',\n",
       " 219: 'ekl',\n",
       " 220: 'corsage',\n",
       " 221: 'remediable',\n",
       " 222: 'obesity',\n",
       " 223: 'shon',\n",
       " 224: 'concentric',\n",
       " 225: 'composite',\n",
       " 226: 'skel',\n",
       " 227: 'capricorn',\n",
       " 228: 'charcoal',\n",
       " 229: 'simiiar',\n",
       " 230: 'respite',\n",
       " 231: 'prank',\n",
       " 232: 'newswires',\n",
       " 233: 'kjroeker',\n",
       " 234: 'poellinger',\n",
       " 235: 'single',\n",
       " 236: 'supposable',\n",
       " 237: 'advertisement',\n",
       " 238: 'goniometer',\n",
       " 239: 'heidi',\n",
       " 240: 'disreagard',\n",
       " 241: 'fungoid',\n",
       " 242: 'abstract',\n",
       " 243: 'battle',\n",
       " 244: 'bwrx',\n",
       " 245: 'emily',\n",
       " 246: 'baum',\n",
       " 247: 'blotch',\n",
       " 248: 'millenium',\n",
       " 249: 'iauklet',\n",
       " 250: 'cleanse',\n",
       " 251: 'extremen',\n",
       " 252: 'lemmon',\n",
       " 253: 'aldr',\n",
       " 254: 'recondite',\n",
       " 255: 'mine',\n",
       " 256: 'chewco',\n",
       " 257: 'vdzqi',\n",
       " 258: 'officemate',\n",
       " 259: 'zhfoefjmc',\n",
       " 260: 'gents',\n",
       " 261: 'valdes',\n",
       " 262: 'bkhlr',\n",
       " 263: 'norwalk',\n",
       " 264: 'ubwopt',\n",
       " 265: 'prochaine',\n",
       " 266: 'jstara',\n",
       " 267: 'echten',\n",
       " 268: 'global',\n",
       " 269: 'trot',\n",
       " 270: 'seraglio',\n",
       " 271: 'thudgelmir',\n",
       " 272: 'viakgra',\n",
       " 273: 'bra',\n",
       " 274: 'keohane',\n",
       " 275: 'calculus',\n",
       " 276: 'thelma',\n",
       " 277: 'alsmedherbs',\n",
       " 278: 'shirt',\n",
       " 279: 'indictment',\n",
       " 280: 'conch',\n",
       " 281: 'bennet',\n",
       " 282: 'attribution',\n",
       " 283: 'doherty',\n",
       " 284: 'oklahoma',\n",
       " 285: 'piaced',\n",
       " 286: 'nterm',\n",
       " 287: 'considerable',\n",
       " 288: 'everlasting',\n",
       " 289: 'cgwd',\n",
       " 290: 'pregnancy',\n",
       " 291: 'poohbear',\n",
       " 292: 'hubby',\n",
       " 293: 'combatant',\n",
       " 294: 'breaker',\n",
       " 295: 'jdhkydx',\n",
       " 296: 'agnomen',\n",
       " 297: 'afraid',\n",
       " 298: 'coracle',\n",
       " 299: 'hfg',\n",
       " 300: 'retrieve',\n",
       " 301: 'pourquoi',\n",
       " 302: 'gir',\n",
       " 303: 'disabled',\n",
       " 304: 'save',\n",
       " 305: 'zuidholland',\n",
       " 306: 'goldfinger',\n",
       " 307: 'br',\n",
       " 308: 'jettison',\n",
       " 309: 'cashout',\n",
       " 310: 'jesus',\n",
       " 311: 'netco',\n",
       " 312: 'affaires',\n",
       " 313: 'bower',\n",
       " 314: 'ilona',\n",
       " 315: 'stengel',\n",
       " 316: 'vlagrra',\n",
       " 317: 'prairie',\n",
       " 318: 'heartbeat',\n",
       " 319: 'atrium',\n",
       " 320: 'macpres',\n",
       " 321: 'bilski',\n",
       " 322: 'pane',\n",
       " 323: 'flow',\n",
       " 324: 'jill',\n",
       " 325: 'debby',\n",
       " 326: 'uni',\n",
       " 327: 'luong',\n",
       " 328: 'independently',\n",
       " 329: 'javautillocale',\n",
       " 330: 'mineralised',\n",
       " 331: 'yelppamela',\n",
       " 332: 'denouement',\n",
       " 333: 'dmco',\n",
       " 334: 'computing',\n",
       " 335: 'vmh',\n",
       " 336: 'deiiver',\n",
       " 337: 'sres',\n",
       " 338: 'alternatively',\n",
       " 339: 'ehli',\n",
       " 340: 'horseman',\n",
       " 341: 'amlp',\n",
       " 342: 'xqnxvn',\n",
       " 343: 'deregulation',\n",
       " 344: 'leben',\n",
       " 345: 'mmw',\n",
       " 346: 'acervantes',\n",
       " 347: 'chateau',\n",
       " 348: 'hgpl',\n",
       " 349: 'negatively',\n",
       " 350: 'fleas',\n",
       " 351: 'photoshkop',\n",
       " 352: 'interact',\n",
       " 353: 'hill',\n",
       " 354: 'gardell',\n",
       " 355: 'subscr',\n",
       " 356: 'connoisseur',\n",
       " 357: 'chamber',\n",
       " 358: 'circumstantial',\n",
       " 359: 'tlf',\n",
       " 360: 'liquefaction',\n",
       " 361: 'video',\n",
       " 362: 'pharrn',\n",
       " 363: 'caustic',\n",
       " 364: 'heterostructure',\n",
       " 365: 'blackboard',\n",
       " 366: 'wally',\n",
       " 367: 'papery',\n",
       " 368: 'nylon',\n",
       " 369: 'logonid',\n",
       " 370: 'bgcolor',\n",
       " 371: 'bmany',\n",
       " 372: 'fir',\n",
       " 373: 'td',\n",
       " 374: 'zhu',\n",
       " 375: 'perceive',\n",
       " 376: 'ovyabl',\n",
       " 377: 'velteck',\n",
       " 378: 'contradistinction',\n",
       " 379: 'izxgw',\n",
       " 380: 'exile',\n",
       " 381: 'kiejvrv',\n",
       " 382: 'dlscreet',\n",
       " 383: 'kwunsch',\n",
       " 384: 'certified',\n",
       " 385: 'owmrs',\n",
       " 386: 'outbid',\n",
       " 387: 'camera',\n",
       " 388: 'bellow',\n",
       " 389: 'talented',\n",
       " 390: 'alerte',\n",
       " 391: 'uyit',\n",
       " 392: 'mgbabyface',\n",
       " 393: 'inccsnrmq',\n",
       " 394: 'basswood',\n",
       " 395: 'qis',\n",
       " 396: 'publication',\n",
       " 397: 'belies',\n",
       " 398: 'twa',\n",
       " 399: 'sdw',\n",
       " 400: 'skeleton',\n",
       " 401: 'goodlett',\n",
       " 402: 'bohnet',\n",
       " 403: 'cartography',\n",
       " 404: 'gpvf',\n",
       " 405: 'shepard',\n",
       " 406: 'skywest',\n",
       " 407: 'ceremonious',\n",
       " 408: 'marseille',\n",
       " 409: 'bethought',\n",
       " 410: 'kvus',\n",
       " 411: 'annum',\n",
       " 412: 'il',\n",
       " 413: 'decision',\n",
       " 414: 'bismark',\n",
       " 415: 'superorganize',\n",
       " 416: 'fingernail',\n",
       " 417: 'porche',\n",
       " 418: 'francie',\n",
       " 419: 'ob',\n",
       " 420: 'ipod',\n",
       " 421: 'evitr',\n",
       " 422: 'mitcham',\n",
       " 423: 'chantale',\n",
       " 424: 'iusomcc',\n",
       " 425: 'kerwin',\n",
       " 426: 'couldn',\n",
       " 427: 'typhon',\n",
       " 428: 'airline',\n",
       " 429: 'juan',\n",
       " 430: 'modestly',\n",
       " 431: 'actobat',\n",
       " 432: 'kdavis',\n",
       " 433: 'emtk',\n",
       " 434: 'binocyles',\n",
       " 435: 'rider',\n",
       " 436: 'pftc',\n",
       " 437: 'inherent',\n",
       " 438: 'fnxhhrhioidagqi',\n",
       " 439: 'joined',\n",
       " 440: 'postwar',\n",
       " 441: 'regis',\n",
       " 442: 'signing',\n",
       " 443: 'rite',\n",
       " 444: 'sycamore',\n",
       " 445: 'trimer',\n",
       " 446: 'spjzcd',\n",
       " 447: 'srupprecht',\n",
       " 448: 'ppatccch',\n",
       " 449: 'prospective',\n",
       " 450: 'handline',\n",
       " 451: 'liste',\n",
       " 452: 'vlcodd',\n",
       " 453: 'darenfarmer',\n",
       " 454: 'wall',\n",
       " 455: 'classificatory',\n",
       " 456: 'stratum',\n",
       " 457: 'nxxttxu',\n",
       " 458: 'insight',\n",
       " 459: 'lipton',\n",
       " 460: 'vardon',\n",
       " 461: 'revoir',\n",
       " 462: 'kldhcayh',\n",
       " 463: 'uvo',\n",
       " 464: 'kennan',\n",
       " 465: 'coupists',\n",
       " 466: 'gut',\n",
       " 467: 'synm',\n",
       " 468: 'fleck',\n",
       " 469: 'knippa',\n",
       " 470: 'puddingstone',\n",
       " 471: 'brajenovlc',\n",
       " 472: 'kdnuggets',\n",
       " 473: 'yjycunv',\n",
       " 474: 'milf',\n",
       " 475: 'russell',\n",
       " 476: 'dfs',\n",
       " 477: 'precondition',\n",
       " 478: 'sleep',\n",
       " 479: 'transmissive',\n",
       " 480: 'incur',\n",
       " 481: 'lambert',\n",
       " 482: 'xoqigx',\n",
       " 483: 'emaaaaail',\n",
       " 484: 'lengthman',\n",
       " 485: 'assignation',\n",
       " 486: 'appl',\n",
       " 487: 'considerably',\n",
       " 488: 'protean',\n",
       " 489: 'sympatico',\n",
       " 490: 'build',\n",
       " 491: 'escherichia',\n",
       " 492: 'bradley',\n",
       " 493: 'snowfall',\n",
       " 494: 'antimony',\n",
       " 495: 'sina',\n",
       " 496: 'integrator',\n",
       " 497: 'kingsley',\n",
       " 498: 'propeller',\n",
       " 499: 'cumulative',\n",
       " 500: 'blvd',\n",
       " 501: 'westbrook',\n",
       " 502: 'pyrope',\n",
       " 503: 'augean',\n",
       " 504: 'burdensome',\n",
       " 505: 'cardiovascular',\n",
       " 506: 'venusians',\n",
       " 507: 'hirl',\n",
       " 508: 'mnxv',\n",
       " 509: 'neeedeed',\n",
       " 510: 'partnership',\n",
       " 511: 'zeit',\n",
       " 512: 'gasification',\n",
       " 513: 'electrolytically',\n",
       " 514: 'dado',\n",
       " 515: 'stealth',\n",
       " 516: 'tangible',\n",
       " 517: 'speaking',\n",
       " 518: 'rake',\n",
       " 519: 'fuels',\n",
       " 520: 'onlsine',\n",
       " 521: 'uqnhjs',\n",
       " 522: 'extensive',\n",
       " 523: 'bangura',\n",
       " 524: 'saavve',\n",
       " 525: 'dxkvqqaw',\n",
       " 526: 'film',\n",
       " 527: 'availabilty',\n",
       " 528: 'fuel',\n",
       " 529: 'bilder',\n",
       " 530: 'promise',\n",
       " 531: 'mycon',\n",
       " 532: 'rgqbxnz',\n",
       " 533: 'fricative',\n",
       " 534: 'spaniel',\n",
       " 535: 'nhbqlfivih',\n",
       " 536: 'satin',\n",
       " 537: 'rather',\n",
       " 538: 'preservation',\n",
       " 539: 'toro',\n",
       " 540: 'sinus',\n",
       " 541: 'guardian',\n",
       " 542: 'ironstonetotem',\n",
       " 543: 'catalpa',\n",
       " 544: 'babe',\n",
       " 545: 'fog',\n",
       " 546: 'jbxtz',\n",
       " 547: 'zui',\n",
       " 548: '2001',\n",
       " 549: 'campsite',\n",
       " 550: 'lng',\n",
       " 551: 'carri',\n",
       " 552: 'lager',\n",
       " 553: 'kauffman',\n",
       " 554: 'gedeon',\n",
       " 555: 'bettergitit',\n",
       " 556: 'convocate',\n",
       " 557: 'queue',\n",
       " 558: 'wid',\n",
       " 559: 'polymer',\n",
       " 560: 'cayley',\n",
       " 561: 'castrol',\n",
       " 562: '01',\n",
       " 563: 'nxl',\n",
       " 564: 'contributators',\n",
       " 565: 'economise',\n",
       " 566: 'beter',\n",
       " 567: 'enxenpuqh',\n",
       " 568: 'ammount',\n",
       " 569: 'qzoup',\n",
       " 570: 'orgasm',\n",
       " 571: 'criticize',\n",
       " 572: 'drastic',\n",
       " 573: 'hagelmann',\n",
       " 574: 'witchcraft',\n",
       " 575: 'coon',\n",
       " 576: 'asperity',\n",
       " 577: 'ciayis',\n",
       " 578: 'rebate',\n",
       " 579: 'sumrow',\n",
       " 580: 'kratzer',\n",
       " 581: 'benevolence',\n",
       " 582: 'protect',\n",
       " 583: 'himhogan',\n",
       " 584: 'finalists',\n",
       " 585: 'sind',\n",
       " 586: 'docorder',\n",
       " 587: 'entercon',\n",
       " 588: 'qh',\n",
       " 589: 'failsoft',\n",
       " 590: 'ineducable',\n",
       " 591: 'info',\n",
       " 592: 'midrange',\n",
       " 593: 'jillian',\n",
       " 594: 'qhworzeei',\n",
       " 595: 'classmate',\n",
       " 596: 'marriott',\n",
       " 597: 'sending',\n",
       " 598: 'dru',\n",
       " 599: 'http',\n",
       " 600: 'curtis',\n",
       " 601: 'joy',\n",
       " 602: 'bezzant',\n",
       " 603: 'surety',\n",
       " 604: 'kpwfwu',\n",
       " 605: 'porter',\n",
       " 606: 'solitude',\n",
       " 607: 'canadaskylimo',\n",
       " 608: 'indignity',\n",
       " 609: 'adtfa',\n",
       " 610: 'record',\n",
       " 611: 'silicic',\n",
       " 612: 'dtoi',\n",
       " 613: 'paragraph',\n",
       " 614: 'kimscott',\n",
       " 615: 'beautify',\n",
       " 616: 'acceptance',\n",
       " 617: 'cicutoxin',\n",
       " 618: 'deluge',\n",
       " 619: 'siberia',\n",
       " 620: 'heirsubtracter',\n",
       " 621: 'thnks',\n",
       " 622: 'dpitts',\n",
       " 623: 'tablet',\n",
       " 624: 'algeria',\n",
       " 625: 'quake',\n",
       " 626: 'aumevzcppzek',\n",
       " 627: 'fiskrob',\n",
       " 628: 'mmc',\n",
       " 629: 'stepan',\n",
       " 630: 'jdsh',\n",
       " 631: 'pldphb',\n",
       " 632: 'pending',\n",
       " 633: 'fealty',\n",
       " 634: 'expected',\n",
       " 635: 'rick',\n",
       " 636: 'salvation',\n",
       " 637: 'cynqruh',\n",
       " 638: 'hewn',\n",
       " 639: 'psalm',\n",
       " 640: 'throngmauve',\n",
       " 641: 'arrantee',\n",
       " 642: 'anthonytrevelyan',\n",
       " 643: 'camelopard',\n",
       " 644: 'wor',\n",
       " 645: 'poppi',\n",
       " 646: 'ciborium',\n",
       " 647: 'chuckwalla',\n",
       " 648: 'audibly',\n",
       " 649: 'spin',\n",
       " 650: 'draftsman',\n",
       " 651: 'dis',\n",
       " 652: 'yokel',\n",
       " 653: 'ccrw',\n",
       " 654: 'react',\n",
       " 655: 'wov',\n",
       " 656: 'equiv',\n",
       " 657: 'ee',\n",
       " 658: 'lemma',\n",
       " 659: 'inyhoc',\n",
       " 660: 'lesliel',\n",
       " 661: 'mrichard',\n",
       " 662: 'emission',\n",
       " 663: 'distribtued',\n",
       " 664: 'ethos',\n",
       " 665: 'gallishaw',\n",
       " 666: 'interracial',\n",
       " 667: 'uorrmgbr',\n",
       " 668: 'luebsbdf',\n",
       " 669: 'tex',\n",
       " 670: 'embouchure',\n",
       " 671: 'maxine',\n",
       " 672: 'densitometer',\n",
       " 673: 'imbue',\n",
       " 674: 'bupropion',\n",
       " 675: 'ssurprised',\n",
       " 676: 'homegain',\n",
       " 677: 'decontrol',\n",
       " 678: 'kandylo',\n",
       " 679: 'magi',\n",
       " 680: 'paln',\n",
       " 681: 'lenhart',\n",
       " 682: 'ppharmacybymail',\n",
       " 683: 'fontfont',\n",
       " 684: 'lclarabella',\n",
       " 685: 'astrodome',\n",
       " 686: 'abound',\n",
       " 687: 'denary',\n",
       " 688: 'kia',\n",
       " 689: 'savandra',\n",
       " 690: 'vmagra',\n",
       " 691: 'red',\n",
       " 692: 'samah',\n",
       " 693: 'concurrent',\n",
       " 694: 'susie',\n",
       " 695: 'oahu',\n",
       " 696: 'filet',\n",
       " 697: 'absolutionelision',\n",
       " 698: 'yqjxkjam',\n",
       " 699: 'workable',\n",
       " 700: 'magallanes',\n",
       " 701: 'mccampbell',\n",
       " 702: 'oppose',\n",
       " 703: 'predisposition',\n",
       " 704: 'race',\n",
       " 705: 'kjjjip',\n",
       " 706: 'influence',\n",
       " 707: 'phon',\n",
       " 708: 'aspartic',\n",
       " 709: 'vargas',\n",
       " 710: 'pollacia',\n",
       " 711: 'vexatious',\n",
       " 712: 'topics',\n",
       " 713: 'helpful',\n",
       " 714: 'inkjets',\n",
       " 715: 'concur',\n",
       " 716: 'thomas',\n",
       " 717: 'verification',\n",
       " 718: 'embezzle',\n",
       " 719: 'duplicator',\n",
       " 720: 'cruise',\n",
       " 721: 'thebr',\n",
       " 722: 'ceos',\n",
       " 723: 'prototype',\n",
       " 724: 'number',\n",
       " 725: 'schooner',\n",
       " 726: 'sticktight',\n",
       " 727: 'aniline',\n",
       " 728: 'slacker',\n",
       " 729: 'bhhdd',\n",
       " 730: 'confinement',\n",
       " 731: 'fruitless',\n",
       " 732: 'ntris',\n",
       " 733: 'saving',\n",
       " 734: 'cartridgesfor',\n",
       " 735: 'falfurrias',\n",
       " 736: 'mannequin',\n",
       " 737: 'metods',\n",
       " 738: 'dav',\n",
       " 739: 'polluting',\n",
       " 740: 'sengupta',\n",
       " 741: 'jgxufgic',\n",
       " 742: 'tditata',\n",
       " 743: 'deja',\n",
       " 744: 'berth',\n",
       " 745: 'reflect',\n",
       " 746: 'uplifted',\n",
       " 747: 'jo',\n",
       " 748: 'sultanate',\n",
       " 749: 'ations',\n",
       " 750: 'interface',\n",
       " 751: 'ogbfp',\n",
       " 752: 'multilanguage',\n",
       " 753: 'prostheses',\n",
       " 754: 'immortal',\n",
       " 755: 'justifiable',\n",
       " 756: 'eveready',\n",
       " 757: 'thessalonian',\n",
       " 758: 'dnd',\n",
       " 759: 'rent',\n",
       " 760: 'dadaist',\n",
       " 761: 'man',\n",
       " 762: 'musturbating',\n",
       " 763: 'megonna',\n",
       " 764: 'aac',\n",
       " 765: 'yesenia',\n",
       " 766: 'playmate',\n",
       " 767: 'quadrature',\n",
       " 768: 'endothermic',\n",
       " 769: 'uqs',\n",
       " 770: 'initiative',\n",
       " 771: 'loo',\n",
       " 772: 'tolstoy',\n",
       " 773: 'slakie',\n",
       " 774: 'tburn',\n",
       " 775: 'contro',\n",
       " 776: 'clmp',\n",
       " 777: 'abode',\n",
       " 778: 'dielectric',\n",
       " 779: 'superintendent',\n",
       " 780: 'dixon',\n",
       " 781: 'snippy',\n",
       " 782: 'pizza',\n",
       " 783: 'architeriors',\n",
       " 784: 'transfer',\n",
       " 785: 'infrastructure',\n",
       " 786: 'dendritic',\n",
       " 787: 'gallivant',\n",
       " 788: 'wellington',\n",
       " 789: 'qualitty',\n",
       " 790: 'scuba',\n",
       " 791: 'psig',\n",
       " 792: 'redstone',\n",
       " 793: 'sdram',\n",
       " 794: 'alva',\n",
       " 795: 'atropos',\n",
       " 796: 'seperate',\n",
       " 797: 'cytoplasm',\n",
       " 798: 'allocated',\n",
       " 799: 'sabine',\n",
       " 800: 'farther',\n",
       " 801: 'prometheus',\n",
       " 802: 'rib',\n",
       " 803: 'bearberry',\n",
       " 804: 'surrey',\n",
       " 805: 'populace',\n",
       " 806: 'mzay',\n",
       " 807: 'absorptionbark',\n",
       " 808: 'tcaix',\n",
       " 809: 'specia',\n",
       " 810: 'wachs',\n",
       " 811: 'breakfast',\n",
       " 812: 'ontario',\n",
       " 813: 'marvia',\n",
       " 814: 'nowl',\n",
       " 815: 'canker',\n",
       " 816: 'mitigation',\n",
       " 817: 'illovo',\n",
       " 818: 'breitling',\n",
       " 819: 'melton',\n",
       " 820: 'lithospheric',\n",
       " 821: 'cuilla',\n",
       " 822: 'annul',\n",
       " 823: 'marthon',\n",
       " 824: 'kosovo',\n",
       " 825: 'extraordinarily',\n",
       " 826: 'perfection',\n",
       " 827: 'bggv',\n",
       " 828: 'waldron',\n",
       " 829: 'amended',\n",
       " 830: 'resultingly',\n",
       " 831: 'vaughn',\n",
       " 832: 'coherent',\n",
       " 833: 'mere',\n",
       " 834: 'biz',\n",
       " 835: 'application',\n",
       " 836: 'shippiing',\n",
       " 837: 'cannon',\n",
       " 838: 'rotation',\n",
       " 839: 'dpie',\n",
       " 840: 'cybersitebuilders',\n",
       " 841: 'hypothesis',\n",
       " 842: 'cyctzw',\n",
       " 843: 'mental',\n",
       " 844: 'secondhand',\n",
       " 845: 'geographer',\n",
       " 846: 'keyboard',\n",
       " 847: 'kirstenkloepfer',\n",
       " 848: 'reynolds',\n",
       " 849: 'bregenz',\n",
       " 850: 'hasa',\n",
       " 851: 'newpower',\n",
       " 852: 'suepr',\n",
       " 853: 'anthracnose',\n",
       " 854: 'quietus',\n",
       " 855: 'diligent',\n",
       " 856: 'doorkeeper',\n",
       " 857: 'lvldezrcrjo',\n",
       " 858: 'label',\n",
       " 859: 'vilify',\n",
       " 860: 'lashing',\n",
       " 861: 'purchase',\n",
       " 862: 'yfr',\n",
       " 863: 'unmanageably',\n",
       " 864: 'allison',\n",
       " 865: 'cloddish',\n",
       " 866: 'kgav',\n",
       " 867: 'rutherford',\n",
       " 868: 'zmedabsd',\n",
       " 869: 'summertime',\n",
       " 870: 'antennas',\n",
       " 871: 'dilogarithm',\n",
       " 872: 'lefttrtd',\n",
       " 873: 'xzxzjs',\n",
       " 874: 'beer',\n",
       " 875: 'ulysses',\n",
       " 876: 'sugper',\n",
       " 877: 'dole',\n",
       " 878: 'qda',\n",
       " 879: 'recap',\n",
       " 880: 'loth',\n",
       " 881: 'raillery',\n",
       " 882: 'waz',\n",
       " 883: 'qfnk',\n",
       " 884: 'jacky',\n",
       " 885: 'slouch',\n",
       " 886: 'divisional',\n",
       " 887: 'lg',\n",
       " 888: 'reavis',\n",
       " 889: 'flaxseed',\n",
       " 890: 'tele',\n",
       " 891: 'borland',\n",
       " 892: 'native',\n",
       " 893: 'meeeeessaaagees',\n",
       " 894: 'ante',\n",
       " 895: 'acquisitive',\n",
       " 896: 'ofcthe',\n",
       " 897: 'executrixkettle',\n",
       " 898: 'cunuvjnfs',\n",
       " 899: 'ernst',\n",
       " 900: 'reger',\n",
       " 901: 'francisoma',\n",
       " 902: 'steve',\n",
       " 903: 'speckels',\n",
       " 904: 'pongo',\n",
       " 905: 'pxf',\n",
       " 906: 'tcalpcfys',\n",
       " 907: 'meiner',\n",
       " 908: 'elementary',\n",
       " 909: 'miilion',\n",
       " 910: 'expire',\n",
       " 911: 'rfmejycss',\n",
       " 912: 'synaptic',\n",
       " 913: 'predominant',\n",
       " 914: 'isentropic',\n",
       " 915: 'adrial',\n",
       " 916: 'kkwjizqotyyj',\n",
       " 917: 'greasy',\n",
       " 918: 'patriarch',\n",
       " 919: 'ude',\n",
       " 920: 'gennifer',\n",
       " 921: 'jraawcbk',\n",
       " 922: 'triac',\n",
       " 923: 'yjjjhz',\n",
       " 924: 'candlelit',\n",
       " 925: 'mayor',\n",
       " 926: 'siltation',\n",
       " 927: 'rogercdavis',\n",
       " 928: 'refo',\n",
       " 929: 'candidate',\n",
       " 930: 'excavate',\n",
       " 931: 'cheerful',\n",
       " 932: 'puller',\n",
       " 933: 'regina',\n",
       " 934: 'dishwasher',\n",
       " 935: 'thick',\n",
       " 936: 'peculate',\n",
       " 937: 'persecution',\n",
       " 938: 'bristle',\n",
       " 939: 'astrometry',\n",
       " 940: 'carbide',\n",
       " 941: 'memoir',\n",
       " 942: 'prenatal',\n",
       " 943: 'ascribe',\n",
       " 944: 'encourager',\n",
       " 945: 'covariate',\n",
       " 946: 'qdjbc',\n",
       " 947: 'tracor',\n",
       " 948: 'ctnou',\n",
       " 949: 'benefit',\n",
       " 950: 'painter',\n",
       " 951: 'nasty',\n",
       " 952: 'bvdkf',\n",
       " 953: 'march',\n",
       " 954: 'prophylactic',\n",
       " 955: 'referral',\n",
       " 956: 'jazzy',\n",
       " 957: 'bfear',\n",
       " 958: 'chimeric',\n",
       " 959: 'emigrant',\n",
       " 960: 'fcwkwjx',\n",
       " 961: 'wypowf',\n",
       " 962: 'weapon',\n",
       " 963: 'fossesca',\n",
       " 964: 'multiply',\n",
       " 965: 'errorbulletin',\n",
       " 966: 'homesbybetty',\n",
       " 967: 'ultimatum',\n",
       " 968: 'consulage',\n",
       " 969: 'underpay',\n",
       " 970: 'quadrant',\n",
       " 971: 'discriminate',\n",
       " 972: 'flannigan',\n",
       " 973: 'dibble',\n",
       " 974: 'menu',\n",
       " 975: 'hither',\n",
       " 976: 'mnzfg',\n",
       " 977: 'ingrid',\n",
       " 978: 'lorazeepam',\n",
       " 979: 'lgdxgcf',\n",
       " 980: 'midd',\n",
       " 981: 'jlreadpa',\n",
       " 982: 'kdstewart',\n",
       " 983: 'henn',\n",
       " 984: 'decillion',\n",
       " 985: 'assassin',\n",
       " 986: 'sudlz',\n",
       " 987: 'interrogator',\n",
       " 988: 'maledict',\n",
       " 989: 'unipolar',\n",
       " 990: 'cigaaretes',\n",
       " 991: 'wichita',\n",
       " 992: 'northward',\n",
       " 993: 'uns',\n",
       " 994: 'wildfire',\n",
       " 995: 'tbr',\n",
       " 996: 'rthompso',\n",
       " 997: 'represent',\n",
       " 998: 'uawu',\n",
       " 999: 'honk',\n",
       " ...}"
      ]
     },
     "execution_count": 746,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dictionary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 747,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_train_vector = vectorize(spam_train_clean, dictionary)\n",
    "ham_train_vector = vectorize(ham_train_clean, dictionary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 748,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33579 1125 2754\n"
     ]
    }
   ],
   "source": [
    "print(len(spam_train_vector[0]), len(spam_train_vector), len(ham_train_vector))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 749,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tag_and_train(spam_vector, ham_vector):\n",
    "    \n",
    "    for vector in spam_vector:\n",
    "        vector.append(1)\n",
    "    for vector in ham_vector:\n",
    "        vector.append(0)\n",
    "\n",
    "    train_vector = spam_vector + ham_vector\n",
    "    \n",
    "    return train_vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 750,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_vector = tag_and_train(spam_train_vector, ham_train_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 751,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_vector1 = np.array(train_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 752,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33580 3879\n"
     ]
    }
   ],
   "source": [
    "print(len(train_vector[0]), len(train_vector))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 753,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_test_vector = vectorize(spam_test_clean, dictionary)\n",
    "ham_test_vector = vectorize(ham_test_clean, dictionary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 754,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33579 375 918\n"
     ]
    }
   ],
   "source": [
    "print(len(spam_test_vector[0]), len(spam_test_vector), len(ham_test_vector))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 755,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_vector = tag_and_train(spam_test_vector, ham_test_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 756,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_vector1 = np.array(test_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 757,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "157"
      ]
     },
     "execution_count": 757,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(test_vector1[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 758,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33580 1293\n"
     ]
    }
   ],
   "source": [
    "print(len(test_vector1[0]), len(test_vector1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 759,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclidean_distance(train_vector_instance, test_vector_instance, norm):\n",
    "    distance = np.linalg.norm(train_vector_instance[:-1]-test_vector_instance[:-1], ord=norm)\n",
    "    return distance  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 760,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_neighbors(train_vector, test_vector_instance, k, norm):\n",
    "    distance = []\n",
    "    norm = norm\n",
    "    for x in range(len(train_vector)):\n",
    "        dist = euclidean_distance(train_vector[x], test_vector_instance, norm)\n",
    "        distance.append((train_vector[x], dist))\n",
    "    distance.sort(key=operator.itemgetter(1))\n",
    "    neighbors = []\n",
    "    for x in range(k):\n",
    "        neighbors.append(distance[x][0])\n",
    "    return neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 761,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_response(neighbors):\n",
    "    class_counter = Counter()\n",
    "    for x in range(len(neighbors)):\n",
    "        response = neighbors[x][-1]\n",
    "        class_counter[response] += 1        \n",
    "        return class_counter.most_common(1)[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 762,
   "metadata": {},
   "outputs": [],
   "source": [
    "def accuracy_NN(test_vector, prediction):\n",
    "    correct = 0\n",
    "    for x in range(len(test_vector)):\n",
    "        if test_vector[x][-1] == prediction[x]:\n",
    "            correct += 1\n",
    "    return ((correct / float(len(test_vector))) * 100.0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 763,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 5-NN is 89.7138437741686\n"
     ]
    }
   ],
   "source": [
    "prediction = []\n",
    "k = 5\n",
    "norm = 2\n",
    "for x in range(len(test_vector1)):\n",
    "    neighbors = get_neighbors(train_vector1, test_vector1[x], k, norm)\n",
    "    result = get_response(neighbors)\n",
    "    prediction.append(result)\n",
    "accuracy = accuracy_NN(test_vector1, prediction)\n",
    "print('The accuarcy for '+ str(k) + '-NN is ' + str(accuracy))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 764,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 5-NN is 78.11291569992265\n"
     ]
    }
   ],
   "source": [
    "prediction1 = []\n",
    "k = 5\n",
    "norm = np.inf\n",
    "for x in range(len(test_vector1)):\n",
    "    neighbors = get_neighbors(train_vector1, test_vector1[x], k, norm)\n",
    "    result = get_response(neighbors)\n",
    "    prediction1.append(result)\n",
    "accuracy_3 = accuracy_NN(test_vector1, prediction1)\n",
    "print('The accuarcy for '+ str(k) + '-NN is ' + str(accuracy_3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 765,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 5-NN is 80.81979891724671\n"
     ]
    }
   ],
   "source": [
    "prediction1 = []\n",
    "k = 5\n",
    "norm = 1\n",
    "for x in range(len(test_vector1)):\n",
    "    neighbors = get_neighbors(train_vector1, test_vector1[x], k, norm)\n",
    "    result = get_response(neighbors)\n",
    "    prediction1.append(result)\n",
    "accuracy_3 = accuracy_NN(test_vector1, prediction1)\n",
    "print('The accuarcy for '+ str(k) + '-NN is ' + str(accuracy_3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 766,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 10-NN is 89.7138437741686\n"
     ]
    }
   ],
   "source": [
    "prediction = []\n",
    "k = 10\n",
    "norm = 2\n",
    "for x in range(len(test_vector1)):\n",
    "    neighbors = get_neighbors(train_vector1, test_vector1[x], k, norm)\n",
    "    result = get_response(neighbors)\n",
    "    prediction.append(result)\n",
    "accuracy = accuracy_NN(test_vector1, prediction)\n",
    "print('The accuarcy for '+ str(k) + '-NN is ' + str(accuracy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 767,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 10-NN is 80.81979891724671\n"
     ]
    }
   ],
   "source": [
    "prediction = []\n",
    "k = 10\n",
    "norm = 1\n",
    "for x in range(len(test_vector1)):\n",
    "    neighbors = get_neighbors(train_vector1, test_vector1[x], k, norm)\n",
    "    result = get_response(neighbors)\n",
    "    prediction.append(result)\n",
    "accuracy = accuracy_NN(test_vector1, prediction)\n",
    "print('The accuarcy for '+ str(k) + '-NN is ' + str(accuracy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 768,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 10-NN is 78.11291569992265\n"
     ]
    }
   ],
   "source": [
    "prediction = []\n",
    "k = 10\n",
    "norm = np.inf\n",
    "for x in range(len(test_vector1)):\n",
    "    neighbors = get_neighbors(train_vector1, test_vector1[x], k, norm)\n",
    "    result = get_response(neighbors)\n",
    "    prediction.append(result)\n",
    "accuracy = accuracy_NN(test_vector1, prediction)\n",
    "print('The accuarcy for '+ str(k) + '-NN is ' + str(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# KD TREE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 383,
   "metadata": {},
   "outputs": [],
   "source": [
    "def magnitude(vector_list, norm = 2):\n",
    "    magnitude_v = []\n",
    "    for vector in vector_list:\n",
    "        temp = [numpy.linalg.norm(vector[:-1], ord=norm), vector[-1]]\n",
    "        magnitude_v.append(temp) \n",
    "    magnitude_v.sort(key=operator.itemgetter(0))\n",
    "    \n",
    "    return magnitude_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 384,
   "metadata": {},
   "outputs": [],
   "source": [
    "normed_train = magnitude(train_vector, norm=2)\n",
    "normed_test = magnitude(test_vector, norm=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 382,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kdtree(train_vector_norm, test_vector,k):\n",
    "    median = int(len(train_vector_norm) / 2)\n",
    "    if len(train_vector_norm) == k :\n",
    "        neighbor = train_vector_norm\n",
    "        return neighbor\n",
    "    else:\n",
    "        if test_vector[0] < train_vector_norm[median][0]:\n",
    "            neighbor = kdtree(train_vector_norm[:median],test_vector,k)\n",
    "            return neighbor\n",
    "        elif test_vector[0] >= train_vector_norm[median][0]:\n",
    "            neighbor = kdtree(train_vector_norm[median:],test_vector,k)\n",
    "            return neighbor\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 385,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_response(neighbor):\n",
    "    response_label = {}\n",
    "    for x in range(len(neighbor)):\n",
    "        response = neighbor[x][-1]\n",
    "        if response in response_label:\n",
    "            response_label[response] += 1\n",
    "        else:\n",
    "            response_label[response] = 1\n",
    "    sorted_label = sorted(response_label.items(), key = operator.itemgetter(1), reverse = True)\n",
    "    return sorted_label[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 386,
   "metadata": {},
   "outputs": [],
   "source": [
    "def accuracy_NN(test_vector, prediction):\n",
    "    correct = 0\n",
    "    for x in range(len(test_vector)):\n",
    "        if test_vector[x][-1] == prediction[x]:\n",
    "            correct += 1\n",
    "    return ((correct / float(len(test_vector))) * 100.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 397,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for 1-NN is66.3768115942029\n"
     ]
    }
   ],
   "source": [
    "prediction = []\n",
    "k = 1\n",
    "norm = 2\n",
    "for x in normed_test:\n",
    "    neighbors = kdtree(normed_train, x, k)\n",
    "    result = get_response(neighbors)\n",
    "    prediction.append(result)\n",
    "accuracy = accuracy_NN(test_vector, prediction)\n",
    "print('The accuarcy for '+ str(k) + '-NN is' + str(accuracy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 392,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4142135623730951"
      ]
     },
     "execution_count": 392,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "normed_test[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 394,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.8284271247461903"
      ]
     },
     "execution_count": 394,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "normed_train[123][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 399,
   "metadata": {},
   "outputs": [],
   "source": [
    "l = np.array([1,2,5,1])\n",
    "b = np.array([1,2,3,4])\n",
    "\n",
    "a = numpy.linalg.norm(l-b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 401,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 401,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l = [1,2,3,4]\n",
    "l[:-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DECISION TREE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 667,
   "metadata": {},
   "outputs": [],
   "source": [
    "def word_bag(email_lemma, most_common):\n",
    "    x = most_common\n",
    "    clean_dict = {}\n",
    "    for i in email_lemma:\n",
    "        for word in i:\n",
    "            if word not in clean_dict:\n",
    "                clean_dict[word] = 1\n",
    "            else:\n",
    "                clean_dict[word] = clean_dict[word] + 1\n",
    "    \n",
    "    word_bag = {}\n",
    "    count_dict = Counter(clean_dict)\n",
    "    count_dict = count_dict.most_common(x)\n",
    "    count_dict.sort(key=operator.itemgetter(0))\n",
    "    for i in count_dict:\n",
    "        word_bag[i[0]] = i[1]\n",
    "    return word_bag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 668,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''word_bag is dictioanry of words as keys and their occurence as their value'''\n",
    "word_bag = word_bag(train_clean, 10000)  #original word bag with no most_common is 36345"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 669,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vectorize(email_list, word_bag):     #email_list is list of list of words in meail\n",
    "    vector = []\n",
    "    for email in email_list:\n",
    "        email_vector = []\n",
    "        for key in word_bag:\n",
    "            temp = email.count(key)\n",
    "            email_vector.append(temp)\n",
    "        vector.append(email_vector)\n",
    "    \n",
    "    return vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 670,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_train_vector = vectorize(spam_train_clean, word_bag)\n",
    "ham_train_vector = vectorize(ham_train_clean, word_bag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 671,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tag_and_train(spam_vector, ham_vector):\n",
    "    \n",
    "    for vector in spam_vector:\n",
    "        vector.append(1)\n",
    "    for vector in ham_vector:\n",
    "        vector.append(0)\n",
    "\n",
    "    train_vector = spam_vector + ham_vector\n",
    "    \n",
    "    return train_vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 672,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_vector = tag_and_train(spam_train_vector, ham_train_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 673,
   "metadata": {},
   "outputs": [],
   "source": [
    "spam_test_vector = vectorize(spam_test_clean, word_bag)\n",
    "ham_test_vector = vectorize(ham_test_clean, word_bag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 674,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_vector = tag_and_train(spam_test_vector, ham_test_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 675,
   "metadata": {},
   "outputs": [],
   "source": [
    "features = list(word_bag.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 676,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unique_vals(rows, col):\n",
    "    \"\"\"Find the unique values for a column in a dataset.\"\"\"\n",
    "    return set([row[col] for row in rows])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 677,
   "metadata": {},
   "outputs": [],
   "source": [
    "def class_counts(rows):\n",
    "    \"\"\"Counts the number of each type of example in a dataset.\"\"\"\n",
    "    counts = {}  # a dictionary of label -> count.\n",
    "    for row in rows:\n",
    "        # in our dataset format, the label is always the last column\n",
    "        label = row[-1]\n",
    "        if label not in counts:\n",
    "            counts[label] = 0\n",
    "        counts[label] += 1\n",
    "    return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 678,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Question:\n",
    "    \"\"\"A Question is used to partition a dataset.\"\"\"\n",
    "\n",
    "    def __init__(self, column, value):\n",
    "        self.column = column\n",
    "        self.value = value\n",
    "\n",
    "    def match(self, example):\n",
    "        # Compare the feature value in an example to the\n",
    "        # feature value in this question.\n",
    "        val = example[self.column]\n",
    "        return val >= self.value\n",
    "        \n",
    "    def __repr__(self):\n",
    "        # This is just a helper method to print\n",
    "        # the question in a readable format.\n",
    "        condition = \">=\"\n",
    "        return \"Is %s %s %s?\" % (\n",
    "            features[self.column], condition, str(self.value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 679,
   "metadata": {},
   "outputs": [],
   "source": [
    "t= Question(1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 680,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 680,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t.match(train_vector[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 681,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(rows, question):\n",
    "    \"\"\"Partitions a dataset.\n",
    "\n",
    "    For each row in the dataset, check if it matches the question. If\n",
    "    so, add it to 'true rows', otherwise, add it to 'false rows'.\n",
    "    \"\"\"\n",
    "    true_rows, false_rows = [], []\n",
    "    for row in rows:\n",
    "        if question.match(row):\n",
    "            true_rows.append(row)\n",
    "        else:\n",
    "            false_rows.append(row)\n",
    "    return true_rows, false_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 682,
   "metadata": {},
   "outputs": [],
   "source": [
    "true_rows, false_rows = partition(train_vector, Question(3, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 683,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 683,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(true_rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 684,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(rows):\n",
    "    \"\"\"Calculate the Gini Impurity for a list of rows.\"\"\"\n",
    "    counts = class_counts(rows)\n",
    "    impurity = 1\n",
    "    for lbl in counts:\n",
    "        prob_of_lbl = counts[lbl] / float(len(rows))\n",
    "        impurity -= prob_of_lbl**2\n",
    "    return impurity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 685,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.41185481381606737"
      ]
     },
     "execution_count": 685,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "current_uncertainty = gini(train_vector)\n",
    "current_uncertainty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 686,
   "metadata": {},
   "outputs": [],
   "source": [
    "def info_gain(left, right, current_uncertainty):\n",
    "    \"\"\"Information Gain.\n",
    "\n",
    "    The uncertainty of the starting node, minus the weighted impurity of\n",
    "    two child nodes.\n",
    "    \"\"\"\n",
    "    p = float(len(left)) / (len(left) + len(right))\n",
    "    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 687,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 687,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "true_rows, false_rows = partition(train_vector, Question(8, 2))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 688,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best_split(rows):\n",
    "    \"\"\"Find the best question to ask by iterating over every feature / value\n",
    "    and calculating the information gain.\"\"\"\n",
    "    best_gain = 0  # keep track of the best information gain\n",
    "    best_question = None  # keep train of the feature / value that produced it\n",
    "    current_uncertainty = gini(rows)\n",
    "    n_features = len(rows[0]) - 1  # number of columns\n",
    "\n",
    "    for col in range(n_features):  # for each feature\n",
    "\n",
    "        values = set([row[col] for row in rows])  # unique values in the column\n",
    "\n",
    "        for val in values:  # for each value\n",
    "\n",
    "            question = Question(col, val)\n",
    "\n",
    "            # try splitting the dataset\n",
    "            true_rows, false_rows = partition(rows, question)\n",
    "\n",
    "            # Skip this split if it doesn't divide the\n",
    "            # dataset.\n",
    "            if len(true_rows) == 0 or len(false_rows) == 0:\n",
    "                continue\n",
    "\n",
    "            # Calculate the information gain from this split\n",
    "            gain = info_gain(true_rows, false_rows, current_uncertainty)\n",
    "\n",
    "            # You actually can use '>' instead of '>=' here\n",
    "            # but I wanted the tree to look a certain way for our\n",
    "            # toy dataset.\n",
    "            if gain >= best_gain:\n",
    "                best_gain, best_question = gain, question\n",
    "\n",
    "    return best_gain, best_question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 689,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is enron >= 1?"
      ]
     },
     "execution_count": 689,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_gain, best_question = find_best_split(train_vector)\n",
    "best_question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 690,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Leaf:\n",
    "    \"\"\"A Leaf node classifies data.\n",
    "\n",
    "    This holds a dictionary of class (e.g., \"Spam(1)\") -> number of times\n",
    "    it appears in the rows from the training data that reach this leaf.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, rows):\n",
    "        self.predictions = class_counts(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 691,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Decision_Node:\n",
    "    \"\"\"A Decision Node asks a question.\n",
    "\n",
    "    This holds a reference to the question, and to the two child nodes.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self,\n",
    "                 question,\n",
    "                 true_branch,\n",
    "                 false_branch):\n",
    "        self.question = question\n",
    "        self.true_branch = true_branch\n",
    "        self.false_branch = false_branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 692,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(rows):\n",
    "    \"\"\"Builds the tree.\"\"\"\n",
    "\n",
    "    # Try partitioing the dataset on each of the unique attribute,\n",
    "    # calculate the information gain,\n",
    "    # and return the question that produces the highest gain.\n",
    "    gain, question = find_best_split(rows)\n",
    "\n",
    "    # Base case: no further info gain\n",
    "    # Since we can ask no further questions,\n",
    "    # we'll return a leaf.\n",
    "    if gain == 0:\n",
    "        return Leaf(rows)\n",
    "\n",
    "    # If we reach here, we have found a useful feature / value\n",
    "    # to partition on.\n",
    "    true_rows, false_rows = partition(rows, question)\n",
    "\n",
    "    # Recursively build the true branch.\n",
    "    true_branch = build_tree(true_rows)\n",
    "\n",
    "    # Recursively build the false branch.\n",
    "    false_branch = build_tree(false_rows)\n",
    "\n",
    "    # Return a Question node.\n",
    "    # This records the best feature / value to ask at this point,\n",
    "    # as well as the branches to follow\n",
    "    # dependingo on the answer.\n",
    "    return Decision_Node(question, true_branch, false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 693,
   "metadata": {},
   "outputs": [],
   "source": [
    "decision_tree = build_tree(train_vector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 694,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(row, node):\n",
    "    \"\"\"See the 'rules of recursion' above.\"\"\"\n",
    "\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, Leaf):\n",
    "        return node.predictions\n",
    "\n",
    "    # Decide whether to follow the true-branch or the false-branch.\n",
    "    # Compare the feature / value stored in the node,\n",
    "    # to the example we're considering.\n",
    "    if node.question.match(row):\n",
    "        return classify(row, node.true_branch)\n",
    "    else:\n",
    "        return classify(row, node.false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 695,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 1}"
      ]
     },
     "execution_count": 695,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "classify(train_vector[5], decision_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 696,
   "metadata": {},
   "outputs": [],
   "source": [
    "def accuracy_DT(test_vector, prediction):\n",
    "    correct = 0\n",
    "    for x in range(len(test_vector)):\n",
    "        if test_vector[x][-1] == prediction[x]:\n",
    "            correct += 1\n",
    "    return ((correct / float(len(test_vector))) * 100.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 666,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for Decision Tree with 10 feature size is 79.5169082125604\n"
     ]
    }
   ],
   "source": [
    "prediction = []\n",
    "for row in test_vector:\n",
    "    pred_dict = classify(row, decision_tree)\n",
    "    prediction_value = max(pred_dict.items(), key=operator.itemgetter(1))[0]\n",
    "    prediction.append(prediction_value)\n",
    "accuracy = accuracy_DT(test_vector, prediction)\n",
    "print('The accuarcy for Decision Tree with 10 feature size is '+ str(accuracy))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 697,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The accuarcy for Decision Tree for 10,000 feature is 95.65217391304348\n"
     ]
    }
   ],
   "source": [
    "prediction1 = []\n",
    "for row in test_vector:\n",
    "    pred_dict = classify(row, decision_tree)\n",
    "    prediction_value = max(pred_dict.items(), key=operator.itemgetter(1))[0]\n",
    "    prediction1.append(prediction_value)\n",
    "accuracy = accuracy_DT(test_vector, prediction1)\n",
    "print('The accuarcy for Decision Tree for 10,000 feature is '+ str(accuracy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}