数据挖掘之lsh（局部敏感hash） minhash、simhash

在项目中碰到这样的问题：

互联网用户每天会访问很多的网页，假设两个用户访问过相同的网页，说明两个用户相似，相同的网页越多，用户相似度越高，这就是典型的CF中的user-based推荐算法。

算法的原理很简单，只要两两计算用户的相似性，针对每个用户，获取最相似的K个用户即可。

但是在实际的工程上，假定用户规模在亿的规模N，计算复杂度为N*N，即使是分布式，也是非常可怕的复杂度。

考虑一下，我们是不是真的需要计算所有用户之间的相似性？其实我们只需要计算和用户A最相似的K个用户即可，如果已知B和A一定不相似，那么就没有必要计算，这就是LSH的思想。

?

LSH：local sensitive hash，局部敏感哈希，关注可能相似的pair，而非所有的pair，这是lsh的基本思想。

举个例子：

用户user1 访问过 url1,url2

用户user2访问过 url2,url3

用户user3访问过url3

很明显，user1和user2相似，而 user1和user3是不相似的，换句话，user1和user3是不需要比较的。

如何做到呢?最简单的思路，把url作为hash的key，user作为value，计算同一个key下面user的相似度。

url1:user1

url2:user1 user2

url3:user2 user3

这样分别计算user1 user2 以及user2和user3的相似性即可，不用计算user1和user3,也就是不相似的user不需要计算其相似性，基本上就是LSH的思想

但是，很明显，上面的作法过于简单和粗暴：

1.如果每个user有上w维的特征，针对每个特征做一个hash，会导致计算复杂度大大增加，两个特征相同的用户，需要计算w次相似性

2.无法刻画lsh中，只关注相似的paire 中的"相似”程度，比如如果相似性<0.5,则认为不相似，尽量不出现在一个桶等等

第一个问题谈到是降维，第二个是如何进行刻画相似性以及进行hash。

minhash以及simhash就是来解决上面的两个问题的，这两个都是来刻画jaccard距离的。

回到刚开始的例子，及时就是计算user1与user2的jaccard距离，假设url进行了编号，有唯一的id，最大编号为N，每个用户访问过的url数目为N(u)。

这样我们可以理解每个用户有N个特征，其中访问过的对应位置为1，没有访问的为0，维数很高，几十B的规模。

minhash就是来解决降维的问题，具体的minhash原理网上有很多介绍，就不在详细说了。

minhash最后的产出是每个用户有K维的特征{id1,id2....idk}，不同用户第k特特征相同的概率和直接利用用户原始的N维特征计算jaccard距离的相似性相同,K<<N，达到降维的目的。

如果利用K维特征，计算2-2相似性，复杂度还是很高。

利用LSH思想，我们只需要计算可能形似用户的相似度，保证相似的用户对应的hash值一样，而不相似的对应的hash值不同。

两个用户度为p，则用户对应相同位置特征值相同的概率为p，有证明。

将K个特征划分为band，b1,b2...bm，每个band里面的元素个数为r个，r*m=K

用户每个band里面r个特征全部相同的概率为p^r，也就是基于这个band作为hash值，两个用户hash值相同的概率为p^r，那么hash值不同的概率为1-s^r，m个band hash值都不一样的概率为(1-p^r)^m，也就是两个用户不在任何一个桶里面的概率。

而1-（1-p^r)^m 则为两个用户落在至少一个桶里面的概率，很容易理解，如果r越小，最后值越大，很不相似（p很小)的元素落在一个桶里面的概率很大，计算的复杂度高。如果r很大，则最后的值很小，也就是很相似(p比较到)落在一个桶里面的概率很小.

比如 r=1,m=16，p=0.2，计算后为99.8%，也就是相似性为0.2的两个元素，99.2%的概率会落在一个桶里面，进行计算，事实上是没有必要的。

r=20,m=1,p=0.8，计算后0.02%,也就是说相似性为0.8的两个元素，0.02%的概率是落着一个桶里面，概率很低，影响召回率。

这时候根据实际需要来确定r的大小，比如 r=2,m=8，

p=0.3时为53%概率落在一个桶

p=0.5时为90%概率落在一个桶

p=0.7时为99.6%概率裸着一个桶。

通过这个方法平衡计算复杂度和项目需求

整体来看,minhash主要是用来降维，且为LSH提供的条件。

