Locality_Sensitive_Hashing_and_Distance_Measures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Locality-Sensitive Hashing and Distance Measures\n",
    "## Question 1\n",
    "The edit distance is the minimum number of character insertions and character deletions required to turn one string into another. Compute the edit distance between each pair of the strings he, she, his, and hers. Then, identify the pairs at each edit distance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def lcs(a, b):\n",
    "    lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]\n",
    "    for i, x in enumerate(a):\n",
    "        for j, y in enumerate(b):\n",
    "            if x == y:\n",
    "                lengths[i+1][j+1] = lengths[i][j] + 1\n",
    "            else:\n",
    "                lengths[i+1][j+1] = max(lengths[i+1][j], lengths[i][j+1])\n",
    "    # read the substring out from the matrix\n",
    "    result = \"\"\n",
    "    x, y = len(a), len(b)\n",
    "    while x != 0 and y != 0:\n",
    "        if lengths[x][y] == lengths[x-1][y]:\n",
    "            x -= 1\n",
    "        elif lengths[x][y] == lengths[x][y-1]:\n",
    "            y -= 1\n",
    "        else:\n",
    "            assert a[x-1] == b[y-1]\n",
    "            result = a[x-1] + result\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 [('he', 'she')]\n",
      "2 [('he', 'hers')]\n",
      "3 [('he', 'his'), ('she', 'hers'), ('his', 'hers')]\n",
      "4 [('she', 'his')]\n"
     ]
    }
   ],
   "source": [
    "strings = [\"he\",\"she\",\"his\",\"hers\"]\n",
    "pairs =  list(combinations(strings,2))\n",
    "\n",
    "length = defaultdict(list)\n",
    "for pair in pairs:\n",
    "    x = pair[0]\n",
    "    y = pair[1]\n",
    "    dist = len(x) + len(y) - 2 * (len(lcs(x,y)))\n",
    "    length[dist].append((x,y))\n",
    "\n",
    "for k,v in length.items():\n",
    "    print k,v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2\n",
    "Consider the following matrix:\n",
    "\n",
    "    |   | C1 | C2 | C3 | C4 |\n",
    "    |R1 | 0 | 1 | 1 | 0 |\n",
    "    |R2 | 1 | 0 | 1 | 1 |\n",
    "    |R3 | 0 | 1 | 0 | 1 |\n",
    "    |R4 | 0 | 0 | 1 | 0 |\n",
    "    |R5 | 1 | 0 | 1 | 0 |\n",
    "    |R6 | 0 | 1 | 0 | 0 |\n",
    "\n",
    "Perform a minhashing of the data, with the order of rows: R4, R6, R1, R3, R5, R2. Which of the following is the correct minhash value of the stated column? Note: we give the minhash value in terms of the original name of the row, rather than the order of the row in the permutation. These two schemes are equivalent, since we only care whether hash values for two columns are equal, not what their actual values are."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def convertToRows(minhash_row, order):\n",
    "    the_rows = []\n",
    "\n",
    "    for item in minhash_row:\n",
    "        the_rows.append(order[item - 1])\n",
    "\n",
    "    return the_rows\n",
    "\n",
    "def minhash(matrix, order):\n",
    "    m = matrix.shape[1]\n",
    "    minhash_row = [0] * m\n",
    "    i = 1\n",
    "\n",
    "    for r in order:\n",
    "        row = matrix[r - 1]\n",
    "        for c in range(0, m):\n",
    "            if minhash_row[c] == 0:\n",
    "                minhash_row[c] = i * row[c]\n",
    "        i += 1\n",
    "        if 0 not in minhash_row:\n",
    "            break\n",
    "\n",
    "    return minhash_row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 6, 4, 3]\n"
     ]
    }
   ],
   "source": [
    "matrix = np.array([[0, 1, 1, 0],\n",
    "                   [1, 0, 1, 1],\n",
    "                   [0, 1, 0, 1],\n",
    "                   [0, 0, 1, 0],\n",
    "                   [1, 0, 1, 0],\n",
    "                   [0, 1, 0, 0]])\n",
    "order = [4, 6, 1, 3, 5, 2]\n",
    "minhash_row = minhash(matrix, order)\n",
    "rows_that_contributed = convertToRows(minhash_row, order)\n",
    "print(rows_that_contributed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3\n",
    "Consider a matrix representing the signatures of seven columns, C1 through C7:\n",
    "\n",
    "    |C1 |C2 |C3 |C4 |C5 |C6 |C7|\n",
    "    |1 |2 |1 |1 |2 |5 |4\n",
    "    |2 |3 |4 |2 |3 |2 |2|\n",
    "    |3 |1 |2 |3 |1 |3 |2|\n",
    "    |4 |1 |3 |1 |2 |4 |4|\n",
    "    |5 |2 |5 |1 |1 |5 |1|\n",
    "    |6 |1 |6 |4 |1 |1 |4|\n",
    "\n",
    "Suppose we use locality-sensitive hashing with three bands of two rows each. Assume there are enough buckets available that the hash function for each band can be the identity function (i.e., columns hash to the same bucket if and only if they are identical in the band). Find all the candidate pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Candidate pairs:\n",
      "C1,C4\n",
      "C2,C5\n",
      "C1,C6\n",
      "C1,C3\n",
      "C4,C7\n"
     ]
    }
   ],
   "source": [
    "def candPair(x, y):\n",
    "    i = 0\n",
    "    while i < len(x):\n",
    "        j = i + 1\n",
    "        while j < len(x):\n",
    "            if x[i] == x [j] and y[i] == y[j]:\n",
    "                print \"C%s,C%s\" % (i+1,j+1)\n",
    "            j += 1\n",
    "        i += 1\n",
    "\n",
    "print \"Candidate pairs:\"\n",
    "candPair([1,2,1,1,2,5,4], [2,3,4,2,3,2,2])\n",
    "candPair([3,1,2,3,1,3,2], [4,1,3,1,2,4,4])\n",
    "candPair([5,2,5,1,1,5,1], [6,1,6,4,1,1,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4\n",
    "Find the set of 2-shingles for the \"document\": ABRACADABRA and also for the \"document\": BRICABRAC. Answer the following questions:\n",
    "\n",
    "1. How many 2-shingles does ABRACADABRA have?\n",
    "2. How many 2-shingles does BRICABRAC have?\n",
    "3. How many 2-shingles do they have in common?\n",
    "4. What is the Jaccard similarity between the two documents\"?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "str1 = \"ABRACADABRA\"\n",
    "str2 = \"BRICABRAC\"\n",
    "\n",
    "def getShingles(str):\n",
    "    shingles = []\n",
    "    doc_shingles = []\n",
    "    for i in range(len(str)-1):\n",
    "        shingles.append(str[i]+str[i+1])\n",
    "    return set(shingles)\n",
    "        \n",
    "def getCommon(list1,list2):\n",
    "    s1 = set(list1)\n",
    "    s2 = set(list2)\n",
    "    return len(s1.intersection(s2))\n",
    "\n",
    "def getTotal(list1,list2):\n",
    "    s1 = set(list1)\n",
    "    s2 = set(list2)\n",
    "    return len(s1.union(s2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Set of 2-shinlges in ABRACADABRA = set(['AC', 'AB', 'AD', 'CA', 'DA', 'RA', 'BR'])\n",
      "Set of 2-shinlges in BRICABRAC = set(['AC', 'AB', 'CA', 'RA', 'BR', 'IC', 'RI'])\n",
      "\n",
      "Number of 2-shinlges in ABRACADABRA =  7\n",
      "Number of 2-shinlges in BRICABRAC =  7\n",
      "\n",
      "Number of Common Shingles =  5\n",
      "Total Number of Shingles =  9\n"
     ]
    }
   ],
   "source": [
    "print \"Set of 2-shinlges in ABRACADABRA =\",  getShingles(str1)\n",
    "print \"Set of 2-shinlges in BRICABRAC =\", getShingles(str2)\n",
    "print\n",
    "print \"Number of 2-shinlges in ABRACADABRA = \", len(getShingles(str1))\n",
    "print \"Number of 2-shinlges in BRICABRAC = \", len(getShingles(str2))\n",
    "print\n",
    "print \"Number of Common Shingles = \", getCommon(getShingles(str1),getShingles(str2))\n",
    "print \"Total Number of Shingles = \", getTotal(getShingles(str1),getShingles(str2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5\n",
    "How many distinct 3-shingles are there in the string \"hello world\" (excluding the quotes)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hel\n",
      "ell\n",
      "llo\n",
      "lo \n",
      "o w\n",
      " wo\n",
      "wor\n",
      "orl\n",
      "rld\n",
      "\n",
      "set(['lo ', 'ell', ' wo', 'wor', 'orl', 'o w', 'llo', 'rld', 'hel'])\n",
      "\n",
      "Number of 3-shinlges in \"hello world\" = 9\n"
     ]
    }
   ],
   "source": [
    "str1 = \"hello world\"\n",
    "\n",
    "def shingle(str):\n",
    "    s = set()\n",
    "    for i,c in enumerate(str):\n",
    "        if i < len(str) - 2:\n",
    "            shing = c+str[i+1]+str[i+2]\n",
    "            print shing\n",
    "            s.add(shing)\n",
    "    print\n",
    "    print s\n",
    "    return s\n",
    "\n",
    "shingle1 = shingle(str1)\n",
    "print \n",
    "print('Number of 3-shinlges in \"hello world\" = '+str(len(shingle1)));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 6\n",
    "Suppose we want to assign points to whichever of the points (0,0) or (100,40) is nearer. Depending on whether we use the L1 or L2 norm, a point (x,y) could be clustered with a different one of these two points. For this problem, you should work out the conditions under which a point will be assigned to (0,0) when the L1 norm is used, but assigned to (100,40) when the L2 norm is used. Identify one of those points from the list: (50,18), (53,15), (56,15), (52,13)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(50, 18)\n",
      "(50, 18) assigned to (0, 0) under L1 norm\n",
      "(50, 18) assigned to (0, 0) under L2 norm\n",
      "\n",
      "(53, 15)\n",
      "(53, 15) assigned to (0, 0) under L1 norm\n",
      "(53, 15) assigned to (100, 40) under L2 norm\n",
      "\n",
      "(56, 15)\n",
      "(56, 15) assigned to (100, 40) under L1 norm\n",
      "(56, 15) assigned to (100, 40) under L2 norm\n",
      "\n",
      "(52, 13)\n",
      "(52, 13) assigned to (0, 0) under L1 norm\n",
      "(52, 13) assigned to (0, 0) under L2 norm\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def distance(pt1, pt2, norm=2):\n",
    "    differences = sum(abs(coord1-coord2)**norm for coord1, coord2 in zip(pt1,pt2))\n",
    "    return np.power(differences, 1./norm)\n",
    "\n",
    "for pt1 in ((50,18), (53,15), (56,15), (52,13)):\n",
    "    print pt1\n",
    "    for norm in range(1,3):\n",
    "        pt2 = ((0,0), (100,40))\n",
    "        one = distance(pt1, pt2[0], norm=norm)\n",
    "        two = distance(pt1, pt2[1], norm=norm)\n",
    "        if one < two:\n",
    "            print pt1, \"assigned to\", pt2[0], \"under L{} norm\".format(norm)\n",
    "        else:\n",
    "            print pt1, \"assigned to\", pt2[1], \"under L{} norm\".format(norm)\n",
    "    print"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 7\n",
    "Suppose we have an LSH family h of (d1,d2,.6,.4) hash functions. We can use three functions from h and the AND-construction to form a (d1,d2,w,x) family, and we can use two functions from h and the OR-construction to form a (d1,d2,y,z) family. Calculate w, x, y, and z."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# import numpy as np\n",
    "\n",
    "# LSH family h (d1, d2, p1, p2) = (d1, d2, 0.6, 0.4)\n",
    "p1 = 0.6\n",
    "p2 = 0.4\n",
    "\n",
    "# We can use three functions from h and the AND-construction to form a (d1,d2,w,x) family\n",
    "# we cube the probabilities associated with h\n",
    "# (d1, d2, (p1)^3, (p2)^3)\n",
    "def AND_hash(p):\n",
    "    return p ** 3\n",
    "# w = np.power(p1, 3)\n",
    "# x = np.power(p2, 3)\n",
    "\n",
    "# We can use two functions from h and the OR-construction to form a (d1,d2,y,z) family\n",
    "# we take each probability associated with h, subtract it from 1, \n",
    "# square the result, and subtract that from 1\n",
    "def OR_hash(p):\n",
    "    return 1 - (1-p) ** 2\n",
    "# y = 1 - np.power(1 - p1, 2)\n",
    "# z = 1 - np.power(1 - p2, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w = 0.216\n",
      "x = 0.064\n",
      "y = 0.84\n",
      "z = 0.64\n"
     ]
    }
   ],
   "source": [
    "print \"w =\", AND_hash(p1)\n",
    "print \"x =\", AND_hash(p2)\n",
    "print \"y =\", OR_hash(p1)\n",
    "print \"z =\", OR_hash(p2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 8\n",
    "There are 8 strings that represent sets: s1 = abcef; s2 = acdeg; s3 = bcdefg; s4 = adfg; s5 = bcdfgh; s6 = bceg; s7 = cdfg; s8 = abcd. The upper limit on Jaccard distance is 0.2, and we index the strings based on symbols appearing in the prefix. For each of s1, s3, and s6, determine how many other strings that string will be compared with, if it is used as the probe string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# The 8 strings that represent sets:\n",
    "s1 = \"abcef\"\n",
    "s2 = \"acdeg\"\n",
    "s3 = \"bcdefg\"\n",
    "s4 = \"adfg\"\n",
    "s5 = \"bcdfgh\"\n",
    "s6 = \"bceg\"\n",
    "s7 = \"cdfg\"\n",
    "s8 = \"abcd\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Prefix lenth of s1 to s8: [2, 2, 2, 1, 2, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "# Upper limit on Jaccard distance is 0.2\n",
    "# We index a string of length L on the symbols appearing in its prefix of length floor(0.2L+1)\n",
    "# Strings of length 5 and 6 are indexed on their first 2 symbols\n",
    "# Strings of length 4 are indexed on their first symbol\n",
    "Jaccard = 0.2\n",
    "\n",
    "def prefxlen(str, Jaccard):\n",
    "    return int(np.floor(len(str)*Jaccard + 1))\n",
    "\n",
    "s = [s1, s2, s3, s4, s5, s6, s7, s8]\n",
    "length = map(lambda s: prefxlen(s, Jaccard), s)\n",
    "print \"Prefix lenth of s1 to s8:\", length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "strings in a, b and c: {'a': ['abcef', 'acdeg', 'adfg', 'abcd'], 'c': ['acdeg', 'bcdefg', 'bcdfgh', 'cdfg'], 'b': ['abcef', 'bcdefg', 'bcdfgh', 'bceg']}\n"
     ]
    }
   ],
   "source": [
    "# We want to find the strings in index a, b and c\n",
    "def index(str):\n",
    "    indx = {}\n",
    "    for s in str:\n",
    "        for l in range(prefxlen(s, Jaccard)):\n",
    "            if s[l] in indx:\n",
    "                indx[s[l]].append(s)\n",
    "            else:\n",
    "                indx[s[l]] = [s]   \n",
    "    return indx\n",
    "    \n",
    "indx = index(s)\n",
    "print \"strings in a, b and c:\", indx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "String, number of strings for comparisons, set of strings for comparisons:\n",
      "('abcef', 6, set(['abcd', 'bcdfgh', 'acdeg', 'adfg', 'bceg', 'bcdefg']))\n",
      "('bcdefg', 5, set(['cdfg', 'abcef', 'bcdfgh', 'acdeg', 'bceg']))\n",
      "('bceg', 3, set(['bcdfgh', 'abcef', 'bcdefg']))\n"
     ]
    }
   ],
   "source": [
    "# Number of strings compared with each of s1, s3 and s6 when it is used as the probe string\n",
    "def count(indx, s):\n",
    "    counts = set(sum([indx[s[l]] for l in range(prefxlen(s, Jaccard))], []))\n",
    "    counts.remove(s)\n",
    "    return (s, len(counts), counts)\n",
    "\n",
    "print \"String, number of strings for comparisons, set of strings for comparisons:\" \n",
    "for s in [s1, s3, s6]:\n",
    "    print count(indx, s)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}