{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "28a39cd3",
   "metadata": {},
   "source": [
    "# Set Similarity"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "435dc503",
   "metadata": {},
   "source": [
    "When we are given a dataset of documents, which can be news articles, webpages, item descriptions, and we are asked to determine how similar these documents are, the naive approach is to compare each possible pair then compute for the similarity of each pair. However, as we may guess, this approach is quite expensive as it requires looking at all pairs.\n",
    "\n",
    "This would mean that for a given $N$ document, looking at all the pairs would take roughly $O(N^2)$ time (Equation \\ref{brute-force}):\n",
    "\n",
    "$$\n",
    "\\frac{N!}{2! (N - 2)!} \\sim N^2/2 \\sim O(N^2) \\tag{1} \\label{brute-force}\n",
    "$$\n",
    "\n",
    "Throughout this chapter, we will discuss one way we can approximate the computation of this simlarity through the use of *hashing* functions, specifically, **Locality-Sensitive Hashing (LSH)**, which allows us to focus on pairs that are likely to be similar without looking at all the pairs. These fucntions are built to contain property that pairs that are more similar tend to be on the same bucket defined by the hash functions.\n",
    "\n",
    "To build our understanding of LSH, we first need to define a metric that allows us to evaluate the similarity of the pairs of items. In this section, we discuss the notion of the **Jaccard Similarity** of sets, as this will be the basis in which we will define our LSH. Such LSH define in this metric is called **Minhash functions** which we will discuss in [Section 3](./minhashing.ipynb) of this Chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d95f869",
   "metadata": {},
   "source": [
    "## Jaccard Similarity of Sets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa902965",
   "metadata": {},
   "source": [
    "```{figure} ./images/jaccard-similarity.png\n",
    ":name: jaccard-similarity\n",
    ":width: 400px\n",
    "\n",
    "Two sets A and B having a Jaccard similarity of 3/9.\n",
    "```\n",
    "\n",
    "**Jaccard Similarity** is a metric defined as the similarity of the sets in relation to the size of their intersection (See {numref}`jaccard-similarity`). "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f90afefe",
   "metadata": {},
   "source": [
    "Mathematically, if we are given two sets $A$ and $B$, the Jaccard Similarity which we denote as $SIM(A, B)$ is given by:\n",
    "\n",
    "$$\n",
    "SIM(A, B) = \\frac{|A \\cap B |}{| A \\cup B |} \\tag{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2db8f35d",
   "metadata": {},
   "source": [
    "### Example 1: Calculating the Jaccard Similarity of two sets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50de2a35",
   "metadata": {},
   "source": [
    "Two movie goers have watch the following shows:\n",
    "\n",
    "```\n",
    "Leo = {'Detachment (2011)', 'Hotel Transylvania (2012)', 'Interstellar (2014)', 'The Godfather (1972)'}\n",
    "Mike = {'Interstellar (2014)', 'Hotel Transylvania (2012)', 'October Sky (1999)', 'American Beauty (1999)'}\n",
    "```\n",
    "\n",
    "Compute for the Jaccard Similarity of these two users."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a7c873e",
   "metadata": {},
   "source": [
    "#### Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "910cd227",
   "metadata": {},
   "source": [
    "Let us denote $L$ and $M$ as the movies that Leo and Mike watched respectively. Mathematically, we can compute for the intersection and union of each sets as:\n",
    "\n",
    "$$\n",
    "L \\cap M =  \\text{{'Interstellar (2014)', 'Hotel Transylvania (2012)'}} \\\\\n",
    "L \\cup M = \\text{{'Interstellar (2014)', 'Hotel Transylvania (2012)', 'October Sky (1999)', 'American Beauty (1999)', 'Detachment (2011)', 'The Godfather (1972)'}}\n",
    "$$\n",
    "\n",
    "Afterwards, verifying that the length of intersection between the two set is 2, while the length of the union of the two sets is 6, we get the Jaccard Similarity as:\n",
    "\n",
    "$$\n",
    "SIM(L, M) = \\frac{2}{6} = \\frac{1}{3}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14407058",
   "metadata": {},
   "source": [
    "We can also solve the problem using Python. First we define the two sets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d3d69cda",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-28T08:03:06.928608Z",
     "start_time": "2022-03-28T08:03:06.910653Z"
    }
   },
   "outputs": [],
   "source": [
    "L = {'Detachment (2011)', 'Hotel Transylvania (2012)', 'Interstellar (2014)',\n",
    "     'The Godfather (1972)'}\n",
    "M = {'Interstellar (2014)', 'Hotel Transylvania (2012)', 'October Sky (1999)',\n",
    "     'American Beauty (1999)'}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "632fcede",
   "metadata": {},
   "source": [
    "Then compute the length of their intersection nad length of their union."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "f796a3be",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-28T08:04:28.764402Z",
     "start_time": "2022-03-28T08:04:28.758802Z"
    }
   },
   "outputs": [],
   "source": [
    "intersection_length = len(L.intersection(M))\n",
    "union_length = len(L.union(M))\n",
    "\n",
    "jaccard_LM = intersection_length / union_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b48ed532",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-28T08:04:29.305400Z",
     "start_time": "2022-03-28T08:04:29.299687Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Jaccard Similarity of L and M is 0.333\n"
     ]
    }
   ],
   "source": [
    "print(f\"The Jaccard Similarity of L and M is {jaccard_LM:.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41597e73",
   "metadata": {},
   "source": [
    "## Characteristic Matrix Representation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78c0a5c9",
   "metadata": {},
   "source": [
    "We may also represent the sets $L$ and $M$ and all the movie items in the universe as a **characteristic matrix**. Here, the columns of the matrix corresponds to the sets, and the rows corresponds to the elements of the universal sets. In this representation, the $L$ and $M$ sets chosen from the universal set of `{I, HT, OS, AB, D, TG}` may be written as:\n",
    "\n",
    "| | L | M |\n",
    "|-|-----|-----|\n",
    "|I| 1 | 1 |\n",
    "|HT | 1 | 1 |\n",
    "|OS| 0 |1|\n",
    "|AB| 0 |1|\n",
    "|D| 1 | 0|\n",
    "|TG| 1 |0|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67eaa70e",
   "metadata": {
    "raw_mimetype": "text/markdown"
   },
   "source": [
    "```{eval-rst}\n",
    "We leave it as an exercise for the reader for them how to define the jaccard similarity given a characteristic matrix representation. However, using the ``alis`` API function :py:func:`~alis.similarity._jaccard.jaccard_sim` from the :py:mod:`alis.similarity` module, this can be done as follows:\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "dd5bee86",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-28T08:24:41.660946Z",
     "start_time": "2022-03-28T08:24:41.643336Z"
    }
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from alis.similarity import jaccard_sim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b6a72162",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-03-28T08:25:21.576817Z",
     "start_time": "2022-03-28T08:25:21.562270Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.33333333333333337"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "characteristic_matrix = np.array(\n",
    "    [[1, 1],\n",
    "     [1, 1],\n",
    "     [0, 1],\n",
    "     [0, 1],\n",
    "     [1, 0],\n",
    "     [1, 0]])\n",
    "\n",
    "jaccard_sim(characteristic_matrix, 0, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45501635",
   "metadata": {},
   "source": [
    "We get the same result as what we previously computed earlier mathematically and using set operations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5145014",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a93dfdf",
   "metadata": {},
   "source": [
    "### Exercise 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d13c1348",
   "metadata": {},
   "source": [
    "Compute for the Jaccard similarity between each pair of the following sets:\n",
    "\n",
    "```\n",
    "L = {'A', 'B', 'C', 'D', 'E'}\n",
    "M = {'B', 'C', 'F', 'G', 'H'}\n",
    "N = {'F', 'H', 'A', 'B'}\n",
    "```\n",
    "\n",
    "Try to construct the characteristic matrix of the above sets along with the universal items then use the `jaccard_sim` function to easily compute the Jaccard similarity of each pairs."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "interpreter": {
   "hash": "7039502ba4c31c57de5b26608ea91fac1d3675b0a01e61c2984de922cfd5c530"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}