simhash_for_question_deduplication/simhash.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SimHash\n",
    "Using hashing for Kaggl's Question Duplicate Pair Detection. Content from the blog post [SimHash for question deduplication](http://datawhatnow.com/simhash-question-deduplicatoin/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python3.5/dist-packages/sklearn/cross_validation.py:44: DeprecationWarning: This module was deprecated in version 0.18 in favor of the model_selection module into which all the refactored classes and functions are moved. Also note that the interface of the new CV iterators are different from that of this module. This module will be removed in 0.20.\n",
      "  \"This module will be removed in 0.20.\", DeprecationWarning)\n"
     ]
    }
   ],
   "source": [
    "# Utility libraries\n",
    "import pandas as pd\n",
    "\n",
    "# Dataset\n",
    "from nltk.corpus import stopwords\n",
    "from nltk.tokenize import word_tokenize\n",
    "from nltk import ngrams\n",
    "from simhash import Simhash\n",
    "from sklearn.model_selection import train_test_split\n",
    "from multiprocessing import Pool # We use pool to speed up feature creation\n",
    "\n",
    "#Metrics\n",
    "from sklearn.metrics import f1_score, log_loss, accuracy_score, precision_score, recall_score\n",
    "\n",
    "# Models\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from xgboost import XGBClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load the dataset\n",
    "The dataset (train.csv) comes from the Quao challange on Kaggle. To get the dataset download it from the official competition page on Kaggle https://www.kaggle.com/c/quora-question-pairs/data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "train = pd.read_csv('train.csv', dtype={'question1': str, 'question2': str})\n",
    "\n",
    "train.question1 = train.question1.astype(str)\n",
    "train.question2 = train.question2.astype(str)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data preprocessing\n",
    "SimHash is a hashing function that takes chuncks of text as inputs. We have to process the text into chunks first (words, char n-grams, word n-grams)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tokenize(sequence):\n",
    "    words = word_tokenize(sequence)\n",
    "    filtered_words = [word for word in words if word not in stopwords.words('english')]\n",
    "    return filtered_words\n",
    "\n",
    "def clean_sequence(sequence):\n",
    "    tokens = tokenize(sequence)\n",
    "    return ' '.join(tokens)\n",
    "\n",
    "def get_word_ngrams(sequence, n=3):\n",
    "    tokens = tokenize(sequence)\n",
    "    return [' '.join(ngram) for ngram in ngrams(tokens, n)]\n",
    "\n",
    "def get_character_ngrams(sequence, n=3):\n",
    "    sequence = clean_sequence(sequence)\n",
    "    return [sequence[i:i+n] for i in range(len(sequence)-n+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>qid1</th>\n",
       "      <th>qid2</th>\n",
       "      <th>question1</th>\n",
       "      <th>question2</th>\n",
       "      <th>is_duplicate</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>What is the story of Kohinoor (Koh-i-Noor) Dia...</td>\n",
       "      <td>What would happen if the Indian government sto...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>5</td>\n",
       "      <td>6</td>\n",
       "      <td>How can I increase the speed of my internet co...</td>\n",
       "      <td>How can Internet speed be increased by hacking...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>7</td>\n",
       "      <td>8</td>\n",
       "      <td>Why am I mentally very lonely? How can I solve...</td>\n",
       "      <td>Find the remainder when [math]23^{24}[/math] i...</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>9</td>\n",
       "      <td>10</td>\n",
       "      <td>Which one dissolve in water quikly sugar, salt...</td>\n",
       "      <td>Which fish would survive in salt water?</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   id  qid1  qid2                                          question1  \\\n",
       "0   0     1     2  What is the step by step guide to invest in sh...   \n",
       "1   1     3     4  What is the story of Kohinoor (Koh-i-Noor) Dia...   \n",
       "2   2     5     6  How can I increase the speed of my internet co...   \n",
       "3   3     7     8  Why am I mentally very lonely? How can I solve...   \n",
       "4   4     9    10  Which one dissolve in water quikly sugar, salt...   \n",
       "\n",
       "                                           question2  is_duplicate  \n",
       "0  What is the step by step guide to invest in sh...             0  \n",
       "1  What would happen if the Indian government sto...             0  \n",
       "2  How can Internet speed be increased by hacking...             0  \n",
       "3  Find the remainder when [math]23^{24}[/math] i...             0  \n",
       "4            Which fish would survive in salt water?             0  "
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "train.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Mary little lamb , really liked .\n"
     ]
    }
   ],
   "source": [
    "sequence = \"Mary had a little lamb, and she really liked it.\"\n",
    "print(clean_sequence(sequence))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: ['Mary', 'little', 'lamb', ',', 'really', 'liked', '.']\n",
      "\n",
      "Word ngrams: ['Mary little', 'little lamb', 'lamb ,', ', really', 'really liked', 'liked .']\n",
      "\n",
      "Character ngrams: ['Ma', 'ar', 'ry', 'y ', ' l', 'li', 'it', 'tt', 'tl', 'le', 'e ', ' l', 'la', 'am', 'mb', 'b ', ' ,', ', ', ' r', 're', 'ea', 'al', 'll', 'ly', 'y ', ' l', 'li', 'ik', 'ke', 'ed', 'd ', ' .']\n"
     ]
    }
   ],
   "source": [
    "sequence = \"Mary had a little lamb, and she really liked it.\"\n",
    "\n",
    "print('Tokens:', tokenize(sequence)) \n",
    "# ['Mary', 'little', 'lamb', ',', 'really', 'liked', '.']\n",
    "\n",
    "print('\\nWord ngrams:', get_word_ngrams(sequence, 2))  \n",
    "# ['Mary little', 'little lamb', 'lamb ,', ', really', 'really liked', 'liked .']\n",
    "\n",
    "print('\\nCharacter ngrams:', get_character_ngrams(sequence, 2))  \n",
    "# ['Ma', 'ar', 'ry', 'y ', ' l', 'li', 'it', 'tt', 'tl', 'le', 'e ', ' l', 'la', 'am', 'mb', 'b ', ' ,', ', ', ' r', 're', 'ea', 'al', 'll', 'ly', 'y ', ' l', 'li', 'ik', 'ke', 'ed', 'd ', ' .']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simhash examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokenize simhash: 20\n",
      "Word ngram simhash: 34\n",
      "Tokenize simhash: 16\n"
     ]
    }
   ],
   "source": [
    "q1 = \"How can I be a good geologist?\"\n",
    "q2 = \"What should I do to be a great geologist?\"\n",
    "\n",
    "print('Tokenize simhash:', Simhash(tokenize(q1)).distance(Simhash(tokenize(q2))))\n",
    "print('Word ngram simhash:', Simhash(get_word_ngrams(q1)).distance(Simhash(get_word_ngrams(q2))))\n",
    "print('Tokenize simhash:', Simhash(get_character_ngrams(q1)).distance(Simhash(get_character_ngrams(q2))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Feature creation\n",
    "The code below is kinda messy. I wrote it as a single function just to be able to use the Pool.map() method, otherwise this step takes a lot of time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def caluclate_simhash_distance(sequence1, sequence2):\n",
    "    return Simhash(sequence1).distance(Simhash(sequence2))\n",
    "\n",
    "def get_word_distance(questions):\n",
    "    q1, q2 = questions.split('_split_tag_')\n",
    "    q1, q2 = tokenize(q1), tokenize(q2)\n",
    "    return caluclate_simhash_distance(q1, q2)\n",
    "\n",
    "def get_word_2gram_distance(questions):\n",
    "    q1, q2 = questions.split('_split_tag_')\n",
    "    q1, q2 = get_word_ngrams(q1, 2), get_word_ngrams(q2, 2)\n",
    "    return caluclate_simhash_distance(q1, q2)\n",
    "\n",
    "def get_char_2gram_distance(questions):\n",
    "    q1, q2 = questions.split('_split_tag_')\n",
    "    q1, q2 = get_character_ngrams(q1, 2), get_character_ngrams(q2, 2)\n",
    "    return caluclate_simhash_distance(q1, q2)\n",
    "\n",
    "def get_word_3gram_distance(questions):\n",
    "    q1, q2 = questions.split('_split_tag_')\n",
    "    q1, q2 = get_word_ngrams(q1, 3), get_word_ngrams(q2, 3)\n",
    "    return caluclate_simhash_distance(q1, q2)\n",
    "\n",
    "def get_char_3gram_distance(questions):\n",
    "    q1, q2 = questions.split('_split_tag_')\n",
    "    q1, q2 = get_character_ngrams(q1, 3), get_character_ngrams(q2, 3)\n",
    "    return caluclate_simhash_distance(q1, q2)\n",
    "\n",
    "train['questions'] = train['question1'] + '_split_tag_' + train['question2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>qid1</th>\n",
       "      <th>qid2</th>\n",
       "      <th>question1</th>\n",
       "      <th>question2</th>\n",
       "      <th>is_duplicate</th>\n",
       "      <th>questions</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>0</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>What is the story of Kohinoor (Koh-i-Noor) Dia...</td>\n",
       "      <td>What would happen if the Indian government sto...</td>\n",
       "      <td>0</td>\n",
       "      <td>What is the story of Kohinoor (Koh-i-Noor) Dia...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   id  qid1  qid2                                          question1  \\\n",
       "0   0     1     2  What is the step by step guide to invest in sh...   \n",
       "1   1     3     4  What is the story of Kohinoor (Koh-i-Noor) Dia...   \n",
       "\n",
       "                                           question2  is_duplicate  \\\n",
       "0  What is the step by step guide to invest in sh...             0   \n",
       "1  What would happen if the Indian government sto...             0   \n",
       "\n",
       "                                           questions  \n",
       "0  What is the step by step guide to invest in sh...  \n",
       "1  What is the story of Kohinoor (Koh-i-Noor) Dia...  "
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "train.head(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instead of 8, swap the number with the number of cpu cores/threads you have\n",
    "pool = Pool(processes=8)\n",
    "\n",
    "train['tokenize_distance'] = pool.map(get_word_distance, train['questions'])\n",
    "\n",
    "train['word_2gram_distance'] = pool.map(get_word_2gram_distance, train['questions'])\n",
    "train['char_2gram_distance'] = pool.map(get_char_2gram_distance, train['questions'])\n",
    "\n",
    "train['word_3gram_distance'] = pool.map(get_word_3gram_distance, train['questions'])\n",
    "train['char_3gram_distance'] = pool.map(get_char_3gram_distance, train['questions'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>qid1</th>\n",
       "      <th>qid2</th>\n",
       "      <th>question1</th>\n",
       "      <th>question2</th>\n",
       "      <th>is_duplicate</th>\n",
       "      <th>questions</th>\n",
       "      <th>tokenize_distance</th>\n",
       "      <th>word_2gram_distance</th>\n",
       "      <th>char_2gram_distance</th>\n",
       "      <th>word_3gram_distance</th>\n",
       "      <th>char_3gram_distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>2</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>0</td>\n",
       "      <td>What is the step by step guide to invest in sh...</td>\n",
       "      <td>12</td>\n",
       "      <td>1</td>\n",
       "      <td>13</td>\n",
       "      <td>4</td>\n",
       "      <td>17</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>4</td>\n",
       "      <td>What is the story of Kohinoor (Koh-i-Noor) Dia...</td>\n",
       "      <td>What would happen if the Indian government sto...</td>\n",
       "      <td>0</td>\n",
       "      <td>What is the story of Kohinoor (Koh-i-Noor) Dia...</td>\n",
       "      <td>25</td>\n",
       "      <td>15</td>\n",
       "      <td>29</td>\n",
       "      <td>13</td>\n",
       "      <td>25</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   id  qid1  qid2                                          question1  \\\n",
       "0   0     1     2  What is the step by step guide to invest in sh...   \n",
       "1   1     3     4  What is the story of Kohinoor (Koh-i-Noor) Dia...   \n",
       "\n",
       "                                           question2  is_duplicate  \\\n",
       "0  What is the step by step guide to invest in sh...             0   \n",
       "1  What would happen if the Indian government sto...             0   \n",
       "\n",
       "                                           questions  tokenize_distance  \\\n",
       "0  What is the step by step guide to invest in sh...                 12   \n",
       "1  What is the story of Kohinoor (Koh-i-Noor) Dia...                 25   \n",
       "\n",
       "   word_2gram_distance  char_2gram_distance  word_3gram_distance  \\\n",
       "0                    1                   13                    4   \n",
       "1                   15                   29                   13   \n",
       "\n",
       "   char_3gram_distance  \n",
       "0                   17  \n",
       "1                   25  "
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "train.head(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model performance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "features = ['tokenize_distance', 'word_2gram_distance', 'char_2gram_distance',\n",
    "           'word_3gram_distance', 'char_3gram_distance']\n",
    "target = 'is_duplicate'\n",
    "\n",
    "X = train[features]\n",
    "y = train[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "XGBClassifier(base_score=0.5, colsample_bylevel=1, colsample_bytree=1,\n",
       "       gamma=0, learning_rate=0.1, max_delta_step=0, max_depth=3,\n",
       "       min_child_weight=1, missing=None, n_estimators=100, nthread=-1,\n",
       "       objective='binary:logistic', reg_alpha=0, reg_lambda=1,\n",
       "       scale_pos_weight=1, seed=0, silent=True, subsample=1)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model = XGBClassifier()\n",
    "model.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Acc: 0.680959212447\n",
      "LogLoss: 0.55707137604\n"
     ]
    }
   ],
   "source": [
    "prediction_probas = model.predict_proba(X_test)\n",
    "predictions = model.predict(X_test)\n",
    "\n",
    "print('Acc:', accuracy_score(y_test, predictions))\n",
    "print('LogLoss:', log_loss(y_test, prediction_probas))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}