Vector Space Model.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vector Space Model\n",
    "\n",
    "## From Scratch\n",
    "\n",
    "### Algorithm:\n",
    "\n",
    "* inverted_index = {}\n",
    "* *For each doc in document*:\n",
    "        for each unique term:\n",
    "            add doc number in posting list ==> inverted index\n",
    "        make doc vector for each doc // normalized vector\n",
    "        \n",
    "        for eg : India COEP ===> (1,1) ===> (0.707, 0.707)\n",
    "*  *for each term in query*:\n",
    "        calculate t.f\n",
    "        calculate d.f\n",
    "        calculate i.d.f\n",
    "        calculate w (t,q)  // do not normalize\n",
    "        \n",
    "        do fetch postings list for term\n",
    "        for each pair(d, tf(t,d)) in postings list\n",
    "            do Scores[d] += wf(t,d) × w(t,q)\n",
    "*   *for each d*:\n",
    "        do Scores[d] = Scores[d]/Length[d]\n",
    "*     return Top K components of Scores[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "import string\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "from collections import deque\n",
    "from nltk.corpus import stopwords\n",
    "from nltk.stem import PorterStemmer\n",
    "from nltk.tokenize import SpaceTokenizer\n",
    "from nltk.tokenize import TweetTokenizer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "imported libraries "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*process_line()* is useful for preprocessing of document linewise and query which is itself a line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_line(line):\n",
    "    \"\"\"Process doc function.\n",
    "    Input:\n",
    "        doc: a string containing a information\n",
    "    Output:\n",
    "        doc_clean: a list of words containing the processed doc\n",
    "\n",
    "    \"\"\"\n",
    "    stemmer = PorterStemmer()\n",
    "    stopwords_english = stopwords.words('english')\n",
    "    tokenizer = TweetTokenizer(preserve_case=False, strip_handles=True,\n",
    "                               reduce_len=True)\n",
    "    line_tokens = tokenizer.tokenize(line)\n",
    "\n",
    "    line_clean = []\n",
    "    for word in line_tokens:\n",
    "        if (word not in stopwords_english and  # remove stopwords\n",
    "                word not in string.punctuation):  # remove punctuation\n",
    "            # doc_clean.append(word)\n",
    "            stem_word = stemmer.stem(word)  # stemming word\n",
    "            line_clean.append(stem_word)\n",
    "\n",
    "    return line_clean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*process_doc()* is a function which reads file linewise and stores all terms in one file with the term frequency"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_doc(docdata, file):\n",
    "    global vsm\n",
    "    terms = []\n",
    "    for line in docdata:\n",
    "        linedata = process_line(line)\n",
    "        for term in linedata:\n",
    "            vsm.PostingList(term, file)\n",
    "            terms.append(term)\n",
    "    terms = Counter(terms)\n",
    "    vsm.AddAllTerms(terms, file)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*GetData()* function is useful for making document vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "def GetData(filelist, path):\n",
    "    global vsm\n",
    "    for file in filelist:\n",
    "        filename = os.path.join(path, file)\n",
    "        f = open(filename, 'r')\n",
    "        docdata = f.readlines()\n",
    "        process_doc(docdata, file)\n",
    "    vsm.MakeDocVector()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "helper snippet to call *GetData()* function so that Corpus processing can take place"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [],
   "source": [
    "dirname = os.getcwd()\n",
    "path = os.path.join(dirname, 'Data')\n",
    "filelist = os.listdir(path)\n",
    "GetData(filelist, path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is important class of Vector Space Model which is useful to store Inverted Index, Document Frequencies and Document Vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "class VSM():\n",
    "    def __init__(self):\n",
    "        self.posting_list = {}\n",
    "        self.docvectors = {}\n",
    "        self.docinfo = {}\n",
    "        \n",
    "        dirname = os.getcwd()\n",
    "        path = os.path.join(dirname, 'Data')\n",
    "        filelist = os.listdir(path)\n",
    "        self.N = len(filelist)\n",
    "        \n",
    "    def MakeDocVector(self):\n",
    "        for doc in self.docinfo.keys():\n",
    "            vector = []\n",
    "            c = self.docinfo[doc]\n",
    "            for term in self.posting_list.keys():\n",
    "                tf = self.TermFrequency(c[term])\n",
    "                idf = self.InverseDocumentFrequency(len(self.posting_list[term]))\n",
    "                vector.append(tf * idf)\n",
    "            self.docvectors[doc] = vector\n",
    "        self.df = pd.DataFrame(data = self.docvectors, index = self.posting_list.keys())\n",
    "                \n",
    "    def PostingList(self, term, docname):\n",
    "        if term in self.posting_list.keys():\n",
    "            if docname not in self.posting_list[term]:\n",
    "                self.posting_list[term].append(docname)\n",
    "        else:\n",
    "            self.posting_list[term] = []\n",
    "            self.posting_list[term].append(docname)\n",
    "    \n",
    "    def AddAllTerms(self, terms, docname):\n",
    "        self.docinfo[docname] = terms\n",
    "    \n",
    "    def TermFrequency(self, termfrequency):\n",
    "        if termfrequency == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + np.log10(termfrequency)\n",
    "    \n",
    "    def InverseDocumentFrequency(self, documentfrequency):\n",
    "        return np.log10(self.N / documentfrequency)\n",
    "vsm = VSM()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "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>hillary_diane_rodham_clinton.txt</th>\n",
       "      <th>foreign_investement _to_gujrat.txt</th>\n",
       "      <th>obama.txt</th>\n",
       "      <th>barack_hussein_obama.txt</th>\n",
       "      <th>united_state_presidential_election_2016.txt</th>\n",
       "      <th>president_of_the_united_states.txt</th>\n",
       "      <th>narendra_damodardas_modi.txt</th>\n",
       "      <th>modi_visit_us.txt</th>\n",
       "      <th>united_states_of_america.txt</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>hillari</td>\n",
       "      <td>0.477121</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.477121</td>\n",
       "      <td>0.477121</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>dian</td>\n",
       "      <td>0.954243</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>rodham</td>\n",
       "      <td>0.954243</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>clinton</td>\n",
       "      <td>0.954243</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.477121</td>\n",
       "      <td>0.620749</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>ˈhɪləri</td>\n",
       "      <td>0.954243</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>scientif</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.954243</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>research</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.954243</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>technolog</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.954243</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>innov</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.954243</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>40</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.954243</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>1154 rows × 9 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "           hillary_diane_rodham_clinton.txt  \\\n",
       "hillari                            0.477121   \n",
       "dian                               0.954243   \n",
       "rodham                             0.954243   \n",
       "clinton                            0.954243   \n",
       "ˈhɪləri                            0.954243   \n",
       "...                                     ...   \n",
       "scientif                           0.000000   \n",
       "research                           0.000000   \n",
       "technolog                          0.000000   \n",
       "innov                              0.000000   \n",
       "40                                 0.000000   \n",
       "\n",
       "           foreign_investement _to_gujrat.txt  obama.txt  \\\n",
       "hillari                                   0.0        0.0   \n",
       "dian                                      0.0        0.0   \n",
       "rodham                                    0.0        0.0   \n",
       "clinton                                   0.0        0.0   \n",
       "ˈhɪləri                                   0.0        0.0   \n",
       "...                                       ...        ...   \n",
       "scientif                                  0.0        0.0   \n",
       "research                                  0.0        0.0   \n",
       "technolog                                 0.0        0.0   \n",
       "innov                                     0.0        0.0   \n",
       "40                                        0.0        0.0   \n",
       "\n",
       "           barack_hussein_obama.txt  \\\n",
       "hillari                    0.477121   \n",
       "dian                       0.000000   \n",
       "rodham                     0.000000   \n",
       "clinton                    0.477121   \n",
       "ˈhɪləri                    0.000000   \n",
       "...                             ...   \n",
       "scientif                   0.000000   \n",
       "research                   0.000000   \n",
       "technolog                  0.000000   \n",
       "innov                      0.000000   \n",
       "40                         0.000000   \n",
       "\n",
       "           united_state_presidential_election_2016.txt  \\\n",
       "hillari                                       0.477121   \n",
       "dian                                          0.000000   \n",
       "rodham                                        0.000000   \n",
       "clinton                                       0.620749   \n",
       "ˈhɪləri                                       0.000000   \n",
       "...                                                ...   \n",
       "scientif                                      0.000000   \n",
       "research                                      0.000000   \n",
       "technolog                                     0.000000   \n",
       "innov                                         0.000000   \n",
       "40                                            0.000000   \n",
       "\n",
       "           president_of_the_united_states.txt  narendra_damodardas_modi.txt  \\\n",
       "hillari                                   0.0                           0.0   \n",
       "dian                                      0.0                           0.0   \n",
       "rodham                                    0.0                           0.0   \n",
       "clinton                                   0.0                           0.0   \n",
       "ˈhɪləri                                   0.0                           0.0   \n",
       "...                                       ...                           ...   \n",
       "scientif                                  0.0                           0.0   \n",
       "research                                  0.0                           0.0   \n",
       "technolog                                 0.0                           0.0   \n",
       "innov                                     0.0                           0.0   \n",
       "40                                        0.0                           0.0   \n",
       "\n",
       "           modi_visit_us.txt  united_states_of_america.txt  \n",
       "hillari                  0.0                      0.000000  \n",
       "dian                     0.0                      0.000000  \n",
       "rodham                   0.0                      0.000000  \n",
       "clinton                  0.0                      0.000000  \n",
       "ˈhɪləri                  0.0                      0.000000  \n",
       "...                      ...                           ...  \n",
       "scientif                 0.0                      0.954243  \n",
       "research                 0.0                      0.954243  \n",
       "technolog                0.0                      0.954243  \n",
       "innov                    0.0                      0.954243  \n",
       "40                       0.0                      0.954243  \n",
       "\n",
       "[1154 rows x 9 columns]"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vsm.df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Query Processing Unit and Result :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter Your Query:Narendra Modi\n",
      "0.0 hillary_diane_rodham_clinton.txt\n",
      "0.0795117096900166 foreign_investement _to_gujrat.txt\n",
      "0.0 obama.txt\n",
      "0.0 barack_hussein_obama.txt\n",
      "0.0 united_state_presidential_election_2016.txt\n",
      "0.0 president_of_the_united_states.txt\n",
      "0.06978501195246557 narendra_damodardas_modi.txt\n",
      "0.06983458798985998 modi_visit_us.txt\n",
      "0.0 united_states_of_america.txt\n"
     ]
    }
   ],
   "source": [
    "query = input('Enter Your Query:')\n",
    "query = process_line(query)\n",
    "c = Counter(query)\n",
    "vector = []\n",
    "for term in vsm.posting_list:\n",
    "    tf = vsm.TermFrequency(c[term])\n",
    "    idf = vsm.InverseDocumentFrequency(len(vsm.posting_list.get(term,[])))\n",
    "    vector.append(tf * idf)\n",
    "for key, docvector in vsm.df.iteritems():\n",
    "    print(np.dot(docvector, vector)/ np.linalg.norm(docvector), key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sample Input and its result\n",
    "Enter Your Query:   Narendra Modi  <br> \n",
    "\n",
    "\n",
    "Score               Document Name <br> \n",
    "    \n",
    "    0.0                 hillary_diane_rodham_clinton.txt <br>\n",
    "    0.0795117096900166  foreign_investement _to_gujrat.txt <br>\n",
    "    0.0                 obama.txt<br>\n",
    "    0.0                 barack_hussein_obama.txt<br>\n",
    "    0.0                 united_state_presidential_election_2016.txt<br>\n",
    "    0.0                 president_of_the_united_states.txt<br>\n",
    "    0.06978501195246557 narendra_damodardas_modi.txt<br>\n",
    "    0.06983458798985998 modi_visit_us.txt<br>\n",
    "    0.0                 united_states_of_america.txt<br>\n",
    "\n"
   ]
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}