Mining Massive Datasets 学习笔记: LSH

01 Jul 2017 by fleuria

怎样在大规模数据集中发现相似的项对列表？

最糙的解法是嵌套两层 for 循环遍历所有的项对，计算彼此的相似性再按相似性排序，这一计算量显然是不可接受的。而 k-d tree 之类的多维搜索树，面向高维度的数据集性能也退化的厉害，几乎与嵌套两层 for 循环无异。

最近在看《大数据：互联网大规模数据挖掘与分布式处理》介绍了 LSH (Locality Sensitive Hashing, 距离敏感哈希) 算法，它的思路是对数据项计算哈希，想办法将相似的项对分到同一个哈希桶中，从而简化大大计算过程。过程很有意思，在这里记一下。

集合的 Jaccard 相似度

集合 S 和 T 的 Jaccard 相似度表示为 S 和 T 的交集与并集之间的差：

\[Jaccard(S, T) = | S \cup T | \div | S \cap T |\]

集合相似度可以用于衡量文本文档的相似性，比如论文抄袭、重复新闻的检测；可以应用于协同过滤的场景，如一位用户喜欢的书籍集合和我的书籍集合相似，那么可以认为我们喜好相似；也可以将 uber 的驾车行驶路线表示为集合，继而可以通过 LSH 算法找出相似路线。

将文本文档表示为集合的 Shingling 方法和搜索引擎的 N-gram 是同义词，如 k-shingle 等于长度为 k 的任意子串。

对于重复新闻检测，可以将 shingle 定义为停用词加上后续的两个词形成 shingle 集，这一做法基于假定：新闻正文中富含停用词，而正文内混插的广告语通常是简短的口号性的文本，停用词少。这样做有助于减少同一新闻内容受站点插入的广告造成的干扰。

shingle 集合非常大，远远大于原始文档的体积。幸运的是可以通过 SimHash 将集合压缩为摘要，而摘要仍能用于相似性的计算。

\[minHash(S) = min \{ h(x) \ for \ all \ x \ in \ S \}\] \[h(x) = (ax + b) \ \% \ m\]

minHash 之所以有用，在于两个集合的在经过 minHash 转换之后相等的概率恰好等于两者的 Jaccard 相似度。

设 shingle 集中有两个 shingle 集合 S 和 T，分别求取 minHash 等价于在两个集合中随机抽取一个元素：

易知随机抽取的两个元素相等的概率等于 Jaccard 相似度。

类似 bloom filter，使用的哈希函数越多，Jaccard 相似度的估算也就越精确。生成 100 个哈希函数，分别应用于一个集合所得的 minHash 列表可作为一个集合的 minHash 签名，对两个集合的签名做概率计算，即可估算出彼此的 Jaccard 相似度。

哈希表可以保证相同的键分到同一个哈希桶，而相似性哈希的精髓在于，将划分到同一哈希桶的对象视为相似，并通过增加样本数提高相似性判定的精确性。

对每个集合计算 minHash，并将 minHash 分别划分到哈希桶中，分到同一桶中的集合会被视为可能相似的候选集。

为了提高精确性，计算多个 minHash 并分桶，同一对集合可能存在于多个桶中，后续通过一次排重扫描，找出哈希桶重复度最高的一批集合匹配，最后在它们中间计算 Jaccard 距离，进一步确认出最相似的集合。