Minhash原理

　minhash是一种基于jaccard index 相似度的算法。属于LSH(Location Sensitive Hash)家族中的一员。

　例如：jaccard index ：有两个集合A={a , b , c , d , e } ，B={a , e , f , g},根据jaccard index 来计算两个集合的相似度Jaccard(A,B)=|A∩B| / |AUB|=2/7。 A∩B={a , e}   AUB = {a , b , c , d , e , f , g} , 这里，我们假如要从AUB中随机挑选一个元素，毫无疑问这个元素属于A∩B的概率也为2/7，即与A,B的jaccard相似度相等，我们假设自己有A ， B集合中有很多数据，我们不方便直接计算A∩B ， 但是我们可以从A中随机抽取部分（可以按比例）数据记作AA，从B中也随机抽取部分（可以按比例）数据 记作BB，则从AAUBB中随机抽取一个元素，这个元素落在AA∩BB中的概率 等 AA∩BB / AAUBB = A∩B / AUB，而这就是minhash降维的基本原理。

前言

       在数据挖掘中，一个最基本的问题就是比较两个集合的相似度。通常通过遍历这两个集合中的所有元素，统计这两个集合中相同元素的个数，来表示集合的相似度；这一步也可以看成特征向量间相似度的计算（欧氏距离，余弦相似度）。当这两个集合里的元素数量异常大（特征空间维数很大），同时又有很多个集合需要判断两两间的相似度时，传统方法会变得十分耗时，最小哈希（minHash）可以用来解决该问题。

Jaccard相似度

       在本例中，我们仅探讨集合的相似度，先来看Jaccard相似度。假设有两个集合A，B，则

       Jaccard(A, B)= |A ∩ B| / |A ∪ B|，我们举一个例子：

       在上述例子中，sim(A,B)=2/7。

minHash最小哈希

       假设现在有4个集合，分别为S1，S2，S3，S4；其中，S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d}，所以全集U={a,b,c,d,e}。我们可以构造如下0-1矩阵：

       为了得到各集合的最小哈希值，首先对矩阵进行随机行打乱，则某集合（某一列）的最小哈希值就等于打乱后的这一列第一个值为1的行所在的行号。举一个例子：

       定义一个最小哈希函数h，用于模拟对矩阵进行随机行打乱，打乱后的0-1矩阵为

       如图所示，h(S1)=2, h(S2)=4, h(S3)=0, h(S4)=2。

这里h(S1)：表示S1集合中最小元素a出现的位置，因为S1={a，d}，假设认为集合中排在前面的是最小元素。同理h(S2)=4，（4表示从上往下数的顺序，序号从0开始），h(S3)=0：表示S3集合中b出现的位置。 h(S4)=2表示S4集合中最小元素a出现的位置序号。

在经过随机行打乱后，两个集合的最小哈希值相等的概率等于这两个集合的Jaccard相似度，证明如下：

现仅考虑集合S1和S2，那么这两列所在的行有下面3种类型：

1、S1和S2的值都为1，记为X

2、只有一个值为1，另一个值为0，记为Y

3、S1和S2的值都为0，记为Z

       S1和S2交集的元素个数为x，并集的元素个数为x+y，所以sim(S1,S2) = Jaccard(S1,S2) = x/(x+y)。接下来计算h(S1)=h(S2)的概率，经过随机行打乱后，从上往下扫描，在碰到Y行之前碰到X行的概率为x/(x+y)，h(S1)=h(S2)的概率为x/(x+y)。