{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "e1ca4ad0-37e5-e4c4-6b57-5e0db4d03ee6"
      },
      "source": [
        "In this notebook we explore the possibilities of fuzzy search algorithms in finding similarities.\n",
        "\n",
        "**Classification using fuzzy matching**\n",
        "\n",
        "-Classify whether question pairs are duplicate or not\n",
        "\n",
        "-Let us start with importing the necessary modules for exploring the data."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "a94bbb2d-c58b-0b72-72ad-b48274e69ea2"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import pandas as pd\n",
        "from sklearn.ensemble import RandomForestClassifier\n",
        "#from pyxdameraulevenshtein import damerau_levenshtein_distance, normalized_damerau_levenshtein_distance\n",
        "from nltk.stem.porter import *\n",
        "stemmer = PorterStemmer()\n",
        "import random\n",
        "import re\n",
        "\n",
        "random.seed(1337)\n",
        "\n",
        "df_train = pd.read_csv('../input/train.csv', encoding=\"ISO-8859-1\")\n",
        "df_test = pd.read_csv('../input/test.csv', encoding=\"ISO-8859-1\")\n",
        "\n",
        "num_train = df_train.shape[0]\n",
        "print (num_train)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "da76958c-1499-2049-54ff-8884ee1ab734"
      },
      "outputs": [],
      "source": [
        "df_train.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "a0bb69ea-4af9-61df-4b8a-a378cb9ef028"
      },
      "outputs": [],
      "source": [
        "df_test.head()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "dcce789a-b8cc-812f-78bc-83214d0afc6a"
      },
      "source": [
        "We use Jaccard similarity and Levenshtein distance to find the similarity between the questions. The number of words matched are also used as features for prediction."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "2ab37e88-5b93-ff99-dbd0-73e286dd41ce"
      },
      "outputs": [],
      "source": [
        "def str_stem(str1):\n",
        "    str1 = str(str1)\n",
        "    str1 = re.sub(r'[^a-zA-Z0-9 ]',r'',str1)\n",
        "    str1 = str1.lower()\n",
        "    #str1 = (\" \").join([stemmer.stem(z) for z in str1.split(\" \")])\n",
        "    return str1\n",
        "\n",
        "def str_common_word(str1, str2):\n",
        "    str1, str2 = str1.lower(), str2.lower()\n",
        "    words, cnt = str1.split(), 0\n",
        "    for word in words:\n",
        "        if str2.find(word)>=0:\n",
        "            cnt+=1\n",
        "    return cnt\n",
        "def ngram(tokens, n):\n",
        "    grams =[tokens[i:i+n] for i in range(len(tokens)-(n-1))]\n",
        "    return grams\n",
        "\n",
        "def get_sim(a_tri,b_tri):\n",
        "    intersect = len(set(a_tri) & set(b_tri))\n",
        "    union = len(set(a_tri) | set(b_tri))\n",
        "    if union == 0:\n",
        "        return 0\n",
        "    return float(intersect)/(union)\n",
        "\n",
        "def jaccard_similarity(str1,str2):\n",
        "    sentence_gram1 = str1\n",
        "    sentence_gram2 = str2\n",
        "    grams1 = ngram(sentence_gram1, 5)\n",
        "    grams2 = ngram(sentence_gram2, 5)\n",
        "    similarity = get_sim(grams1, grams2)\n",
        "    return similarity\n",
        "    \n",
        "    \n",
        "df_all = pd.concat((df_train, df_test), axis=0, ignore_index=True)\n",
        "\n",
        "\n",
        "df_all['question1'] = df_all['question1'].map(lambda x:str_stem(x))\n",
        "df_all['question2'] = df_all['question2'].map(lambda x:str_stem(x))\n",
        "\n",
        "df_all['len_of_q1'] = df_all['question1'].map(lambda x:len(x.split())).astype(np.int64)\n",
        "df_all['len_of_q2'] = df_all['question2'].map(lambda x:len(x.split())).astype(np.int64)\n",
        "\n",
        "df_all['questions'] = df_all['question1']+\"|\"+df_all['question2']\n",
        "print (\"Questions combined...\")\n",
        "df_all['q2_in_q1'] = df_all['questions'].map(lambda x:str_common_word(x.split('|')[0],x.split('|')[1]))\n",
        "df_all['q1_in_q2'] = df_all['questions'].map(lambda x:str_common_word(x.split('|')[1],x.split('|')[0]))\n",
        "print (\"Common words found ...\")\n",
        "df_all['jaccard'] = df_all['questions'].map(lambda x:jaccard_similarity(x.split('|')[0],x.split('|')[1]))\n",
        "print (\"Jaccard similarities computed...\")\n",
        "#df_all['lev_distance'] = df_all['questions'].map(lambda x:normalized_damerau_levenshtein_distance(x.split('|')[0],x.split('|')[1]))\n",
        "#print (\"Levenshtein distances computed...\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "c7be7e9d-57fb-af97-395d-39f37490aaee"
      },
      "outputs": [],
      "source": [
        "df_all.head()"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "ee951743-270f-c81f-b8af-e0994f90655a"
      },
      "outputs": [],
      "source": [
        "\n",
        "df_all = df_all.drop(['id','qid1','qid2','question1','question2','questions'],axis=1)\n",
        "\n",
        "df_train = df_all.iloc[:num_train]\n",
        "df_test = df_all.iloc[num_train:]\n",
        "id_test = df_test['test_id']\n",
        "\n",
        "y_train = df_train['is_duplicate'].values\n",
        "X_train = df_train.drop(['test_id','is_duplicate'],axis=1).values\n",
        "X_test = df_test.drop(['test_id','is_duplicate'],axis=1).values\n",
        "\n",
        "from sklearn.cross_validation import train_test_split\n",
        "\n",
        "x_trainb, x_validb, y_trainb, y_validb = train_test_split(X_train, y_train, test_size=0.2, random_state=4747)\n",
        "\n",
        "import xgboost as xgb\n",
        "\n",
        "params = {}\n",
        "params['objective'] = 'binary:logistic'\n",
        "params['eval_metric'] = 'logloss'\n",
        "params['eta'] = 0.02\n",
        "params['max_depth'] = 4\n",
        "\n",
        "d_train = xgb.DMatrix(x_trainb, label=y_trainb)\n",
        "d_valid = xgb.DMatrix(x_validb, label=y_validb)\n",
        "\n",
        "watchlist = [(d_train, 'train'), (d_valid, 'valid')]\n",
        "\n",
        "bst = xgb.train(params, d_train, 300, watchlist, early_stopping_rounds=50, verbose_eval=10)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "33309a0f-1360-7e87-e404-e5a4c702cd0a"
      },
      "outputs": [],
      "source": [
        "d_test = xgb.DMatrix(X_test)\n",
        "p_test = bst.predict(d_test)\n",
        "\n",
        "sub = pd.DataFrame()\n",
        "sub['test_id'] = np.int32(id_test)\n",
        "sub['is_duplicate'] = p_test\n",
        "sub.to_csv('simple_xgb.csv', index=False)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "099177b4-e02e-5dd0-75ac-ba876d3a8a43"
      },
      "outputs": [],
      "source": [
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "be8bfce1-b937-10a7-527a-4cf9d4c29455"
      },
      "source": [
        "This is my first notebook in Kaggle. Looking for suggestions to improve the model. The levenshtein algorithm is commented out since it is unavailable in Kaggle."
      ]
    }
  ],
  "metadata": {
    "_change_revision": 0,
    "_is_fork": false,
    "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.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}