分布式平台下MinHash算法研究与实现

王洪亚等

摘 要：MinHash作为位置敏感哈希（LSH）算法中的一种，可以用来快速估算两个集合的相似度，查找网络上的重复网页或者相似新闻网页，MinHash算法使用Jaccard相似度来度量对象的相似程度。本文针对MinHash算法在分布式平台上的实现和性能表现进行分析和研究，给出了MinHash的分布式算法。最后通过具体的实验，验证了提出的MinHash算法在处理实际问题上的正确性和准确性。

关键词：MinHash；分布式；算法实现

中图分类号：TP311 文献标识号：A 文章编号：2095-2163（2014）06-

Abstract： MinHash is a kind of Locality Sensitive Hashing algorithm （LSH）， which can be used to quickly estimate the similarity of two sets to find the？duplicate？web pages or the similar news pages on the web. This paper focuses on the MinHash implementations and Performance in distributed platform， and devise the distributed MinHash algorithm. To verify the soundness of the new version， the paper conducts extensive experiments with several real datasets. Experimental results confirm the validity and accuracy of the proposed implementation.

Keywords： MinHash； Distributed； Algorithm Implementation

0 引 言

近年来，在很多应用设计中，面对和需要处理的往往是具有很高维度的，因而大数据研究领域也随之创建与兴起。怎样海量的高维数据集合中快速寻获与某一数据最相似（距离最近）的一个或多个数据即成为该领域的重点问题。如果是低维的小数据集，通过线性查找（Linear Search）就可以轻松解决；但如果是对一个海量的高维数据集采用线性查找匹配，时间开销必然巨大，针对此一问题，就需要采用诸如索引的技术来加快查找过程，通常可将其称为最近邻查找（Nearest Neighbor Search）[1]。最近邻查找是在很多重要实际应用中发挥了优势作用的经典技术。迄至目前为止，随着数据量的不断增大，数据维度的日渐增加，更多的新算法正陆续提出以用于解决在各类背景条件下出现的最近邻查找问题。

在现实研究进程中，随着精确最近邻查找问题解决难度的增加，人们发现近似最近邻查找的结果也能满足实际的应用需求[2]，而将其与精确最近邻查找相比，又能在效率上获得很大的提高，因此近似最近邻查找问题又相应地成为研发热点。近似最近邻查找是以牺牲查找精度为代价来换取查找效率的提高，从而达到将查找效率与查找结果折衷平衡的目的。位置敏感哈希（LSH）即可用于解决近似最近邻查找问题，并在实际应用中获得了显著突出的效果，而且堪称是解决维度灾难的一个有效方法。LSH方法能够以概率方式在保证一定查询精确度的前提下实现快速的近似最近邻查询[1]。MinHash也是LSH 算法中的一种，多是用来快速估算两个集合的相似，其中通过使用Jaccard相似度来度量对象的相似程度。具体来说，MinHash是由Andrei Broder首次提出，可用于在搜索引擎中检测重复网页或者查找相似新闻网页以及文章[2，3]，MinHash算法的实际效果与其重要参数k、L密切相关，这些参数的设定与数据本身的性质是直接对应的。所以为了实现MinHash算法，对各种不同类型的高维数据集与MinHash算法的参数之间联系而开展研究将具有重要的现实及理论意义。

基于上述讨论，本文主要贡献如下：

（1）研究分析MinHash算法在分布式开源平台中应用的可行性，并发现MinHash算法在分布式平台上将比非分布式平台具有更大优势，尤其是当处理大规模数据集时。

（2）给出了MinHash算法的新的分布式模型，实现了分布式平台中MinHash算法，并通过具体实验进行了验证以及说明。

1相关工作

LSH由Indyk等人最初提出用来解决近似最近邻查找问题，其基本思想是使数据集中距离相近的点生成相同的哈希键值，也就是能哈希到一个桶中，而对数据集中距离较远的点将生成不同的键值，从而哈希到不同的桶中[1]。经过实践已经证明，LSH算法在空间占用以及时间查询效率上较其他算法都具有明显优势地位[4]。LSH方法就是以概率方式在保证一定查询精确度的前提下实现快速的近似最近邻查询，并通过查全率和准确率而换取了空间或时间效率。

LSH的应用场景众多，凡是需要进行大量数据之间的相似度（或距离）计算的场合都可以使用LSH来加快查找匹配速度，具体例示则如查找网络上的重复网页或者查找相似新闻网页以及文章这些具体研究即需要LSH算法族中的MinHash来实现与完成。MinHash算法作为该算法族中的一个常用方法，其最基本应用即在于搜索引擎中检测重复网页等。

基于以上介绍，本文将针对MinHash算法在分布式平台上的设计实现和性能方面表现进行分析与研究。并且由于位置敏感哈希（LSH）在高维数据空间近邻查找性能的高效表现，该算法在实际研究中得到了众多应用。只是目前全部已有算法的性能分析都是基于理论分析模型来实现估算，却少有学者致力于理论分析模型在分布式平台上的应用研究。

2 MinHash算法原理

LSH提供了一种在海量的高维数据集中查找与查询数据点（Query data point）近似最相邻的某个或某些数据点的有效方法。LSH并非一定能够找到与查询点最相邻的数据，而是在尽量减少需要匹配的数据点个数的同时，却能保证查找到最近邻数据点的概率较大。MinHash算法则使用Jaccard相似度作为度量标准，可用于在搜索引擎中检测重复网页等。下面分别给出LSH算法和MinHash算法的具体论述和分析。

