大规模数据挖掘-第三章 学习笔记二

3.4 文档局部性敏感哈希（Locality-Sensitive Hashing for Documents）
虽然我们可以通过minhash来压缩大的文档到小的签名，并且仍然能够保留每对文档的相似性。
但是找到相似的对仍然很难实现，因为虽然文档数可能不是非常多，但是文档的对数会变得非常的大。
如果我们的目标是计算每对文档的相似度，那么我们没有办法减少我们的工作量，虽然并行处理的方法可以减少花费的时间。然而如果我们想找到最相似的对或者在一个相似度下界之上的相似对，那么我们可以值把关注聚集在那些最可能相似的对中，不需要计算所有的对。这就是Locality-Sensitive Hashing的理论。在这节我们只考虑特殊形式的LSH，为我们已经学习到的问题设计：有shingle集合代表的文档，然后用minhash到短的签名。在3.6节我们会展示LSH的基本理论、一些应用和相关技术。
3.4.1 Minhash签名的LSH
LSH一个通用的方法是将item进行多次hash，这样相似的item就比不相似的更有可能hash到同一个桶中。我们将hash到同一个桶中的所有的对作为候选的对，然后只检查候选对的相似度。我们希望不相似的对不会hash到相同的桶中，所以就不会被检查。那些不相似的对被hash到同一个桶中被称为假阳性，希望在所有的对中只会占很小的比例。我们仍然希望真正相似的对会hash到同一个桶中，至少在这些hash函数中的一个，否则被称为假阴性，我们希望在真正相似的对中，假阴性只占一小部分比例。
如果我们已经将所有的items都已经进行了minhash签名，一种有效的方式是选择hash能够把签名矩阵分成b个段，每个段有r行。对于每一个段，有一个hash函数把r个整数组成的向量（在那个段里的一列的一部分）hash成某个很大的桶号。我们可以对所有的段使用同一个hash函数，但是对每一个段我们使用一个单独的桶，所以在不同段具有相同向量的列不会hash到同一个桶中。
越是相似的两个列，他们越是可能在某个段上相等，因此从直观上这个策略能够使得越是相似的列越可能成为候选的对。
3.4.2 分段（Banding）技术分析
假如我们使用了b个段，每个段r行，假设一个对文档的Jaccard相似度是s，他们的minhash签名在签名矩阵的一行相同的概率是s。我们 计算一下这些文档成为候选pair的概率。
1.在一个段中签名的所有行相同的概率是s^r。
2.在一个段中前面在至少一行都不相等的概率是1-s^r
3.任意一个段签名不是在所有的行中都相等的概率（1-s^r)^b
4.签名至少在一个band中所有的行都相等，即候选pair的概率是1-（1-s^r)^b。
不管我们怎么选择常量b和r，这个函数的形式是S-曲线。
例子：比如我们考虑b = 20, r = 5.
1-（1-s^5)^20的在值为：
s    1-(s-s^r)^b
.2   .006
.3   .047
.4   .186
.5   .470
.6   .802
.7   .975
.8   .9996
当我们去s=0.8,即我们考虑两个文档80%相似，他们称为候选對的概率是99.96%。
3.4.3 将这些技术结合起来
我们现在已经有一种方式可以找到结合的相似的候选对，然后从中选择真正相似的文档。
这种方式可能出现假阴的现象：真正相似的由于没有成为候选对而没有被标示为相似。
结合起来过程如下：
1.选择k的值，然后将每一个文档构建k-shingles，可选的，将k-shingles hash成
更短的桶号。
2.将document-shingle按照shingle排序。
3.选择minhash签名的长度n.计算每个文档的的minhash签名
4.选择相似文档的相似的threshold t，选择bands数b和行数r，br=n，t大约等于
(1/b)^(1/r).如果避免假因现象，可以选择b和r使其小于t。如果速度是比较重要
的因素，希望显示假阳的样例，可以选择b和r使其大于t。
5.根据LSH的算法来构建候选pairs
6.检查候选对的签名，判断是否他们匹配度是否小于t。
7.可选择的，如果签名相似，可以再检查一下文档本身，检查他们是否相似，避免两个
文档不相似的文档侥幸的具有相似的签名。

3.5 距离计算方法
我们来学习一下各种距离计算方法，Jaccard相似度给出了两个集合的相似度，1减去
Jaccard相似度被称为Jaccard距离。还有其他很多的描述距离的方法。
3.5.1距离定义：
距离是一个函数d(x,y)，以空间中的两个点x，y为参数，结果为一个实数，并且满足：
1. d(x,y) >= 0
2. d(x,y) == 0 当且仅当x=y
3. d(x,y) == d(y,x)
4. d(x,y) <= d(x,z) + d(z,y)

3.5.2 欧拉距离：
d([x1,x2,...,xn],[y1,y2,...,yn]) = sqrt(sum(xi - yi)^2)
更一般的:
d([x1,x2,...,xn],[y1,y2,...,yn]) = (sum(xi - yi)^r)^(1/r)
称为Lr-norm。
当r=2的时候L2-norm，r=1的时候L1-norm被称为曼哈顿距离。
3.5.3 Jaccard Distance
d(x,y) = 1-SIM(x,y)
3.5.4 cosine距离：
X = [x1 , x2 , . . . , xn ]
Y = [y1 , y2 , . . . , yn ]

d(X,Y) = X . Y / |Y| * |X|
3.5.5 编辑距离：
两个字符串x=x1x2...xn, y=y1y2...yn，最小的添加、删除、修改单个字符，将x变成
y的操作次数。
可以使用动态规划的方法来计算。
3.5.6 海明距离
给一个空间向量，海明距离被定义为两个向量不同组建的个数。海明距离最常用在二进制类型的向量中。
3.6 局部敏感函数理论【待续】