LSH（局部敏感哈希）算法

参考/摘自：
minHash(最小哈希)和LSH(局部敏感哈希)
大规模数据的相似度计算：LSH算法

LSH（locality sensitivity Hashing，局部敏感性哈希）算法是一种海量数据中进行相似性搜索的算法。

在传统的基于用户或基于物品的协同推荐算法中，一个常见的步骤是计算user-user之间的相似度或者item之间的相似度，计算量为O(n**2)在用户或者物品较少的时候，这些计算量是可以接受的，但是随着用户或者物品的增大，计算量会变得异常大，即便是有大规模计算集群也变得难以维持。因此我们需要提升计算效率。

Min Hashing

Min Hashing能够对高维稀疏数据进行压缩，从而提升计算效率。继续以上面推荐中的例子，来进行说明，假设下面的表格表示4个用户分别对5个商品的购买情况：

jaccard相似度，白话即为两个集合的交集比上并集：
jaccard(A, B) = (A∩B)/(A∪B)。

利用jaccard相似度可以计算各个用户之间的相似度，如:
jaccard(u1, u4) = (i4+i5)/(i3+i4+i5) = 2/3

虽然上面的计算非常简单，但是随着物品以及用户达到了千万或以上的量级，计算量依然是非常庞大的。现在，我们将使用Min Hashing 来对数据进行降维。

最小哈希

为了得到“最小哈希值”，我们需要先对行进行一个扰动（或者称为permutation，打乱），随机交换行数。如下图：

在交换完行数之后，变可以得到每一列（这里就是每一个user）的最小哈希值了，以上图为例：

灵魂画手，见谅
每一次随机交换行数便可以得到一个最小哈希值，如上图，各个连线表明了各个user的最小哈希值的来源，说明如下：

• （1）第一步随机交换行数，如上图，我们进行了两次交换行数；
• （2）对于交换行数后的矩阵，从上往下进行扫描，每一个user的最小哈希值为交换行后其第一个不为0的行的index，如第一次交换行后，各个user第一个item不为0的行index分别为0，4，1，0，因此此次交换行后各个user得到的最小哈希值分别为0，4，1，0。

每一次交换行数后都能得到一个最小哈希值，交换次数一般远小于原始矩阵行数，因此可以对数据维度进行压缩。

最小哈希值与Jaccard相似度

在经过打乱后的两个集合（这里即两个用户）计算得到的最小哈希值相等的概率等于这两个集合的jaccard相似度。简单推导如下。
假设只考虑两个用户，那么这两个用户的行有下面三种类型：

• （1）这一行的u1和u2的值均为1，记为X类；
• （2）这一行只有1 个值为1，另一个值为0，记为Y类；
• （3）这一行两列的值都为0，记为Z类。

假设属于X类的行有x个，属于Y类的行有y个，所以u1和u2交集的元素个数为x，并集的元素个数为x+y，所以SIM(u1, u2) = x / (x+y)。注：SIM(u1, u2)就是集合S1和S2的Jaccard相似度。

接下来计算最小哈希值h(u1) = h(u2)的概率。经过打乱后，对特征矩阵从上往下进行扫描，在碰到Y类行之前碰到X类行的概率是x/(x+y)；又因为X类中h(u1)=h(u2)，所以h(u1)=h(u2)的概率为x/(x+y)，也就是这两个集合的jaccard相似度。

Min Hashing的实际实现

在上面中每一次打乱生成一个最小哈希值，假设原来有n个物品，打乱m次，便可以得到m个最小哈希值，一般来说m《 n，以对原始矩阵进行维度压缩。这时候的最小哈希值组成的矩阵便称为最小哈希签名（signature）矩阵。

但是，在实践中我们一般不会这么做，因为对于一个巨大的矩阵，多次打乱行数也是一个计算量巨大的操作。通常我们可以使用一个针对row index的哈希函数来达到permutation的效果，虽然可能会产生哈希碰撞的情况，但是只要碰撞的概率不大，对结果的影响就会很小。具体做法如下：
（1）取m个这针对row index的哈希函数，h1到h_m；
（2）记Sig(i, v)为v列原向量在第i个哈希函数下的min hash值，初始值可设置为inf；
（3）对于原矩阵的每一行r：

• 计算h1(r), h2(r)，..., h_m(r)（这里可理解为新增m列，每一列通过一个哈希值得到，具体见下图）；
• 对每一个列向量v：
  • 如果v的当前行取值为0，则忽略继续下一行，知道找到值不为0的行；
  • 如果v在r行的取值为1，则v的新特征（也即最小哈希值）为此行对应的h1(r), h2(r)，..., h_m(r)与SIG(i, v)之间的最小值，i∈（1，m）；

