LSH（局部敏感哈希）算法

参考/摘自：

minHash(最小哈希)和LSH(局部敏感哈希)

大规模数据的相似度计算：LSH算法

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

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

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

利用jaccard相似度可以计算各个用户之间的相似度，如:

jaccard(u1, u4) = (i4+i5)/(i3+i4+i5) = 2/3

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

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

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

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

在经过打乱后的两个集合（这里即两个用户）计算得到的最小哈希值相等的概率等于这两个集合的jaccard相似度。简单推导如下。

假设只考虑两个用户，那么这两个用户的行有下面三种类型：

假设属于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相似度。

在上面中每一次打乱生成一个最小哈希值，假设原来有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：

如下图：

具体的每一步是如何填充的可以参考 >

按照某种特征定义你的，采用最优Hamilton路或最优Hamilton圈（即TSP）的思想建立优化模型。关于TSP的求解方法有很多，在求解过程中需要注意到非对称距离矩阵或者是有向图等特点，还可能有种种优化模型与算法

以上就是关于LSH（局部敏感哈希）算法全部的内容，包括:LSH（局部敏感哈希）算法、如何捕获相似基因（两个相似哈希算法分析）、图片相似搜索应怎么提取图片特征用matlab，用什么作为特征等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！