csdn博客推荐系统实战

上一篇说了simhash，本质是降维，计算量会大幅降低。simhash可以用来去复，也可以用来计算相似度，今天要说的minhash和simhash很相似，可用于去重和计算相似度，主要也是降维的路思。

就是simhash和汉明距离配套一样，和minhash配套的是Jaccard距离。

minhash是LSH(局部敏感哈希)的一种，快速检索大量数据。

特征矩阵是推荐系统必须要做的事，不管是用户-用户，用户-物品，物品-物品，词-文章，主题-文章，都要用到特征矩阵。minhash就是在特征矩阵上下功夫降维。

以词-文章特征矩阵为例，一列就对应一个集合，所有的行加起来就是所有集合元素的全集，如果集合中有那个元素，则矩阵中的对应位置为1，否则为0。

假设现在有4个集合，分别为S1，S2，S3，S4；其中，S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d}，所以全集U={a,b,c,d,e}

那么这4个集合的特征矩阵为：

构建集合的特征矩阵是为了计算集合的最小哈希。

为了计算最小哈希，首先对特征矩阵的行进行打乱（也即随机调换行与行之间的位置），这个打乱是随机的。然后某一列的最小哈希值就等于打乱后的这一列第一个值为1的行所在的行号（不明白的直接看例子），行号从0开始。

例如，定义一个最小哈希函数h，然后对上面的特征矩阵进行行打乱，原来第一列的顺序为abcde，打乱后为beadc，则新的特征矩阵为：

对于列S1，从这一列的第一行往下走，直到遇到第一个1，所在的行号则为这一列的最小哈希值。所以这4列的最小哈希值依次为h(S1) = 2, h(S2) = 4, h(S3) = 0, h(S4) = 2.

最小哈希签名

上面是用一个行打乱来处理特征矩阵，然后就可以得到每个集合最小哈希值，这样多个集合就会有多个最小哈希值，这些值就可以组成一列。当我们用多个随机行打乱（假设为n个，分别为h1,h2…hn）来处理特征矩阵时，然后分别计算打乱后的这n个矩阵的最小哈希值；这样，对于集合S，就会有n个最小哈希值，这n个哈希值就可以组成一个列向量，为[h1(S), h2(S)…hn(S)]；因此对于一个集合，经过上面的处理后，就能得到一个列向量；如果有m个集合，就会有m个列向量，每个列向量中有n个元素。把这m个列向量组成一个矩阵，这个矩阵就是特征矩阵的签名矩阵；这个签名矩阵的列数与特征矩阵相同，但行数为n，也即哈希函数的个数。通常来说，n都会比特征矩阵的行数要小很多，所以签名矩阵就会比特征矩阵小很多。

最小签名的计算

其实得到上面的签名矩阵之后，我们就可以用签名矩阵中列与列之间的相似度来计算集合间的Jaccard相似度了；但是这样会带来一个问题，就是当一个特征矩阵很大时（假设有上亿行），那么对其进行行打乱是非常耗时，更要命的是还要进行多次行打乱。

为了解决这个问题，可以通过一些随机哈希函数来模拟行打乱的效果。

考虑上面的特征矩阵，将abcde换成对应的行号，在后面加上两个哈希函数，其中h1(x)=(x+1) mod 5，h2(x) = (3*x+1) mod 5，注意这里x指的是行号：

接下来计算签名矩阵。一开始时，全部初始化为Inf:

接着看特征矩阵中的第0行；这时S2和S3的值为0，所以无需改动；S1和S4的值为1，需改动。h1= 1，h2= 1。1比Inf小，所以需把S1和S4这两个位置对应的值替换掉，替换后效果如下：

接着看第1行；只有S3的值为1；此时h1= 2，h2= 4；对S3那一列进行替换，得到：

接着看第2行；S2和S4的值为1；h1=3，h2=2；因为签名矩阵S4那一列的两个值都为1，比3和2小，所以只需替换S2那一列：

接着看第3行；S1，S3和S4的值都为1，h1=4, h2= 0；替换后效果如下：

接着看第4行；S3值为1，h1=0, h2= 3，最终效果如下：

这样，所有的行都被遍历一次了，最终得到的签名矩阵如下：

基于这个签名矩阵，我们就可以估计原始集合之间的Jaccard相似度了。由于S2和S4对应的列向量完全一样，所以可以估计SIM(S1，S4)=1;同理可得SIM(S1，S3) = 0.5;

以上这个过程我已经实现，没什么难度。

但是如果文档数量特别的多，几千万，几十亿，即使降维降到50维，计算量依然很大，线性计算不可为，是大忌，怎么办呢？

有很多篇文档，找出相似度很高的文档，先计算出所有文档的签名矩阵，然后依次两两比较签名矩阵的相似度,时间，空间复杂度太高，不可行。那可不可以只比较那些相似度可能会很高的文档，而直接忽略过那些相似度很低的文档。当然可以！！

首先，我们可以通过上面的方法得到一个签名矩阵，然后把这个矩阵划分成b个行条(band)，每个行条由r行组成。对于每个行条，存在一个哈希函数能够将行条中的每r个整数组成的列向量（行条中的每一列）映射到某个桶中。可以对所有行条使用相同的哈希函数，但是对于每个行条我们都使用一个独立的桶数组，因此即便是不同行条中的相同列向量，也不会被哈希到同一个桶中。这样，只要两个集合在某个行条中有落在相同桶的两列，这两个集合就被认为可能相似度比较高，作为后续计算的候选对；而那些在所有行条中都不落在同一个桶中的两列，就会被认为相似度不会很高，而被直接忽略。下面直接看一个例子：

例如，现在有一个12行签名矩阵，把这个矩阵分为4个行条，每个行条有3行；为了方便，这里只写出行条1的内容。

可以看出，行条1中第2列和第4列的内容都为[0,2,1]，所以这两列会落在行条1下的相同桶中，因此无论在剩下的3个行条中这两列是否有落在相同桶中，这两个集合都会成为候选对。在行条1中不相等的两列还有另外的3次机会成为候选对，因为他们只需在剩下的3个行条中有一次相等即可。

经过上面的处理后，我们就找出了相似度可能会很高的一些候选对，接下来我们只需对这些候选队进行比较就可以了，而直接忽略那些不是候选对的集合。这个方法适合用来计算相似度超过某个值的文档的相似度，而不适用于计算所有文档的相似度，因为那些相似度可能很低的文档已经被直接忽略了。

LSH是一个算法族，里面有很多的算法，minhash只是其中的一个而已，有兴趣的朋友可以好好研究研究。

LSH这个算法我没有实现，不过感谢python无所不能的包啊，已经有了很多的实现，LSHash,sklearn,datasketch,都已经实现了LSH,直接用就可以了。