Document-Information-Retrieval.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    "import time\n",
    "\n",
    "from sklearn.cluster import MiniBatchKMeans\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "from sklearn.decomposition import PCA\n",
    "from sklearn.manifold import TSNE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Mention', ' DBpedia Uri', ' NIF Uri', ' Type']\n"
     ]
    }
   ],
   "source": [
    "import csv\n",
    "with open(\"/home/aditi/document-information-retrieval/wikilink_ner.csv\", \"r\") as f:\n",
    "    reader = csv.reader(f)\n",
    "    i = next(reader)\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Importing libraries\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "from sklearn.cluster import KMeans\n",
    "from nltk.corpus import stopwords \n",
    "from nltk.stem.wordnet import WordNetLemmatizer\n",
    "import string\n",
    "import re\n",
    "import numpy as np\n",
    "from collections import Counter\n",
    "\n",
    "stop = set(stopwords.words('english'))\n",
    "exclude = set(string.punctuation) \n",
    "lemma = WordNetLemmatizer()\n",
    "\n",
    "# Cleaning the text sentences so that punctuation marks, stop words & digits are removed  \n",
    "def clean(doc):\n",
    "    stop_free = \" \".join([i for i in doc.lower().split() if i not in stop])\n",
    "    punc_free = ''.join(ch for ch in stop_free if ch not in exclude)\n",
    "    normalized = \" \".join(lemma.lemmatize(word) for word in punc_free.split())\n",
    "    processed = re.sub(r\"\\d+\",\"\",normalized)\n",
    "    y = processed.split()\n",
    "    return y\n",
    "\n",
    "import nltk.data\n",
    "\n",
    "data = []\n",
    "corpus = []\n",
    "tokenizer = nltk.data.load('tokenizers/punkt/english.pickle')\n",
    "fp = open(\"sentences.txt\")\n",
    "for line in fp:\n",
    "    line = line.strip()\n",
    "    cleaned = clean(line)\n",
    "    data.append(cleaned)\n",
    "\n",
    "corpus = [' '.join(i) for i in data]\n",
    "#print(corpus)\n",
    "\n",
    "#Count Vectoriser then tidf transformer\n",
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "\n",
    "vectorizer = CountVectorizer()\n",
    "X = vectorizer.fit_transform(corpus)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(30, 251)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "scipy.sparse.csr.csr_matrix"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.feature_extraction.text import TfidfTransformer\n",
    "\n",
    "transformer = TfidfTransformer(smooth_idf=False)\n",
    "tfidf = transformer.fit_transform(X)\n",
    "print(tfidf.shape) \n",
    "type(tfidf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 1 1 1 1 1 1 1 1 1 2 2 2 2 0 2 2 2 2 2 0 0 0 0 2 0 0 0 0 0]\n",
      "Time taken for K-means Clustering:  1.127117395401001\n",
      "[1 1 1 1 1 1 1 1 1 1 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      "Time taken for Agglomerative Clustering:  0.10764503479003906\n",
      "[0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2]\n",
      "Time taken for Spectral Clustering:  0.5962066650390625\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "numpy.ndarray"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "times = []\n",
    "algorithm = ['K-means', 'Agglomerative', 'Spectral']\n",
    "start_time = time.time()\n",
    "from sklearn.cluster import KMeans\n",
    "\n",
    "num_clusters = 3\n",
    "km = KMeans(n_clusters=num_clusters)\n",
    "km.fit(tfidf)\n",
    "print(km.labels_)\n",
    "clusters = km.labels_.tolist()\n",
    "elapsed_time = time.time() - start_time\n",
    "times.append(elapsed_time)\n",
    "\n",
    "print(\"Time taken for K-means Clustering: \", elapsed_time)\n",
    "\n",
    "# ====================================================================\n",
    "#   Modification-1 : Implement Agglomerative Heirarchical Clustering\n",
    "# ====================================================================\n",
    "\n",
    "start_time = time.time()\n",
    "from sklearn.cluster import AgglomerativeClustering\n",
    "\n",
    "cluster = AgglomerativeClustering(n_clusters=3, affinity='euclidean', linkage='ward')\n",
    "cluster.fit(tfidf.toarray())\n",
    "print(cluster.labels_)\n",
    "\n",
    "elapsed_time = time.time() - start_time\n",
    "times.append(elapsed_time)\n",
    "\n",
    "print(\"Time taken for Agglomerative Clustering: \", elapsed_time)\n",
    "type(cluster.labels_)\n",
    "\n",
    "# =========================================================\n",
    "#   Modification-2 : Implement Spectral Clustering\n",
    "# =========================================================\n",
    "\n",
    "start_time = time.time()\n",
    "from sklearn.cluster import SpectralClustering \n",
    "\n",
    "# Building the clustering model \n",
    "spectral_model_rbf = SpectralClustering(n_clusters = 3, affinity ='nearest_neighbors') \n",
    "\n",
    "# Training the model and Storing the predicted cluster labels \n",
    "labels_rbf = spectral_model_rbf.fit_predict(tfidf.toarray()) \n",
    "print(labels_rbf)\n",
    "\n",
    "elapsed_time = time.time() - start_time\n",
    "times.append(elapsed_time)\n",
    "\n",
    "print(\"Time taken for Spectral Clustering: \", elapsed_time)\n",
    "type(cluster.labels_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For number of clusters: 2 ,average Silhouette Score: 0.030369886188607167\n",
      "For number of clusters: 3 ,average Silhouette Score: 0.0415726449734021\n",
      "For number of clusters: 4 ,average Silhouette Score: 0.05810545532468503\n",
      "For number of clusters: 5 ,average Silhouette Score: 0.05513626562733793\n",
      "For number of clusters: 6 ,average Silhouette Score: 0.04393264055788708\n",
      "For number of clusters: 7 ,average Silhouette Score: 0.06083926013790073\n",
      "For number of clusters: 8 ,average Silhouette Score: 0.05330135484023437\n",
      "For number of clusters: 10 ,average Silhouette Score: 0.07146135578128995\n",
      "For number of clusters: 11 ,average Silhouette Score: 0.06732478747285929\n",
      "For number of clusters: 12 ,average Silhouette Score: 0.05784648938780677\n",
      "For number of clusters: 13 ,average Silhouette Score: 0.06910901652237274\n"
     ]
    }
   ],
   "source": [
    "# =======================================================================\n",
    "#   Modification-3 : Implemented Silhouette Analysis to get best cluster\n",
    "# =======================================================================\n",
    "\n",
    "\n",
    "from sklearn.metrics import silhouette_samples, silhouette_score\n",
    "from sklearn.cluster import KMeans\n",
    "def getCluster(n):\n",
    "    km = KMeans(n_clusters=n)\n",
    "    km.fit(tfidf)\n",
    "    clusters = km.labels_\n",
    "    runSilhoutteAnalysis(tfidf, clusters, n)\n",
    "    \n",
    "def runSilhoutteAnalysis(X, cluster, n):\n",
    "    sil_avg = silhouette_score(X, cluster)\n",
    "    print('For number of clusters:', n,',average Silhouette Score:', str(sil_avg))\n",
    "    # Compute the silhouette scores for each sample\n",
    "    sample_silhouette_values = silhouette_samples(X, cluster)\n",
    "    \n",
    "for cluster in [2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13]:\n",
    "    getCluster(cluster)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY4AAAFvCAYAAABdHCxbAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XeYHWX5xvHvnYTQeyJIDdKkCvxC\nEaWoiIACYkFCERREsCsWQESKigoKKqCiIEhHFEQBUUSKUiQqRcBopEZQQu91n98fz3vYyck5uzvJ\n7p4t9+e65to9M3PmvDOnPPN2RQRmZmZ9NabTCTAzs+HFgcPMzGpx4DAzs1ocOMzMrBYHDjMzq8WB\nw8zManHgGKEkHSzpx51ORyuS7pa01SC8TkhaZaBfZ7Bfq5d0dOR9l3SYpDMG6NibSZrWw/ZJ5fqP\nG4jXt9k5cAxTkp6qLF2Snq083i0ivhYR+wxCOkbFl1bSqyWdLOkBSU9K+oekwyUt2I+vcaqkr8zN\nMQbrfR9MEXFNRKzeeDxYNx7WngPHMBURCzUW4F5g+8q6MzudvpFE0hLAdcD8wOsjYmHgrcBiwMqd\nTFvVSAzeI/GcRgIHjhGqWnRQyRV8QNJ9kh6VtJ+kDSXdIukxScc3Pf+Dku4o+14macU2L3V1+ftY\nye28XtLKkq6Q9LCkhySdKWmxNul8raS7JO1SHi8j6eeSZpb1n2g6p/Mk/bTc9d8maXIvl2I7SXeW\ndBwtaYykeSU9ImmdyrFfVXJtE1sc4zPAk8DuEXE3QETcFxGfjIhbWpzTlZL2qTzeS9Ify/+SdKyk\nByU9Xq7/2pL2BXYDPl+u46/6eD3Ol3SGpCeAvdq873tKurdcgy9Wnj+/pNPKe3yHpM9LmtHuQkr6\nTvn8PCHpL5I262Hf90u6p3wGvlTNJZTrf5yk+8tynKR5y7YtJc2Q9AVJ/wV+0lhXtp8OrAD8qlyn\nz1dedrc253mYpJ+V6/SkpFslrSbpoPI+3Cdp66b3686y712Sdmt3nqOVA8fosjGwKvA+4Djgi8BW\nwFrAzpK2AJD0TuBg4F3AROAa4Ow2x9y8/F2s5HauAwQcBSwDrAEsDxzW/ERJGwC/BT4eEedIGgP8\nCrgZWBZ4C/ApSW+rPG0H4Bzybv8i4Hh6thMwGdgA2BH4YEQ8X46xe2W/KcDlETGzxTG2An4REV29\nvFZfbE1es9XIc3gf8HBEnAScCXyzXMft+3g9dgTOL8dql9N8I7B6ef6hktYo678MTAJeQ+agdm/5\n7G43AusBSwBnAT+TNF/zTpLWBE4kA+GrgUVL+hu+CGxSjvU6YCPgkMr2pctrrAjsWz12ROzBrDns\nb/bhPAG2B04HFgf+BlxG/v4tCxwB/LCkfUHgu8C2JWe5KXBTL9dl1HHgGF2OjIjnIuK3wNPA2RHx\nYET8hwwO65f9PgwcFRF3RMRLwNeA9dQ+1zGLiJgeEb+LiOfLD/G3gS2adtuM/OHfMyJ+XdZtCEyM\niCMi4oWIuBP4EbBL5Xl/jIhLIuJl8ofgdb0k5xsR8UhE3EsGyyll/WnAruXHGWCPcrxWlgQe6OV1\n+upFYGHgtYDKNW537L5cj+si4sKI6IqIZ9sc5/CIeDYibiaDUOOa7Qx8LSIejYgZ5A9mWxFxRkQ8\nHBEvRcS3gHnJH+pm7wF+FRF/jIgXgEOB6qB4uwFHlM/eTOBw8vo3dAFfLp+fdudU5zwBromIy8rn\n+WfkDdHXI+JF8iZiUiVX3AWsLWn+iHggIm6rkYZRwYFjdPlf5f9nWzxeqPy/IvAdZRHWY8AjZC6i\netfYVin2OUfSf0oRyhnAhKbd9gOujYg/VNatCCzTeN3y2gcDS1X2+W/l/2eA+dRzOfh9lf/vIXNB\nRMQNZPDcQtJrgVXIQNbKw+Sd81yLiCvIXNIJwP8knSRpkTa79+V63Nf6qbNovmaN93mZpuf3eCxJ\nB5QircdLWhZl9vd1tuNGxDPkNaxuv6fy+JX3pZgZEc/1lJY22p0nzP5Zf6jcfDQeAywUEU+TucD9\ngAckXVw+H1bhwGGt3Ad8OCIWqyzzR8S1LfZtNbzyUWX9uhGxCFkEoqZ99gNWkHRs0+ve1fS6C0fE\ndnNxLstX/l8BuL/y+LSStj2A83v4sboc2KmSO+nN08AClcdLVzdGxHcj4v/IIsLVgM81NjUdpy/X\nY26Gt34AWK7yePl2O5b6jC+QuZTFI2Ix4HFmf19nO66k+clcW8P9ZFBsaH5fejunAR3Su+RM3kre\nLPyDzOVZhQOHtfID4CBJawFIWlTSe9vsO5PM2r+msm5h4CmywnxZun8Yq54EtgE2l/T1su7PwBOl\nYnR+SWNLxfGGc3Eun5O0uKTlgU8C51a2nU7WgewO/LSHY3wbWAQ4rVFcJ2lZSd+WtG6L/W8C3iVp\nAWXfjr0bG5QNEjaWNA8ZYJ4DGne+/2PW6zgQ16PqPPJ9Xry8Tx/rYd+FgZfI93ucpEPJa9LK+cD2\nkjaVNJ4siqoGmLOBQyRNlDSBLMqq0wek+Tr1G0lLSdqh1HU8T36OX+7laaOOA4fNJiIuAL4BnFOK\nmv4ObNtm32eArwJ/KsUpm5A/FBuQd6QXA79o89zHyErZbSUdWYoOticrTe8CHgJ+TBaJzKlfAn8h\nf8wvBk6uvP4M4K/kHew17Q4QEY+QlaQvAjdIehL4fTm/6S2ecizwAvkDdxqzVlovQt7BPkoW0TwM\nHFO2nQysWa7jhQN0PaqOAGaUY19O/uA/32bfy4BLgX+WdD9Hm6KtUifwcbLu4AHyJuHByrG/AkwF\nbgFuJd+DOv1XjiIDz2OSPlvjeX0xBjiAzAE9QtbNfaSfX2PYkydystFM0inA/RFxSK87j3CS9gd2\niYjmhgxze9yFgMeAVSPirv48tnWGcxw2akmaRDY5PrnnPUcmZW/4Nyj7tqxO3mlf0E/H3r4U1S1I\n5qhuBe7uj2Nb5zlw2Kgk6UiyCO7oUXwXPJ7sv/AkcAVZrHdiPx17R7K4536y79Au4eKNEcNFVWZm\nVotzHGZmVsuIHEBswoQJMWnSpE4nw8xsWPnLX/7yUES0Gq9tFiMycEyaNImpU6d2OhlmZsOKpHt6\n38tFVWZmVpMDh5mZ1eLAYWZmtThwmJlZLQ4cZmZWiwOHmZnV4sBhZma1OHCYmVktDhxmZlbLiOw5\nPjcmHXhxp5MwYt399bd3Oglm1g+c4zAzs1ocOMzMrBYHDjMzq8WBw8zManHgMDOzWhw4zMysFgcO\nMzOrxYHDzMxqceAwM7NaHDjMzKwWBw4zM6vFgcPMzGpx4DAzs1ocOMzMrBYHDjMzq8WBw8zManHg\nMDOzWhw4zMysFgcOMzOrpaOBQ9Ipkh6U9Pc22yXpu5KmS7pF0gaDnUYzM5tVp3McpwLb9LB9W2DV\nsuwLfH8Q0mRmZj3oaOCIiKuBR3rYZUfgp5GuBxaT9OrBSZ2ZmbXS6RxHb5YF7qs8nlHWzUbSvpKm\nSpo6c+bMQUmcmdloNNQDh1qsi1Y7RsRJETE5IiZPnDhxgJNlZjZ6DfXAMQNYvvJ4OeD+DqXFzMwY\n+oHjIuD9pXXVJsDjEfFApxNlZjaajevki0s6G9gSmCBpBvBlYB6AiPgBcAmwHTAdeAb4QGdSamZm\nDR0NHBExpZftAXx0kJJjZmZ9MNSLqszMbIhx4DAzs1ocOMzMrBYHDjMzq8WBw8zManHgMDOzWhw4\nzMysFgcOMzOrxYHDzMxqceAwM7NaHDjMzKwWBw4zM6vFgcPMzGpx4DAzs1ocOMzMrBYHDjMzq6X2\nRE6SJgMbAYsDY1vsEhFx5NwmzMzMhqY+Bw5JiwC/AN4EqIddA3DgMDMboerkOI4G3gxcA/wEuA94\naSASZWZmQ1edwLEj8FfgTRHRNUDpMTOzIa5O5fiiwB8cNMzMRrc6geNfwFIDlRAzMxse6gSOE4Dt\nJS07UIkxM7Ohr04dx6Vk5fifJB0O/AV4rNWOEXFvP6TNzMyGoDqB426yqa2AH/ewX9Q8rpmZDSN1\nfuB/SgYFMzMbxfocOCJirwFMh5mZDRMeq8rMzGqZo8Ah6bWSdpK0x9wmQNI2kqZJmi7pwBbbV5D0\nB0l/k3SLpO3m9jXNzGzO1QocktaTNBW4DTgfOLWybQtJz0javsbxxpLNfLcF1gSmSFqzabdDgPMi\nYn1gF+DEOmk2M7P+1efAIWk14EpgdeA7ZPPcqquBR4D31Hj9jYDpEXFnRLwAnEMObVIVwCLl/0WB\n+2sc38zM+lmdHMeXgfHARhHxGeDG6saICOA6YMMax1yWHCyxYUZZV3UYsLukGcAlwMdbHUjSvpKm\nSpo6c+bMGkkwM7M66gSOtwC/iIg7etjnXmCZGsdsNTx7c5PfKcCpEbEcsB1wuqTZ0h0RJ0XE5IiY\nPHHixBpJMDOzOuoEjsXIHEFvxxtf45gzgOUrj5dj9qKovYHzACLiOmA+YEKN1zAzs35UJ3A8CKzS\nyz5rMWvRU29uBFaVtJKk8WTl90VN+9xL5naQtAYZOFwWZWbWIXUCxxXkIIert9ooaUPyB/6yvh4w\nIl4CPlaecwfZeuo2SUdI2qHsdgDwIUk3A2cDe5X6FDMz64A6Q44cBbwXuFrSYZS6DElrAZuTledP\nAsfUSUBEXEJWelfXHVr5/3bgDXWOaWZmA6fOkCPTJL2bvOs/vqwWcEv5+xjwLo+Ma2Y2stUaxTYi\nfiNpJWBPYBNgSeBx4HrgJxHxSP8n0czMhpLaw59HxGNkB8Dv9H9yzMxsqKvTc/wtfdzv8DlPjpmZ\nDXV1WlX9XNI6Pe0g6WBybCkzMxuh6gSOp4FLJC3XaqOkTwNfAa7tj4SZmdnQVCdwbAcsDFwqadHq\nBkn7A98iO/Rt23/JMzOzoabPgSMibgbeDawG/LL09EbSPmTz3JuBt0XEUwORUDMzGxpqzccREb8n\nx47ajBxs8P3AD4B/AFuVFldmZjaCzUlz3DMkLUv2JH8P8G/gLRHxcH8nzszMhp62gUPSCj0872xg\nYzLn8QFgfHV/9x43Mxu5espx3M3sc2M0EznzX1X0clwzMxvGevqB/ym9Bw4zMxtl2gaOiNhrENNh\nZmbDRK1WVWZmZg4cZmZWS+1K7DLT39uAZYF5W+wSEbH33CbMzMyGpj4HDkkCTgV2J1tTRfnbEJX1\nDhxmZiNUnaKqjwF7AKcDk8kgcRywKXAwOW3sOcBr+jmNZmY2hNQpqtoTmNZobZUZEB6LiOuB6yVd\nRs4E+DvgJ/2cTjMzGyLq5DhWB65oWvdK4ImIvwG/Bj7SD+kyM7Mhqk7gEDm/eMPTwBJN+/wLeO3c\nJsrMzIauOoHjP2RLqoY7gf9r2mdVMqCYmdkIVSdw/JlZA8WlwEaSviRpLUkfBXYk6znMzGyEqjXn\nODBW0krl8TeBe4DDgVuA7wGPAQf2awrNzGxI6XOrqoi4ELiw8vgRSesDHwJWJkfT/WlEPNDfiTQz\ns6FjroY/j4jHgWP6KS1mZjYM9LmoStIpknboZZ93SDqlTgIkbSNpmqTpkloWc0naWdLtkm6TdFad\n45uZWf+qU8exF7BeL/u8juwo2CeSxgInANsCawJTJK3ZtM+qwEHAGyJiLeBTNdJsZmb9rL9Hx50X\neLnG/hsB0yPizoh4gRyyZMemfT4EnBARjwJExIP9klIzM5sjdQNH2xkBJc0LbA78t8bxlgXuqzye\nwax9RQBWA1aT9CdJ10vaps3r7ytpqqSpM2fOrJEEMzOro8fKcUl3Nq36tKQPtNh1LDCRzHH8oMbr\nq8W65uA0juxYuCWwHHCNpLUj4rFZnhRxEnASwOTJkz3lrdkQNunAizudhBHr7q+/fcBfo7dWVWPo\n/iFvDJve6sf+ReBW4PfAV2q8/gxg+crj5YD7W+xzfUS8CNwlaRoZSG6s8TpmZtZPegwcETGp8b+k\nLuDYiDiiH1//RmDV0qnwP8AuwK5N+1wITAFOlTSBLLpqzgmZmdkgqdOP401kJ79+ExEvSfoYcBlZ\n3HVKRNwm6QhgakRcVLZtLel2suL9cxHxcH+mw8zM+q5Oz/GrBiIBEXEJcEnTukMr/wfwmbKYmVmH\n9XdzXDMzG+EcOMzMrBYHDjMzq8WBw8zManHgMDOzWhw4zMysltrzcUhal+yktwawYERsVdZPIgct\n/F1jQEIzMxt5agWO0jHvYLpzKtUxocYAZ5PDnn+vX1JnZmZDTp2JnHYBDgF+R87LcVR1e0TcCUwF\nepzsyczMhrc6dRyfAKYDO0bELcALLfa5gxyA0MzMRqg6gWMd4LIy4VI79wNLzV2SzMxsKKsTOAR0\n9bLPUsBzc54cMzMb6uoEjn8Bm7bbWOYPfyNw29wmyszMhq46geM8YANJB7TZfhCwCnDWXKfKzMyG\nrDrNcY8D3gt8U9LOlKa4ko4BNgMmA9dTpm81M7ORqc58HM9KehPwHWA3cuIlyHkyuoAzgI9FxEv9\nnkozMxsyanUAjIjHgb0kfQbYEFgSeBz4c0TMHID0mZnZEFN7yBGAiHiEnNLVzMxGGQ9yaGZmtdQd\nq2oBYG9yyJHlgHla7BYR8ZZ+SJuZmQ1BfQ4cZVTc3wITyc6A7UQP28zMbJirU1R1HBk0vgxMAuaJ\niDEtlrE9HsXMzIa1OkVVmwA/j4ivDFRizMxs6KuT43gKuGegEmJmZsNDncBxBbDxQCXEzMyGhzqB\n42BgDUkHSuqpctzMzEawOkOO3CnpjcC1wIck3UT2Gm+xa+zdXwk0M7OhpU5z3OWAXwKLl2WlNrsG\n2dfDzMxGoLrNcVcDTgG2IKeIXanF8po6CZC0jaRpkqZLOrCH/d4jKSRNrnN8MzPrX3Wa476ZnDp2\nn/568TL50wnAW4EZwI2SLoqI25v2W5ic8/yG/nptMzObM3VyHGOAW/v59TcCpkfEnWUu83OAHVvs\ndyTwTTwtrZlZx9UJHNcDa/fz6y8L3Fd5PKOse4Wk9YHlI+LXPR1I0r6SpkqaOnOmR3g3MxsodQLH\nF4EtJe3Sj6/fqlnvK2NdSRoDHAu0m662+0kRJ0XE5IiYPHHixH5MopmZVdWp43g72QnwTEn7AX+h\nfXPcI/t4zBnA8pXHywH3Vx4vTOZyrixdR5YGLpK0Q0RMrZF2MzPrJ3UCx2GV/zcvSytB1kn0xY3A\nqpJWAv4D7ALs+sqBcsbBCY3Hkq4EPuugYWbWOXUCx5v6+8Uj4iVJHyNnExwLnBIRt0k6ApgaERf1\n92uamdncqdNz/KqBSEBEXAJc0rTu0Db7bjkQaTAzs77z1LFmZlaLA4eZmdXStqhKUhfQBawZEf8s\nj/syLWxERK25zM3MbPjo6Qf+ajJQPNP02MzMRrG2gaO5ItoV02ZmBr3UcUh6v6R1BysxZmY29PVW\nOX4q8M5BSIeZmQ0TblVlZma1OHCYmVktDhxmZlZLX/pbLCZphToHjYh75zA9ZmY2xPUlcHyyLH0V\nfTyumZkNQ335gX8CeGygE2JmZsNDXwLHsRFxxICnxMzMhgVXjpuZWS0OHGZmVosDh5mZ1eLAYWZm\ntfRYOR4RDixmZjYLBwYzM6vFgcPMzGpx4DAzs1ocOMzMrBYHDjMzq8WBw8zManHgMDOzWhw4zMys\nFgcOMzOrpeOBQ9I2kqZJmi7pwBbbPyPpdkm3SPq9pBU7kU4zM0sdDRySxgInANsCawJTJK3ZtNvf\ngMkRsS5wPvDNwU2lmZlVdTrHsREwPSLujIgXgHOAHas7RMQfIuKZ8vB6YLlBTqOZmVV0OnAsC9xX\neTyjrGtnb+DSVhsk7StpqqSpM2fO7MckmplZVacDh1qsi5Y7SrsDk4GjW22PiJMiYnJETJ44cWI/\nJtHMzKr6Muf4QJoBLF95vBxwf/NOkrYCvghsERHPD1LazMyshU7nOG4EVpW0kqTxwC7ARdUdJK0P\n/BDYISIe7EAazcysoqOBIyJeAj4GXAbcAZwXEbdJOkLSDmW3o4GFgJ9JuknSRW0OZ2Zmg6DTRVVE\nxCXAJU3rDq38v9WgJ8rMzNrqdFGVmZkNMw4cZmZWiwOHmZnV4sBhZma1OHCYmVktDhxmZlaLA4eZ\nmdXiwGFmZrU4cJiZWS0OHGZmVosDh5mZ1dLxsarM5takAy/udBJGrLu//vZOJ8GGIOc4zMysFgcO\nMzOrxYHDzMxqceAwM7NaHDjMzKwWBw4zM6vFgcPMzGpx4DAzs1ocOMzMrBYHDjMzq8WBw8zManHg\nMDOzWhw4zMysFgcOMzOrxYHDzMxqceAwM7NaOh44JG0jaZqk6ZIObLF9Xknnlu03SJo0+Kk0M7OG\njgYOSWOBE4BtgTWBKZLWbNptb+DRiFgFOBb4xuCm0szMqjqd49gImB4Rd0bEC8A5wI5N++wInFb+\nPx94iyQNYhrNzKyi03OOLwvcV3k8A9i43T4R8ZKkx4ElgYeqO0naF9i3PHxK0rQBSfHQM4GmazFU\nyXlFGEbvF/g9K0bTe7ZiX3bqdOBolXOIOdiHiDgJOKk/EjWcSJoaEZM7nQ7rG79fw4/fs9l1uqhq\nBrB85fFywP3t9pE0DlgUeGRQUmdmZrPpdOC4EVhV0kqSxgO7ABc17XMRsGf5/z3AFRExW47DzMwG\nR0eLqkqdxceAy4CxwCkRcZukI4CpEXERcDJwuqTpZE5jl86leEgadcVzw5zfr+HH71kT+ebdzMzq\n6HRRlZmZDTMOHGZmVosDh5mZ1eLAYWZmtThwmJkNEZK2lXR8p9PRGwcOM7MhQNJCwCeAj0h6e6fT\n0xMHDpsjkvzZsVlIGlMdgNSDkfadJEXEU8B3ydEzjpC0QIeT1Za//FaL0tiI6CqPJ0iar9Ppss6S\nNC4iuiIiGp8Hj/AwR34LnAesD3yow2lpyx0Arc8kjakEjOWBz5FD4/8COD4inulk+mzwlTvlKP8v\nDHwBWKts/iNwfkTcU93PWmt8vyRtQE4l8SpgckTc18tTB51zHNZn5UMtSV8B/gFsD8wDvESLEYtt\n5KsEjb2Ae4CPA6sD6wFHAxdLWq/kRFx01YPGTVlE/BX4KTAR+HxHE9WGcxzWZ+WO8jvAzmR2+mfA\nVc5pjG6StgXOBG4GjicHIn1U0v7k5+UmYIuIeLaDyRxSSnHvyy3Wjytj+K0I/Bh4E7BpRPx50BPZ\nA+c4rI5NgCnkTIyfi4hLHTRGjzKtQfO6+YFPlYefjoifl6AxHpgG3AVMBnYdvJQOXY0GBI2gIWkd\nSatKWhpy4Nfy9x7gVOB54LChlltz4LBZlHng29kcmJcst35Y0jySFpY0SdK+kt4uaZVBSqoNsnIn\nPF7SMpXVq5Cfi59HxE2lKHND4AjgbHKOnUMi4uQOJHlIKQGj0YDg9ZKuAC4HbgCulfRBSQtWnnIR\n8HNgG3JKiSGj0zMA2hDRyDpX7oQWBx4v9RqNbPUtwHPAXpJeCywFbAi8ke6bkL9K2j8ibuzAadgA\nkrQOWRx1Ht3TG4whbyb+KWkCsDuwN1lBfjbw8Yh4pDx//oh4drRWlJeAsRDwZbK/xr/IVlQPkt+h\nHwFLSTomIl6MiCclnUYWVx0m6bKIeKJT6a9yjsMAqASM90q6AbgSuEbSpsD4stsN5NwE7wK+Sn74\nxwEHAfsD3wc2AD49qIm3wfJo45/KnfF44Fny/T8N+DZZvLJxROzWCBrFFElLjJag0Vy0V2l1NoWc\nZ2jfiNgjIg4A3kEGkN3IRicARMTvgTOANYCPDlLSexcRXkbpAoyt/D+e/OF/EbiTzF10AXeTH/Dq\n8zYE3gasWx6PKX8XAp4ks9fzdfr8vPT6/k8EFmhaN66H/ZcgZ+28oWn9n8pn5WFg+xbPWwQ4gZyI\n7U2dPu9Buraq/L96+bsS8B/ge8Dile3vJzv9vVSu4y+AV1W2rwP8BZgJvKbT5xYRDhyjfSlf6s2B\nLYHpwJFkc8rxZM7iSbLp7fpl/7FtjjOW7NfRBRzQ6fPy0uv7vkV5r05os33+5vcbmB+4pjxvtcr6\nrcu6GS2OsyGZS/0fmRtZpNPnPoDXVI2bqPJ4tcr1mlDWbVbZvgZwRdl+OVn8dzFZHLx/07E/VvY7\nv9PnGRGu4xjNJC0JXEje0VwO/BM4IiJeLLv8ojQL/BawH/DhaN2EcDKZA/kQcDVZBm5D25PkjcLS\njboHAElvIvsQ/Jr88WoUYY6LrJ+4FtgYWJ78vBARv5X0A2A/SdOA08lc60bAm8kf0JOAw2OIlNEP\nhMhf+CjD8SwMHEPmwn9A5tYeiohrACRtQubwlwYOAc6LiOmSXiQD8XslXR0Rt5XD/5K8wbt8MM+p\nrU5HLi+dW8jOe/uRRQhdlCIpMrdRzWr/nfyheXt5PA5YkQwU55ftXcCvgBU6fV5e+vz+r970WMBm\nwH/L+3k8sE7jPS9/P1S2va88nrf8Xax8lv5VtneVz9W1zHqXrYE8p0G+fqIpBw7sSxbVHgo8DezE\nrLmQRt+5E8m6ob2btu9Vrt1M4MimY48ZiPOYk8WV4yNcu+a1ZXiDF8lWHb8qqycCRMQLERGV5x4A\nLAjsL2nhyLbmy5Ef8g3JepDtImL7iLh3wE7GamnV9r8x1hhAREyTtJCkn0h6W6RryOafZwEfAU6V\ntEp5zyHrMSBzEkTE86WV1GMR8QOyCOyNwBuAbSJi04i4przumCi/gMOVpLdKel/jXKI7R6bSp+V1\nZLB4H/D9iLggsmXiGHilZdVYYAfgVuCnUXqMF8uRxVvzA5+QtHZjQ+M4Q6JPR6cjl5eBWZi94vvt\nZBHDmi323ZFs0XEpbXIMZFa5miuZB1gVWKPT5+ql18/CO4BFaXG3T/YP6CLHlZq3+vkBfli2/Q3Y\ntaxflGxddS5NOdMeXr9lvdhwW8jK7WfIHPaqZd1aZLHe28rj9emut/huWaem40wErgLuBZYv6xYk\nK8kfJ3Mhbwbe0elzbnstOp0ALwP8BsOHyTGEniof5qfI5rPVVhtLki09XgD2pNKyhu4WU6sCL5M9\ngYdEyw4vvb7344FvlPd9l8r6Pci7Ycg72+PLPvuUdWPL34XIsaceL9s/CLyGbJb9r06fXweu5wLk\n2FEvko1ITirX5SFgp7LPfGTT5OfJ+sOly/rm4HFIOc6VZF3IaWQR4VXAip0+116vRacT4GWA3lhY\nmex5+gxwGXAY3eWvXcAxTfv5ujtuAAAe00lEQVS/gazsvAF4bdO2RvD4PvDnxpfBy9BfyNzkdLJS\ndSuy8UIX2ax2qbLPpmTdxD3AxLKuWse1EzCDLLM/imwa+iCwYafPrwPXcwngvnKT9XT50X9D083W\nymQu5CFg66bnN75Ly5Xg0VWO9SjZAXDRTp9jn65DpxPgZQDe1MxBnExmhQ9i1qaTk8oH/hGyDLqx\nfn6yc1IX8EVK+36yArBRoTdkKue89PoZqP7wH013hfU0suPmGk37f6ls/3qb421ags6zlWNt0enz\nHOhryKwV1wsC55Rzfxn4DZXcdyUoiGzK/gTZee/VPbzGysDrgZUr64Z80V7HE+BlLt68NuXLZAXd\n9eSgc6/sS84u1mix0UWOYlp93prlx2E6OSJnx8/Ry1x9PsaQTThfJotOHiN7LVfrvxrFUquSlbLP\nAmu3+owBE8h6sBfIAfjGd/ocB/DaVXMQi9BdF7Ez2Wjg0pJL2KnN8yeWHMSz5ACPvd50lfdrWNyc\ndTwBXubgTcsPWKuKzuqXfM3K/zuSxRDPkm3KJ5PNJLuADzUdd4+y/jRgoU6fq5c+fybU9P437n6X\nLe/5D8gy9aOBeZo/L+XxPiUozNbJrBJglu/pDnq4L03XUGRx0g1k7/j3VLZtXHIUv6bkOlpcz83K\n9+4qKrn+kbB0PAFear5hs94trlHugLZk1sruavHSDmSZ7K1kq41Gufa7S4D4B6Vcu6xfAfgKo7D8\nerguTXfHs+UCyg3BsmRl7RM0DftR+awsQXbe7KL02enhNccwDIpU5uKabld+9B8nW0l9i2xB1QjI\nC5I94V8kB3KsXpfG9VyoBJ4XyKLA+Tt9Xv12fTqdAC9z8KblF/xMsq7iufJFvx84qrLPGLJJ5YVk\nEcWmTcf4DDk2zlPAcZ0+Jy9z9Dmolr+PJfvbnE5OAPQRmsYLI/sWPAJcACxRWV+90Xg7OZ7SVJrG\nsRotC5kjv4scCXhX2jQGKTdud5ZrNblpW6PD5DrlWOcDC3b63PrtGnU6AV5qvmFZf3ET2arlO2Tz\n2e3J7HAXOcFSY9+lyx3TH1sc5yflTurFchc6YosfRvpCjqj6AFmP8V+yk15XeY+rlbdLkkVWXeUH\ncbYcAzkqwMlln606fW4duJYi6ya6aNMiqulafbLs+83K+s3JJrkTyw3cKp0+r36/Tp1OgJeab1gG\ni5fJIZYXqazfnGxO20X23hWZVf4jWRy1SdlvBXI4hCfK3dAbgZU6fV5e+vTeN5ehN+Z2eJBs4bMX\nWSQ1D92tpE5ses6WZNPbvwKTyrrFyNzI5PJ4bVp0FB0pC5XWTy22LUfm3v/evH+bYy1dbsCeKUH5\na2QupIvZc/kjpmiv4wnwUuPNysHingDOrqxbrOQ4zi0f1hmUVjFkB7D9yTLWO8ns8h/Lh/wsYPFW\nXx4vQ29pkzvYurzf51LGlCrrlynvdReZA9mxsm1e4ODymTiDHHX1e2Xf65qO37IRxnBd6EOrJbK5\n+oPAJfSxHqfcgD1E5vieJUdZWLXT5zuQi0fHHUIaE9W3WN+YMe1V5F3mtWW8m43JSu4PkkHiMxFx\nXOU5L0g6nazI+xTZFv8x4AsR8b1BOSnrF9E9JtIxwL0R8V2yjuuMiDiwsZ+krwIHkgHlLLJIan9J\nl0fE05FjS51N/kDuQw7l/QJZ1HJg02tWx1Aa1srYUl3l/0ajkkZgvTwi7iq7jieLb99A1kk82fTc\nMVFmxSSD0IsRcWuZLncF4MmI+GvZtzFz5sjT6cjlpWURxObAesw+yc7rybuaH5EjkTaKpn5EU8Ub\ns3fwWohsFTJvf6ffy4B9LqqV36+mewykn1OKKekenfb/6O6HcSo51tE4ssd4F/CxpmOPJ3OqH6BS\nv0UPEzkN94Xs5Po9uhuFPF+uzb/J3vGNBgKNTn6HNd6HpvdiHrIH/V49vNaIKZZqeX6dToCXypsB\nb6F7iPLHyUldNqhsX51sWtuYKewPwOtaHGcb4A66Z+gbMcUNo20hi0HeQo45No3MJcw2ECVZof0U\nWQxVDQQn0j3EyEpl3Twtnj92JH9OyCLd08li2hPJ1mNLkDn2f5MjPO9c9l2L7t7xb2bWwR/XIOsy\nZpK5tRF7zXq8np1OwGhd6K6ga/xtjBd0bflgNtrT3wEsVnleo1XM71occ2FyZM17gd8By3T6PL3M\n1WdkEpmDuInszX90m/22KJ+Jc1psO5/s4TxbRXllnxH/40d2gm10gK1+nxYl+y11kdMlL1nWH1jW\nPUpObPUecmDDq0vw+V71OKNt6XgCRttC+6lXv0vmNjaqrGt8oI+nFEWRrWb+UdZ/nsyFjCMrSo8j\np+j8KyN8HKGRtNCmlQ850urh5b1+ju5WT/M07bcRWS7/TSodAMvd9H/J8vzHyBn4On6+HbrG55Ug\n0OgAuxCZMz+jBJS7mXXstnnIDrM30537eA64nUpjg9G6NMr0bJBJ2o0ckuBuclypb5Bzdf+xURku\naRJwLLAt2ZP1ysiKuXeQHfi2JD/Mz5TDLkG23T8gIh4bvLOxOVGZ3KdtJbSkVcnhXzYB9o6In7TY\nZ22yGGYBclDLf5D1ZPuQlbVvkjRfRDzX/2fRee0alZRtIus2fkPedK1DDiy4K9moZHFypr0jK88Z\nHxEvlP+XJm/O5gNejojLK/uN3MrvXjhwDILqB1vSa8jy6C0quzxKljG/PSL+VGlFhaR3keP+3wjs\nHhEPl/ULk9nnTci7oSfJFja3DNJp2VxoaqmzGlleDpljvCIi/lW2jScHJvwJeXf8qYh4pOkzMo7s\nCHo0WZb/OFlseTs5x8afyw+oYMS1lqpeh+3InMTDwDWNH/+y7dfkzdcPyBu2tchK8I83vlNlv2WB\nxSPi7z28ZttANWp0OsszWhbKWFLAZ8khCD5BDm2wA/lBfwl4a2X/RvHFonRPtLMXo6A8erQsZMum\nxnhHT9E9fMy95E1BY2DBpcnRWB+kqZik+nkgK3KPJnMoH+j0+fXTNWo5mGfTeW9CzhHSVVn+DLy3\nss+elW1/A9Zrcdy1yfGpjmAEty7rl/el0wkYDQs5gU4X2Urqd8Anm7Z/hGxLf3HT+kaOcDOy+OEm\n2kzt6mV4LWSO4GSyfP2HZNPYxclK3DvI1nNTyr5jyTqsZ4Gf0T3Ed7th9atNR4flDyCzj8M1psX6\ncWRnx+tKoPgyOVnZ9+me7XKbEmheS7ZCfBp4V9NrzU82x72aLDp+60Cf33BfOp6A0bCQ021OKx/a\n++ieTnJ8+bsI3W3H31nWVQeeG0uWXXcBX2eYjNnvpcfPxDZk3dQpzDrg4CJ0DxdyBzChrF+QLGZ5\njspQ+D0cf1h+RprTXX7QD24+5/J9OI0ctfZ/wGZN2w8t37cb6B5J4d10z0vyebKv1HvIhikzyNzG\n+zt9DYbD0vEEDOeF7Cna4x1d5U7pE+VLP40sh20Ehcbft5UvwN+Ztd14Y/u6ZF3HRv15Dl4G9PPR\ntliR7KT3FCUHSVZsv7Wsf5ocoXaHpuesV37grqT03+npNYbbwqzFT7uSRUqP0J1bX6Zsqw7/fhs5\nEkLjeY0OkROAE8o+B1a+R++neyypF+luXPIzZu3/MmKu64C8V51OwHBcypf8Z2Sfi6V6+YFoBI75\n6O7Fu2NZN65p32+X7Z8tj/3hHYYL7ZtcNyqo5yOLLO8lcxhrkk2vHyg/Zkc0Pa8x8dJ4unOeh7R7\nneG8kC2eLivneDWZc3gd2Xu72tR4c7rrNQ4v65pzK9uRY7vd0LR+CWB34EPkCAzrVt87f+/68D51\nOgHDcSHnE+4CPtLDPq1mY9uerMu4tbpfZXtjyPRHcF3GsF+Ad5Yfpq1bbGvcMf+gvOdd5WbkVU37\nvbrph20lsm/H4p0+vwG4Xq8mcxbPk/UVq1W2NefQF6a7k97ZjevR/L0jcyRdlNF+m4NL9fgjMRAP\n1DIGmxNTyCzu79vtEI1PozSBzDYTEb8iP+RrSfpk2fWVZpkRcTP549EY8daGIUlrSroG+AU5vMVv\nJB1fBtdrOB8IsjJ3HLBxRLw3Ih6sHGc1cjTj3UqzXCLiroj4ckQ8WprYDnuV89iJ7LP0nYg4PCL+\nWbaPb3yfKn+fJEewvY4cw22dxnZJY0ofiy6y3uJRcogQotIUufG6jSa9MUr7ZMwJB44+anTWkvQq\nstnj9WQLjHb7LyRpW3IAwgMkTSybjiXrMg6TtGhEvFw+6I334kdkD+ETBuhUrB+VUVJp+hH/EnlH\nfAgZGM4nW859UtJ8ZZ/byOKqF4CvRsSNlWPOJ2l7srXVPGTHzxcqx5+l/8JwVzmPt5W/v4X8zjVG\neS6PJ0iaV9KiZb87yNkOlwE+XDpLEhFd5Xs1mRxBejpZb9TydUfKdRxUnc7yDNWF/MKeT/cImY2p\nILemh2IqMsu7MTn8w4Nl3/2a9mkMI/Hd8nhYtoAZzQtNxRqUaVrJUWpfAHaqbBtPd/3WvpV1O5A/\naE+SLYfWJ4tBjyPrP2aQvcU7fr6DcD3HkIHy5cZ3i+7JyP6PLNL7AzlN6w1kh8kFyNz8z8u1vZSs\nI1mRLCa8guwftWenz2+kLR1PwFBdyOaPjQ5DjeazKh/uLipTcjY9b2VysMIusqnlQpVt1Q5djYq9\n2Ua39TJ8FrI55zVlOZucGOn0yvZGxfZr6e58tnxl+/vIO+Ku8iP3PNnK54Km/UZ8hW25lg+TjQRO\nK8Hi6sr38AmyyKmLrAf8fHnetmSn2kYT5kdL4H24+abNSz+9V51OwFBeyLF+usihPCCnlbyr3PWM\nb/dlJnMb61cej6O7Uq9REf7Rcge1YqfP00ufPw9jq/+TPfqfJ8vR7yJbRHVRZmis3Cg0/h5Xtn+l\n6biLk81PG618Nmh6nREfNMq5zgN8gcx1NILF7eQ4XB8mcxerkrmzmWSjgtXIlmlHl/2/BrwDeC+w\ncOXYztX34+KxqnpQ6h0eJcurX0cGixuBQyPiKy32n2XQs1aD2I2ksunRSNIiZB3Xw2QP5YvIu+OH\ngD2AY8j5HbaLiH9XPwOlfuMBsmHFDhFxo6R5IuLFNq81KgfRk7QemUO7i7yuMyPiicr2ZclgshGw\nZURMlbQpOfz5f8nxuf5R9h1HDk7o71w/cuV4D8oP/rbl4WlkayrIqVvnq+5bBq17uelxVzQNKOcP\n8PAlaX6yh/95ZMX3Q+RNxLTIgfKOJ4syVyXrKmh8BsrAeM+Rd9RLkZXlVINGtZVP2TbqggZARNwU\nEedExA0R8e+IeEJpnrL9P+QwIQuUv5BFgCeRLax2lrRQWe+gMQCc4+gDSX8iP5BPkZV1L5NDh9wK\n/JpsMjkjsomgDXM95QpLa6czyFzopyPiO5LmjYjny/blyfqr/5JTi/61OhJu2eductSBN0TEdQN8\nOsNWdX7v6J5zfQw52OePgTMjYo/K/quTwWMZ4IMRcU0Hkj0qOMfRN+8rf8eTY0VdQFaUN5pM3grc\nLukXkvaQtLqk5StNbG2YKDmDnu6mriaHBYHMWdAIGuX/+8j5qNcGdq/8+KkUm0BOrPROB42eRXf/\npkbQWJUcXfpwshL8pLJ+bHnKdPL7uDKwT5l6wAaAcxx9JOlY4JPAQRHxjdKWfB1yMqXXlf9Xqzxl\nKjmj2CODnVarr2l+jHnJ+orx5IB4N0fEbZV9JwO/BO4n72xvbZoXYgHgT2RP6D0j4rJ2uRjXebVX\n6pMWBpYnmy5vQn7friVbS802Z4ak5chGBhdGxN8GL7WjiwNHH5U6jafJnMYaETGtaftCZDv8yWRV\nxnGDn0rrjaTFIuKxdhXPkvYmc5WLkK18IIcz/yRwUUQ8WALDAeSd7xeBYyLixabgsT0ZXH4D7BYR\njw74yY0wkl5Pjn67CVmfdDfZq/zMsr1RF+QfsUHmwFGDpCnAmcAFEfHuxg+FPCPYkFZ+YJal9LeI\niPe32A459tGXyR7d55PNPbcnK7IXAo6LiEPLc15DFlnOS3bqu7rF615B1oft7MBRXyna24ccmuWu\niPhtZduobHE2VDhw1FB+YO4nW8VsFRFXOGgMH5Ia87C/OyJ+31Q8tSw5XPlTZfudZf04crSAk8kg\nsWtE/Ka08JlC1necCHwpcvyo6jEXjYjHB+8MRz4HjKHBlbc1lCzxNuXh2WWdg8YQV6mU3pMsgvqE\ncuC8rkoDhs3JStULKkFjbES8FBGXkB3LFqMMOFia0V5KDrT3buBNMGufnUbQqLy+zSUHjaHBgaOm\nyBFsLwd+1xiErdNpsp41gntE/JIcv2h7YLem3ZYrf/8Hr7Suqv5IXQz8k5xQa9lyvJnkoJVLkYPs\nLdnT65uNFA4cc2bbiNi9dO5yWd8QVZrANjrVNe76P1H+fkTSqys5hDvL33dAyx/7x8liyrXJoUUa\nbiA79R1aOgGajXgOHHPA2eXhIYpS7/BSacxwOzl43v+RQ543/JYcnHJj5XD4SBpbGTLkYXLcqCfI\nuo7GazwVEUdHxA3Ofdpo4cBhI0qlM1jj8QHAdyUtVMkdfp5sWr2PpPXLuufJsacmAF+QtHhEvFyp\n6N4W2JQssrqrxeu6P4aNGg4cNiKUUqlXxguT9CpJK5NFT/uTA+I1Ovo9RY6wuiw5SjGRkwWdQVZ2\nbw6cLWlHSetJ2h/4Kjmw4cnRNP5Yeb6Dho0abo5rI4qktckhtl9NDoD3BFksdQ7wqZh1atbbgdcA\n742c1hdJSwFnAW8ge44/U44zjeytPFt/DbPRxoHDRozSQfPH5Mx555NzNkwgcxeQzXHPhFeGOd+a\n7Nn9W+BdEfFMOc4iwBuBDcgRWG+OiHMrr+NiKRvVHDhsRCjDgFxKjhm2O3BZpdhqX3LgwXvJAHFX\n5XkXkcVZH42I7/cUFNzZ0yy5jsOGlRaV342WTCsBm5FDbV8SES+X3t2Qk/4cTw5GuXsZxLDhU+Xv\nvpJWKq2wZmkdVRkTyUHDDAcOGyYqP94vS3qNpB1KRXcjd7By+TtvY//KwIPPkq2h7iVHTl2n7DOm\n9BL/LhlU3l1eY5Ych4ulzGbloRBsSGsUD1VGnV2YrJOYB3gQuL7sehvZxHZ1SStExL3VYqeI+LOk\nacBbgfdL+md0T0f6OWB6RBw/iKdmNmw5x2FDWqN4SNL7JR0NHEROnLUksIO6J+t5jhz9di1yaHtK\nsdPYSpHVNHKI9H3Jobob41G92Aga8uRbZr3yl8SGNElrSPoj8CMyIGxF1mcsALwT2KLsej9ZHDU/\nOW7UhpBFW6XIahVy5r0LyOFD9ivPi8prqVUfDTOblYuqbNDVHBr7EGBjcp6MsyPiLkkrAIeSc0/v\nLOlvEfEfSZeSk2l9EFhQ0keBB4D1yro7gMOAicA7S2X4Ky2sXJdh1jcOHDboKs1kN4mI68v/szWD\nVU7ROgW4JCK+VtnvXklHAYsCO5Ej3p4aEXdKOpIsxtoR+Bs52u0C5MyNB0fEdEn/IHMuy9Bi+BAz\n65mLqmzQSdpQ0tPAtZKOkDShzd3+wkAXcGN5XnVwwX+TEyi9DOwqaa2y/h5gV+C9ZGe/G8me4GtW\nKr9XJAPJfwfi/MxGOuc4rBO2IesiniaLotaX9PGIuBtmyX1MJG9u1gGIiOebjvMv4M/A64F3lJZS\nLwLPRcTPgZ9LWjAini7HfTWwN7Ad8OMSfMysJuc4bNBUOtbdRFZKnwz8EtgW+IWk7Zue8mvgEeAN\njcruaquniJhRjrMgWVG+UVkflX2eLgMevhM4EvgS2SrrpH4/QbNRwoHDBk3lB/1uchjzZ8jhQb5I\nVmCfLWlXcnpXyj4nkzPs7V2O0dXUs/slckbGjYGtJc3X2FBGzJ0M3EO2ytoZOAHYOCKmDsQ5mo0G\nHqvKBp2k1cmZ8+6JiNeVdZ8GPkY2tT0F2LcEidWAi4DVyHk0vlX6ZywHfAD4CLAPcCAwH/Bm4KlK\nh8F5gM+SHQZPK3UgZjYXHDisIyRNJVs/bRMR00pOYR3gNOC1wLnAiRFxTWUU2wCuJltCrQBsSI6G\newQ5bMgewOoR8a+m16rT/NfMeuGiKht0JUj8C1iaLK4CeD4ibiRzHY+TraLOkfTGiPgtWQ9yETnc\n+buA1YEjIuKAiHic/Cx3kbmOWThomPUvBw4bdBHxHN1zd7+5rAtJnyArywP4OzkZ07mSDoqIyyJi\nJ3LWvm3InMW34JVpXd8FXAW4pZTZAHPgsEFVGRb9qvL3ZUnbSroDOI5s8fRJsmPfh8hmu1+VdLKk\npSLiwYi4PiKeKaPk7gN8g6wkP74xGZOZDRz347BBVSk2eqH8PQZ4FVlvcShwbqWO4mRJ/yMrty+I\niP/BK9PDHgwsR9Zz/A+YEhGXDM5ZmI1urhy3jpD0WuB2shPg2cDJEXFDZXvbCu3y3AuBR4HzIuLY\nQUiymRUOHDboSj+MxYDfAwsBb4mI+8q2Ma1GqG0Eksb2MtDhQy6aMht8LqqyQVeZnnUeYJXyt8dc\nRmN9I6hExL2DlFwza+LKceuIiHgEuK483Lisc7NZs2HAgcM66aXy9z8dTYWZ1eI6DuuYMpzI0xHh\nwGE2jDhwWMd5SBCz4cWBw8zManEdh5mZ1eLAYWZmtThwmJlZLQ4cZmZWiwOHmZnV4sBhI4qkwySF\npC07nZZmkk4taZtU4zlbluccNmAJM6vJgcOGDUlfLD+iUeYtH/YkTSrnc2qn02LWVw4cNiyUQRH3\nJmcHhJzkabg5CFgDD7Fiw5wDhw0XWwMrAaeREzftKWl8Z5NUT0Q8EBH/iIgXO50Ws7nhwGHDRSOH\n8SPgTGACOb1sn0naTdJfJT0r6UFJp0taRtKVkmYbQkHSGEn7SbpR0lOSni7/7y9ptu9OKXK6UtLS\nkn4s6T+SXpa0V9k+Sx1Hqbe4qzx9z0oxXDSe03T89SRdLOkxSc9IukrSpi32e6WeR9IUSX8p+98v\n6duS5i37vbmk9wlJj5brsWSL460r6WxJd0t6XtLMch2PkzRPjbfARgjPx2FDnqSlgB2Af0bEtZKe\nAD4D7Auc28djfA74Jjlr4GnA48BbgT+V/1s5HdgVuA/4MVlMthNwIvBGYLcWz1kCuB54CvgF0EXm\nkFq5kpzQ6pPAzeSshg03Ne07Gfg8ORT9j4EVgHcDv5e0XkRMa3H8jwPbluNeSebaPg0sIemXwDnA\nxcBJwKbA7mRA3rZxAEnrAjeUc7+IDHSLkPOofAQ4BHAOarSJCC9ehvQCHEj+cB1UWfcX8kd5laZ9\nDyv7bllZ9xryx20msHxlvchpayO/CrMcZ0pZ/1dgocr6BYGpZduuTc+JsvwUGNfiPE4t2ydV1k0q\n605tc+5bVo67V9O2D5f1J7a5Bo8Da1TWzwvcBrwMPAxsUdk2Bvhded56lfXfKut2bJG2xYExnf58\neBn8xUVVNqSVSvF9yCDx08qmU8kf/n36cJhdydz196JMUQslUmRQajUy7wfL3wMj4qnKc54GvlAe\ntnrtF4DPRsRLLbbNjT9FxKlN604h5zTZqM1zvhsRdzQeRMTzZA5tDHBxRFxV2dYFnFEevq7FsZ5t\nXhERj0aLaX5t5HPgsKHuzcDKwO9i1nk7ziJ/pPfqQzn7+uXvH5s3RMQ9ZFFUsw3IYHVli21XkcFm\n/Rbb7o6IB3tJz5yY2rwispL9f+Sdf5+eA9xf/v6lxbbG9V2usu5c8lwvlPRTSe+XtHLfkmwjlQOH\nDXX7lr+nVldGxMPAr4ClgB17Ocai5W+7uoZW6xcFHomIF5o3lNzEQ5XjVv23l7TMqcfarH8JGNtm\nW6u6m5f6sO2VQBwRfwY2A64A3kPWD02X9A9JU3pLtI1MDhw2ZEmaCLyzPDy7qdVRkJXD0B1c2nmi\n/F2qzfZW6x8nK5Fny81IGkdWIj8x27O6+5mMGBFxXUS8g8zZvAE4krxmZ0naqqOJs45wqyobyvYE\nxpPFKs2tjBp2ALaStFJE3NVmn7+RraHeSN45v0LSisDybZ7zFmBz4PdN2zYn7/L/2odz6E2jfqVd\nrmHIKHUk1wLXSvoXWee0I3B5RxNmg845DhvKGpXPH4mIfVotwA/pvZL8LLIY5uOSXgkSpeL9KFr/\naJ9S/h4laYHKcxYAvl4enjxHZzWrR8lcygr9cKx+J2kzSa2K5Bq5tGcGMz02NDjHYUNSGaRwdeDW\nUs7ezsnAF4EPSPpyqx0i4t+SDgW+Btws6Vy6+3EsQfahWLfpOWdJ2hHYGbhN0oXkD/w7yR7s50XE\nmXNxio3XeUrSDcBmks4E/knmQi6KiFvm9vj94ABga0lXAneS/VPWIvt6PEr2AbFRxoHDhqpGT/Ef\n97RTRNwt6XIyCGzfw35HSZpBdhz8APAkcBnZqe63tK6vmEK2oPog2WcC4A6yb8P3+3wmvdsDOBbY\nprymgBnAUAgcJ5IBYmOyfmMcmbYTgW+VVmk2yiibspuNTpIWIVtV3RQRr+90esyGA9dx2KggaWJz\nC6nSOupbwHzABR1JmNkw5ByHjQqS9gOOIFsA3UfWbWwOrEa22No0ImbrHW1ms3Mdh40WN5A9xzcH\nGiPA3gV8FfiGg4ZZ3znHYWZmtbiOw8zManHgMDOzWhw4zMysFgcOMzOrxYHDzMxq+X80MbS57ONr\nAgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "def plot_bar_x():\n",
    "    index = np.arange(len(algorithm))\n",
    "    plt.bar(index, times)\n",
    "    plt.xlabel('Algorithms', fontsize=20)\n",
    "    plt.ylabel('Time taken', fontsize=20)\n",
    "    plt.xticks(index, algorithm, fontsize=20, rotation=30)\n",
    "    plt.title('Time taken by Clustering algorithms')\n",
    "    plt.show()\n",
    "plot_bar_x()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "idea = {'Idea':corpus, 'Cluster':clusters} #Creating dict having doc with the corresponding cluster number.\n",
    "frame = pd.DataFrame(idea,index=[clusters], columns=['Idea','Cluster']) # Converting it into a dataframe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "                                                Idea  Cluster\n",
      "1  cricket bat ball game played two team eleven p...        1\n",
      "1  phase play called inning one team bat attempti...        1\n",
      "1  team one two inning apiece and first inning en...        1\n",
      "1  match begin two team captain meet pitch toss c...        1\n",
      "1  two batsman eleven fielder enter field play be...        1\n",
      "1  common dismissal cricket match bowled bowler h...        1\n",
      "1  run scored two main method either hitting ball...        1\n",
      "1             main objective team score run opponent        1\n",
      "1  team batting last scored fewer run opponent sa...        1\n",
      "1  role striker batsman prevent ball hitting stum...        1\n",
      "2  artificial intelligence intelligence exhibited...        2\n",
      "2  field ai research defines study intelligent ag...        2\n",
      "2  overall research goal artificial intelligence ...        2\n",
      "2  natural language processing give machine abili...        2\n",
      "0  ai researcher developed sophisticated mathemat...        0\n",
      "2  intelligent agent system perceives environment...        2\n",
      "2  ai technique become essential part technology ...        2\n",
      "2  recent advancement ai specifically machine lea...        2\n",
      "2  ai research revived commercial success expert ...        2\n",
      "2  advanced statistical technique loosely known d...        2\n",
      "0  compound pure chemical substance composed one ...        0\n",
      "0  since property element mostly determined elect...        0\n",
      "0  property inertness noble gas make suitable che...        0\n",
      "0  atom also smallest entity envisaged retain che...        0\n",
      "2  nucleus made positively charged proton uncharg...        2\n",
      "0  atom basic unit chemistry consists dense core ...        0\n",
      "0  chemical reaction transformation substance one...        0\n",
      "0  chemistry sometimes called central science bri...        0\n",
      "0  chemistry includes topic property individual a...        0\n",
      "0  chemistry branch physical science study compos...        0\n",
      "\n",
      "\n",
      "2    10\n",
      "1    10\n",
      "0    10\n",
      "Name: Cluster, dtype: int64\n"
     ]
    }
   ],
   "source": [
    "print(\"\\n\")\n",
    "print(frame) #Print the doc with the labeled cluster number.\n",
    "print(\"\\n\")\n",
    "print(frame['Cluster'].value_counts()) #Print the counts of doc belonging to each cluster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [14, 20, 21, 22, 23, 25, 26, 27, 28, 29], 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 2: [10, 11, 12, 13, 15, 16, 17, 18, 19, 24]}\n"
     ]
    }
   ],
   "source": [
    "result = {}\n",
    "\n",
    "for i in range(len(clusters)):\n",
    "    if clusters[i] in result:\n",
    "        result[clusters[i]].append(i)\n",
    "    else:\n",
    "        temp = [i]\n",
    "        result[clusters[i]] = temp\n",
    "        \n",
    "print(result)\n",
    "\n",
    "# =================================\n",
    "# Call DCI_Closed for each cluster\n",
    "# =================================\n",
    "# d1 -> word1, word2, word3\n",
    "# d2 -> word2, word3\n",
    "# ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['2', '4']\n",
      "['1', '2', '3', '4']\n",
      "['1', '2', '3']\n",
      "['3']\n",
      "{1: [2, 3], 2: [1, 2, 3], 3: [2, 3, 4], 4: [1, 2]}\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# ===========================================================\n",
    "#       Step 1 : Create vertical database into memory\n",
    "# ===========================================================\n",
    "file = open(\"database.txt\", \"r\")\n",
    "verticalDatabase = open(\"vdb.txt\", \"w+\")\n",
    "\n",
    "# Use a dictionary for HashMap<Integer, Set<Integer>>\n",
    "# We mapped items to transactions they appear in\n",
    "\n",
    "maxItemId = 0\n",
    "tidCount = 1\n",
    "database = {}      # Dictionary for hashing (int -> list(int))\n",
    "\n",
    "for line in file:\n",
    "    items = line.split()\n",
    "    print(items)\n",
    "    for i in items:\n",
    "        item = int(i)\n",
    "        maxItemId = max(maxItemId, item)\n",
    "        if item in database:\n",
    "            database[item].append(tidCount)\n",
    "        else:\n",
    "            database.update({item: [tidCount]})\n",
    "    tidCount += 1\n",
    "    \n",
    "print(database)\n",
    "print(maxItemId)\n",
    "file.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 293,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('cricket', 0.5546549432332832),\n",
       " ('bat', 0.27741674773179725),\n",
       " ('ball', 0.2595098011369835),\n",
       " ('game', 0.36741142246757896),\n",
       " ('played', 0.36741142246757896),\n",
       " ('team', 0.23125473575543234),\n",
       " ('player', 0.36741142246757896),\n",
       " ('field', 0.2993330791115057)]"
      ]
     },
     "execution_count": 293,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ========================================================\n",
    "# Calculating TF-IDF values of all words in each sentence\n",
    "# ========================================================\n",
    "from sklearn.feature_extraction.text import TfidfTransformer\n",
    " \n",
    "docs = idea['Idea']\n",
    "tf = TfidfVectorizer(input=docs, analyzer='word', min_df = 0, stop_words = 'english', sublinear_tf=True)\n",
    "tfidf_matrix =  tf.fit_transform(corpus)\n",
    "feature_names = tf.get_feature_names()\n",
    "\n",
    "tfidf_values = []\n",
    "for doc in range(0, len(docs)):\n",
    "    feature_index = tfidf_matrix[doc,:].nonzero()[1]\n",
    "    tfidf_scores = zip(feature_index, [tfidf_matrix[doc, x] for x in feature_index])\n",
    "    currSentence = []\n",
    "    for w, s in [(feature_names[i], s) for (i, s) in tfidf_scores]:\n",
    "        currSentence.append((w, s))\n",
    "    tfidf_values.append(currSentence)\n",
    "\n",
    "# tfidf_values = list of list of tuples of the form (word, TF-IDF score)\n",
    "tfidf_values[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "dict"
      ]
     },
     "execution_count": 315,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ========================================================\n",
    "#         Run DCI_Closed for every cluster\n",
    "# ========================================================\n",
    "\n",
    "# Store vertical database for each cluster, access through hD[i]\n",
    "horizontalDatabase = []\n",
    "\n",
    "# Iterating through all clusters\n",
    "for i in range(0, len(result)):\n",
    "    currentCluster = {}\n",
    "    for j in range(0, len(result[i])):   # j = document number\n",
    "        document = result[i][j]          # document id  \n",
    "        for k in range(0, len(tfidf_values[document])):\n",
    "            if tfidf_values[document][k][0] in currentCluster:\n",
    "                currentCluster[tfidf_values[document][k][0]].append(document)\n",
    "            else:\n",
    "                temp = [document]\n",
    "                currentCluster[tfidf_values[document][k][0]] = temp    \n",
    "    horizontalDatabase.append(currentCluster)\n",
    "print(len(horizontalDatabase))\n",
    "type(horizontalDatabase[0])\n",
    "horizontalDatabase"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 295,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "68\n",
      "{0: [['action', 'agent', 'chance', 'environment', 'maximize', 'perceives', 'intelligent', 'success'], ['artificial', 'intelligence', 'machine'], ['goal', 'intelligent', 'research'], ['learning', 'machine'], ['natural'], ['science'], ['solve', 'ai'], ['technique', 'computer'], ['technology', 'computer'], ['computer'], ['computer', 'machine', 'machine'], ['human'], ['human', 'intelligence', 'intelligence', 'machine'], ['human', 'machine', 'intelligence', 'machine'], ['intelligence', 'machine'], ['intelligent'], ['research'], ['research', 'success', 'success', 'ai'], ['research', 'ai', 'success', 'ai'], ['success'], ['success', 'ai', 'ai'], ['ai'], ['machine']], 1: [['called', 'cloud', 'consists', 'nucleus', 'electron'], ['cloud', 'consists', 'nucleus', 'electron'], ['compound', 'chemical', 'property'], ['consists', 'nucleus', 'electron'], ['nucleus', 'electron'], ['chemistry', 'atom'], ['chemistry', 'atom', 'property', 'property'], ['electron'], ['element', 'property'], ['element', 'property', 'chemical', 'chemical'], ['atom'], ['atom', 'chemical', 'chemical', 'property'], ['atom', 'property', 'property'], ['atom', 'property', 'property', 'chemical', 'chemical'], ['chemical', 'property'], ['property']], 2: [['begin', 'team'], ['bowler', 'batsman', 'ball'], ['cricket', 'ball'], ['end'], ['field', 'ball', 'team'], ['hitting', 'batsman', 'ball', 'run'], ['inning', 'team'], ['main', 'run'], ['match'], ['opponent', 'run', 'team'], ['play', 'team'], ['role'], ['scored', 'run'], ['stump', 'batsman', 'ball'], ['score', 'run'], ['score', 'run', 'bat', 'bat'], ['score', 'run', 'team', 'team'], ['bat'], ['bat', 'ball', 'ball'], ['bat', 'run', 'run'], ['bat', 'team', 'team'], ['batsman', 'ball'], ['batsman', 'ball', 'run', 'run'], ['ball'], ['ball', 'run', 'run'], ['ball', 'team', 'team'], ['run'], ['run', 'team', 'team'], ['team']]}\n"
     ]
    }
   ],
   "source": [
    "# ====================================================================\n",
    "#       Step 2: Initialise variables for first call to DCI_Closed\n",
    "# ====================================================================\n",
    "frequentPatterns = {}\n",
    "closedSet = []\n",
    "preSet = []\n",
    "postSet = []\n",
    "closedSetTids = set()\n",
    "closedCount = 0\n",
    "# [Changeable] User-defined minimum support threshold value\n",
    "minSupport = 2\n",
    "clusterId = 1\n",
    "\n",
    "for c in range(0, len(horizontalDatabase)):\n",
    "    clusterId = c\n",
    "    # =============================\n",
    "    # Step 2-1: Creating postSet\n",
    "    # =============================\n",
    "    maxItemId = len(horizontalDatabase[clusterId])\n",
    "\n",
    "    for i in horizontalDatabase[clusterId]:\n",
    "    #     print(i)\n",
    "        tidSet = horizontalDatabase[clusterId].get(i, None)\n",
    "        if (tidSet != None and len(tidSet) >= minSupport):\n",
    "            postSet.append(i)\n",
    "\n",
    "    # print(postSet)\n",
    "\n",
    "    # =============================================================\n",
    "    # Step 2-2: Sort postSet by ascending + lexicographical order\n",
    "    # =============================================================\n",
    "    def bySuppLex(item1, item2):\n",
    "        if(horizontalDatabase[clusterId].get(item1) == None):\n",
    "            return -1\n",
    "        if(horizontalDatabase[clusterId].get(item2) == None):\n",
    "            return 1\n",
    "        size1 = len(horizontalDatabase[clusterId].get(item1))\n",
    "        size2 = len(horizontalDatabase[clusterId].get(item2))\n",
    "        if(size1 == size2):\n",
    "            if item1 < item2:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "        return size1 - size2\n",
    "\n",
    "    def cmp_to_key(myCompare):\n",
    "        class K:\n",
    "            def __init__(self, obj, *args):\n",
    "                self.obj = obj\n",
    "            def __lt__(self, other):\n",
    "                return myCompare(self.obj, other.obj) < 0\n",
    "            def __gt__(self, other):\n",
    "                return myCompare(self.obj, other.obj) > 0\n",
    "            def __eq__(self, other):\n",
    "                return myCompare(self.obj, other.obj) == 0\n",
    "            def __le__(self, other):\n",
    "                return myCompare(self.obj, other.obj) <= 0\n",
    "            def __ge__(self, other):\n",
    "                return myCompare(self.obj, other.obj) >= 0\n",
    "            def __ne__(self, other):\n",
    "                return myCompare(self.obj, other.obj) != 0\n",
    "        return K\n",
    "\n",
    "    # sort modifies the list which is called, sorted returns \n",
    "    # sorted copy without changing original list\n",
    "\n",
    "    postSet.sort(key = cmp_to_key(bySuppLex))\n",
    "    # print(postSet)\n",
    "    # print(\"preset: \", preSet)\n",
    "\n",
    "    # ==========================================\n",
    "    #  Step 3-4: DCI_Closed function\n",
    "    # ==========================================    \n",
    "    def dci_closed(firstTime, closedSet, closedSetTids, postSet, preSet):\n",
    "        global closedCount\n",
    "        for i in postSet:\n",
    "                newGenTids = set()\n",
    "                if(firstTime):\n",
    "                    if(horizontalDatabase[clusterId].get(i) != None):  \n",
    "                        newGenTids = set(horizontalDatabase[clusterId].get(i))\n",
    "                else:\n",
    "                    newGenTids = intersectTidSet(closedSetTids, set(horizontalDatabase[clusterId].get(i)))    \n",
    "                if len(newGenTids) >= minSupport:\n",
    "                    newGen = []\n",
    "                    newGen = closedSet.copy()\n",
    "                    newGen.append(i)\n",
    "                    if(isDup(newGenTids, preSet) == False):\n",
    "                        closedSetNew = []\n",
    "                        closedSetNew = newGen.copy()\n",
    "                        closedSetNewTIDs = set()\n",
    "                        if firstTime:\n",
    "                            closedSetNewTIDs = set(horizontalDatabase[clusterId].get(i))\n",
    "                        else:\n",
    "                            for i in newGenTids:\n",
    "                                closedSetNewTIDs.add(i)      # Checkpoint\n",
    "                        postSetNew = []\n",
    "                        for j in postSet:\n",
    "                            if smallerAccToTotalOrder(i, j):\n",
    "                                if set(newGenTids).issubset(horizontalDatabase[clusterId].get(j)):\n",
    "                                    closedSetNew.append(j)\n",
    "                                    jTIDs = set(horizontalDatabase[clusterId].get(j))\n",
    "                                    it = iter(closedSetNewTIDs)\n",
    "                                    while it:\n",
    "                                        try:\n",
    "                                            tid = next(it)\n",
    "                                            if tid in jTIDs == False:\n",
    "                                                closedSetNewTIDs.remove(tid)\n",
    "                                        except StopIteration as e:\n",
    "                                            print(e)\n",
    "                                            break\n",
    "                                else:\n",
    "                                    postSetNew.append(j)\n",
    "                        # Uncomment to print FP with support\n",
    "                        # print(closedSetNew, len(closedSetNewTIDs))\n",
    "                        if clusterId in frequentPatterns:\n",
    "                            frequentPatterns[clusterId].append(closedSetNew)\n",
    "                        else:\n",
    "                            temp = [closedSetNew]\n",
    "                            frequentPatterns[clusterId] = temp  \n",
    "                        \n",
    "                        #frequentPatterns.append(closedSetNew)\n",
    "                        closedCount = closedCount + 1\n",
    "                        preSetNew = preSet\n",
    "                        dci_closed(False, closedSetNew, closedSetNewTIDs, postSetNew, preSetNew)\n",
    "                        preSet.append(i)  \n",
    "\n",
    "    dci_closed(True, closedSet, closedSetTids, postSet, preSet)\n",
    "print(closedCount)\n",
    "print(frequentPatterns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n",
      "[1, 4, 2, 3]\n",
      "preset:  []\n",
      "\n",
      "\n",
      "[1, 2, 3] 2\n",
      "[1, 2, 3, 4] 1\n",
      "[3] 3\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# ============================================\n",
    "#       For numerical data (dummy data)\n",
    "# ============================================\n",
    "\n",
    "\n",
    "# ====================================================================\n",
    "#       Step 2: Initialise variables for first call to DCI_Closed\n",
    "# ====================================================================\n",
    "closedSet = []\n",
    "preSet = []\n",
    "postSet = []\n",
    "closedSetTids = set()\n",
    "closedCount = 0\n",
    "# [Changeable] User-defined minimum support threshold value\n",
    "minSupport = 1\n",
    "\n",
    "# =============================\n",
    "# Step 2-1: Creating postSet\n",
    "# =============================\n",
    "for i in range (1, maxItemId + 1):\n",
    "    tidSet = database.get(i, None)\n",
    "    if (tidSet != None and len(tidSet) >= minSupport):\n",
    "        postSet.append(i)\n",
    "        \n",
    "print(postSet)\n",
    "\n",
    "# =============================================================\n",
    "# Step 2-2: Sort postSet by ascending + lexicographical order\n",
    "# =============================================================\n",
    "def bySuppLex(item1, item2):\n",
    "    size1 = len(database.get(item1))\n",
    "    size2 = len(database.get(item2))\n",
    "    if(size1 == size2):\n",
    "        if item1 < item2:\n",
    "            return -1\n",
    "        else:\n",
    "            return 1\n",
    "    return size1 - size2\n",
    "\n",
    "def cmp_to_key(myCompare):\n",
    "    class K:\n",
    "        def __init__(self, obj, *args):\n",
    "            self.obj = obj\n",
    "        def __lt__(self, other):\n",
    "            return myCompare(self.obj, other.obj) < 0\n",
    "        def __gt__(self, other):\n",
    "            return myCompare(self.obj, other.obj) > 0\n",
    "        def __eq__(self, other):\n",
    "            return myCompare(self.obj, other.obj) == 0\n",
    "        def __le__(self, other):\n",
    "            return myCompare(self.obj, other.obj) <= 0\n",
    "        def __ge__(self, other):\n",
    "            return myCompare(self.obj, other.obj) >= 0\n",
    "        def __ne__(self, other):\n",
    "            return myCompare(self.obj, other.obj) != 0\n",
    "    return K\n",
    "\n",
    "# sort modifies the list which is called, sorted returns \n",
    "# sorted copy without changing original list\n",
    "\n",
    "postSet.sort(key = cmp_to_key(bySuppLex))\n",
    "print(postSet)\n",
    "print(\"preset: \", preSet)\n",
    "\n",
    "# ==========================================\n",
    "#  Step 3-4: DCI_Closed function\n",
    "# ==========================================    \n",
    "def dci_closed(firstTime, closedSet, closedSetTids, postSet, preSet):\n",
    "    global closedCount\n",
    "    for i in postSet:\n",
    "            newGenTids = set()\n",
    "            if(firstTime):\n",
    "                newGenTids = set(database.get(i))\n",
    "            else:\n",
    "                newGenTids = intersectTidSet(closedSetTids, set(database.get(i)))    \n",
    "            if len(newGenTids) >= minSupport:\n",
    "                newGen = []\n",
    "                newGen = closedSet.copy()\n",
    "                newGen.append(i)\n",
    "                if(isDup(newGenTids, preSet) == False):\n",
    "                    closedSetNew = []\n",
    "                    closedSetNew = newGen.copy()\n",
    "                    closedSetNewTIDs = set()\n",
    "                    if firstTime:\n",
    "                        closedSetNewTIDs = set(database.get(i))\n",
    "                    else:\n",
    "                        for i in newGenTids:\n",
    "                            closedSetNewTIDs.add(i)      # Checkpoint\n",
    "                    postSetNew = []\n",
    "                    for j in postSet:\n",
    "                        if smallerAccToTotalOrder(i, j):\n",
    "                            if set(newGenTids).issubset(database.get(j)):\n",
    "                                closedSetNew.append(j)\n",
    "                                jTIDs = set(database.get(j))\n",
    "                                it = iter(closedSetNewTIDs)\n",
    "                                while it:\n",
    "                                    try:\n",
    "                                        tid = next(it)\n",
    "                                        if tid in jTIDs == False:\n",
    "                                            closedSetNewTIDs.remove(tid)\n",
    "                                    except StopIteration as e:\n",
    "                                        print(e)\n",
    "                                        break\n",
    "                            else:\n",
    "                                postSetNew.append(j)\n",
    "                    print(closedSetNew, len(closedSetNewTIDs))\n",
    "                    closedCount = closedCount + 1\n",
    "                    preSetNew = preSet\n",
    "                    dci_closed(False, closedSetNew, closedSetNewTIDs, postSetNew, preSetNew)\n",
    "                    preSet.append(i)  \n",
    "    \n",
    "dci_closed(True, closedSet, closedSetTids, postSet, preSet)\n",
    "print(closedCount)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 296,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# ===================================================================\n",
    "#        Step 3: Calling DCI_Closed recursive procedure\n",
    "# ===================================================================\n",
    "\n",
    "# ==========================================\n",
    "#  Step 3-1: Find intersection of two sets\n",
    "# ==========================================\n",
    "def intersectTidSet(tidSet1, tidSet2):\n",
    "    tidSet = set()\n",
    "    if(len(tidSet1) > len(tidSet2)):\n",
    "        for tid in tidSet2:\n",
    "            if tid in tidSet1:\n",
    "                tidSet.add(tid)\n",
    "    else:\n",
    "        for tid in tidSet1:\n",
    "            if tid in tidSet2:\n",
    "                tidSet.add(tid)\n",
    "    return tidSet\n",
    "\n",
    "# =====================================================\n",
    "#  Step 3-2: Check if newGenTids is already duplicated\n",
    "# =====================================================\n",
    "    \n",
    "def isDup(newGenTids, preSet):\n",
    "    for j in preSet: \n",
    "        if(horizontalDatabase[clusterId].get(j) == None):\n",
    "            return False\n",
    "        if set(newGenTids).issubset(horizontalDatabase[clusterId].get(j)):          # Checkpoint\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "# =====================================================\n",
    "#  Step 3-3: Check if item is smaller by support + lex\n",
    "# =====================================================\n",
    "def smallerAccToTotalOrder(i, j):\n",
    "    if(horizontalDatabase[clusterId].get(i) == None):\n",
    "        return True\n",
    "    if(horizontalDatabase[clusterId].get(j) == None):\n",
    "        return False\n",
    "    size1 = len(horizontalDatabase[clusterId].get(i))\n",
    "    size2 = len(horizontalDatabase[clusterId].get(j))\n",
    "    if size1 == size2:\n",
    "        if i < j:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    return size2 - size1 > 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 15]\n",
      "Cluster 3 has maximum number of matches with  15 matches.\n",
      "\n",
      "2\n",
      "***************************************\n",
      "Retrieved documents are as follows:\n",
      "***************************************\n",
      "0 cricket bat ball game played two team eleven player cricket field\n",
      "1 phase play called inning one team bat attempting score many run possible\n",
      "2 team one two inning apiece and first inning end team swap role next inning\n",
      "3 match begin two team captain meet pitch toss coin determine team bat first\n",
      "4 two batsman eleven fielder enter field play begin member fielding team known bowler delivers ball\n",
      "5 common dismissal cricket match bowled bowler hit stump directly ball dislodges bail batsman get out\n",
      "6 run scored two main method either hitting ball hard enough cross boundary two batsman swapping end\n",
      "7 main objective team score run opponent\n",
      "8 team batting last scored fewer run opponent said lost n run\n",
      "9 role striker batsman prevent ball hitting stump using bat and simultaneously strike well enough score run\n"
     ]
    }
   ],
   "source": [
    "# ======================================\n",
    "#  Step 4: Query Resolution\n",
    "# ======================================\n",
    "query = ['bat', 'run']\n",
    "clusterScore = []\n",
    "\n",
    "# ===================================================================\n",
    "#  Step 4-1: Picking best cluster: Calculate similarity with clusters\n",
    "# ===================================================================\n",
    "\n",
    "def intersection(list1, list2):\n",
    "    return list(set(list1) & set(list2))\n",
    "\n",
    "for i in frequentPatterns:\n",
    "    ithCluster = frequentPatterns[i]\n",
    "    currScore = 0\n",
    "    for j in range(0, len(ithCluster)):\n",
    "        if(len(intersection(ithCluster[j], query)) != 0):\n",
    "            currScore+=1\n",
    "    clusterScore.append(currScore)\n",
    "print(clusterScore)\n",
    "\n",
    "maxScore = max(clusterScore)\n",
    "clusterWithMaxScore = clusterScore.index(maxScore)\n",
    "print(\"Cluster\", clusterWithMaxScore+1, \"has maximum number of matches with \", maxScore, \"matches.\\n\")\n",
    "\n",
    "# ======================================================================\n",
    "#  Step 4-2: Picking best documents: Calculate similarity with documents\n",
    "# ======================================================================\n",
    "\n",
    "print(clusterWithMaxScore)\n",
    "print(\"***************************************\")\n",
    "print(\"Retrieved documents are as follows:\")\n",
    "print(\"***************************************\")\n",
    "for i in range(0, len(idea['Cluster'])):\n",
    "    if(idea['Cluster'][i] == clusterWithMaxScore):\n",
    "        print(i, idea['Idea'][i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 322,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: pyfpgrowth in /home/aditi/anaconda3/lib/python3.5/site-packages (1.0)\n",
      "\u001b[33mYou are using pip version 18.1, however version 19.3.1 is available.\n",
      "You should consider upgrading via the 'pip install --upgrade pip' command.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "!pip install pyfpgrowth\n",
    "import pyfpgrowth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 335,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      
     ]
    }
   ],
   "source": [
    "# ============================================================\n",
    "#   Modification-4 : Implemented FP-Growth algorithm\n",
    "# ============================================================\n",
    "\n",
    "\n",
    "test = idea['Idea'][24:29]\n",
    "patterns = pyfpgrowth.find_frequent_patterns(test, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:anaconda3]",
   "language": "python",
   "name": "conda-env-anaconda3-py"
  },
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}