simhash和minhash有很大的相似性，都是lsh的一个方法，但是其牛逼的地方在于，simhash值之间的海明距离可以刻画其相似程度。

simhash本身也是用来降维以及很方便的利用LSH思想。

具体的simhash的介绍很多，不做介绍。

假设simhash的结果是16bit的0-1串作为特征 ，假设有最多k个bit不同，我们认为其相似，那么需要将其划分成k+1个band

比如 k=3,我们需要划分成4个band，这个比较容易理解，也有很完整的证明。

整体来看，lsh是来解相似性计算的规模问题，避免计算所有pair，只计算可能相似的pair。

基本的思路就是划分band，band的大小和计算复杂度以及召回率有很大的关系。

针对基于jaccard距离的问题，直接基于在原始特征上，无法划分band，因为维度过高以及数据很稀疏，效果不好。

这时候，就需要将数据降维，便于高效处理。

minhash、simhash从不同的角度解决这个问题。

来源：http://blog.csdn.net/hxxiaopei/article/details/7977248?

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

? ? ? ? ?在数据挖掘中，有一个比较基本的问题，就是比较两个集合的相似度。关于这个问题，最笨的方法就是用一个两重循环来遍历这两个集合中的所有元素，进而统计这两个集合中相同元素的个数。但是，当这两个集合里的元素数量非常庞大时，同时又有很多个集合需要判断两两之间的相似度时，这种方法就呵呵了，对内存和时间的消耗都非常大。因此，为了解决这个问题，数据挖掘中有另一个方法。

Jaccard相似度

?????????在介绍具体算法之前，我们首先来了解一个概念：Jaccard相似度。

???????? Jaccard相似度是用来描述两个集合间的相似度的，其计算方法如下（假设有两个集合A，B）：

，也就是A与B交集的元素个数除以A与B并集的元素个数；为了书写方便，下面的讨论中我们将集合A和B的Jaccard相似度记为SIM(A,B)；

例如：上图中有两个集合A，B；A中有4个元素，B中有5个元素；A，B的交集元素个数为2，并集元素个数为7，所以SIM(A,B) = 2 / 7；

k-Shingle

? ? ???假如我们把一整篇文章看成一个长的字符串，那么k-shingle就是这篇文档中长度为k的任意字符子串。所以，一篇文章就是很多个不同的k-shingle的集合。

? ? ? ? 例如：现在我们有一篇很短的文章，文章内容为abcdabd，令k=2，那么这篇文章中所有的2-shingle组成的集合为{ab,bc,cd,da,bd}，需要注意的是，ab在文章中出现了两次，但是在集合中只出现一次，这是因为集合中不能有相同的元素。

???????? 尽管用k-shingle的方式来表示每篇文章，然后再通过判断每篇文章中shingle集合的相同元素的数量，就可以得出文章的相似度；但是，一篇文章得到的shingle集合的元素个数是很多的。假定k=4，那么每个shingle中就会有4个字符，存在内存中就至少需要4个字节；那么要以这种方式存下一篇文章的所有shingle，需要的内存空间大概是原文档大小的4倍（假设原文档大小为100K，那么存下这篇文档的所有shingle则需要400K），这是因为原文档中的每个字符串都会出现在4个shingle中（除了开头和结尾那几个字符）。因此，以shingle的方式来存文章会消耗大量的内存。

???????? 接下来，我们需要把上面的shingle集合替换成规模小很多的“签名”集合。这样，就可以通过比较两篇文章的签名集合的相似度，就能够估计shingle的相似度了。这样得到的相似度只是原来相似度的近似值。

???????? 在介绍签名集合之前，我们先来看下如何将集合表示成其特征矩阵。

特征矩阵

特征矩阵的一列就对应一个集合，所有的行加起来就是所有集合元素的全集，如果集合中有那个元素，则矩阵中的对应位置为1，否则为0（好吧，讲的不是很清楚，还是直接上例子吧）：

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

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

其中第一行和第一列不是特征矩阵的一部分，只是为了便于理解而写上的。

最小哈希

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

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

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

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

最小哈希与Jaccard相似度

???????? 在经过行打乱后的两个集合计算得到的最小哈希值相等的概率等于这两个集合的Jaccard相似度。简单推导如下：

???????? 假设只考虑集合S1和S2，那么这两列所在的行有下面三种类型：

1.??????这一行的S1和S2的值都为1（即两列值都为1），记为X类；

