[转]文内情似性算法：simhash/minhash/余弦算法

数据发掘之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从差异的角度办理这个题目。

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

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!