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

? ? ? ? ?在数据发掘中，有一个较量根基的题目，就是较量两个荟萃的相似度。关于这个题目，最笨的要领就是用一个两重轮回来遍历这两个荟萃中的全部元素，进而统计这两个荟萃中沟通元素的个数。可是，当这两个荟萃里的元素数目很是复杂时，同时又有许多个荟萃必要判定两两之间的相似度时，这种要领就呵呵了，对内存和时刻的耗损都很是大。因此，为了办理这个题目，数据发掘中有另一个要领。

Jaccard相似度

?????????在先容详细算法之前，我们起首来相识一个观念：Jaccard相似度。

???????? Jaccard相似度是用来描写两个荟萃间的相似度的，其计较要领如下（假设有两个荟萃A，B）：

譬喻：上图中有两个荟萃A，B；A中有4个元素，B中有5个元素；A，B的交集元素个数为2，并集元素个数为7，以是SIM(A,B) = 2 / 7；

? ? ???若是我们把一整篇文章当作一个长的字符串，那么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，则新的特性矩阵为：

最小哈希与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:

???????? 通过上面的要领处理赏罚事后，一篇文档可以用一个很小的署名矩阵来暗示，节减下许多内存空间；可是，尚有一个题目没有办理，那就是假若有许多篇文档，那么假如要找出相似度很高的文档，个中一种步伐就是先计较出全部文档的署名矩阵，然后依次两两较量署名矩阵的相似度；这样做的弱点是当文档数目许多时，要较量的次数会很是大。那么我们可不行以只较量那些相似度也许会很高的文档，而直接忽略过那些相似度很低的文档。接下来我们就接头这个题目的办理要领。

???????? 起首，我们可以通过上面的要领获得一个署名矩阵，然后把这个矩阵分别成b个行条(band)，每个行条由r行构成。对付每个行条，存在一个哈希函数可以或许将行条中的每r个整数构成的列向量（行条中的每一列）映射到某个桶中。可以对全部行条行使沟通的哈希函数，可是对付每个行条我们都行使一个独立的桶数组，因此即即是差异行条中的沟通列向量，也不会被哈希到统一个桶中。这样，只要两个荟萃在某个行条中有落在沟通桶的两列，这两个荟萃就被以为也许相似度较量高，作为后续计较的候选对；而那些在全部行条中都不落在统一个桶中的两列，就会被以为相似度不会很高，而被直接忽略。下面直接看一个例子：

譬喻，此刻有一个12行署名矩阵，把这个矩阵分为4个行条，每个行条有3行；为了利便，这里只写出行条1的内容。

???????? 颠末上面的处理赏罚后，我们就找出了相似度也许会很高的一些候选对，接下来我们只需对这些候选队举办较量就可以了，而直接忽略那些不是候选对的荟萃。这个要领适实用来计较相似度高出某个值的文档的相似度，而不合用于计较全部文档的相似度，由于那些相似度也许很低的文档已经被直接忽略了。

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

聚类之minhash

（编辑：湖南网）

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