如下图：

具体的每一步是如何填充的可以参考https://blog.csdn.net/liujan511536/article/details/47729721中的说明。

如上，我们使用了两个哈希函数，因此压缩后的哈希签名矩阵为两行。此时可以利用新的矩阵来计算Jaccard相似度：
Sim(u1, u4) = 2/2 = 1。

LSH (Locality Sensitivity Hashing, 局部敏感哈希)算法

通过上面的Min Hashing可以将一个大矩阵通过哈希映射压缩成一个小矩阵，同时保持各列之间的相似性，从而降低了复杂度。但是，虽然我们降低了特征复杂度，如果用户非常多的话，我们的计算量依然是非常大的（O(n**2)），如果我们能先粗略地将用户分桶，将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“备选相似用户集”就会相对较小，降低寻找其相似用户的计算复杂度，LSH就是这样一个近似算法。

LSH的具体做法是在Min Hashing所得的signature向量的基础上，将每一个向量分为几段，称之为band（即每个band包含多行），如下图所示：

每一列分成4个band, 每个band包含3行

每个signature向量被分成了4段，图上仅展示了各向量第一段的数值。其基本想法是：如果两个向量的其中一个或多个band相同，那么这两个向量就可能相似度较高；相同的band数越多，其相似度高的可能性越大。所以LSH的做法就是对各个用户的signature向量在每一个band上分别进行哈希分桶来计算相似度，在任意一个band上被分到同一个桶内的用户就互为candidate相似用户，这样只需要计算所有candidate用户的相似度就可以找到每个用户的相似用户群了。

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

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

实际操作中我们可以对每一个band使用同一个哈希函数，但是哈希分桶id需要每个band不一样，具体说来，假设向量 A, B均被分为3个band：[A1, A2, A3]和[B1, B2, B3]。则向量A、B的每个band都被hash到一个桶类，相同行band如果被分到一个桶内便说明A、B是相似的，互为candidate相似用户。

LSH分桶优化

下面我们对signature向量的分桶概率作一些数值上的分析，以便针对具体应用确定相应的向量分段参数。假设我们将signature向量分为b个band，每个band的大小（也就是band内包含的行数）为r。假设两个用户向量之间的Jaccard相似度为s，前面我们知道signature向量的任意一行相同的概率等于Jaccard相似度s，我们可以按照以下步骤计算两个用户成为candidate用户的概率：

• 两个signature向量的任意一个band内所有行的值都相同的概率为 s^r;
• 两个signature向量的任意一个band内至少有一行值不同的概率为1-s^r;
• 两个signature向量的所有band都不同的概率为 (1-s^r)^b;
• 两个signature向量至少有一个band相同的概率为 1-(1-s^r)^b，即为两个用户成为candidate相似用户的概率；

这个概率在r和b取不同值时总是一个S形的曲线，例如当b=100，r=4时，1-(1-s⁴)¹⁰⁰的曲线如下图所示：

两个用户成为candidate相似用户的概率

这个曲线的特点在于，当s超过一个阈值之后，两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值，也就是概率变化最陡的地方，近似为t=(1/b)^1/r。实际应用当中，我们需要首先决定 s>s_min为多少才可以视为相似用户，以及signature向量的长度来确定这里的b和r，并考虑：
（1）如果想要尽可能少的出现false negative，就需要选择b和r使得概率变化最陡的地方小于 s_min 。例如假设我们认为s在0.5以上才属于相似用户，那么我们就要选择b和r使得S曲线的最陡处小于0.5（上图所示的b=100，r=4就是一个较好的选择），这样的话，s在0.5以上的“真正”的相似用户就会以很大的概率成为candidate用户。
（2）如果想要保证计算速度较快，并且尽可能少出现false positive，那么最好选择b和r使得概率变化最陡的地方较大，例如下图所示的b=20，r=6。这样的话，s较小的两个用户就很难成为candidate用户，但同时也会有一些“潜在”的相似用户不会被划分到同一个桶内。（candidate用户是一部分质量较高的相似用户）。

两个用户成为candidate相似用户的概率

这样针对具体应用，经过前期的数据探索之后，我们便可以为LSH算法设置具体的参数，使得在保证精度的情况下，提升计算效率。当然这里只是说明了Jaccard相似度下的LSH算法，对于其他的相似度度量比如余弦相似度等，可参考《mining of massive datasets》中chapter 3：finding similar items.

参考：
http://www.360doc.com/content/18/0927/15/39821762_790129444.shtml