【PyLSHasH】Locality Sensitive Hashing

项目地址

https://github.com/guofei9987/pyLSHash

原理

这样一个任务：

1. 数据库中存了 1亿 个 n 维向量
2. 设计一个系统，使它能够
3. 每次有一个 n 维向量 query 这个系统时，能够给出数据库中与它相似（距离较近）的向量
4. 首先想到的是用暴力遍历，计算 1亿 次距离，然后卡阈值，但这效率极低
5. 引出这里要介绍的一个算法：Locality Sensitive Hashing，它可以很好的解决此问题

算法原理很简单：

1. 随机生成一个矩阵 Km×nK_{m\times n}Km×n​，然后求矩阵积 Km×na⃗n×1K_{m\times n} \vec a_{n\times 1}Km×n​an×1​
2. 把结果离散化，就是 a⃗\vec aa 的 “指纹”。
   • 这里的离散化就粗暴一些：大于0记为1，否则记为0。指纹长度为 m
3. 因为矩阵是随机生成的，离散化也粗暴，因此可以把以上多做几次，也就是对饮 num_hashtables 个矩阵

几何角度理解

• 从几何角度，矩阵积实际上是 m 个向量积。
• 向量积 k⃗⋅a⃗1\vec k \cdot \vec a_1k⋅a1​ 和 k⃗⋅a⃗2\vec k \cdot \vec a_2k⋅a2​ 相似，意味着 a⃗1,a⃗2\vec a_1, \vec a_2a1​,a2​ 在向量 k⃗\vec kk 上的投影相似
• 回到矩阵积，m 个投影都相似，也就意味着 a⃗1,a⃗2\vec a_1, \vec a_2a1​,a2​ 在 m 个基看来是近似的，也就是在空间上近似
• 极端情况，假设 KKK 是单位矩阵，那么所谓的 “相似” 指的就是 “在同一象限”

参考资料

min-hash

MinHash 是什么

• 是LSH的一种，
• 可以用来快速估算两个集合的相似度。
• MinHash由Andrei Broder提出，最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。

• 输入是一个 01 矩阵，它代表一个集合
• 随机生成 k 种打乱顺序的方法（k种全排列）
• 记录下每种排列下，第 0 个 1 所在的位置
• 得到 k 个数字，它就是 MinHash 值

性质：对于 A，B 集合，MinHash 值相等的概率，等于 Jaccard 相似度

算法问题：如果特征很大，那么全排列非常耗时 算法改进：

• 定理：h(x)=(ax+b)mod  nh(x) = (ax+b) \mod nh(x)=(ax+b)modn，如果 a和n互素，那么这个函数可以生成全排列，
  • 例如：h(x)=(3x+1)mod  5h(x) = (3x+1) \mod 5h(x)=(3x+1)mod5 把 0,1,2,3,4 映射到 1,4,2,0,3
• 算法：遍历，取当前的最小值

min-hash 得到的是 Hash 值，通常还要判断其类别，就接上面的 LSH 算法

参考：https://blog.csdn.net/OrthocenterChocolate/article/details/38943491