2.??????这一行只有一个值为1，另一个值为0，记为Y类；

3.??????这一行两列的值都为0，记为Z类。

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

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

最小哈希签名

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

最小签名的计算

?????????? 其实得到上面的签名矩阵之后，我们就可以用签名矩阵中列与列之间的相似度来计算集合间的Jaccard相似度了；但是这样会带来一个问题，就是当一个特征矩阵很大时（假设有上亿行），那么对其进行行打乱是非常耗时，更要命的是还要进行多次行打乱。?????????????? 为了解决这个问题，可以通过一些随机哈希函数来模拟行打乱的效果。具体做法如下:

?????????? 假设我们要进行n次行打乱，则为了模拟这个效果，我们选用n个随机哈希函数h1,h2,h3…hn（注意，这里的h跟上面的h不是同一个哈希函数，只是为了方便，就不用其他字母了）。处理过程如下：

令SIG(i,c)表示签名矩阵中第i个哈希函数在第c列上的元素。开始时，将所有的SIG(i,c)初始化为Inf(无穷大)，然后对第r行进行如下处理：

1.??????计算h1(r),h2(r)…hn(r)；

2.??????对于每一列c:

a)????????如果c所在的第r行为0，则什么都不做；

b)????????如果c所在的第r行为1，则对于每个i=1,2…n，将SIG(i,c)置为原来的SIG(i,c)和hi(r)之间的最小值。

（看不懂的直接看例子吧，这里讲的比较晦涩）

例如，考虑上面的特征矩阵，将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;

局部敏感哈希算法（LSH）

???????? 通过上面的方法处理过后，一篇文档可以用一个很小的签名矩阵来表示，节省下很多内存空间；但是，还有一个问题没有解决，那就是如果有很多篇文档，那么如果要找出相似度很高的文档，其中一种办法就是先计算出所有文档的签名矩阵，然后依次两两比较签名矩阵的相似度；这样做的缺点是当文档数量很多时，要比较的次数会非常大。那么我们可不可以只比较那些相似度可能会很高的文档，而直接忽略过那些相似度很低的文档。接下来我们就讨论这个问题的解决方法。

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

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

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

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

文章来源：http://blog.csdn.net/liujan511536/article/details/47729721

聚类之minhash

最小哈希法

最小哈希原理介绍

1. MinHash是基于Jaccard Index相似度（海量数据不可行）的算法,一种降维的方法A，B 两个集合：A = {s1,s3,s6,s8,s9}? B = {s3,s4,s7,s10}
2. MinHash的基本原理:在A∪B这个大的随机域里，选中的元素落在A∩B这个区域的概率，这个概率就等于Jaccard的相似度

最小哈希：

?	S1	S2	S3
A	1	0	0
B	0	1	0
C	0	0	0
D	1	0	1

行的随机排列转换（也称置换运算）

?	S1	S2	S3
B	0	1	0
D	1	0	1
A	1	0	0
C	0	0	0

哈希值：排列转换后的行排列次序下第一个列值为1的行的行号，例如h(S1)=D，h(S2)=B

两个集合经随机排列之后得到的两个最小哈希值相等的概率等于这两个集合的Jaccard相似度。

问题：

对于上百万甚至数十亿的行选择一个随机排列转换极其消耗时间，怎么办？

1. 随机选择n个哈希函数h1，h2…
2. 对每列C进行如下操作：

　　　　a) ?如果c在第r行为0，则什么也不做；

　　　　b)?? 否则，如果c在第r行为1，那么对于每个i=1,2，…，n，将SIG（i,c）置为原来的SIG（i，c）和h(r)中的较小值

?

行	S1	S2	S3	S4	x+1 mod 5	3x+1 mod 5
0	1	0	0	1	1	1
1	0	0	1	0	2	4
2	0	1	0	1	3	2
3	1	0	1	1	4	0
4	0	0	1	0	0	3

计算最小哈希签名矩阵：

?	S1	S2	S3	S4
h1	1	3	0	1
h2	0	2	0	0

计算Jaccard相似度：

SIM(S1，S4)=1.0；SIM(S1，S3)=1/3；SIM(S1，S2)=0

真实SIM(S1，S4)=2/3；SIM(S1，S3)=1/4；SIM(S1，S2)=0

?

相关论文：

1.《Google News Personalization: Scalable Online Collaborative Filtering》

