理解Jaccard相似度,Minhash和LSH算法

前言：
记录一下学习 Jaccard 相似度，Minhash 和 LSH 算法的笔记，方便以后查找。

Jaccard 相似度[狭义]

理解有限，广义就不深入了。
判断两个集合是否相等，一般使用称之为 Jaccard 相似度的算法（后面用 Jac(S,S)来表示集合 S 和 S 的 Jaccard 相似度）。举个列子，集合 X = {a,b,c}，Y = {b,c,d}。那么 Jac(X,Y) = 2 / 3 = 0.67。也就是说，结合 X 和 Y 有 67%的元素相同。下面是形式的表述 Jaccard 相似度公式：

Jac(X,Y) = |X∩Y| / |X∪Y|

也就是两个结合交集(∩)的个数比上两个集合并集(∪)的个数。范围在[0,1]之间。

由相似度，可以转换成 Jaccard 距离：

Jaccard distance  (A, B） = 1 - Jaccard（A, B）

降维技术 Minhash:

解决的是原始高维计算时间太长，将原始集合压缩成更小的集合，而且又不失去相似性，可以缩短计算时间。

LSH –  局部敏感哈希:

场景：用于海量高维数据的近似最近邻快速查找技术。
基本思路：将相似的集合聚集到一起，减小查找范围，避免比较不相似的集合。

这种类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest  Neighbor,AN），例如 K-d tree；或近似最近邻查找（Approximate Nearest  Neighbor, ANN），例如 K-d tree with BBF, Randomized Kd-trees, Hierarchical K-means Tree。而 LSH 是 ANN 中的一类方法。

基于概率的分桶方法当然会有漏网之鱼，我们希望下面两种情况的集合越少越好：

• False Positives: 相似度很低的两个集合被哈希到同一个桶内；
• False Negatives: 真正相似的集合在每一个 band 上都没有被哈希到同一个桶内。

Cell-probe 方法

加速查找的典型方法是对数据集进行划分，我们采用了基于 Multi-probing(best-bin KD 树变体)的分块方法。

• 特征空间被切分为 ncells 个块
• 数据被划分到这些块中（k-means 可根据最近欧式距离），归属关系存储在 ncells 个节点的倒排列表中
• 搜索时，检索离目标距离最近的 nprobe 个块
• 根据倒排列表检索 nprobe 个块中的所有数据。

这便是 IndexIVFFlat，它需要另一个索引来记录倒排列表。
IndexIVFKmeans 和 IndexIVFSphericalKmeans 不是对象而是方法，它们可以返回 IndexIVFFlat 对象。
注意：对于高维的数据，要达到较好的召回，需要的 nprobes 可能很大。

和 LSH 的关系

最流行的 cell-probe 方法可能是原生的 LSH 方法，可参考E2LSH。然而，这个方法及其变体有两大弊端：

• 需要大量的哈希函数（=分块数），来达到可以接受的结果。
• 哈希函数很难基于输入动态调整，实际应用中容易返回次优结果。

Faiss 示例

# d是输入数据的维度，nbits是存储向量的bits数目。
n_bits = 2 * d
lsh = faiss.IndexLSH (d, n_bits)
lsh.train (x_train)
lsh.add (x_base)
D, I = lsh.search (x_query, k)

注意：算法不是 vanilla-LSH，而是更好的选择。如果 n_bits <= d，则使用正交投影仪组，如果 n_bits> d，则使用紧密帧。

小结：

MinHash 降维，LSH 减少查找范围。

以上内容摘自链接如下：

强烈推荐阅读一下链接，加深理解。

• 利用 Minhash 和 LSH 寻找相似的集合
• Faiss 索引