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实质也是一种降维技术,降维后的数据计算复杂度会减少很多。

分类: 算法