Loading... ## 前言 MinHash算法属于`Locality Sensitive Hashing, LSH`,用于快速估计两个集合的相似度。最早由Broder Andrei Z. 在1997年提出,最初在AltaVista搜索引擎中用于在搜索结果中检测并消除重复Web页面。如今广泛应用于大数据集的相似检索、推荐系统、聚类分析等中。 --- ## 局部敏感哈希 局部敏感哈希`LSH(Locality Sensitive Hashing)`算法是**近似最近邻搜索算法**中最流行的一种,而近似最近邻搜索最通俗的解释就是寻找与指定对象相似的目标对象。其主要应用于从**海量的**数据中挖掘出**相似的**数据,可以具体应用到文本相似度检测、网页搜索等领域。 LSH算法过程大致分为三步: 1. Shingling:将文本文档转换为集合表示 (通常是转换为布尔型向量) 2. Min-Hashing: 将高维度的向量转换为低维的哈希签名,此时再计算哈希签名的相似性 3. Locality-Sensitive Hashing: 重点关注来自相似文档的一对候选哈希签名 (上述的三个步骤中,第一步Shingling属于文本的向量化,这是一个非常大的方面) MinHash算法主要工作是对输入的高维向量(可能是几百万维甚至更高)转换为低维的向量(降维后的向量被称作数字签名),然后再对低维向量计算其相似,以达到降低计算成本,提高运行效率的目的, 我们接下来需要关注的就是MinHash是如何实现上述需求的了。 --- ## Jaccard 相似度 Jaccard相似度计算的是两个集合的相似性, 两个集合中,交集的个数/并集的个数。 定义集合A和B的的 Jaccard 系数为 $$ \frac{|A \cap B|}{|A \cup B|} $$ 假设有如下集合, $$ \begin{align} S_1 &= \{1,2,5\} \\ S_2 &= \{3\} \\ S3 &= \{2,3,4,6\} \end{align} $$ 集合 $S_1$ 和 $S_3$ 之间的 `Jaccard similarity` 为 $$ \begin{align} JS(S_1, S_3) = \frac{|\{ 2\}|}{|\{1,2,3,4,5,6\}|} = \frac{1}{6} \end{align} $$ 当处理文本时,两个集合可以是两个文本的 `字` 集合,也可以是分词后的 `词` 集合, 如果词集合太大,也可以先用 `TF-IDF` 筛选出比较重要的关键词作为词集。 Jaccard相似度和汉明距离类似的,只不过汉明距离考虑位置信息,而Jaccard相似度不考虑位置。 --- ## MinHash 与SimHash不同,MinHash要从衡量两个文档的相似度说起。Jaccard相似度用于描述两个集合的相似程度,假设有两个集合A和B,相似度=A与B交集的元素个数/A与B并集的元素个数,公式为: $$ JS(A,B) = \frac{|A \cap B|}{|A \cup B|} $$ 海量文本直接求Jaccard相似度复杂度太高,两个文档需要逐个词比较,为降低复杂度,我们使用两个文档的最小哈希值相等的概率来等价于两个文档的Jaccard相似度,并可以证明两者是相等的。首先说明一下如何求一个集合的最小哈希值,假设现在有4个集合,分别为S1,S2,S3,S4;其中,S1={a,d}, S2={c}, S3={b,d,e}, S4={a,c,d},所以全集U={a,b,c,d,e}。我们可以构造如下0-1矩阵: | 元素 | S1 | S2 | S3 | S4 | | ---- | -- | -- | -- | -- | | a | 1 | 0 | 0 | 1 | | b | 0 | 0 | 1 | 0 | | c | 0 | 1 | 0 | 1 | | d | 1 | 0 | 1 | 1 | | e | 0 | 0 | 1 | 0 | 为得到各集合的最小哈希值,首先对矩阵进行`随机行打乱`,则某个集合(某一列)的最小哈希值就等于打乱后第一个值为1的行所在的行号。定义一个最小哈希函数h,用于模拟对矩阵进行随机打乱,假设打乱后的矩阵如下表所示: | 元素 | S1 | S2 | S3 | S4 | | ---- | -- | -- | -- | -- | | b | 0 | 0 | 1 | 0 | | e | 0 | 0 | 1 | 0 | | a | 1 | 0 | 0 | 1 | | d | 1 | 0 | 1 | 1 | | c | 0 | 1 | 0 | 1 | 则h(S1)=2, h(S2)=4, h(S3)=0, h(S4)=2。经过随机打乱后,两个集合的最小哈希值相等的概率=两集合的Jaccard的相似度证明如下: > 仅考虑集合S1和S2,那么这两列所在的行有以下三种情况: > > 1. S1和S2的值都为1,用X表示; > 2. 一个值为1,另一个为0,用Y表示; > 3. S1和S2的值都为0,用Z表示。 S1与S2的交集元素个数为X,并集个数为X+Y,所以sim(S1,S2)=Jaccard(S1,S2)=X/(X+Y)。随机打乱后h(S1)=h(S2)的概率等于从上往下扫描,在遇到Y行之前遇到X行的概率(Z行没有影响),或者说把X个黑球和Y个白球放入一个袋子中,首次拿到黑球的概率,即h(S1)=h(S2)的概率为X/(X+Y)。假设特征矩阵很大时,对其进行打乱非常耗时,而且要进行多次打乱,其实可以通过多个随机哈希函数来模拟打乱的效果。具体地,定义n个随机哈希函数$h_1, h_2,…,h_n$,sig(i,j)表示签名矩阵中第i个哈希函数在第j列上的元素,将签名矩阵中各个元素sig(i,j)初始化为inf(无穷大),对原矩阵中每一行r: 1. 计算$h_1(r),h_2(r),...,h_n(r) $; 2. 对于每一列j: * 如果j所在的第r行为0,什么都不做; * 如果j所在的第r行为1,则对每个i=1,2,…,n,$sig(i,j)=min(sig(i,j), h_i(r))$ 例如$h_1(x)=(x+1)%5, h_2(x)=(3\*x+1)%5$,则经过上述操作可获得如下的签名矩阵: | 哈希函数 | S1 | S2 | S3 | S4 | | -------- | -- | -- | -- | -- | | $h_1$ | 1 | 3 | 0 | 1 | | $h_2$ | 0 | 2 | 0 | 0 | 上述获得各文档签名矩阵可以理解为一个降维过程,获得签名后,假如数据量十分庞大的话,两两比较的话计算复杂度仍然非常高,所以需要类似SimHash索引分块的方法来降低查询复杂度。当一个新文档到达时,希望仅比较与其相似性较高的文档,忽略相似性较低的集合。如下图所示,假设签名矩阵有12行,我们将3行为一组放进一个“桶”里: [![](https://zoe.red/usr/uploads/2024/04/3042030321.png)](https://octopuscoder.github.io/images/bucket.png) 对于S2,仅需要查询与其具有相同桶的集合,如下图所示: [![](https://zoe.red/usr/uploads/2024/04/4234801376.png)](https://octopuscoder.github.io/images/bucket5.png) 即只需要查询S4和S5。 --- ## 代码 开源地址: https://nbviewer.org/github/mattilyra/LSH/blob/master/examples/Introduction.ipynb 以下是一些流行的实现 MinHash 算法的开源库: 1. **Datasketch** * **GitHub链接**:[datasketch](https://github.com/ekzhu/datasketch) * Datasketch 是一个用于大数据集的概率数据结构库,支持 MinHash、LSH、HyperLogLog 等。这个库特别适合处理大规模数据集,提供了 Python 接口,易于使用和集成。 2. **LSH Ensemble** * **GitHub链接**:[lsh-ensemble](https://github.com/ekzhu/lsh-ensemble) * LSH Ensemble 是基于局部敏感哈希(LSH)的 MinHash 的变种,适用于处理具有不同大小的数据集。这是由同一个作者开发的,专门设计用来处理高度不均匀的数据分布。 3. **scikit-learn-contrib** * **GitHub链接**:[scikit-learn-contrib](https://github.com/scikit-learn-contrib/scikit-learn-contrib) * 尽管 scikit-learn 本身不直接支持 MinHash,但它的扩展库中可能包括类似的功能。scikit-learn-contrib 是社区驱动的项目,包含了许多为 scikit-learn 添加新功能的库。 4. **MinHashC3** * **GitHub链接**:[MinHashC3](https://github.com/mattilyra/LSH) * MinHashC3 是另一个 Python 实现,专注于提供 MinHash 和局部敏感哈希 (LSH) 算法的高效实现。 <div class="hideContent">此处内容需要评论回复后(审核通过)方可阅读。</div> THE END 本文作者:将夜 本文链接:https://zoe.red/2024/508.html 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。 最后修改:2024 年 04 月 22 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