基于MinHash的相似性算法

原文链接：基于MinHash的相似性算法 – 每天进步一点点

MinHash也称最小哈希式独立排列局部性敏感哈希，是一种非常快速的对两个不同集合进行相似性分析的方法。该算法起初主要用于在搜索引擎中的重复网页检查，现在也应用于解决大规模聚类问题。

1.与Jaccard相似性关系

在采用基于Jaccard算法进行形似度计算时，需要两两计算交集和并集，这在海量数据中是一件比较困难的事情，空间复杂度和时间复杂度都会比较大，因此需要引人新的相似性算法-MinHash，用于解决计算量较大的问题。
采用MinHash 可以减小过程中的计算复杂度。其基本原理为有两个集合A、B，在集合A与集合B的并集中，选取的元素同时也在集合4和集合B中的概率等于Jaccard的相似度。例如，对于集合A＝｛a，b，c｝，集合B＝（b，c，d｝，根据Jaccard相似系数计算出集合4和集合B的Jaccard相似度为：2÷4＝0.5；计算过程中AUB＝｛a，b，c，d｝，ANB＝｛b，c｝，将并集中随机选取一个元素，属于交集的概率为0.5，即与Jaccard相似度相等。

2.计算网页文本相似性过程

整个计算流程依然基于Jaccard 相似系数，不同的是引入了哈希函数的机制。例如，针对哈希函数H，对集合中的每个元素进行哈希计算，如集合A中包含10个元素，则对10个元素均进行哈希计算，选取出计算过程中哈希值最小的元素。采用同样的哈希函数H，对集合B中的每个元素也进行哈希计算，选取出哈希值最小的元素，在集合A和集合B中最小哈希值相等的概率即为集合A和集合B的相似度。
上述过程仅采用了一组哈希函数H，重复上面的步骤，用N个哈希函数进行对每组元素进行哈希计算，每个哈希函数产生的最小哈希值均进行存放，则对集合A而言，产生了N个最小哈希值，对于集合B而言，也产生了N个最小哈希值，现在只需要对集合A产生的最小哈希值集合以及集合B产生的最小哈希值集合计算其Jaccard相似度即可。如图4-1所示，集合A｛a，b，c，d｝计算出的哈希值为11和8，集合B｛c，d，e｝计算出的哈希值为11和9。

计算集合A和集合B的Jaccard 相似度，通过两个哈希方法之后，转换为求新集合的Jaccard 相似度。试想，集合A和集合B都非常庞大的情况下，如果进行交集和并集计算，性能上则存在隐患。通过N个哈希函数求得最小哈希值的方式，虽然不能非常精确的计算出集合的相似度，但是MinHash的方法使结果非常接近最终的结果，并且计算复杂度大大降低。

通过上述流程可以降低计算的复杂度，因为MinHash实质也是一种降维技术，降维后的数据计算复杂度会减少很多。