相似性发现

读书笔记

---

【Rajaraman A, Ullman J D. 大数据: 互联网大规模数据挖掘与分布式处理[J]. 2012.】

相似度

1、集合的Jaccard相似度

集合S和T的Jaccard相似度记为SIM（S，T），其值为|S∩T|与|S∪T|的比值。

2、文档的相似度

在侧重于字面上的相似性的文档判定时，可以采用Jaccard相似度作为判断依据。常用于判断是否为抄袭文档，是否为镜像页面以及是否为同源新闻稿上。

3、协同过滤

在线购物
如果两个顾客购买的商品集合中具有较高的Jaccard相似度，那么可以认为他们星期相似。类似的，若两件商品的购买顾客集合之间具有较高的Jaccard相似度，则认为这两件商品相似。这个可以用于做商品的推荐。当然，一般情况下这些使用场景中，我们不应该奢求他们的Jaccard相似度达到80%甚至90%，基本上只要能有20%就可以判断相似了。
电影评级
如果电影被许多相同的用户租借或者评级打分很高，那么久认为这些电影相似。如果用户租借的很多相同的电影或者对它们的评价都很高，那么可以认为这些用户有相同的观影习惯。当然，评级本身也等于引入了一个新的要素，可以如下处理。如果用户的评级从1星到5星，则将评级为n的电影在集合中重复n次。这样可以通过所谓包之间的Jaccard相似度（与集合之间的相似度不同，集合不能有重复元素）来计算用户之间的相似度，即在计算B和C的交集时，其元素在B、C中出现的最小次数作为交集结果，计算并集时则以这个元素在两个集合中出现的次数之和作为并集结果。

Shingling

1、k-Shingle

一篇文档就是一个字符串。文档的k-Shingle定义为其中任意长度为k的子串。例如字符串abcdabd的2-Shingle组成的集合为{ab，bc，cd，da，bd}。

2、k值的选择

理论上，k可以设为任意值。但是，k太小的话，可以想见两篇差异很大的文档的Jaccard相似度也会很高，所以，k值的选择依赖于文档的典型长度以及典型的字符表大小。
典型的，我们在做邮件的处理时，k值一般设为5。而对于研究论文来说，k设为9则更加安全。

3、对Shingle进行哈希

可以不将字符串直接用成shingle，而是通过某个哈希函数将长度为k的字符串映射为桶彪马，然后将得到的桶编号看成最终的shingle。例如，对于文档可以构建9-shingle的集合，然后将每个9-shingle映射到0到$2^{32}$-1之间的一个桶编号。那么，每个shingle就由4个字节而不是9个字节来表示了。

4、基于此的shingle

除了对字符的shingle外，还可以将shingl定义为基于词的shingle。例如，在新闻报道中，可以将shingle定义为一个停用词（and、you、to、from等）加上后续的两个词来行程一个有效的shingle集。

保持相似度的集合的摘要表示

使用最小哈希可以将大文档压缩成小的签名并同时保持任意对文档之间的预期相似度。

1、集合的矩阵表示

现有集合S1={a,d},S2={c},S3={b,d,e},S4={a,c,d}。则他们的矩阵表示为

元素	S1	S2	S3	S4
a	1	0	0	1
b	0	0	1	0
c	0	1	0	1
d	1	0	1	1
e	0	0	1	0

2、最小哈希

对上述矩阵做随机行变换，如

元素	S1	S2	S3	S4
b	0	0	1	0
e	0	0	1	0
a	1	0	0	1
d	1	0	1	1
c	0	1	0	1

其最小哈希表示为每一列的第一个非0值，则我们得到h（S1）=a、h（S2）=c、h（S3）=b和h（S4）=a。

3、最小哈希与Jaccard相似度

他们之间有着非同寻常的关联：两个集合经随机排列转换之后得到的两个最小哈希值相等的概率等于这两个集合的Jaccard相似度。（证明略）

4、最小哈希签名的计算

待定

距离测度

距离测度是一个函数$d（x，y）$，以空间中的两个点作为参数，输出一个实数值。该函数必须满足以下四个条件：
（1）$d（x，y）≥ 0$（距离非负）；
（2）$d（x，y）= 0$当且仅当$x=y$（只有点到自身的距离为0，其他距离都大于0）；
（3）$d（x，y） = d（y，x）$（距离具有对称性）；
（4）$d（x，y）≤ d（x，z） + d（z，y）$（三角不等式）。

1、欧式距离

欧式距离就是我们通常所想象的“距离”，也就是我们常说的$L_2$范式定义为

$$d（[x_1，x_2，…，x_n][y_1，y_2，…，y_n]）=\sqrt{\sum_{i=1}^n （x_i-y_i）^2}$$
当然，欧式空间下还有一些其他的距离测度方法（如$L_r$范式）。

2、Jaccard距离

集合Jaccard距离可以定义为

$$d（x，y）=1-SIM（x，y）$$

3、余弦距离

在有维度的空间下余弦距离才有意义，这些空间包括欧式空间及离散欧式空间。余弦距离定义为向量x与y的夹角的角度（即通过先通过$x·y$再除以两个向量的$L_2$范式得到他们的夹角余弦值，再通过反余弦函数将结果转换为0~180度之间的角度）。

4、编辑距离

编辑距离只适用于字符串的比较。定义为将字符串x转换为y所需的单字符插入和删除操作的最小数目。
编辑距离的一种计算方式为先求出x和y的最长公共子序列（LCS），那么编辑距离就等于x与y的长度之和减去它们的LCS长度的两倍。

5、海明距离

在一个向量空间中，海明距离定义为两个向量中不同分量的个数。比如10101与11110的海明距离为3。

LSH函数簇（略）

面向高相似度的方法（略）