{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Populating the interactive namespace from numpy and matplotlib\n"
]
}
],
"source": [
"%pylab inline\n",
"import pandas as pd\n",
"\n",
"import numpy as np\n",
"from __future__ import division\n",
"import itertools\n",
"\n",
"import matplotlib.pyplot as plt\n",
"import seaborn as sns\n",
"\n",
"import logging\n",
"logger = logging.getLogger()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"3 Finding Similar Items\n",
"===================\n",
"Problem: \n",
"+ \"similar\": finding sets with a relatively large intersection. \n",
" - shingling \n",
" - minhashing \n",
"+ too many pairs of items to test \n",
" - locality-sentitive hashing\n",
" \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3.1 Applications of Near-Neighbor Search\n",
"\n",
"The *Jaccard Similarity* of sets $S$ and $T$:\n",
"\\begin{equation}\n",
"SIM(S,T) = \\frac{| S \\cup T |}{| S \\cap T |}\n",
"\\end{equation}\n",
"\n",
"##### Similar-sets Problem\n",
"1. Similar Documents \n",
"In many applicatons, the documents are not identical, yet they share large portions of their text. \n",
"eg: Plagiarism, Mirror Pages, Articles from the Same Source. \n",
"2. Collaborative Filtering(Similar Tastes) \n",
"eg: \n",
" + Online Purchases \n",
" + Movie Ratings \n",
" When data is not binary: \n",
" - Ignore low-rated customer/movie pairs \n",
" - \"liked\" VS \"hated\" \n",
" - 1-to-5-starts, put it in a set $n$ times. <= _Jaccard similarity for bags_\n",
" \n",
"##### Exercises"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"a:set([1, 2, 3, 4]), b:set([2, 3, 5, 7]), SIM:0.333\n",
"a:set([1, 2, 3, 4]), b:set([2, 4, 6]), SIM:0.400\n",
"a:set([2, 3, 5, 7]), b:set([2, 4, 6]), SIM:0.167\n"
]
}
],
"source": [
"#Exercise 3.1.1\n",
"logger.setLevel(logging.WARNING)\n",
"\n",
"data = [\n",
" set([1, 2, 3, 4]),\n",
" set([2, 3, 5, 7]),\n",
" set([2, 4, 6]),\n",
"]\n",
"\n",
"def Jaccard_similarity_calc(set_a, set_b):\n",
" \"\"\"calculate the Jaccard similarity of two sets\n",
" \n",
" res = \\frac{a \\cap b}{a \\cup b}\n",
" \"\"\"\n",
" \n",
" assert isinstance(set_a, set), '{} is not a set'.format(set_a)\n",
" assert isinstance(set_b, set), '{} is not a set'.format(set_b)\n",
" \n",
" logging.debug('a:{}, b:{}'.format(set_a, set_b))\n",
" logging.debug('inter:{}, union:{}'.format(set_a.intersection(set_b), set_a.union(set_b)))\n",
" return len(set_a.intersection(set_b)) / len(set_a.union(set_b))\n",
"\n",
"for comb in list(itertools.combinations(range(3),2)):\n",
" set_a, set_b = data[comb[0]], data[comb[1]]\n",
" print('a:{}, b:{}, SIM:{:.3f}'.format(set_a, set_b, Jaccard_similarity_calc(set_a, set_b)))\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"a:[1, 1, 1, 2], b:[1, 1, 2, 2, 3], JbSIM:0.333\n",
"a:[1, 1, 1, 2], b:[1, 2, 3, 4], JbSIM:0.250\n",
"a:[1, 1, 2, 2, 3], b:[1, 2, 3, 4], JbSIM:0.333\n"
]
}
],
"source": [
"#Exercise 3.1.2\n",
"logger.setLevel(logging.WARNING)\n",
"\n",
"data = [\n",
" [1, 1, 1, 2],\n",
" [1, 1, 2, 2, 3],\n",
" [1, 2, 3, 4],\n",
"]\n",
"\n",
"def Jaccard_bag_similarity_calc(a, b):\n",
" \"\"\"calculate the Jaccard bag similarity of two sets\n",
" \n",
" see page 76, movie ratings 3.\n",
" intersecton = min(times of element in the two sets)\n",
" union = sum of length of the two sets\n",
" res = intersection / union\n",
" \"\"\"\n",
" \n",
" from collections import Counter\n",
" \n",
" count_a = Counter(a)\n",
" count_b = Counter(b)\n",
" logging.debug('count_a:{}\\n count_b:{}'.format(count_a,count_b))\n",
" \n",
" inter = [min(count_a[x], count_b[x]) for x in count_a if x in count_b]\n",
" logging.debug('intersection:{}'.format(inter))\n",
" \n",
" return sum(inter) / (len(a) + len(b))\n",
" \n",
"for comb in list(itertools.combinations(range(3),2)):\n",
" set_a, set_b = data[comb[0]], data[comb[1]]\n",
" print('a:{}, b:{}, JbSIM:{:.3f}'.format(set_a, set_b, Jaccard_bag_similarity_calc(set_a, set_b)))\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"_exercise 3.1.3_\n",
"\n",
"引理： \n",
"定义\n",
"\n",
"\\begin{equation}\n",
" I\\{A\\} = \\begin{cases}\n",
" 1 & \\text{if $A$ occurs.} \\\\\n",
" 0 & \\text{otherwise.}\n",
" \\end{cases}\n",
"\\end{equation}\n",
"\n",
"令 $X_A = I\\{A\\}$，则有 $E[X_A] = \\sum I\\{A\\}P[A] = P[A]$\n",
"\n",
"\n",
"令 $x_i$ 表示 S 和 T 中有 $i$ 个相同元素，则：\n",
"\n",
"\\begin{align}\n",
" E[x_i] & = P[\\text{S 和 T 中有 $i$ 个相同元素}] \\\\\n",
" & = \\frac{C_n^i \\, C_{n-i}^{2(m-i)}}{C_n^{m} C_n^{m}}\n",
"\\end{align}\n",
"\n",
"所以\n",
"\n",
"\\begin{align}\n",
" E[J] & = \\sum_{i=0}^m E[x_i] \\, J_i \\\\\n",
" & = \\frac{\\sum_{i=0}^m \\, C_n^i \\, C_{n-i}^{2(m-i)} \\, \\frac{i}{2(m-i)}}{C_n^{m} C_n^{m}}\n",
"\\end{align}\n",
"\n",
"\n",
"`#todo 推导最终式`\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3.2 Shingling of Documents\n",
"\n",
"**k-shingle**: any substring of length $k$ found within the document. \n",
"+ variation: set -> bag\n",
"+ multiple white-space => one white-space\n",
"+ choosing k \n",
" - **large enough** that prob. of **any given shingle** appearing in **any given document** is **low**. \n",
" k 越大，对相似性要求越高\n",
" - estimate the number of k-shingles as $20^k$, instead of 27 char, 因为各个字符的出现频率并非一致\n",
" - in general, \n",
" email: k = 5; \n",
" large documents, such as research articles: k = 9 \n",
"+ stop words, such as \"and\", \"you\", \"to\" \n",
" - ignore them in many application\n",
" - **\"stop words + two words\"** used as shingle in finding similar **news articles**.\n",
" \n",
"**hashing Shingles**: h(shingle) = bucket\n",
"+ 9-shingles, then hash to 4 char > 4-shingles"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Example 3.3: ['ab', 'bc', 'cd', 'da', 'bd']\n",
"other example: ['he', 'el', 'll', 'lo', 'o ', ' i', 'i ', ' m', 'm ', ' s', 'so']\n"
]
}
],
"source": [
"logger.setLevel(logging.WARNING)\n",
"\n",
"def to_alphanumeric_string(s):\n",
" \"\"\"remove any non-alphanumeric characte in string s.\n",
" \"\"\"\n",
" import re\n",
" \n",
" s = s.lower()\n",
" s = re.sub('\\W', ' ', s)\n",
" logging.debug('after: del special char: {}'.format(s))\n",
" s = re.sub('\\s+', ' ', s).strip()\n",
" logging.debug('after: del multiple whitespace: {}'.format(s))\n",
" \n",
" return s\n",
"\n",
"def k_shingle_extrac(document, k):\n",
" \"\"\"extract all k-shingles from document.\n",
" \n",
" \"\"\"\n",
" document = to_alphanumeric_string(document)\n",
"\n",
" assert len(document) >= k, 'k should be less than the length of document'\n",
" \n",
" k_shingles = []\n",
" while len(document) >= k:\n",
" shingle = document[0:k]\n",
" if shingle not in k_shingles:\n",
" k_shingles.append(shingle)\n",
" document = document[1:]\n",
" \n",
" return k_shingles\n",
"\n",
"\n",
"print('Example 3.3: {}'.format(k_shingle_extrac('abcdabd', 2)))\n",
"print('other example: {}'.format(k_shingle_extrac(\"Hello, I'm So-So. \", 2)))"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"##### exercise"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"first 10 3-shingles:['the', 'he ', 'e m', ' mo', 'mos', 'ost', 'st ', 't e', ' ef', 'eff']\n"
]
}
],
"source": [
"#exercise 3.2.1\n",
"\n",
"data = \"The most effective way to represent documents as sets, for the purpose of iden- tifying lexically similar documents is to construct from the document the set of short strings that appear within it. \"\n",
"\n",
"print('first 10 3-shingles:{}'.format(k_shingle_extrac(data,3)[0:10]))"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"stop-shingles:['the most effective', 'to represent documents', 'as sets for', 'for the purpose', 'the purpose of', 'of iden tifying', 'is to construct', 'to construct from', 'from the document', 'the document the', 'the set of', 'of short strings', 'that appear within', 'it']\n"
]
}
],
"source": [
"#exercise 3.2.2\n",
"logger.setLevel(logging.WARNING)\n",
"\n",
"def stopwords_shingles_extract(document, k):\n",
" \"\"\"extract the stopwords-shingle.\n",
" \n",
" stropwords-shingle = stop-words + k words\n",
" \"\"\"\n",
" stop_words_list = ['the', 'you', 'to', 'as', 'for', 'of', 'is', 'that', 'it', 'from']\n",
" \n",
" document = to_alphanumeric_string(document)\n",
" document = document.split()\n",
" logging.debug('split:{}'.format(document))\n",
" \n",
" shingles = []\n",
" k = k + 1 #len(shingle) = 1 stop-word + k words\n",
" while(document):\n",
" try:\n",
" logging.debug('check:{}'.format(document[0]))\n",
" if document[0] in stop_words_list:\n",
" shingle = ' '.join(document[0:k])\n",
" logging.debug('hit: {}'.format(shingle))\n",
" \n",
" if shingle not in shingles:\n",
" shingles.append(shingle)\n",
" \n",
" except IndexError:\n",
" logging.debug('Index Error: no of char:{}, k: {}'.format(len(document), k))\n",
" k = len(document)\n",
" continue\n",
" \n",
" document = document[1:]\n",
" \n",
" return shingles\n",
"\n",
"print('stop-shingles:{}'.format(stopwords_shingles_extract(data, 2)))\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`#exercise 3.2.3`\n",
"\n",
"k-shingles 最大数量：所有提取的 shingle 均不同 \n",
"故从左向右依次取片，有： \n",
"the largest number = n - (k - 1) = n - k + 1\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3.3 Similarity-Preserving Summaries of Sets\n",
"\n",
"##### Matrix Representation of Sets: \n",
"(r,c) = 1: the element for row r is a member of the set for column c. \n",
"(r,c) = 0: otherwise \n",
"\n",
"+ matrices are almost always **sparse**"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"
\n",
" \n",
" \n",
" | \n",
" S1 | \n",
" S2 | \n",
" S3 | \n",
" S4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | a | \n",
" 1 | \n",
" 0 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" | b | \n",
" 0 | \n",
" 0 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
" | c | \n",
" 0 | \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" | d | \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
" 1 | \n",
"
\n",
" \n",
" | e | \n",
" 0 | \n",
" 0 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
"
\n",
"
\n",
"
\n",
" \n",
" \n",
" | \n",
" S1 | \n",
" S2 | \n",
" S3 | \n",
" S4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | h1 | \n",
" a | \n",
" c | \n",
" b | \n",
" a | \n",
"
\n",
" \n",
"
\n",
"
\n",
"
\n",
" \n",
" \n",
" | \n",
" S1 | \n",
" S2 | \n",
" S3 | \n",
" S4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | h1 | \n",
" 1 | \n",
" 3 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" | h2 | \n",
" 0 | \n",
" 2 | \n",
" 0 | \n",
" 0 | \n",
"
\n",
" \n",
"
\n",
"
\n",
"
\n",
" \n",
" \n",
" | \n",
" S1 | \n",
" S2 | \n",
" S3 | \n",
" S4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | h1 | \n",
" 1 | \n",
" 3 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" | h2 | \n",
" 0 | \n",
" 2 | \n",
" 0 | \n",
" 0 | \n",
"
\n",
" \n",
" | h3 | \n",
" 0 | \n",
" 3 | \n",
" 0 | \n",
" 0 | \n",
"
\n",
" \n",
" | h4 | \n",
" 3 | \n",
" 0 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
"
\n",
"
\n",
"
\n",
" \n",
" \n",
" | \n",
" S1 | \n",
" S2 | \n",
" S3 | \n",
" S4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | h1 | \n",
" 5 | \n",
" 1 | \n",
" 1 | \n",
" 1 | \n",
"
\n",
" \n",
" | h2 | \n",
" 2 | \n",
" 2 | \n",
" 2 | \n",
" 2 | \n",
"
\n",
" \n",
" | h3 | \n",
" 0 | \n",
" 1 | \n",
" 4 | \n",
" 0 | \n",
"
\n",
" \n",
"
\n",
"