06_Document_indexing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Document indexing with LSH Forest\n",
    "\n",
    "Practical course material for the ASDM Class 09 (Text Mining) by Florian Leitner.\n",
    "\n",
    "© 2016 Florian Leitner. All rights reserved.\n",
    "\n",
    "## Introduction\n",
    "\n",
    "Today's lab will cover the two most fundamental techniques of Text Mining: Document classification and indexing; This notebook covers the latter (\"building the world's fastest search engine\").\n",
    "\n",
    "For background, please check the \"Pitfalls for budding data scientists\" and the \"Shingling and Jaccard's similarity\" notebooks.\n",
    "\n",
    "An excellent resource for basic LSH is the free book (PDF) by Rajaraman, [\"Mining of Massive Datasets\"](http://infolab.stanford.edu/~ullman/mmds/book.pdf). We will specifically be looking at a \"self-tuning\" LSH design, the [LSH Forest by Bawa et al.](http://infolab.stanford.edu/~bawa/Pub/similarity.pdf) Another design variant of this hashing technique is [LSH Ensemble by Zhu et al.](http://www.vldb.org/pvldb/vol9/p1185-zhu.pdf), which is designed to use LSH on a short (query) sequence lookup against long (document) sequences by modifying similarity to only use the length of the query in the denominator. LSH Ensemble is therefore is a nice simple approach to an ranked IR system \"on the cheap\" and without having to fall back on a pairwise ranking strategy to come up with the most similar matches to the query first. But as we will be using *documents* as our queries, though, we will focus on LSH Forest here.\n",
    "\n",
    "Ensure you have **NLTK** installed or install it with:\n",
    "\n",
    "- Anaconda Python: `conda install nltk`\n",
    "- Stock Python: `pip3 install nltk`\n",
    "\n",
    "Ensure you have **Pandas** installed or install it with:\n",
    "\n",
    "- Anaconda Python: `conda install pandas`\n",
    "- Stock Python: `pip3 install pandas`\n",
    "\n",
    "Also install the **`segtok`** tokenization and segmentation library created by yours truly (the instructor, me):\n",
    "\n",
    "- Anaconda Python: `conda install segtok`\n",
    "- Stock Python: `pip3 install segtok`\n",
    "\n",
    "Once done, the following imports should work; If not, you can always skip the practical document indexing examples below.\n",
    "\n",
    "Once done, the following imports should work; If not, you can always skip the practical example at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "import segtok\n",
    "import sklearn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ensure you have at least NLTK book (and/or popular) downloaded and installed from the dialog window that shows up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#nltk.download()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline --no-import-all"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Jaccard's set similarity\n",
    "\n",
    "(see the relevant Notebook for a detailed discussion)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jaccard(seq1, seq2):\n",
    "    \"\"\"\n",
    "    The Jaccard similarity between two sequences:\n",
    "    |∩(X,Y)| / |∪(X,Y)|\n",
    "    \"\"\"\n",
    "    \n",
    "    x = set(seq1)\n",
    "    y = set(seq2)\n",
    "    return len(x & y) / len(x | y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Min-hash signatures\n",
    "\n",
    "(see the \"Pitfalls...\" Notebook for a discussion of `hash` vs. `id`)\n",
    "\n",
    "We will look into an implementation of LSH by [Christian Jauvin](http://cjauvin.github.io/); see [github.com/go2starr/lshhdc](https://github.com/go2starr/lshhdc) for educational puposes (but note that SciKit-Learn will provide us with the implementation we will be using)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MinHashSignature:\n",
    "    \"\"\"Hash signatures for sets/tuples using minhash.\"\"\"\n",
    "\n",
    "    def __init__(self, size):\n",
    "        \"\"\"\n",
    "        Define the size of the hash pool\n",
    "        (number of hash functions).\n",
    "        \"\"\"\n",
    "        \n",
    "        self.size = size\n",
    "        self.hashes = self.__gen_hash_functions()\n",
    "\n",
    "    def __gen_hash_functions(self):\n",
    "        \"\"\"\n",
    "        Return a list of `size` different hash functions.\n",
    "        \"\"\"\n",
    "        \n",
    "        def hash_factory(mutator):\n",
    "            # note that each element in \n",
    "            # an item from a seq being min-hashed\n",
    "            # will be pushed in here\n",
    "            # I.e., item typically is a token,\n",
    "            # character, n-gram, etc.\n",
    "            return lambda item: hash(\n",
    "                \"salt\" + str(mutator) + str(item) + \"salt\"\n",
    "            )\n",
    "        \n",
    "        return [ hash_factory(m) for m in range(self.size) ]\n",
    "\n",
    "    def sign(self, seq):\n",
    "        \"\"\"\n",
    "        Return the min-hash signatures\n",
    "        for any iterable input `seq`.\n",
    "        \"\"\"\n",
    "        \n",
    "        signature = [ float(\"inf\") ] * self.size\n",
    "        \n",
    "        for idx, hash_function in enumerate(self.hashes):\n",
    "            # min-hashing the input seq:\n",
    "            # for each hash_function generated,\n",
    "            # choose the hash value (ID)\n",
    "            # (from hashing all the input sequence\n",
    "            # with that hash function)\n",
    "            # that has the smallest (i.e., min) value\n",
    "            # as the value for the final signature\n",
    "            signature[idx] = min(hash_function(item) for item in seq)\n",
    "        \n",
    "        return signature"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an example of a min-hash signature instance that generates four different hash values (signature size). This signature can be understood as generating four different, random orderings of the (whole) \"possible\" input vocabulary (if you like, \"hash-permuted row IDs\" of your complete vocabulary). The signature therefore reports the first matching token in the input sequence for each of the size different orderings over the whole vocabulary (not just the words in that document!)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-8625898457116879374,\n",
       " -6882610021360069696,\n",
       " -4279804470400346782,\n",
       " -8181631018342185212]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sig4 = MinHashSignature(4)\n",
    "sig4.sign([\"this\", \"is\", \"an\", \"example\", \"document\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Banded Locality Sensitive Hashing\n",
    "\n",
    "(see the \"Pitfalls...\" Notebook for a discussion of floating point issues with probabity values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BandedLSH:\n",
    "    # n. bands (n. hash tables):\n",
    "    # b = dictionary.hasher.size /\n",
    "    #     dictionary.hasher.bandwidth\n",
    "    #    \n",
    "    # n. hashes per band:\n",
    "    # r = dictionary.hasher.bandwidth \n",
    "    \n",
    "    def __init__(self, size, threshold):\n",
    "        \"\"\"\n",
    "        Set up targeting a Jaccard similarity `threshold`\n",
    "        using the given min-hash signature `size`.\n",
    "        \"\"\"\n",
    "        \n",
    "        # total size (n. rows) of the matrix\n",
    "        # (slide \"Banded locality sensitve hasing\")\n",
    "        self.size = size\n",
    "        # *desired* Jaccard similarity threshold\n",
    "        # of the items belonging together\n",
    "        self.threshold = threshold\n",
    "        # number hashes to use per band\n",
    "        # to get as close to that threshold as possible\n",
    "        # bandwidth is the \"rows per band\"\n",
    "        self.bandwidth = self.get_bandwidth(\n",
    "            size,\n",
    "            threshold)\n",
    "        self.min_hasher = MinHashSignature(size)\n",
    "\n",
    "    @staticmethod\n",
    "    def get_bandwidth(n, t):\n",
    "        \"\"\"\n",
    "        Approximate the bandwidth\n",
    "        (number of rows in each band)\n",
    "        for a fixed total number of\n",
    "        rows `n` (bandwith * n. bands)\n",
    "        needed to achieve the desired\n",
    "        similarity threshold `t`.\n",
    "\n",
    "        Similarity threshold t = (1. / b) ** (1. / r)\n",
    "        with size (total rows in LSH) n = b * r\n",
    "        where:\n",
    "        b = number of bands\n",
    "        r = number of rows per band\n",
    "        therefore:\n",
    "        b = 1 / (t ** r)\n",
    "        and:\n",
    "        r = n /b\n",
    "        \"\"\"\n",
    "        \n",
    "        best = n # default: 1 band with `n` rows\n",
    "        minerr = float(\"inf\") # default: \"infinite\" error\n",
    "        \n",
    "        # Try finding the smallest possible bandwith r\n",
    "        # by starting with one row per band, etc:\n",
    "        for r in range(1, n + 1):\n",
    "            try:\n",
    "                # calculate the number of bands b needed to\n",
    "                # achieve the desired threshold t with the\n",
    "                # current number of rows r\n",
    "                b = 1. / (t ** r)\n",
    "            except: # Divide by zero -> `size` is too big\n",
    "                return best\n",
    "            \n",
    "            # how close would the calculated number bands b\n",
    "            # with the current bandwith r, \n",
    "            # required to achieve the desired threshold t,\n",
    "            # be to the desired total LSH size n?\n",
    "            err = abs(n - b * r)\n",
    "            \n",
    "            if err < minerr:\n",
    "                best = r\n",
    "                minerr = err\n",
    "                \n",
    "        return best\n",
    "\n",
    "    def hash(self, seq):\n",
    "        \"\"\"\n",
    "        Generate one locality-sensitive hash ID for each band,\n",
    "        from the input sequence `seq` (tokens, n-grams, etc.).\n",
    "        \"\"\"\n",
    "        sig = self.min_hasher.sign(seq)\n",
    "        \n",
    "        for band in zip(*(iter(sig),) * self.bandwidth):\n",
    "            # the \"salt\" is to make this approach more robust\n",
    "            # and is specific to how hashing works (out of scope here)\n",
    "            # this final hash is only used to only return \n",
    "            # one unique bucket it per band;\n",
    "            # the `band` itself is a list of `bandwith`\n",
    "            # integers from the signature\n",
    "            yield hash(\"salt\" + str(band) + \"tlas\")\n",
    "\n",
    "    @property\n",
    "    def exact_threshold(self):\n",
    "        \"\"\"\n",
    "        The actual threshold,\n",
    "        as defined by the calculated bandwith.\n",
    "        \"\"\"\n",
    "        \n",
    "        r = self.bandwidth\n",
    "        b = self.size / r\n",
    "        return (1. / b) ** (1. / r)\n",
    "\n",
    "    @property\n",
    "    def n_bands(self):\n",
    "        \"\"\"\n",
    "        Calculate the number of bands.\n",
    "        \"\"\"\n",
    "        \n",
    "        return int(self.size / self.bandwidth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The zip-list iterated over in BandedLSH.hash is simply to generate the signature hash ID subset for each band. E.g., assuming size = 6 for the BandedLSH and, therefore, also for the min-hash signature, and assuming the chosen bandwidth would be, say, 2 (from BandedLSH.get_bandwidth), the cryptical iterator zip(*(iter(sig),) * self.bandwidth) above would produce:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 2), (3, 4), (5, 6)]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "signature = [1,2,3,4,5,6]\n",
    "bandwidth = 2\n",
    "list(zip(*(iter(signature),) * bandwidth))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore, what we get out of BandedLSH.hash is one hash ID value for each band given an item's (min-hash) signature size and Jaccard simlilarty threshold target, by calculating the best bandwidth given those two input parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bandwidth calculated: 2\n",
      "resulting n. bands: 150\n",
      "exact similarity threshold: 0.08164965809277261\n"
     ]
    }
   ],
   "source": [
    "hasher = BandedLSH(300, 0.1)\n",
    "print(\"bandwidth calculated:\", hasher.bandwidth)\n",
    "print(\"resulting n. bands:\", hasher.n_bands)\n",
    "print(\"exact similarity threshold:\", hasher.exact_threshold)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pay attention to bandwidth (and the number of bands, too). This indicates how \"hard\" the threshold can be cut off. If the bandwidth is very small and the bands very large, you might rather fuzzy clusters (and a very streched sigmoid in the plot below). The bandwidth (rows/band) is proportional to the (desired) Jaccard similiarty (the horizontal position of the sigmoid plotted below).\n",
    "\n",
    "To visualize the \"cutoff hardness\" of your setup, you can visualize the probability of two documents being added to the same cluster (i.e., set of buckets) as a function of their Jaccard similarity. (see slide \"Banded Locaility Sensitive Minhashing\", $p_{agreement}$)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEWCAYAAAB42tAoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XecVPW9//HXZ3dhgaUtXTpSBVSQFeyK2E3ExBJ7VKImkag/E5NYrnoxyY0mMddYbjTWqNhQFBHbjSXXRlVg6YiUBaTXhe2f3x9z0GHdHYbdnT0zs+/n47GPOeV7zn6+MzCfPd/vOd+vuTsiIiLVyQg7ABERSW5KFCIiEpMShYiIxKREISIiMSlRiIhITEoUIiISkxKF1Bszu9PMngk7DgAz22lmB4Ydx76Y2ZNm9rsaHhvz/TazeWZ2QuWyZtY9eH8yaxS0pB0lCqlTZnaRmc0IvmjWmtmbZnZMHZ6/p5m5mWXV5jzu3tzdl9VVXKnI3Qe5+wdVbF8ZvD/lAGb2gZn9pN4DlKShRCF1xsxuBP4b+APQEegOPASMDjOuaLVNMHUpmWIRiUWJQuqEmbUCxgHXuvsr7l7o7qXu/rq731RF+RPMrKDStuVmdlKwPDy4MtluZuvM7N6g2L+D163BVcuRQfkrzWyBmW0xs7fNrEfUed3MrjWzJcCSqG19guUnzexBM3vDzHaY2VQz6x11/ClmtsjMtpnZQ2b2YXV/YQdNOBPM7IXgXLPM7NBKdfyNmc0BCs0sy8wOCv5q3xo0B51V6bTtzOzd4HwfVqrbfWa2KnifZprZsZWObbKPWE6qog7fXLWZ2e+BY4EHgvf7geC9+kulY143sxuqek8k9SlRSF05EmgCTKyj890H3OfuLYHewIvB9uOC19ZB88inZnY2cAvwQ6A98H/Ac5XOdzYwAhhYze+7EPhPIBdYCvwewMzaAROAm4G2wCLgqH3EPhp4CWgDjAdeNbNGlX7XmUBrwIDXgXeADsAvgGfNrH9U+YuBu4B2wBfAs1H7pgNDon7XS2bWZD9iicndbyXyfo4N3u+xwFPAhWaWAd+8R6P47nsuaUKJQupKW2Cju5fV0flKgT5m1s7dd7r7ZzHKXgP8l7svCH7/H4Ah0X95B/s3u/vuas7xirtPC45/lsiXL8AZwLzgKqkM+Bvw9T5in+nuE9y9FLiXSAI9Imr/39x9VRDLEUBz4I/uXuLu7wGTiSSTPd5w93+7ezFwK3CkmXUDcPdn3H2Tu5e5+1+AbCA6yewrlv3m7tOAbUSSA8AFwAfuvq4255XkpUQhdWUTkSaSump3HwP0Axaa2XQz+16Msj2A+4Kmm63AZiJ/qXeJKrNqH78v+st/F5Evb4DO0cd6ZBTNvZrMqhBdviIo37maWDoDq4Jye6yoLnZ330mkfp0BzOyXQZPbtqDurYhcecQbS009BVwSLF8CPF0H55Qkpc40qSufAkVEmngmxFG+EGi2ZyW4FbP9nnV3X8K3zRs/BCaYWVugquGOVwG/d/dnq9j3zSnjiKkqa4GuUXFa9Ho1ukWVzwjKr6kmljVANzPLiEoW3YHF1ZyvOZFmpDVBf8RviPxlP8/dK8xsC5EkGW8s8ajqvXsGyA/6PA4CXt3Pc0oK0RWF1Al33wbcDjxoZmebWTMza2Rmp5vZPVUcsphIR+uZQZv5bUSaTQAws0vMrH3w5bk12FwObAAqgOhnIP4O3Gxmg4JjW5nZeXVUtTeAg4M6ZQHXAp32ccwwM/thUP4GoBiorulsKpGk+evg/ToB+D7wfFSZM8zsGDNrTKSvYqq7rwJaAGVE3pMsM7sdaFmLWKqzjr3fb9y9gEj/yNPAyzGa9CQNKFFInXH3e4EbiXzpbyDyl/5YqvhrM0gsPwceBVYT+bKMbtI5DZhnZjuJdGxf4O5F7r6LSEfzx0FT0xHuPhG4G3jezLYD+cDpdVSnjcB5wD1EmtcGAjOIfOFW5zXgR8AW4FLgh0EfQVXnLwHOCuLdSOR24svcfWFUsfHAHUSanIYR6dwGeBt4k0jSXUHkiq5yE1vcscRwH3BucEfZ36K2PwUcjJqd0p5p4iKR+AXNNwXAxe7+fhX77wT6uPsllfelGzM7jkgTVM9KfSySZnRFIbIPZnaqmbU2s2wit+Ea+998k1aC5sLrgUeVJNKfEoXIvh0JfEmkaej7wNkNuU3ezA4i0m90AJEn8SXNqelJRERi0hWFiIjElHLPUbRr18579uwZdhgiIill5syZG929/b5LflfKJYqePXsyY8aMsMMQEUkpZraipseq6UlERGJSohARkZiUKEREJCYlChERiUmJQkREYkpYojCzx81svZnlV7PfzOxvZrbUzOaY2WGJikVERGoukVcUTxIZAbQ6pwN9g5+rgf9JYCwiIlJDCXuOwt3/bWY9YxQZDfwzmDHss2DQtQPcfW2iYhKR9FdR4ZSUV1BcVkFxWTll5U55hVNW4ZRXVFBW4ZSVR63vtf/bV3enwqHc9yw7FRXR6+xV7ptXIssA7uDs2R9Z3jNqknvUMuxVfs/yN/uClVEHdeTQbq3r5X2MFuYDd13Ye+z8gmDbdxKFmV1N5KqD7t2710twIpI4u0vK2byrhMLiMnYWl7GruDzyWlJGYXEZhSXlkdfi4DXYvqukPJIESisoKa+gJEgGJWV7liOJIB2ZQYeWTRpcorAqtlX5Cbv7I8AjAHl5een5r0AkhW3bXcqGHUVsLixlc2Hxd193RV63FJayubCE3aXl+zynGeQ0ziInOzN4zaJpo0yaZ2fRplkG2Y0yaJyZQXZWJo2zMmiclUF28BpZDrZnGpkZGWRlGJkZ9u1rsL1RpfVMMzIyIDPDyDAjwwheIz9mlfZlGAbf7DMMjGB57+1m39YtI1ixb+r77fq35ar6mqx/YSaKAqLm86Vmc/mKSD0oLC5j1ZZdFGzeHXndsptVm3exastuCrbsYkdRWZXH5TTOpE3zxrRp1pj2zbPp17EFbXMak5sT2da8SSQBVE4IOdmZNG2UmTRflA1dmIliEjDWzJ4HRgDb1D8hEp6y8gqWbthJ/urtLFm/Y6+ksLmwZK+yTRpl0C23GV1zm3J4z1y65jalY8smtMlpTG6zxrRtHnlt0igzpNpIXUpYojCz54ATgHZmVkBkzt9GAO7+d2AKcAawFNgFXJGoWERkb0Wl5Sxet4P81dvJX7ONeWu2s3DtdorLIpPVNc7MoGtuU7rkNmVwl1Z0zW36TWLo1qYZbXMa66/9BiSRdz1duI/9DlybqN8vIhGFxWUsWLud/NXbyF8TeV26fuc3nb4tmmQxuHMrLjuyB4O7tGJQ51b0apdDZoYSgUSk3DDjIhKbuzNvzXY+XLyB9xeuZ9bKLey5EahtTmMGd2nFqIM6MLhzq2+uFnR1ILEoUYikge1FpXy0ZCPvL1zPh4s3sH5HMQCDu7TkZyf05rDuuQzq3IqOLbOVFGS/KVGIpCB3Z+HXO/hg0QbeX7SemSu2UF7htGiSxXH92jOyfweO69eODi2ahB2qpAElCpEUUVZewYeLN/Du/HV8sGgDX28vAmDgAS255rgDGTmgA0O7tSYrU2N9St1SohBJcuu2F/H8tFU8P30la7cV0SI7i2P6tmNk/w4c3789HVvqqkESS4lCJAlVVDiffLmJZz5bwbsL1lFe4Rzbtx13fH8Qow7qQCNdNUg9UqIQSSJbCkuYMLOA8dNW8tXGQnKbNWLMMb24aHh3erbLCTs8aaCUKERC5u7MWrmVZz9bweS5aykpq2BYj1yuG9WH0wcfoKebJXRKFCIh2VVSxsTPV/PMZytZsHY7OY0zOT+vKxeP6MFBB7QMOzyRbyhRiNSz8grn5ZkF/PmdRazfUcxBB7Tk9z8YzOghXWierf+Sknz0r1KkHn28dCO/e2MBC9ZuZ2j31jxw0WEc3jNXD8FJUlOiEKkHS9fv5L+mLOBfC9fTNbcpD1w0lDMPPkAJQlKCEoVIAm3aWcx9/1rCs1NX0qxRJjefPoAfH9VTHdSSUpQoRBKgqLScpz5ZzgPvLWVXaTkXj+jO9aP60rZ5dtihiew3JQqROuTuvDF3LX98cyEFW3Zz4oAO3HLGAPp0aBF2aCI1pkQhUkdmrdzC7ybPZ9bKrQzo1IJnxozgmL7twg5LpNaUKERqqaSsgrvfWshjH31F+xbZ3HPOIZwzrKsm/pG0oUQhUgsrN+1i7HOzmFOwjcuO7MFvThtAjp6FkDSjf9EiNTR5zhpufnkuZvD3Sw7jtMEHhB2SSEIoUYjsp6LScu6aPJ9np65kSLfW3H/hULq1aRZ2WCIJo0Qhsh+Wrt/J2PGzWPj1Dq45/kB+dUp/DfktaU+JQiROL88s4LZX82naOJMnrjickf07hB2SSL1QohDZh8LiMv7jtXxembWaEb3acN8FQ+nUSrPKScOhRCESw4K127l2/Cy+2ljI9aP6ct2ovrrtVRocJQqRKrg7z05dybjJ82ndtBHP/mQER/XWw3PSMClRiFRSVFrOTRPm8PrsNRzXrz33nn8o7TRGkzRgShQiUQqLy7j66Rl8vHQTN53an58d35sMNTVJA6dEIRLYtquUy5+cxuxVW/nLeYdyzrCuYYckkhSUKESADTuKufSxqSzbUMhDFw/jtMGdwg5JJGkoUUiDt3rrbi59dCprtxXx2OV5HNu3fdghiSQVJQpp0JZt2Mklj05lR3EZT48ZTl7PNmGHJJJ0Ejr2gJmdZmaLzGypmf22iv3dzex9M/vczOaY2RmJjEck2oK12zn/4U8pKqvguauOUJIQqUbCEoWZZQIPAqcDA4ELzWxgpWK3AS+6+1DgAuChRMUjEm3Wyi386OFPycrI4MVrjmRwl1ZhhySStBJ5RTEcWOruy9y9BHgeGF2pjAMtg+VWwJoExiMCwCdLN3LJo1PJzWnMSz89kj4dmocdkkhSS2QfRRdgVdR6ATCiUpk7gXfM7BdADnBSVScys6uBqwG6d+9e54FKw/Hu/HVcO34Wvdrm8PSY4XRoqTGbRPYlkVcUVT2l5JXWLwSedPeuwBnA02b2nZjc/RF3z3P3vPbtdUeK1MxrX6zmp8/M5KADWvLCNUcoSYjEKZGJogDoFrXele82LY0BXgRw90+BJoAG1JE69+zUFdzwwhcc3jOXZ38ygtbNGocdkkjKSGSimA70NbNeZtaYSGf1pEplVgKjAMzsICKJYkMCY5IG6PGPvuLWifmM7N+BJ68YTnPNaS2yXxKWKNy9DBgLvA0sIHJ30zwzG2dmZwXFfglcZWazgeeAy929cvOUSI29MWct4ybP57RBnXj40mE0aZQZdkgiKSehf1q5+xRgSqVtt0ctzweOTmQM0nDNXLGZ//fiFwzrkct/XzBEU5aK1JD+50ha+mpjIT95agadWzXhH5fl6UpCpBaUKCTtbC4s4YonpgHw5BXDaZOjjmuR2lCvnqSVotJyrvrnDNZsK+K5q0bQs11O2CGJpDxdUUjaqKhwfvnibGau2MJfzx/CsB4au0mkLihRSNq4+62FvDF3LbecMYAzDzkg7HBE0oYShaSFpz9bwcP/XsYlR3TnqmMPDDsckbSiRCEp772F67jjtXxOHNCBO78/CDPNcS1Sl5QoJKXlr97G2PGfM7BzS+6/cChZelZCpM7pf5WkrNVbd3PFk9Np3bQRj//4cHI0NIdIQihRSEraXlTKFU9Mo6iknCeu0HDhIomkP8Ek5ZSUVfCzZ2aybEMhT105nP6dWoQdkkhaU6KQlOLu3DJxLh8v3cSfzzuUo/toVHqRRFPTk6SUxz76igkzC7h+VF/OHdY17HBEGgQlCkkZX6zayt1vLeTkgR254aS+YYcj0mAoUUhK2La7lF88N4sOLZrwp3MP0bMSIvVIfRSS9Nydm1+Zw5qtRbx4zZGaxlSknumKQpLeM1NXMmXu19x0an+G9cgNOxyRBkeJQpLavDXbuGvyfI7v156rNYaTSCiUKCRp7Swu4xfjPye3WSPuPf9QMjLULyESBvVRSFJyd26bOJflmwoZf9URtG2eHXZIIg2WrigkKb00s4BXv1jD9aP6ccSBbcMOR6RBU6KQpLNk3Q5ufy2fIw9sy9gT+4QdjkiDp0QhSWV3STnXjp9FTuMs7rtgCJnqlxAJnfooJKmMmzyPxet28tSVGhFWJFnoikKSxmtfrOa5aav42Qm9Ob5f+7DDEZFAtYnCzPqa2Wtmlm9mz5lZl/oMTBqWrzYWcssrcxnWI5cbT+4XdjgiEiXWFcXjwGTgHGAWcH+9RCQNTnFZOWPHzyIrM4O/XTiURprOVCSpxOqjaOHu/wiW/2Rms+ojIGl4/mvKQuat2c4/LsujS+umYYcjIpXEShRNzGwosOe2k6bR6+6uxCG19lb+1zz5yXKuPLoXJw/sGHY4IlKFWIliLXBv1PrXUesOnJiooKRhWLe9iF9PmM0hXVvx29MHhB2OiFSj2kTh7iNre3IzOw24D8gEHnX3P1ZR5nzgTiLJZ7a7X1Tb3yvJz9255ZW5FJdVcN8FQ2mcpX4JkWSVsOcozCwTeBA4GSgAppvZJHefH1WmL3AzcLS7bzGzDomKR5LLq1+s5l8L13PbmQfRq11O2OGISAyJ/DNuOLDU3Ze5ewnwPDC6UpmrgAfdfQuAu69PYDySJNbvKOLOSfM5rHtrrji6V9jhiMg+JDJRdAFWRa0XBNui9QP6mdnHZvZZ0FT1HWZ2tZnNMLMZGzZsSFC4Uh8io8Lms7u0nHvOPVRDdIikgH02PZnZYVVs3gascPeyWIdWsc2r+P19gROArsD/mdlgd9+610HujwCPAOTl5VU+h6SQ1+es5Z356/jt6QPo06F52OGISBzi6aN4CDgMmEPky39wsNzWzH7q7u9Uc1wB0C1qvSuwpooyn7l7KfCVmS0ikjimx18FSRUbdhRzx2v5HNqtNT85Rk1OIqkinqan5cBQd89z92HAUCAfOAm4J8Zx04G+ZtbLzBoDFwCTKpV5FRgJYGbtiDRFLduvGkjKuGNSPoXF5fz53EPI0tPXIikjnv+tA9x93p6V4K6loe4e8ws9aJYaC7wNLABedPd5ZjbOzM4Kir0NbDKz+cD7wE3uvqkmFZHk9sactUyZ+zXXn9SXvh1bhB2OiOyHeJqeFpnZ/xC5awngR8BiM8sGSmMd6O5TgCmVtt0etezAjcGPpKlNO4u5/bV8Du7SimuOOzDscERkP8WTKC4Hfg7cQKSP4iPgV0SSRK0fypP0d+fr89leVMqz541Qk5NICtpnonD33cBfgp/KdtZ5RJJW3sr/mtdnr+HGk/sxoFPLsMMRkRqI5/bYo4kMsdEjury7qw1BYtpSWMJtr+Yz8ICW/OyE3mGHIyI1FE/T02PA/wNmAuWJDUfSyX++Po+tu0p46srDNceESAqLJ1Fsc/c3Ex6JpJV356/j1S/WcN2ovgzq3CrscESkFuJJFO+b2Z+AV4DiPRs1H4VUZ9uuUm6dOJcBnVowdmSfsMMRkVqKJ1GMCF7zorZpPgqp1rjJ89lUWMJjPz5cw4eLpIF47nrSLbASt/cWruPlWQVcO7I3B3dVk5NIOqg2UZjZJe7+jJlV+TCcu99b1XZpuLYXlXLLK/n07dCc60b1DTscEakjsa4o9swmo/EWJC5/eGMB63cU8fClR5OdlRl2OCJSR2JNhfpwMEvddnf/az3GJClo+vLNPD99FVcd24tDu7UOOxwRqUMxexrdvRw4K1YZkZKyCm6dOJfOrZpww0n9wg5HROpYPHc9fWJmDwAvAIV7Nur2WNnjsY++YvG6nfzjsjxyshM2DbuIhCSe/9VHBa/jorbp9lgBYNXmXdz3r8WcMrAjJw/sGHY4IpIAuj1Waszduf21fDLMuPOsQWGHIyIJss+nocyso5k9ZmZvBusDzWxM4kOTZPdW/te8v2gDN57cj86tm4YdjogkSDyPzT5JZCa6zsH6YiJzU0gDtqOolDtfn8dBB7Tk8qN6hh2OiCRQPIminbu/CFTAN1OcahTZBu7edxezfkcxf/jBYE1GJJLm4vkfXmhmbYl0YGNmRwDbEhqVJLX81dt46pPlXDyiO0O754YdjogkWDx3Pd0ITAJ6m9nHQHvgvIRGJUmrvMK5ZeJc2uRkc9OpA8IOR0TqQTyJYh5wPNCfyJzZi4jvSkTS0DOfrWBOwTbuu2AIrZo2CjscEakH8Xzhf+ruZe4+z93z3b0U+DTRgUnyWbe9iD+9vYhj+7bjrEM77/sAEUkLsUaP7QR0AZqa2VAiVxMALYFm9RCbJJlxk+dTUl7BXaMHY2b7PkBE0kKspqdTgcuBrsBf+DZR7ABuSWxYkmw+WLSeN+as5caT+9GzXc6+DxCRtBFr9NingKfM7Bx3f7keY5IkU1Razn+8ls+B7XO45vgDww5HROpZPH0UXc2spUU8amazzOyUhEcmSeP+95awavNufnf2YM0zIdIAxZMornT37cApQAfgCuCPCY1KksaSdTt45N/L+OFhXTiqd7uwwxGREMSTKPb0TZwBPOHus6O2SRpzd259NZ9mjbO45YyDwg5HREIST6KYaWbvEEkUb5tZC4LhPCS9TZhZwLSvNnPz6QNo1zw77HBEJCTxPHA3BhgCLHP3XcFwHlckNiwJ2+bCEv4wZQF5PXI5P69b2OGISIjiSRTHBK+H6N75huOPby5gR1EZv//BwWRk6HMXacjiSRQ3RS03AYYDM4ljhjszOw24D8gEHnX3KjvBzexc4CXgcHefEUdMkkAzlm/mxRkFXHPcgfTv1CLscEQkZPHMcPf96HUz6wbcs6/jzCwTeBA4GSgAppvZJHefX6lcC+A6YOp+xC0JUlpewW2v5tO5VROuG9U37HBEJAnUZHC/AmBwHOWGA0vdfZm7lwDPA6OrKHcXkcRTVINYpI49+fFyFn69gzvOGkROdjwXnCKS7vb5TWBm9xPMRUEksQwBZsdx7i7Aqqj1AmBEpXMPBbq5+2Qz+1WMGK4Grgbo3r17HL9aamLN1t389X8XM2pAB04Z2DHscEQkScTzJ2N0n0EZ8Jy7fxzHcVX1gPo3O80ygL8SGU8qJnd/BHgEIC8vz/dRXGrorsnzqXDnzrMGadA/EflGPH0UT9Xw3AVA9H2VXYE1UestiDRhfRB8KXUCJpnZWerQrn/vL1rPm/lfc9Op/enWRoMDi8i3Yg0zPpeoK4DoXYC7+yH7OPd0oK+Z9QJWAxcAF+3Z6e7bgG/GhDCzD4BfKUnUv6LScu54bR692+dw1bEa9E9E9hbriuJ7tTmxu5eZ2VjgbSK3xz7u7vPMbBwww90n1eb8UncefH8pKzfvYvxVI2icpckLRWRvsRJFI6Bj5f4IMzuWvZuQquXuU4AplbbdXk3ZE+I5p9StLzfs5OEPl3H2kM4a9E9EqhTrz8f/JjJJUWW7g32S4tyd21/LJ7tRBreeOTDscEQkScVKFD3dfU7ljUEfQs+ERST1ZtLsNXy8dBO/PrU/7Vto0D8RqVqsRNEkxr6mdR2I1K/tRaX87o0FHNK1FReN6BF2OCKSxGIliulmdlXljWY2hshYT5LC7n1nMRt3FvO7sweTqUH/RCSGWJ3ZNwATzexivk0MeUBj4AeJDkwSJ3/1Nv756XIuPaIHh3RtHXY4IpLkqk0U7r4OOMrMRvLt2E5vuPt79RKZJER5hXPrxLm0ycnml6f0DzscEUkB8TyZ/T7wfj3EIvVg/LSVzC7Yxn//aAitmjYKOxwRSQF6uqoB2bCjmHveWshRvdsyekjnsMMRkRShRNGA/NeUBRSVljNu9GAN+icicVOiaCA+/XITr3y+mmuO602fDs3DDkdEUogSRQNQXFbOf7yWT9fcplw7sk/Y4YhIitEUZg3AQ+9/ydL1O3ni8sNp2jgz7HBEJMXoiiLNLV63g4c+WMroIZ0ZOaBD2OGISApSokhj5RXOryfMoXl2Frd/T4P+iUjNKFGksac+Wc4Xq7Zyx/cH0ba5Bv0TkZpRokhTqzbv4k9vL+KE/u31zISI1IoSRRpyd26ZOJcMg9//4GA9MyEitaJEkYZembWa/1uykV+fNoAurTUivIjUjhJFmtm4s5i73pjPsB65XHqE5pkQkdpTokgzd06ax67icu4+52AyNM+EiNQBJYo08r/z1zF5zlrGntiHPh1ahB2OiKQJJYo0sb2olNtezad/xxb89PjeYYcjImlEQ3ikibvfXMj6HUX8/dJhNM5S/heRuqNvlDQwddkmnp26kiuO7sWQbpraVETqlhJFiisqLefmV+bSrU1TfnlKv7DDEZE0pKanFPe3fy1h2cZCnhkzgmaN9XGKSN3TFUUKm7dmGw//exnnDuvKMX3bhR2OiKQpJYoUVVZewW9enkNus8bcduZBYYcjImlMbRUp6rGPviJ/9XYevOgwWjdrHHY4IpLGdEWRgpZvLOTedxdz8sCOnHFwp7DDEZE0l9BEYWanmdkiM1tqZr+tYv+NZjbfzOaY2b/MTIMT7UNZeQW/njCHxpkZ3DV6sEaGFZGES1iiMLNM4EHgdGAgcKGZVZ5m7XMgz90PASYA9yQqnnRx/3tLmbZ8M/85ehCdWjUJOxwRaQASeUUxHFjq7svcvQR4HhgdXcDd33f3XcHqZ0DXBMaT8j79chP3v7eEcw7ryg8P01slIvUjkYmiC7Aqar0g2FadMcCbVe0ws6vNbIaZzdiwYUMdhpg6Nu0s5oYXPqdn2xzGjR4Udjgi0oAkMlFU1XjuVRY0uwTIA/5U1X53f8Td89w9r3379nUYYmpwd3710my27Crl/ouGkpOtm9VEpP4k8hunAOgWtd4VWFO5kJmdBNwKHO/uxQmMJ2U99tFXvL9oA+NGD2JQ51ZhhyMiDUwiryimA33NrJeZNQYuACZFFzCzocDDwFnuvj6BsaSsOQVbufuthZwysKNmrBORUCQsUbh7GTAWeBtYALzo7vPMbJyZnRUU+xPQHHjJzL4ws0nVnK5B2lFUytjxn9OhRRPuOfcQ3QorIqFIaGO3u08BplTadnvU8kmJ/P2pzN25ZWI+q7fu5oWrj9DT1yISGj2ZnaRenLGK12ev4caT+5HXs03Y4YhIA6ZEkYSWrNu/jpLFAAAMUklEQVTBHZPmcXSftprWVERCp0SRZIpKyxk7/nOaZ2fx1x8NITND/RIiEi7dkJ9kxk2ez6J1O3jqyuF0aKEhOkQkfLqiSCJvzFnL+Kkr+enxvTm+X8N7sFBEkpMSRZJYtXkXv315DkO6tdbc1yKSVJQokkBpeQVjn/scDO6/cCiNMvWxiEjyUB9FEvjzO4uYvWorD118GN3aNAs7HBGRvehP15C9M+9rHv5wGReP6M4ZBx8QdjgiIt+hRBGiT5ZuZOxzn3No11b8x/cqz+kkIpIclChCMmvlFn7yzxn0apvDk1cMp0mjzLBDEhGpkhJFCBas3c7lj0+jfYtsnh4znNwcjeMkIslLiaKefbWxkEsfm0ZOdhbPjBlBh5Z6qE5EkpsSRT1avXU3lzw6FXfn6TEjdIeTiKQE3R5bTzbsKObSR6eyvaiU5646gj4dmocdkohIXHRFUQ+27SrlssensXZbEU9cfjiDu2g6UxFJHUoUCVZYXMYVT07jy/U7efjSYZpbQkRSjpqeEqiotJxrnp7J7IJtPHjRYRyngf5EJAXpiiJBSssr+MVzn/PR0o3cc84hnDa4U9ghiYjUiBJFAlRUOL+eMId3569j3OhBnDOsa9ghiYjUmBJFHXN3bp+Uz8TPV3PTqf257MieYYckIlIrShR1yN25+61FPPPZSq45/kB+foLmuxaR1KfO7DqyZutufvPyHP5vyUYuHtGd3542ADPNdy0iqU+JopbcnQkzCxg3eT5l5c5dowdx8YgeShIikjaUKGph/fYibpk4l/9dsJ7hPdvwp/MOoUfbnLDDEhGpU0oUNeDuTJq9hjsmzWN3STm3nXkQVx7di4wMXUWISPpRothPm3YWc9ur+byZ/zVDurXmL+cfSu/2GrdJRNKXEsV+eCt/LbdOzGdHURm/Pq0/Vx97IFmZunFMRNKbEkUctu4q4c5J83j1izUM7tKS8ecNoX+nFmGHJSJSL5Qo9uG9hev47ctz2VxYwv87qR8/H9mbRrqKEJEGRImikuKycvJXb2PG8i188uUmPly8gQGdWvC4hgcXkQYqoYnCzE4D7gMygUfd/Y+V9mcD/wSGAZuAH7n78kTGVNnWXSXMXLGF6cu3MHPFZmYXbKOkrAKAXu1yuG5UX64d2ZvsrMz6DEtEJGkkLFGYWSbwIHAyUABMN7NJ7j4/qtgYYIu79zGzC4C7gR8lKiZ3Z+XmXcxYvoUZKzYzY/kWlqzfCUCjTGNQ51b8+MgeDOvRhmE9cmnfIjtRoYiIpIxEXlEMB5a6+zIAM3seGA1EJ4rRwJ3B8gTgATMzd/e6DuaF6Sv58zuL2bCjGIAWTbLI65HL2UO7kNcjl0O7taZJI101iIhUlshE0QVYFbVeAIyoroy7l5nZNqAtsDG6kJldDVwN0L179xoF075FNsf0acewHrkc3rMNfTs01wNyIiJxSGSiqOpbuPKVQjxlcPdHgEcA8vLyanS1ceKAjpw4oGNNDhURadASeZ9nAdAtar0rsKa6MmaWBbQCNicwJhER2U+JTBTTgb5m1svMGgMXAJMqlZkE/DhYPhd4LxH9EyIiUnMJa3oK+hzGAm8TuT32cXefZ2bjgBnuPgl4DHjazJYSuZK4IFHxiIhIzST0OQp3nwJMqbTt9qjlIuC8RMYgIiK1o7EoREQkJiUKERGJSYlCRERiUqIQEZGYLNXuRjWzDcCKGh7ejkpPfTcwDbn+Dbnu0LDrr7pH9HD39jU5Scolitowsxnunhd2HGFpyPVvyHWHhl1/1b32dVfTk4iIxKREISIiMTW0RPFI2AGErCHXvyHXHRp2/VX3WmpQfRQiIrL/GtoVhYiI7CclChERiSltEoWZnWZmi8xsqZn9tor92Wb2QrB/qpn1jNp3c7B9kZmdWp9x14Wa1t3MeprZbjP7Ivj5e33HXhfiqP9xZjbLzMrM7NxK+35sZkuCnx9XPjbZ1bLu5VGffeUpAJJeHHW/0czmm9kcM/uXmfWI2pfSnzvUuv7799m7e8r/EBnG/EvgQKAxMBsYWKnMz4G/B8sXAC8EywOD8tlAr+A8mWHXqZ7q3hPID7sO9VD/nsAhwD+Bc6O2twGWBa+5wXJu2HWqj7oH+3aGXYcE130k0CxY/lnUv/uU/txrW/+afPbpckUxHFjq7svcvQR4Hhhdqcxo4KlgeQIwysws2P68uxe7+1fA0uB8qaI2dU8H+6y/uy939zlARaVjTwXedffN7r4FeBc4rT6CriO1qXuqi6fu77v7rmD1MyKzbELqf+5Qu/rvt3RJFF2AVVHrBcG2Ksu4exmwDWgb57HJrDZ1B+hlZp+b2Ydmdmyig02A2nx+DeGzj6WJmc0ws8/M7Oy6DS3h9rfuY4A3a3hsMqpN/WE/P/uETlxUj6r667jyfb/VlYnn2GRWm7qvBbq7+yYzGwa8amaD3H17XQeZQLX5/BrCZx9Ld3dfY2YHAu+Z2Vx3/7KOYku0uOtuZpcAecDx+3tsEqtN/WE/P/t0uaIoALpFrXcF1lRXxsyygFZEpl+N59hkVuO6B81tmwDcfSaRNs9+CY+4btXm82sIn3213H1N8LoM+AAYWpfBJVhcdTezk4BbgbPcvXh/jk1ytan//n/2YXfK1FHHThaRDqlefNuxM6hSmWvZu0P3xWB5EHt3Zi8jtTqza1P39nvqSqRTbDXQJuw61XX9o8o+yXc7s78i0qGZGyynTP1rWfdcIDtYbgcsoVJnaDL/xPnvfiiRP376Vtqe0p97HdR/vz/70Ctch2/cGcDi4I25Ndg2jkgmBWgCvESks3oacGDUsbcGxy0CTg+7LvVVd+AcYF7wj2wW8P2w65Kg+h9O5C+wQmATMC/q2CuD92UpcEXYdamvugNHAXODz34uMCbsuiSg7v8LrAO+CH4mpcvnXpv61+Sz1xAeIiISU7r0UYiISIIoUYiISExKFCIiEpMShYiIxKREISIiMSlRSEows50h//4TzGzyfpT/ZD/P/1MzuyxYfrLySK/7efzlZtZ5f44XiSVdhvAQqVNmlunu5TU93t2P2s/yNR7i3cyyKh1/OZBP6j1tLElKVxSSMsyseTCu/iwzm2tmo6P2XRaMuz/bzJ4OtnU0s4nBttlmdlSw/VUzm2lm88zs6qhz7DSzcWY2FTgyGO9/oZl9BPywmpgGmdm0YFz/OWbWd8+5gtcTggEXXzSzxWb2RzO7ODhmrpn1DsrdaWa/quL8t5vZdDPLN7NH9oz6a2YfmNkfzOxD4Po9xwdXInnAs0FMZ5rZxKjznWxmr9Tyo5AGRolCUkkR8AN3P4zIWPt/sYhBRJ6uP9HdDwWuD8r/Dfgw2HYYkafQAa5092FEvlCvM7M9I+nmEJmfYwQwA/gH8H3gWKBTNTH9FLjP3YcE5yuoosyemA4GLgX6uftw4FHgF/uo8wPufri7DwaaAt+L2tfa3Y9397/s2eDuE4LYLw5imgIcZGbtgyJXAE/s43eK7EWJQlKJAX8wszlEhifoAnQETgQmuPtGAHffHJQ/EfifYFu5u28Ltl9nZrOJjNHfDegbbC8HXg6WBwBfufsSjwxf8Ew1MX0K3GJmvwF6uPvuKspMd/e1HhmU7UvgnWD7XCITC8Uy0iKzEs4N6jMoat8L+ziWIPangUvMrDVwJHsPNy2yT+qjkFRyMZGBDIe5e6mZLScyjpUR5zDRZnYCcBJwpLvvMrMPgnMAFFXql9jnOd19fNBUdSbwtpn9xN3fq1SsOGq5Imq9ghj/B82sCfAQkOfuq8zszqhYITJ+UzyeAF4nckX2kkfmJBGJm64oJJW0AtYHSWIksGcO4H8B5+9pQjKzNlHbfxZsyzSzlsE5tgRJYgBwRDW/ayGRSZ16B+sXVlUoGM9/mbv/DZhEZNrRurInKWw0s+ZAvHdC7QBa7FnxyJDSa4DbiIwiK7JflCgk6QVzaBQDzwJ5ZjaDyNXFQgB3nwf8HvgwaFK6Nzj0eiJNN3OBmUSabd4CsoLmq7uIND99h7sXAVcDbwSd2SuqCe9HQL6ZfUGkueqftaxudAxbifSTzAVeBabHeeiTwN+DzuymwbZngVXuPr+u4pOGQ6PHStIzs0OBfwQdwFIDZvYA8Lm7PxZ2LJJ61EchSc3MfgpcB9wQdiypysxmEunP+GXYsUhq0hWFiIjEpD4KERGJSYlCRERiUqIQEZGYlChERCQmJQoREYnp/wMgaPJrb/9RkQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bands = 150\n",
    "bandwidth = 2\n",
    "p_agreement = lambda sim: 1 - (1 - sim**bandwidth)**bands\n",
    "x = np.arange(0.0, 0.25, 0.01)\n",
    "\n",
    "plt.plot(x, p_agreement(x))\n",
    "plt.title('Clustering probability')\n",
    "# (as a function of bandwidth and n. bands)\n",
    "plt.xlabel('Jaccard similarity')\n",
    "plt.ylabel('Clustering P')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Feel free to play around with the above cell, chaning `bandwidth` and `bands` to understand how those two parameters influnce the likelihood of two documents sharing *at least one bucket* given their Jaccard similarity.\n",
    "\n",
    "## Document indexing\n",
    "\n",
    "While the toy implementation above was practical to discuss the algorithm, we will be using a special [LSH **Forest**](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LSHForest.html#sklearn-neighbors-lshforest) implementation to retrieve the closest matching document given a query (document).\n",
    "\n",
    "![title](img/lsh_forest.png)\n",
    "\n",
    "Another attractive LSH implemention is avaliable from the [`datasketch`](https://ekzhu.github.io/datasketch/lsh.html) Python library.\n",
    "\n",
    "### Corpus preparation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Downloading 20news dataset. This may take a few minutes.\n",
      "Downloading dataset from https://ndownloader.figshare.com/files/5975967 (14 MB)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Corpus sizes: train = 11314 ; test = 7532\n"
     ]
    }
   ],
   "source": [
    "from sklearn.datasets import fetch_20newsgroups\n",
    "\n",
    "from nltk.stem.porter import PorterStemmer\n",
    "from nltk.corpus import stopwords\n",
    "\n",
    "from segtok.segmenter import split_multi\n",
    "from segtok.tokenizer import word_tokenizer, split_contractions\n",
    "\n",
    "stemmer = PorterStemmer()\n",
    "train, test = fetch_20newsgroups(), fetch_20newsgroups(subset='test')\n",
    "\n",
    "stopwords_en = frozenset(stopwords.words('english'))\n",
    "stopwords_none = frozenset([])\n",
    "\n",
    "\n",
    "def tokenize(raw_text):\n",
    "    \"\"\"\n",
    "    Convert text to lower-case tokens of length > 2.\n",
    "    \"\"\"\n",
    "    \n",
    "    for sentence in split_multi(raw_text):\n",
    "        for raw in split_contractions(word_tokenizer(sentence)):\n",
    "            token = raw.lower()\n",
    "            \n",
    "            if len(token) > 2 and any(c.isalnum() for c in token):\n",
    "                yield token\n",
    "\n",
    "                \n",
    "def filter_and_stem(raw_text, stopwords):\n",
    "    \n",
    "    for token in tokenize(raw_text):\n",
    "        yield token\n",
    "        if token not in stopwords:\n",
    "            yield stemmer.stem(token)\n",
    "        else:\n",
    "            yield None\n",
    "                \n",
    "                \n",
    "def shingle(\n",
    "    raw_text,\n",
    "    stopwords=stopwords_none,\n",
    "    bigrams=False):\n",
    "    \"\"\"\n",
    "    Shingle text to stop-word-free,\n",
    "    stemmed uni- and bi-grams.\n",
    "    \"\"\"\n",
    "    \n",
    "    last = None\n",
    "    \n",
    "    for t in filter_and_stem(raw_text, stopwords):\n",
    "        if t is not None:\n",
    "            yield t\n",
    "            \n",
    "            if bigrams and last is not None:\n",
    "                yield \"{}_{}\".format(last, t)\n",
    "            \n",
    "        last = t\n",
    "\n",
    "print(\"Corpus sizes: train =\",\n",
    "      len(train.data),\n",
    "      \"; test =\", len(test.data))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's have a look at how that tokenization/shingling works on a document in our collection:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "From: lerxst@wam.umd.edu (where's my thing)\n",
      "Subject: WHAT car is this!?\n",
      "Nntp-Posting-Host: rac3.wam.umd.edu\n",
      "Organization: University of Maryland, College Park\n",
      "Lines: 15\n",
      "\n",
      " I was wondering if anyone out there could enlighten me on this car I saw\n",
      "the other day. It was a 2-door sports car, looked to be from the late 60s/\n",
      "early 70s. It was called a Bricklin. The doors were really small. In addition,\n",
      "the front bumper was separate from the rest of the body. This is \n",
      "all I know. If anyone can tellme a model name, engine specs, years\n",
      "of production, where this car is made, history, or whatever info you\n",
      "have on this funky looking car, please e-mail.\n",
      "\n",
      "Thanks,\n",
      "- IL\n",
      "   ---- brought to you by your neighborhood Lerxst ----\n"
     ]
    }
   ],
   "source": [
    "example = train['data'][0].strip()\n",
    "print(example)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a real-world scenario, you'd probably start cleaning up the above \"mess\", removing the header and possibly the footers from the messages.\n",
    "\n",
    "You can either use `tokenize` to work with single tokens, or `shingle` to work with [higher] n-grams and stopword-filtering, too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "thi history subject park there organ separate whatev made univers looked from you sport addit 70 wa bodi university organization realli spec tellme sports nntp-posting-host lerxst brought car body all the addition year lines model histori name funki colleg this specs maryland were small thing saw know day doors late enlighten anyone e-mail your wondering rac3.wam.umd.edu have look earli please early bricklin 70s funky really neighborhood wam.umd.edu other thank 60s wonder rest tellm line separ what where front could whatever info college 2-door production can call years anyon out called 60 thanks was pleas product engin bumper door engine looking\n"
     ]
    }
   ],
   "source": [
    "tokens = frozenset(shingle(example))\n",
    "print(\" \".join(tokens))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now convert the whole 20News *train* corpus into tokens - this can take a while (possibly 5 minutes!) on most machines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2min 45s, sys: 1.23 s, total: 2min 46s\n",
      "Wall time: 2min 48s\n"
     ]
    }
   ],
   "source": [
    "%time corpus = [frozenset(shingle(doc)) for doc in train['data']]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Similarity threshold estimation\n",
    "\n",
    "First, we'd like to find out how our document similarity behaves across our corpus.\n",
    "To do that we select a random \"target\" document and compute it's Jaccard similiary against all other documents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "other doc with max. Jaccard similarity = 0.2231404958677686\n",
      "Mean Jaccard similarity = 0.08535529656332358\n",
      "Median Jaccard similarity = 0.08636363636363636\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<matplotlib.axes._subplots.AxesSubplot at 0x1a24d8b780>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAD8CAYAAACb4nSYAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAE49JREFUeJzt3X9sXWV+5/H3N8b5QRKhhGSGhZAfFUF18KZT1SVCwGij3WYYUQW0YrQkdEU30SCkjVvtqmiCLJWWKixD1d1VHXZIMtBtR8TATiWINFOlo45bKaLbjZlMCfmlZCABk9EkkMyUJGDH9nf/8E2wjYd7ruPk2jnvl3R173nOc879WoLPffKcX5GZSJLKYUq9C5AkXTmGviSViKEvSSVi6EtSiRj6klQihr4klYihL0klYuhLUokY+pJUItfUu4CR5s2bl4sXL653GZI0qbzxxhsfZOb8av0mXOgvXryYrq6uepchSZNKRBwr0s/pHUkqEUNfkkrE0JekEjH0JalEDH1JKhFDXyqgo6OD5uZmGhoaaG5upqOjo94lSWMy4U7ZlCaajo4O2traeP7557nrrrvYtWsX69evB2DNmjV1rk6qTUy0xyW2tLSk5+lrImlubqa9vZ2VK1debOvs7KS1tZW33nqrjpVJn4qINzKzpWo/Q1/6fA0NDXzyySc0NjZebDt//jzTp0+nv7+/jpVJnyoa+s7pS1U0NTWxa9euYW27du2iqampThVJY2foS1W0tbWxfv16Ojs7OX/+PJ2dnaxfv562trZ6lybVzAO5UhUXDta2trZy4MABmpqa2LRpkwdxNSk5py9JVwHn9CVJn2HoS1KJGPqSVCKGviSViKEvFeC9d3S18JRNqQrvvaOriadsSlU0Nzdz//338+qrr148T//Csvfe0URR9JRNR/pSFfv37+fEiRPMnDmTzOTs2bNs3bqVDz74oN6lSTVzTl+qoqGhgXPnzg1rO3fuHA0NDXWqSBo7R/pSFX19ffT19TFr1iwyk48//pizZ8/WuyxpTBzpSwU0NjZy6tQpAE6dOjXsNsvSZGLoSwX09fUxd+5cAObOnUtfX1+dK5LGplDoR8Q9EXEoIo5ExMZR1v/XiNgfEW9GxN9FxKIh6x6OiMOV18PjWbx0pWQmH374IQAffvghE+2sN6moqqEfEQ3As8BXgWXAmohYNqLbHqAlM5cD3wWeqWw7F3gCWAHcDjwREXPGr3zpyogIrr/++mHv0mRUZKR/O3AkM9/OzF7gJeC+oR0yszMzL5ze8H+BBZXPXwF+kJmnMvM08APgnvEpXbpyrr32WmbMmEFEMGPGDK699tp6lySNSZHQvwl4b8hyd6Xtl1kP/M0Yt5UmpGuuGTzR7cK0zoVlabIpEvqj/Tt21AnNiPgdoAX401q2jYhHIqIrIrpOnjxZoCTpylmwYMHFz0OndYa2S5NFkdDvBm4esrwAOD6yU0T8O6ANWJ2ZPbVsm5lbM7MlM1vmz59ftHbpinjmmWfo7e3l6NGjDAwMcPToUXp7e3nmmWfqXZpUsyKhvxtYGhFLImIq8CCwY2iHiPh1YAuDgX9iyKqdwKqImFM5gLuq0iZNGq+//jo9PT3ccMMNTJkyhRtuuIGenh5ef/31epcm1axq6GdmH7CBwbA+ALySmfsi4smIWF3p9qfALOD/RMSPI2JHZdtTwJ8w+MOxG3iy0iZNGtu2beOOO+7g9OnTDAwMcPr0ae644w62bdtW79KkmnmXTamKiCAi+MIXvsDPfvYzvvjFL3LixAky0/P1NWH4YHRpHE2fPp2Ojg56e3vp6Ohg+vTp9S5JGhNDXyqgp6eHPXv2cP78efbs2UNPT0/1jaQJyOkdqYqIYOnSpRw5coTMJCK45ZZbOHz4sNM7mjCc3pHGycyZMzl8+DCPPvooP//5z3n00Uc5fPgwM2fOrHdpUs28rFCqYs6cOQwMDPDtb3+bb33rWzQ2NjJjxgzmzPE2Upp8HOlLVRw/fpwtW7Zw6623MmXKFG699Va2bNnC8eOfuc5QmvAMfamKpqYmDh06NKzt0KFDNDU11akiaewMfamKlStX8tRTT3Hw4EEGBgY4ePAgTz31FCtXrqx3aVLNDH2piu3bt5OZ9Pf3A9Df309msn379jpXJtXO0JequPBs3NWrV3Py5ElWr149rF2aTAx9qYAVK1bw2muvMW/ePF577TVWrFhR75KkMTH0pQL27t3LkiVLaGhoYMmSJezdu7feJUlj4nn6UgHnzp3j3XffZWBg4OK7NBk50peqGPmoRB+ZqMnM0Jeq6OvrY/bs2cNCf/bs2fT19dW5Mql2hr5UwJkzZ4Y9OevMmTP1LkkaE0NfKuixxx7jo48+4rHHHqt3KdKYGfpSAbNnz6a9vX3YuzQZGfpSAffee+/FWynPnDmTe++9t84VSWNj6EtVzJ07l5dffpl169bx0UcfsW7dOl5++WXmzp1b79Kkmhn6UhWbN29m1qxZbNy4kZkzZ7Jx40ZmzZrF5s2b612aVDNDX6pizZo1PPfcc8Pup//cc8+xZs2aepcm1cxn5ErSVcBn5ErjqKOjg+bmZhoaGmhubqajo6PeJUlj4nXkUhUdHR20tbXx/PPPc9ddd7Fr1y7Wr18P4BSPJh2nd6QqmpubaW9vH/akrM7OTlpbW3nrrbfqWJn0Kad3pHFy4MABuru7h03vdHd3c+DAgXqXJtXM6R2pihtvvJFvfOMbvPjiixendx566CFuvPHGepcm1czQlwo4d+4c69at49ixYyxatIhz5855KwZNSk7vSFW8//77NDY2AhARADQ2NvL+++/XsyxpTAx9qYqpU6fy+OOP884779Df388777zD448/ztSpU+tdmlQzQ1+qore3l82bN9PZ2cn58+fp7Oxk8+bN9Pb21rs0qWbO6UtVLFu2jPvvv5/W1lYOHDhAU1MTa9eu5dVXX613aVLNHOlLVbS1tbF9+3ba29v55JNPaG9vZ/v27bS1tdW7NKlmjvSlKi5cdTt0pL9p0yavxtWk5BW5knQVGNcrciPinog4FBFHImLjKOu/HBE/ioi+iHhgxLr+iPhx5bWj+J8gTRzecE1Xi6rTOxHRADwL/BbQDeyOiB2ZuX9It3eB3wX+YJRdfJyZXxqHWqW68IZrupoUGenfDhzJzLczsxd4CbhvaIfMPJqZbwIDl6FGqa42bdrE2rVraW1tZfr06bS2trJ27Vo2bdpU79KkmhU5kHsT8N6Q5W5gRQ3fMT0iuoA+4OnM/Mx5bhHxCPAIwMKFC2vYtXT57d+/n7Nnz/LCCy9cHOlfuCWDNNkUCf0Ypa2Wo78LM/N4RPwK8MOI2JuZPxm2s8ytwFYYPJBbw76ly27q1Knceeedw87eufPOO/npT39a79KkmhUJ/W7g5iHLC4DjRb8gM49X3t+OiL8Hfh34yeduJE0gPT09vPjiixeX9+3bx759++pYkTR2Reb0dwNLI2JJREwFHgQKnYUTEXMiYlrl8zzgTmD/528lSbpcqoZ+ZvYBG4CdwAHglczcFxFPRsRqgIj4zYjoBr4GbImIC8OgJqArIv4Z6GRwTt/Ql6Q68eIsqYoLt1MezUT7/0fl5eMSpXF2Ifw/70dAmugMfamgKVOmXHxJk5U3XJMK6u/vr3cJ0iVzyCIVNGvWrGHv0mTkSF+lVevc/JkzZ4a9F92HB3s1kTjSV2llZqHXhg0bRt1+w4YNhbaXJhJH+lIV7e3tAGzbto2enh6mTZvG17/+9Yvt0mTiefpSDRZv/B5Hn7633mVIn+F5+pKkzzD0JalEDH1JKhFDX5JKxNCXpBIx9CWpRAx9SSoRQ1+SSsTQl6QSMfQlqUQMfUkqEUNfkkrE0JekEjH0JalEDH1JKhFDX5JKxNCXpBIx9CWpRAx9SSoRQ1+SSsTQl6QSMfQlqUQMfUkqEUNfkkrE0JekEjH0JalEDH1JKpFCoR8R90TEoYg4EhEbR1n/5Yj4UUT0RcQDI9Y9HBGHK6+Hx6twSVLtqoZ+RDQAzwJfBZYBayJi2Yhu7wK/C2wfse1c4AlgBXA78EREzLn0siVJY1FkpH87cCQz387MXuAl4L6hHTLzaGa+CQyM2PYrwA8y81RmngZ+ANwzDnVLksagSOjfBLw3ZLm70lbEpWwrSRpnRUI/RmnLgvsvtG1EPBIRXRHRdfLkyYK7liTV6poCfbqBm4csLwCOF9x/N/BvRmz79yM7ZeZWYCtAS0tL0R8UaZhf++O/5Rcfn7/s37N44/cu6/6vm9HIPz+x6rJ+h8qrSOjvBpZGxBLgfeBBYG3B/e8Enhpy8HYV8HjNVUoF/OLj8xx9+t56l3HJLvePisqt6vROZvYBGxgM8APAK5m5LyKejIjVABHxmxHRDXwN2BIR+yrbngL+hMEfjt3Ak5U2SVIdFBnpk5nfB74/ou0Ph3zezeDUzWjbvgC8cAk1SpLGiVfkSlKJGPqSVCKGviSViKEvSSVi6EtSiRj6klQihr4klUih8/SlyWB200b+9V9+5nEPk87sJoDJf2WxJiZDX1eNjw487W0YpCqc3pGkEjH0JalEDH1JKhFDX5JKxNCXpBIx9CWpRAx9SSoRQ1+SSsTQl6QSMfQlqUQMfUkqEe+9o6vK1XDfmutmNNa7BF3FDH1dNa7EzdYWb/zeVXFTN5WX0zuSVCKGviSViKEvSSVi6EtSiRj6klQihr4klYihL0klYuhLUokY+pJUIoa+JJWIoS9JJWLoS1KJGPqSVCKGviSVSKHQj4h7IuJQRByJiI2jrJ8WES9X1v9TRCyutC+OiI8j4seV13PjW74kqRZV76cfEQ3As8BvAd3A7ojYkZn7h3RbD5zOzFsi4kHgm8B/qKz7SWZ+aZzrliSNQZGR/u3Akcx8OzN7gZeA+0b0uQ/4y8rn7wL/NiJi/MqUJI2HIqF/E/DekOXuStuofTKzD/gFcH1l3ZKI2BMR/xARd19ivZKkS1DkcYmjjdizYJ+fAgsz88OI+A3g1Yi4LTP/ZdjGEY8AjwAsXLiwQEmSpLEoMtLvBm4esrwAOP7L+kTENcB1wKnM7MnMDwEy8w3gJ8CtI78gM7dmZktmtsyfP7/2v0KSVEiR0N8NLI2IJRExFXgQ2DGizw7g4crnB4AfZmZGxPzKgWAi4leApcDb41O6JKlWVad3MrMvIjYAO4EG4IXM3BcRTwJdmbkDeB74TkQcAU4x+MMA8GXgyYjoA/qBRzPz1OX4QyRJ1RWZ0yczvw98f0TbHw75/AnwtVG2+2vgry+xRknSOPGKXEkqEUNfkkrE0JekEjH0JalEDH1JKhFDX5JKxNCXpBIx9CWpRAx9qYDly5cTERz75m8TESxfvrzeJUljYuhLVSxfvpy9e/cOa9u7d6/Br0nJ0JeqGBn41dqliazQvXekq9F4PNytyD4yRz5+QqofQ1+lVTSMPy/YDXRNNk7vSFKJGPqSVCKGviSViKEvSSVi6EtSiRj6klQihr4klYihL0klYuhLUokY+pJUIoa+JJWIoS9JJWLoS1KJGPqSVCKGviSViKEvFXTbbbdx7NgxbrvttnqXIo2ZD1GRCjp48CCLFi2ioaGh3qVIY+ZIXyqov79/2Ls0GRn6UkEXRviO9DWZGfpSFdOmTQM+O9K/0C5NJoa+VEVPT09N7dJEZuhLUokY+pJUIoVCPyLuiYhDEXEkIjaOsn5aRLxcWf9PEbF4yLrHK+2HIuIr41e6dGXNmTOHiGDOnDn1LkUas6qhHxENwLPAV4FlwJqIWDai23rgdGbeAvwP4JuVbZcBDwK3AfcA/6uyP2nSufvuuzlx4gR33313vUuRxqzIxVm3A0cy822AiHgJuA/YP6TPfcAfVT5/F9gcEVFpfykze4B3IuJIZX//OD7lS1fOjh07mD9/fr3LkC5Jkemdm4D3hix3V9pG7ZOZfcAvgOsLbktEPBIRXRHRdfLkyeLVS1fQ4Djm03dpMioS+qP9F54F+xTZlszcmpktmdniSEoTzapVqwDIzGHvF9qlyaRI6HcDNw9ZXgAc/2V9IuIa4DrgVMFtpQlt586drFq1athIf9WqVezcubPOlUm1KzKnvxtYGhFLgPcZPDC7dkSfHcDDDM7VPwD8MDMzInYA2yPivwM3AkuB/zdexUtXigGvq0XV0M/MvojYAOwEGoAXMnNfRDwJdGXmDuB54DuVA7WnGPxhoNLvFQYP+vYB/zkzvVuVJNVJXJifnChaWlqyq6ur3mVI0qQSEW9kZku1fl6RK0klYuhLUokY+pJUIhNuTj8iTgLH6l2H9EvMAz6odxHSKBZlZtULnSZc6EsTWUR0FTlYJk1UTu9IUokY+pJUIoa+VJut9S5AuhTO6UtSiTjSl6QSMfRVahGREfFnQ5b/ICL+qI4lSZeVoa+y6wH+fUTMq3ch0pVg6Kvs+hg8OPtfRq6IiEUR8XcR8WblfWGl/X9HxJ9HxOsR8XZEPDBkm8ciYndlmz++cn+GVIyhL8GzwEMRcd2I9s3AX2XmcuBF4M+HrPtXwF3AbwNPA0TEKgafGXE78CXgNyLiy5e5dqkmhr5KLzP/Bfgr4PdGrLoD2F75/B0GQ/6CVzNzIDP3A1+stK2qvPYAPwJ+lcEfAWnCKPLkLKkM/ieDQf0Xn9Nn6PnNPUM+x5D3/5aZW8a5NmncONKXgMw8BbwCrB/S/DqVp8ABDwG7quxmJ7AuImYBRMRNEfGF8a5VuhSGvvSpP2PwLpoX/B7wnyLiTeA/Ar//eRtn5t8yOB30jxGxF/guMPsy1SqNiVfkSlKJONKXpBIx9CWpRAx9SSoRQ1+SSsTQl6QSMfQlqUQMfUkqEUNfkkrk/wMY2hQJV2U+WAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import random\n",
    "\n",
    "target = random.choice(range(len(corpus)))\n",
    "others = [i for i in range(len(corpus)) if i != target]\n",
    "jsim = lambda i: jaccard(corpus[target], corpus[i])\n",
    "max_sim = max((jsim(i) for i in others))\n",
    "\n",
    "print(\"other doc with max. Jaccard similarity =\",\n",
    "      max_sim)\n",
    "\n",
    "sims = pd.Series(jsim(i) for i in others)\n",
    "print(\"Mean Jaccard similarity =\", sims.mean())\n",
    "print(\"Median Jaccard similarity =\", sims.median())\n",
    "sims.plot.box()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rerun the above cell a few times to get a feeling for the similarty.\n",
    "\n",
    "What you can see is that \"plain\" LSH will *not* be very useful for **clustering** our corpus (represented as _bags-of-words_), because most documents have a very low similiarty to each other.\n",
    "Rather, where LSH shines is detecting duplicates or even plagiarism, because then the Jaccard simliarity is (very) high.\n",
    "\n",
    "### LSH Forest setup\n",
    "\n",
    "A special variant of LSH, LSH *Forest*, is able to detect the best match for a query (document) if there is any reasonable Jaccard similarity between that query and some document in your collection.\n",
    "In addition, and as before for the document classification, we set up a TF-IDF document vectorizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/fnl/work/miniconda3/lib/python3.6/site-packages/sklearn/neighbors/approximate.py:220: DeprecationWarning: LSHForest has poor performance and has been deprecated in 0.19. It will be removed in version 0.21.\n",
      "  DeprecationWarning)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 8.59 s, sys: 407 ms, total: 9 s\n",
      "Wall time: 9.19 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "from sklearn.neighbors import LSHForest\n",
    "from sklearn.feature_extraction.text import TfidfVectorizer\n",
    "\n",
    "vectorizer = TfidfVectorizer(\n",
    "    sublinear_tf=True,\n",
    "    min_df=5,\n",
    "    max_df=0.5,\n",
    "    #ngram_range=(1,2),\n",
    "    token_pattern='(?u)(?:\\\\b|(?<=_))[^\\W_][^\\W_]+(?:\\\\b|(?=_))',\n",
    ")\n",
    "# train (aka, fit) the vectorizer to the train data:\n",
    "X_train = vectorizer.fit_transform(train.data)\n",
    "\n",
    "classifier = LSHForest(n_estimators=30, n_neighbors=1000)\n",
    "classifier.fit(X_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, we've indexed all our documents in virtually no time! Please let this sink in for a moment - most search engines spend ages indexing content, while this solution hardly spends any noticable time at all (compared to the collection size, over 11,000 documents). This property of LSH is *extremely* useful when working with document streams where you don't have much time to process each document!\n",
    "\n",
    "The parameter that has the strongest impact on indexing *and, particularly,* search times is `n_estimators`, but increasing it improves the retrieval quality. Depending on your needs, you will almost certainly want to adjust that parameter to your use-case. The `n_neighbors` parameter only sets the default number of documents returned by a query, but makes the queries  not noticably slower. For the reamining parameters, please refer to the [SciKit-Learn documentation](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LSHForest.html#sklearn.neighbors.LSHForest).\n",
    "\n",
    "## Document search\n",
    "\n",
    "Now, lets use this classifier to predict the nearest neighbor-ranked list for each of the \"test\" documents that we did not yet index (so this isn't just trivially returning exact matches)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2min 39s, sys: 8.62 s, total: 2min 48s\n",
      "Wall time: 3min 2s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\n",
    "# with the fitted vectorizer, transform the test data:\n",
    "X_test = vectorizer.transform(test.data)\n",
    "\n",
    "# now run the queries:\n",
    "indices = classifier.kneighbors(\n",
    "    X_test,\n",
    "    n_neighbors=1000,\n",
    "    return_distance=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is quite noteworthy here is the time it took to search our documents. We searched for around 7,000 documents in a pool of almost 12,000; So each query just took a small fraction of a second!\n",
    "\n",
    "## Evaluation\n",
    "\n",
    "Now we evaluate how good that index mechanism is.\n",
    "We will query the index with our test documents, only retrieving the best match from the indexed training documents.\n",
    "Then, we check if that retrieved training document indeed would have been the most similar document for that query document from the test set (in terms of Jaccard similarity).\n",
    "\n",
    "That is, we will evaluate the (mean) *true* rank of the returned document from LSH Forest by ordering all *training* documents against the query document using the Jaccard similarity measure.\n",
    "\n",
    "First, generate the list of the best matching training documents for all test documents:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best prediction true rank =  8801 with sim = 0.053 ; #1 doc sim = 0.121\n",
      "best prediction true rank =     1 with sim = 0.213 ; #1 doc sim = 0.213\n",
      "best prediction true rank =  5770 with sim = 0.087 ; #1 doc sim = 0.249\n",
      "best prediction true rank =   385 with sim = 0.095 ; #1 doc sim = 0.143\n",
      "best prediction true rank =  7478 with sim = 0.066 ; #1 doc sim = 0.164\n",
      "best prediction true rank =    60 with sim = 0.131 ; #1 doc sim = 0.161\n",
      "best prediction true rank =     2 with sim = 0.342 ; #1 doc sim = 0.348\n",
      "best prediction true rank =     2 with sim = 0.150 ; #1 doc sim = 0.152\n",
      "best prediction true rank =    66 with sim = 0.113 ; #1 doc sim = 0.142\n",
      "best prediction true rank =     1 with sim = 0.274 ; #1 doc sim = 0.274\n",
      "best prediction true rank =    20 with sim = 0.097 ; #1 doc sim = 0.187\n",
      "best prediction true rank =  6564 with sim = 0.072 ; #1 doc sim = 0.178\n",
      "best prediction true rank =     2 with sim = 0.247 ; #1 doc sim = 0.299\n",
      "best prediction true rank =    33 with sim = 0.146 ; #1 doc sim = 0.169\n",
      "best prediction true rank =     1 with sim = 0.255 ; #1 doc sim = 0.255\n",
      "\n",
      "mean reciprocal rank = 0.268\n",
      "median rank = 31\n",
      "\n",
      "CPU times: user 37.4 s, sys: 1.11 s, total: 38.5 s\n",
      "Wall time: 40.2 s\n"
     ]
    }
   ],
   "source": [
    "%%time \n",
    "\n",
    "from statistics import median\n",
    "\n",
    "trr = 0. # total reciprocal ranks\n",
    "ranks = []\n",
    "n_queries = len(test['data']) // 100 # do 1% only\n",
    "samples = random.sample(list(enumerate(indices)), n_queries)\n",
    "\n",
    "for i, predictions in samples:\n",
    "    # query document from\n",
    "    query = frozenset(shingle(test['data'][i]))\n",
    "    prediction = predictions[0]\n",
    "    \n",
    "    # compare the query doc to each doc in training set\n",
    "    # this is the most costly part\n",
    "    pairs = [(jaccard(doc, query), idx)\n",
    "             for idx, doc in enumerate(corpus)]\n",
    "    \n",
    "    # sort and reverse the results (also costly, but much less)\n",
    "    pairs = list(reversed(sorted(pairs)))\n",
    "    \n",
    "    # finally, generate and print some statistics for evaluation\n",
    "    max_similarity = pairs[0][0]\n",
    "    _, correct_ranking = zip(*pairs)\n",
    "    rank = correct_ranking.index(prediction) + 1\n",
    "    sim = 0.0\n",
    "    \n",
    "    if rank == 0: # rank last if nothing found\n",
    "        rank = len(corpus)\n",
    "    else: # get the Jaccard similarity for the matched doc \n",
    "        sim = pairs[rank-1][0]\n",
    "\n",
    "    trr += 1 / rank\n",
    "    ranks.append(rank)\n",
    "        \n",
    "    # report a few cases\n",
    "    if random.random() < 0.2:\n",
    "        print(\"best prediction true rank = %5d\" % rank,\n",
    "              \"with sim = %.3f\" % sim,\n",
    "              \"; #1 doc sim = %.3f\" % max_similarity)\n",
    "\n",
    "mrr = trr / n_queries # mean reciprocal rank\n",
    "print(\"\\nmean reciprocal rank = %.3f\" % mrr)\n",
    "print(\"median rank = %d\\n\" % median(ranks))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, this process is around one to two orders of magnitude slower (notice that we queried 100 times less documents than before against LSH Forest, but that fraction about the same time to run). Notice that pairwise lookups scale with the number of documents in the index, while LSH Forest (mostly) just scales with the number of trees (`n_estimators`).\n",
    "\n",
    "Another useful insight is that when the predicted document isn't the first, the overall best document (\"`true doc: sim.`\") tends to be of relatively low similarity, too. So this is maybe not perfect, but at least it does not fail for the \"obvious\" cases (with high similarities), only for the less clear-cut matches.\n",
    "\n",
    "Therefore, let's look at the other important evaluation scenario: How many documents, on average, would this LSH Forest have to report to cover the truly best match - letting us estimate how big the sets we want to retrieve should be (and the number of pairwise comparisons needed to rank that set against the query)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mean reciprocal rank = 0.736\n",
      "median rank = 1\n",
      "cache misses = 45\n",
      "\n",
      "CPU times: user 40.5 s, sys: 489 ms, total: 41 s\n",
      "Wall time: 46.2 s\n"
     ]
    }
   ],
   "source": [
    "%%time \n",
    "\n",
    "trr = 0.0 # total reciprocal ranks\n",
    "ranks = []\n",
    "misses = 0\n",
    "n_queries = len(test['data']) // 100 # do 1% only\n",
    "samples = random.sample(list(enumerate(indices)), n_queries)\n",
    "\n",
    "for i, predictions in samples:\n",
    "    query = frozenset(shingle(test['data'][i]))\n",
    "    \n",
    "    # compare the query doc to each doc in training set\n",
    "    pairs = [(jaccard(doc, query), idx)\n",
    "             for idx, doc in enumerate(corpus)]\n",
    "    \n",
    "    # reverse-sort the results by Jaccard similarity\n",
    "    pairs = list(reversed(sorted(pairs)))\n",
    "    \n",
    "    # finally, generate and print some statistics for evaluation\n",
    "    best_doc = pairs[0][1]\n",
    "    \n",
    "    try:\n",
    "        rank = np.where(predictions==best_doc)[0][0] + 1\n",
    "        trr += 1 / rank\n",
    "        ranks.append(rank)\n",
    "    except IndexError:\n",
    "        misses += 1\n",
    "\n",
    "mrr = trr / (n_queries - misses) # mean reciprocal rank\n",
    "print(\"mean reciprocal rank = %.3f\" % mrr)\n",
    "print(\"median rank = %d\" % median(ranks))\n",
    "# n. times the top 1000 did not contain the best match at all:\n",
    "print(\"cache misses = %d\\n\" % misses) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, this is a bit more clarifying. So we do have about half of our cases where we don't find the top match at all. I.e., our LSH Forest returns a set of good matches, but it does not necessarily return the best match. So depending on your use-case beware of this.\n",
    "\n",
    "## Conclusion\n",
    "\n",
    "You can build very efficient and very simple document and query search engines with LSH Forest and LSH Ensemble, but the overall performance only gives you a \"sketchy\" view of the true result, i.e., with holes. Admittedly, document clustering with LSH is a bit of a black art. But then, about any data sketching is mostly black art... However, getting this right is extremely rewarding, because indexing documents using only (tree) hashes is probably the most performant and scalable path towards building a super-fast algorithms. Overall, LSH is a great technique to locate near-duplicate documents or highly similar terms with just a few typos."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}