给定两个有限集合A和B，这两个集合具有相同MinHash签名的概率定义可描述为如下函数：

以上函数即称为MinHash函数。

MinHash算法的实现过程中，一般性做法就是对目标项进行多次哈希处理，使得相似项与不相似项相较而言，更具可能哈希到同一桶中。同时再将至少有一次哈希到同一桶中的文档对视为候选对，而只需检查这些候选对之间的相似度，再基于候选对集合找出真正的相似文档。

对给定集合A、B，hmin（A）=hmin（B）成立的条件是中具有最小哈希值的元素也在中。这里有一个假设，h（x）是一个良好的哈希函数，具有良好的均匀性，并能将不同元素映射成不同的整数。所以有，Pr[hmin（A）=hmin（B）]=J（A，B），即集合A和B的相似度为集合A、B经过hash后最小哈希值相等的概率，而其成为候选对的概率则为1-（1-SL）K，其中S是集合A和B的Jaccard相似度[5]。

3 Mahout中MinHash算法实现

本文即在Mahout分布式平台[6]中实现MinHash算法，由于Mahout中算法均由MapReduce算法模型来构造确定，因而基于此，MinHash算法主要包括MinHashDriver、MinHashMapper、MinHashReducer、HashFactory和HashFunction五个java文件。MinHash算法使用简单工厂模式来运作并处理，其中MinHashDriver作为整个算法的驱动程序，所有的参数都在这个文件中指定或者获取，而且还绑定了map程序为MinHashMapper和reduce程序为MinHashReducer；同时HashFunction作为算法的接口，将在MinHashMapper的map中重写哈希函数。

具体地，MinHashDriver是在终端直接调用MinHash代码实现的直接接口，其中指定了MinHash包运行的相关参数的读取和设定，以及map和reduce程序的绑定。类HashFactory中指定HashType，在枚举类型HashType中有LINEAR， POLYNOMIAL， MURMUR， MURMUR3四种子类；在本文的实验中，使用这四种哈希类型验证正确的MinHash算法，结果显示差距不大，因此本文实验使用默认的LINEAR类型。在HashFactory中调用LinearHash函数，生成numFunctions个hashFunction。

MinHash算法主要逻辑实现在MinHashMapper中，map程序读入（key，value）格式数据，使用value中的token作为生成minHashValues的参数在for循环中获得token， 通过对bytesToHash数组做移位操作，然后作为hash函数的参数生成hashIndex，最后再计算哈希函数值，并保留最小哈希值。将minHashValues值组合作为Bucket输出，使用“-”将minHashValues连接起来，外层循环是lTable，内层循环是keyGroups，具体功能是：对每个文件做L次运算（分别映射到L个Bucket中），每个Bucket的格式为XXX-XXX，新的map的key是cluster，即Bucket，value是对应的文件名。

4 实验

在这一节中，将使用数据集Reuters-21578，证明了Mahout平台中原有MinHash算法的错误和修正后MinHash算法的正确，并给出实验分析。本文实验使用Dell PowerEdge T320服务器，操作系统是32位Ubuntu 11.04，Java 1.6，Mahout版本0.6，Hadoop版本0.20.0。需要注意的是，在安装Mahout之前，需要安装Maven3。路透社新闻数据集Reuters-21578 是文本分类研究经常使用的数据集。在整个数据集中有21 578个文档，由135个类别组成，这些文档在做预处理后才能使用Mahout中提供的序列化和向量化工具类。

在2.2节中，可以知道，给定两个有限集合A和B，其成为候选对的概率为1-（1-SL）K，其中S是集合A和B的Jaccard相似度。函数1-（1-SL）K的图像大致是S-曲线。曲线中候选概率为处对应的相似度就是阈值，而且还是L和K的函数，该阈值的一个近似估计是（1/L）1/k。表1给出了对给定参数L=4，k=2时，函数1-（1-SL）K的值与相似度S的变化关系。该表反映了不同Jaccard相似度对应的理想碰撞概率。

5 结束语

本文针对MinHash算法在分布式平台上的实现和性能表现进行分析和研究。通过研究发现， MinHash算法在分布式平台上比非分布式平台有很大优势，尤其是在处理大规模数据集时。为此，即在深入研究MinHash算法原理和分布式平台的基础上，设计了MinHash的分布式算法。实验结果表明本文给出的MinHash分布式算法在处理实际问题上的正确性和准确性，这也为今后的在分布式平台上解决近似近邻问题提供了一个新的思路。

参考文献：

[1] INDYK P， MOTWANI R. Approximate nearest neighbors： towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM， 1998： 604-613.

[2] BRODER， ANDREI Z？.？On the resemblance and containment of documents， Compression and Complexity of Sequences： Proceedings[C]//Positano， Amalfitan Coast， Salerno， Italy， IEEE， June 11-13， 1997：？21–29.

[3] WANG H， CAO J， SHU L C， et al. Locality sensitive hashing revisited： filling the gap between theory and algorithm analysis[C]//Proceedings of the 22nd ACM international conference on Conference on information & knowledge management， ACM， 2013： 1969-1978.

[4] DATAR M， IMMORLICA N， INDYK P， et al. Locality- sensitive hashing scheme based on p-stable distributions[J]. SCG04， June 9-11， 2004.

[5] Rajaraman A， Ullman J D. Mining of massive datasets[M]. Cambridge University Press， 2012.

[6] Anil R， Dunning T， Friedman E. Mahout in action. Manning， 2011.