根据用户的历史点击数据，进行新闻推荐；采用最小哈希聚类的协同过滤算法

2.《The Link-Prediction Problem for Social Networks》

比较社交网络链接预测问题的各种算法

计算好友相似度的流程：

• 找到N个哈希函数，对每个用户好友集合生成一组Minhash（N个）
• 对于一个用户，按Minhash相同个数做排序，给出推荐候选集
• 计算用户跟被备选集的Jaccard Index
• 按Jaccard结果排序，给出TopN进行推荐

哈希函数生成和哈希值计算：

1. 输入向量Vector转换为bytes
   • numHashFunctions--预设生成hash函数的个数（假定为10个）

   • 

     for (int i = 0; i < numHashFunctions; i++) {
           for (Vector.Element ele : featureVector) {
             int value = (int) ele.get();
             bytesToHash[0] = (byte) (value >> 24);
             bytesToHash[1] = (byte) (value >> 16);
             bytesToHash[2] = (byte) (value >> 8);
             bytesToHash[3] = (byte) value;
             int hashIndex = hashFunction[i].hash(bytesToHash); //计算哈希函数值
             //只保留最小哈希值
             if (minHashValues[i] > hashIndex) {
               minHashValues[i] = hashIndex;
             }
           }
         }

     

     ?

2. 采用Mersenne Twister算法构造伪随机生成器
   • Random random = new MersenneTwisterRNG(new FastRandomSeedGenerator());
     • org.uncommons.maths.random. MersenneTwisterRNG.MersenneTwisterRNG( SeedGeneratorseedGenerator)
   • Mersenne Twister（马特赛特旋转演算法），是伪随机数发生器之一，其主要作用是生成伪随机数。
     Mersenne Twister算法的原理：Mersenne Twister算法是利用线性反馈移位寄存器(LFSR)产生随机数的，LFSR的反馈函数是寄存器中某些位的简单异或，这些位也称之为抽头序列。一个n位的LFSR能够在重复之前产生2^n-1位长的伪随机序列。只有具有一定抽头序列的LFSR才能通过所有2^n-1个内部状态，产生2^n - 1位长的伪随机序列，这个输出的序列就称之为m序列。为了使LFSR成为最大周期的LFSR，由抽头序列加上常数1形成的多项式必须是本原多项式。一个n阶本原多项式是不可约多项式，它能整除x^(2*n-1)+1而不能整除x^d+1，其中d能整除2^n-1。例如(32,7,5,3,1,0)是指本原多项式x^32+x^7+x^5+x^3+x^2+x+1，把它转化为最大周期LFSR就是在LFSR第32，7，5，2，1位抽头。利用上述两种方法产生周期为m的伪随机序列后，只需要将产生的伪随机序列除以序列的周期，就可以得到(0，1)上均匀分布的伪随机序列了。
     Mersenne Twister有以下优点：随机性好，在计算机上容易实现，占用内存较少(mt19937的C程式码执行仅需624个字的工作区域)，产生随机数的速度快、周期长，可达到2^19937-1，且具有623维均匀分布的性质，对于一般的应用来说，足够大了，序列关联比较小，能通过很多随机性测试。
3. 四种哈希函数生成器
   • MAX_INT_SMALLER_TWIN_PRIME = 2147482949；为什么选这个值？
     • 它是整型范围内最大孪生素数（相差为2的两个数都是质数的情况）的较小值；哈希用素数取模冲突小
   • seedA、seedB、seedC是采用MersenneTwisterRNG随机生成器生成的0~11均匀分布的随机数
   • 第一种：LinearHash
     

     

         @Override
         public int hash(byte[] bytes) {
           long hashValue = 31;
           for (long byteVal : bytes) {
             hashValue *= seedA * byteVal;
             hashValue += seedB;
           }
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }

     

   • 第二种:PolynomialHash

     

      @Override
         public int hash(byte[] bytes) {
           long hashValue = 31;
           for (long byteVal : bytes) {
             hashValue *= seedA * (byteVal >> 4);
             hashValue += seedB * byteVal + seedC;
           }
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }

     

   • 第三种：MurmurHashWrapper

     @Override
         public int hash(byte[] bytes) {
           long hashValue = MurmurHash.hash64A(bytes,seed);
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }

   • 第四种:MurmurHash3Wrapper

     @Override
         public int hash(byte[] bytes) {
           long hashValue = MurmurHash3.murmurhash3_x86_32(bytes,bytes.length,seed);
           return Math.abs((int) (hashValue % RandomUtils.MAX_INT_SMALLER_TWIN_PRIME));
         }?

