龙空技术网

大规模数据的相似度计算 Min Hashing 和 LSH

NLP与人工智能 847

前言:

现时大家对“算法近似度”大概比较关注,同学们都需要知道一些“算法近似度”的相关内容。那么小编在网络上收集了一些有关“算法近似度””的相关内容,希望大家能喜欢,咱们快快来学习一下吧!

在数据挖掘任务中都涉及了海量数据的相似度计算,例如检索文档的相似度,用户之间的相似度等。这些数据通常维度很高,用 one-hot 编码的文档数据维度等于字典的大小,在数据量大,数据维度高的情况下,计算对象两两之间的相似度需要耗费大量的时间。本文介绍两种近似算法 Min Hashing (最小哈希) 和 Locality Sensitive Hashing (LSH,局部敏感哈希),近似算法可以在牺牲部分精度下大大提升运行效率。

1.Min Hashing

假设给定两个文档 D1 和 D2,其特征向量采用 one-hot 编码,即如果一个位置为 1 则说明文档拥有对应的单词。

文档向量

我们可以用 Jaccard 系数计算两个向量的相似度,公式如下,A 和 B 是两个集合:

Jaccard 系数

Jaccard 系数是 A、B 交集的元素数量除以 A、B 并集的元素数量,因此上面的文档 D1、D2 相似度为 2/5。用 x 表示 A、B 共有的元素数量,y 表示 A、B 单独拥有的元素数量,则 Jaccard 系数可以改写为下面的公式:

Jaccard 系数

Min Hashing 是一种近似计算 Jaccard 系数的方法,主要的步骤如下:

对向量D1、D2 的维度进行 m 次随机排列找到重新排列后 D1、D2 第一个非 0 行的索引,用函数 h(D1)、h(D2) 表示

执行 m 次随机排列后,可以得到 D1、D2 的新特征向量,如下:

Min Hashing 后的特征向量

这一过程如下图所示,下图中 m=3:

Min Hashing 过程示例

得到新的特征向量 Sig(D1) 和 Sig(D2) 后可以计算每一个位置上相同 (即第一个非 0 行索引相同) 的概率 P=1/3,这个概率就是 Jaccard 系数的近似值。这主要是根据下面的原理:

Min Hashing 原理

这个原理可以证明,重新排列后两个向量 D1、D2 后,在每一个维度存在三种可能:

D1、D2 在这一个维度都是 1,对应了 Jaccard 公式中的 xD1、D2 只有一个向量在这一个维度是 1,对应了 Jaccard 公式中的 yD1、D2 在这一维度都是 0

Min Hashing 得到的新向量 Sig(D1) 是 D1 第一个不为 0 的行索引。则 Sig(D1) 和 Sig(D2) 第一个非 0 行索引相同的概率为 x/(x+y) 即 Jaccard 系数公式。

如果采用全排列 (即考虑所有的排列情况) 则 Min Hashing 可以得到准确的 Jaccard 值,但是在实际使用时为了提升效率,通常采用 m 次排列,可以将原向量转为长度为 m 的新向量。

2.LSH

Min Hashing 可以将原始的特征向量转为更低维度的 Sig 向量,减少计算两个对象之间相似度的时间。但是如果对象的数量 N 很大,计算所有对象之间相似度需要执行的次数为 O(N^2),仍然需要耗费大量时间。

LSH 算法 (Locality Sensitive Hashing,局部敏感哈希) 的核心思想是先把数据粗略地进行分桶,使相似度高的数据尽可能出现在同一个桶内。分到同一个桶的数据互相视为 candidate 数据,后续计算相似度时只计算数据和其 candidate 数据的相似度 (即出现在同一个桶内的)。

LSH 先将 Min Hashing 得到的 Sig 向量划分为 b 段 (Bands),每段的长度为 r。下面是将 Sig 向量分段的例子,其中每一列是一整个 Sig 向量,向量被划分为 4 个 Band (b=4),每个 Band 长度为 3 (r=3)。

Sig 向量分段

然后利用哈希函数将每一个 Band 中的向量 (r 维向量) 分配到不同的桶里面,哈希函数的取值 (桶数量) 应该尽可能地多,使两个向量只在完全相同时才会有大概率被分到同一个桶里面。分桶的示意图如下:

LSH 算法分桶的过程

在上面的分桶过程中,每一个 Band 都使用同一个哈希函数,但是采用不同的桶。Band 1 的桶在顶部,Band 4 的桶在底部。在 Band 1 中,第 1 个数据和第 9 个数据分到了同一个桶里 (红色),因此数据 1 和数据 9 互为 candidate 数据,即两个数据只要有一个 Band 被分到同一个桶,就是 candidate。

因为 LSH 分桶是近似的算法,因此会存在一些误差。我们希望可以减少 LSH 的 False Positive (相似度低的数据分到同一个桶) 和 False Negative (相似度高的数据没有分到同一个桶)。为了减少误差,首先需要计算出两个数据被分到同一个桶的概率。

假设有两个数据,他们真实的 Jaccard 系数为 s,LSH 算法把他们的 Sig 向量划分为 b 段,每段长度为 r。在介绍 Min Hashing 算法时,我们知道 Sig 向量保存的是重排列后第一个非 0 行的索引,因此两个数据的 Sig 向量在某一维度上取值相同的概率为 Jaccard 系数,即 s。则我们可以计算出这两个数据至少在一个 Band 里被分到同一个桶里面的概率:

分桶概率计算

上面公式的最后一行即为两个数据至少在一个 Band 里被分到同一个桶里的概率 P,给定 b 和 r,可以画出概率 P 随 Jaccard 系数 s 变化的图像,称为 S-curve,如下图所示。

S-curve

可以看到当 Jaccard 系数变得足够大的时候,两个数据被分到同一个桶的概率会大大增加 (接近 1)。因此一般使用的时候要事先设置好一个 Jaccard 系数的阈值 s,然后调整 b 和 r,使得相似度大于阈值 s 时,两个数据被分到同一个桶的概率最大。

3.参考文献

Mining of Massive Datasets 地址:

标签: #算法近似度