首页 > 代码库 > minhash算法
minhash算法
在实际应用的过程中，相似性度量和计算是非常常用的一个方法，例如网页去重、判断帖子是否相似、推荐系统衡量物品或者用户的相似度等等，当数据量大的时候，计算的时间和空间复杂度就会是一个非常重要的问题，例如在判断相似发帖的时候，我们可以用kmeans来进行聚类，但是资源的消耗是巨大的，所以本文推荐一种方法，minhash+lsh（局部敏感hash），用minhash来降维，用lsh来做近似查询，本文主要介绍一下minhash。
在介绍minhash之前，先给出相似性的度量方法。
相似性的度量
相似性度量有很多方法，欧氏距离是比较常用的，这里我们用一下Jaccard相似性系数，公式如下
计算方法很简单，文档A和文档B共有的单词数除以A和B单词的集合，例如A={a,b,c,d}，B={c,d,e,f}，那么相似性系数就是2/6=0.33。
minhash
刚才我们知道在求相似度的时候我们用到了文档和单词。通常情况下，我们都会将文档和单词表示成doc-term矩阵的形式，可以看到term具体的是什么对最后的结果没有任何影响，所以我索性用行号来代表term，行号跟term是一一对应的，例如
| s1 | s2 | s3 | |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 |
第一行中的S1,、S2、S3表示文档，第一列的01234表示行号，也即单词，其他部分1表示文档S中有这个单词，0表示没有这个单词，有了这个集合，我们看一下minhash是怎么做的
随机确定一个顺序，例如上面的顺序是01234，随机确定一个顺序，例如12340，注意这里是随机，目的就是不让最后的结果受人为的干扰，结果如下
| s1 | s2 | s3 | |
| 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 |
| 4 | 1 | 0 | 0 |
我们看到，行号是不变的，行号还是那个行号，变化的是矩阵的内容。找到排在最前面的1代表这个文档，例如S1排在最前面的1行号为2，那么就用2代表文档S1，同理，用1代表S2，那么可以计算S1和S2的相似性系数了，1交2除以1并2等于0。后面会给出为什么用这种方法是合理的证明。我们暂时先跳过。可以想象一下，用一个单词来代表一个文档偶然性会比较大，那么这个时候我们的想法可能是，可以随机的产生多次变换，取出多个单词来进行比较。这个时候问题就来了，在实际应用的过程中，文档可能有几百万，单词也会有几万，对如此庞大的矩阵做变换时间和空间的代价都会比较大，是不是有别的方法呢，答案是肯定的，我们知道运动是相对的，之前是变换矩阵内容不变行号，我们现在不变矩阵，只变换行号，是不是计算量少了非常多。所以问题转换为如何产生随机的行号，例如
用两个hash函数来产生行号的顺序，两个函数可以自己定义，最好保证hash后的值均匀，例如
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。