来源：http://www.cnblogs.com/shipengzhi/articles/2826209.html

simhash算法原理及实现

simhash是google用来处理海量文本去重的算法。 google出品，你懂的。 simhash最牛逼的一点就是将一个文档，最后转换成一个64位的字节，暂且称之为特征字，然后判断重复只需要判断他们的特征字的距离是不是<n（根据经验这个n一般取值为3），就可以判断两个文档是否相似。

原理

simhash值的生成图解如下

大概花三分钟看懂这个图就差不多怎么实现这个simhash算法了。特别简单。谷歌出品嘛，简单实用。

算法过程大概如下：

1. 将Doc进行关键词抽取(其中包括分词和计算权重)，抽取出n个(关键词，权重)对， 即图中的(feature,weight)们。 记为?feature_weight_pairs?= [fw1,fw2 … fwn]，其中 fwn = (feature_n,weight_n`)。
2. hash_weight_pairs?= [ (hash(feature),weight) for feature,weight infeature_weight_pairs?] 生成图中的(hash,weight)们,此时假设hash生成的位数bits_count = 6（如图）;
3. 然后对?hash_weight_pairs?进行位的纵向累加，如果该位是1，则+weight,如果是0，则-weight，最后生成bits_count个数字，如图所示是[13,108,-22,-5,-32,55],这里产生的值和hash函数所用的算法相关。
4. 到此，如何从一个doc到一个simhash值的过程已经讲明白了。 但是还有一个重要的部分没讲，

   『simhash值的海明距离计算』

   二进制串A 和 二进制串B 的海明距离 就是?A xor B?后二进制中1的个数。

   举例如下：

   A = 100111;
   B = 101010;
   hamming_distance(A,B) = count_1(A xor B) = count_1(001101) = 3;

   当我们算出所有doc的simhash值之后，需要计算doc A和doc B之间是否相似的条件是：

   A和B的海明距离是否小于等于n，这个n值根据经验一般取值为3,

   simhash本质上是局部敏感性的hash，和md5之类的不一样。 正因为它的局部敏感性，所以我们可以使用海明距离来衡量simhash值的相似度。

   『高效计算二进制序列中1的个数』

   /* src/Simhasher.hpp */ bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3) { unsigned short cnt = 0; lhs ^= rhs; while(lhs && cnt <= n) { lhs &= lhs - 1; cnt++; } if(cnt <= n) { return true; } return false; }

   由上式这个函数来计算的话，时间复杂度是 O(n); 这里的n默认取值为3。由此可见还是蛮高效的。

   『计算二进制序列中1的个数之O(1)算法实现』

   感谢?@SCatWang?的评论分享：

   感谢您做的simhash库，感觉会很方便。 有关求二进制中1的个数，其实有各种O(1)的实现。可以参考这个地方：http://stackoverflow.com/a/14682688

   simhash 实现的工程项目

   • C++ 版本?simhash
   • Golang 版本?gosimhash

   主要是针对中文文档，也就是此项目进行simhash之前同时还进行了分词和关键词的抽取。

   对比其他算法

   『百度的去重算法』

   百度的去重算法最简单，就是直接找出此文章的最长的n句话，做一遍hash签名。n一般取3。 工程实现巨简单，据说准确率和召回率都能到达80%以上。

   『shingle算法』

   shingle原理略复杂，不细说。 shingle算法我认为过于学院派，对于工程实现不够友好，速度太慢，基本上无法处理海量数据。

   『其他算法』

   具体看微博上的讨论

   参考

   • Similarity estimation techniques from rounding algorithms
   • simhash与Google的网页去重
   • 海量数据相似度计算之simhash和海明距离
   
   

   
   

   来源：http://yanyiwu.com/work/2014/01/30/simhash-shi-xian-xiang-jie.html

   
   

   
   

   
   

   实现文本相似度算法（余弦定理）
   

   
   

   ? ? ? ?最近由于工作项目，需要判断两个txt文本是否相似，于是开始在网上找资料研究，因为在程序中会把文本转换成String再做比较，所以最开始找到了这篇关于?距离编辑算法?Blog写的非常好，受益匪浅。

   ????? ?于是我决定把它用到项目中，来判断两个文本的相似度。但后来实际操作发现有一些问题：直接说就是查询一本书中的相似章节花了我7、8分钟；这是我不能接受……

   ????? ?于是停下来仔细分析发现，这种算法在此项目中不是特别适用，由于要判断一本书中是否有相同章节，所以每两个章节之间都要比较，若一本书书有x章的话，这里需对比x(x-1)/2次；而此算法采用矩阵的方式，计算两个字符串之间的变化步骤，会遍历两个文本中的每一个字符两两比较，可以推断出时间复杂度至少为?document1.length × document2.length，我所比较的章节字数平均在几千～一万字；这样计算实在要了老命。

   ????? ?想到Lucene中的评分机制，也是算一个相似度的问题，不过它采用的是计算向量间的夹角（余弦公式），在google黑板报中的：数学之美（余弦定理和新闻分类）?也有说明，可以通过余弦定理来判断相似度；于是决定自己动手试试。

   ????? ?首相选择向量的模型：在以字为向量还是以词为向量的问题上，纠结了一会；后来还是觉得用字，虽然词更为准确，但分词却需要增加额外的复杂度，并且此项目要求速度，准确率可以放低，于是还是选择字为向量。

   ????? ?然后每个字在章节中出现的次数，便是以此字向量的值。现在我们假设：

   ????? ?章节1中出现的字为：Z1c1,Z1c2,Z1c3,Z1c4……Z1cn；它们在章节中的个数为：Z1n1,Z1n2,Z1n3……Z1nm；

   ???????章节2中出现的字为：Z2c1,Z2c2,Z2c3,Z2c4……Z2cn；它们在章节中的个数为：Z2n1,Z2n2,Z2n3……Z2nm；

   ????? ?其中，Z1c1和Z2c1表示两个文本中同一个字，Z1n1和Z2n1是它们分别对应的个数，

   ???????最后我们的相似度可以这么计算：

   

   ????? ?程序实现如下：（若有可优化或更好的实现请不吝赐教）

   public class CosineSimilarAlgorithm {
   	public static double getSimilarity(String doc1,String doc2) {
   		if (doc1 != null && doc1.trim().length() > 0 && doc2 != null
   				&& doc2.trim().length() > 0) {
   			
   			Map<Integer,int[]> AlgorithmMap = new HashMap<Integer,int[]>();
   			
   			//将两个字符串中的中文字符以及出现的总数封装到，AlgorithmMap中
   			for (int i = 0; i < doc1.length(); i++) {
   				char d1 = doc1.charAt(i);
   				if(isHanZi(d1)){
   					int charIndex = getGB2312Id(d1);
   					if(charIndex != -1){
   						int[] fq = AlgorithmMap.get(charIndex);
   						if(fq != null && fq.length == 2){
   							fq[0]++;
   						}else {
   							fq = new int[2];
   							fq[0] = 1;
   							fq[1] = 0;
   							AlgorithmMap.put(charIndex,fq);
   						}
   					}
   				}
   			}
   
   			for (int i = 0; i < doc2.length(); i++) {
   				char d2 = doc2.charAt(i);
   				if(isHanZi(d2)){
   					int charIndex = getGB2312Id(d2);
   					if(charIndex != -1){
   						int[] fq = AlgorithmMap.get(charIndex);
   						if(fq != null && fq.length == 2){
   							fq[1]++;
   						}else {
   							fq = new int[2];
   							fq[0] = 0;
   							fq[1] = 1;
   							AlgorithmMap.put(charIndex,fq);
   						}
   					}
   				}
   			}
   			
   			Iterator<Integer> iterator = AlgorithmMap.keySet().iterator();
   			double sqdoc1 = 0;
   			double sqdoc2 = 0;
   			double denominator = 0; 
   			while(iterator.hasNext()){
   				int[] c = AlgorithmMap.get(iterator.next());
   				denominator += c[0]*c[1];
   				sqdoc1 += c[0]*c[0];
   				sqdoc2 += c[1]*c[1];
   			}
   			
   			return denominator / Math.sqrt(sqdoc1*sqdoc2);
   		} else {
   			throw new NullPointerException(
   					" the Document is null or have not cahrs!!");
   		}
   	}
   
   	public static boolean isHanZi(char ch) {
   		// 判断是否汉字
   		return (ch >= 0x4E00 && ch <= 0x9FA5);
   
   	}
   
   	/**
   	 * 根据输入的Unicode字符，获取它的GB2312编码或者ascii编码，
   	 * 
   	 * @param ch
   	 *            输入的GB2312中文字符或者ASCII字符(128个)
   	 * @return ch在GB2312中的位置，-1表示该字符不认识
   	 */
   	public static short getGB2312Id(char ch) {
   		try {
   			byte[] buffer = Character.toString(ch).getBytes("GB2312");
   			if (buffer.length != 2) {
   				// 正常情况下buffer应该是两个字节，否则说明ch不属于GB2312编码，故返回'?'，此时说明不认识该字符
   				return -1;
   			}
   			int b0 = (int) (buffer[0] & 0x0FF) - 161; // 编码从A1开始，因此减去0xA1=161
   			int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一个字符和最后一个字符没有汉字，因此每个区只收16*6-2=94个汉字
   			return (short) (b0 * 94 + b1);
   		} catch (UnsupportedEncodingException e) {
   			e.printStackTrace();
   		}
   		return -1;
   	}
   }

   ????? ?程序中做了两小的改进，以加快效率：

   ????? ?1. 只将汉字作为向量，其他的如标点，数字等符号不处理；2. 在HashMap中存放汉字和其在文本中对于的个数时，先将单个汉字通过GB2312编码转换成数字，再存放。

   ????? ?最后写了个测试，根据两种不同的算法对比下时间，下面是测试结果：

   ????? ?余弦定理算法：doc1 与 doc2 相似度为：0.9954971,耗时：22mm

   ????? ?距离编辑算法：doc1 与 doc2 相似度为：0.99425095,耗时：322mm

   ????? ?可见效率有明显提高，算法复杂度大致为：document1.length + document2.length。

   ? ? ? ?

   文章来源：?http://my.oschina.net/BreathL/blog/42477

   
   

   
   

   PHP实现余弦相似度算法

   
   

   上一次，我用TF-IDF算法自动提取关键词。

   今天，我们再来研究另一个相关的问题。有些时候，除了找到关键词，我们还希望找到与原文章相似的其他文章。比如，"Google新闻"在主新闻下方，还提供多条相似的新闻。

   

   为了找出相似的文章，需要用到"余弦相似性"（cosine similiarity）。下面，我举一个例子来说明，什么是"余弦相似性"。

   为了简单起见，我们先从句子着手。

   　　句子A：我喜欢看电视，不喜欢看电影。

   　　句子B：我不喜欢看电视，也不喜欢看电影。

   请问怎样才能计算上面两句话的相似程度？

   基本思路是：如果这两句话的用词越相似，它们的内容就应该越相似。因此，可以从词频入手，计算它们的相似程度。

   第一步，分词。

   　　句子A：我/喜欢/看/电视，不/喜欢/看/电影。

   　　句子B：我/不/喜欢/看/电视，也/不/喜欢/看/电影。

   第二步，列出所有的词。

   　　我，喜欢，看，电视，电影，不，也。

   第三步，计算词频。

   　　句子A：我 1，喜欢 2，看 2，电视 1，电影 1，不 1，也 0。

   　　句子B：我 1，喜欢 2，看 2，电视 1，电影 1，不 2，也 1。

   第四步，写出词频向量。

   　　句子A：[1,0]

   　　句子B：[1,1]

   到这里，问题就变成了如何计算这两个向量的相似程度。

   我们可以把它们想象成空间中的两条线段，都是从原点（[0,...]）出发，指向不同的方向。两条线段之间形成一个夹角，如果夹角为0度，意味着方向相同、线段重合；如果夹角为90度，意味着形成直角，方向完全不相似；如果夹角为180度，意味着方向正好相反。因此，我们可以通过夹角的大小，来判断向量的相似程度。夹角越小，就代表越相似。

   以二维空间为例，上图的a和b是两个向量，我们要计算它们的夹角θ。余弦定理告诉我们，可以用下面的公式求得：

   假定a向量是[x1,y1]，b向量是[x2,y2]，那么可以将余弦定理改写成下面的形式：

   数学家已经证明，余弦的这种计算方法对n维向量也成立。假定A和B是两个n维向量，A是 [A1,A2,...,An] ，B是 [B1,B2,Bn] ，则A与B的夹角θ的余弦等于：

   使用这个公式，我们就可以得到，句子A与句子B的夹角的余弦。

   余弦值越接近1，就表明夹角越接近0度，也就是两个向量越相似，这就叫"余弦相似性"。所以，上面的句子A和句子B是很相似的，事实上它们的夹角大约为20.3度。

   由此，我们就得到了"找出相似文章"的一种算法：

   　　（1）使用TF-IDF算法，找出两篇文章的关键词；

   　　（2）每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；

   　　（3）生成两篇文章各自的词频向量；

   　　（4）计算两个向量的余弦相似度，值越大就表示越相似。

   "余弦相似度"是一种非常有用的算法，只要是计算两个向量的相似程度，都可以采用它。

   
   

   下面是PHP实现余弦相似度计算的算法

   <?php
   /**
    * 数据分析引擎
    * 分析向量的元素 必须和基准向量的元素一致，取最大个数，分析向量不足元素以0填补。
    * 求出分析向量与基准向量的余弦值
    */
   /**
    * 获得向量的模
    * @param unknown_type $array 传入分析数据的基准点的N维向量。|eg:array(1,1);
    */
   function getMarkMod($arrParam){
           $strModDouble = 0;
           foreach($arrParam as $val){
                   $strModDouble += $val * $val;
           }
           $strMod = sqrt($strModDouble);
           //是否需要保留小数点后几位
           return $strMod;
   }
   
   /**
    * 获取标杆的元素个数
    * @param unknown_type $arrParam
    * @return number
    */
   function getMarkLenth($arrParam){
           $intLenth = count($arrParam);
           return $intLenth;
   }
   
   /**
    * 对传入数组进行索引分配，基准点的索引必须为k，求夹角的向量索引必须为 'j'.
    * @param unknown_type $arrParam
    * @param unknown_type $index
    * @ruturn $arrBack
    */
   function handIndex($arrParam,$index = 'k'){
           foreach($arrParam as $key => $val){
                   $in = $index.$key;
                   $arrBack[$in] = $val;
           }
           return $arrBack;
   }
   
   /**
    *
    * @param unknown_type $arrMark 标杆向量数组（索引被处理过）|array('k0'=>1,'k1'=>2....)
    * @param unknown_type $arrAnaly 分析向量数组（索引被处理过）|array('j0'=>1,'j1'=>2....)
    * @param unknown_type $strMarkMod 标杆向量的模
    * @param unknown_type $intLenth 向量的长度
    */
   function getCosine($arrMark,$arrAnaly,$strMarkMod,$intLenth){
           $strVector = 0;
           $strCosine = 0;
           for($i = 0; $i < $intLenth; $i++){
                   $strMarkVal = $arrMark['k'.$i];
                   $strAnalyVal = $arrAnaly['j'.$i];
                   $strVector += $strMarkVal * $strAnalyVal;
           }
           $arrAnalyMod = getMarkMod($arrAnaly); //求分析向量的模
           $strFenzi = $strVector;
           $strFenMu = $arrAnalyMod * $strMarkMod;
           $strCosine = $strFenzi / $strFenMu;
           if(0 !== (int)$strFenMu){
                   $strCosine = $strFenzi / $strFenMu;
           }
           return $strCosine;
   }
   //基准点的N维向量
   $arrMark = array(1,1);
   //分析点的N维向量
   $arrAnaly = array(1,4,5);
   //向量的模
   $MarkMod = getMarkMod($arrMark);
   //向量的长度
   $MarkLenth = getMarkLenth($arrMark);
   //标杆向量数组
   $Index1 = handIndex($arrMark,"k");
   //分析向量数组
   $Index2 = handIndex($arrAnaly,"j");
   //分析向量与基准向量的余弦值
   $Cosine = getCosine($Index1,$Index2,$MarkMod,$MarkLenth);
   echo "向量的模：".$MarkMod;
   echo "<br>";
   echo "向量的长度：".$MarkLenth;
   echo "<br>";
   echo "标杆向量数组：";
   print_r($Index1);
   echo "<br>";
   echo "分析向量数组：";
   print_r($Index2);
   echo "<br>";
   echo "分析向量与基准向量的余弦值：".$Cosine;
   ?>

   
   
   

   

   
   

   
   

   

   
   

   
   小润测试的demo如上图

   
   

   来源：http://www.tuicool.com/articles/YB3uy2N

   
   

   
   

   简单结论：

   标题相似性的判断，一般使用 minhash，内容相似性判断一般使simhash，简单业务可以使用余弦算法。