[译]针对大数据的Jaccard相似度计算优化

在大量数据对间计算Jaccard相似度是一个巨大的难题。因为它的复杂度是O(N^2). 然而这里有许多优化技术能够显著地降低计算量。我花了大约一周的时间搜索了相关资料,研究了大量技术。下面是我找到的不同方法的总结,同时提供了部分有用信息的链接。值得提到的是以下两个非常有用的资料:
《Similarity Joins in Relational Databases》第六章
《Mining Massive Datasets》第三章

  1. 基于Token的过滤:
    想法:根据token来放置数据,同时仅仅考虑至少有一个token匹配的数据对。

提醒:当你想要计算所有数据的相似度时再用这种方法。那些没有相同token的数据对就不再输入匹配。如果有重复的token,你就需要考虑预处理将重复token转换成集合。

引用:
《Similarity Joins in Relational Databases》第六章

2.前缀过滤:
想法:与上一方法不同,该方法只使用最多出现的几种token的数据。排名取决于你所需的最小Jaccard相似度。

提醒:这种方法只需考虑Jaccard相似度大于某阈值的数据对。例如,Jaccard相似度大于阈值的数据对会一直被考虑。因此考虑特定token来计算Jaccard距离就变得非常重要。该方法需要额外的预先计算步骤来以某种规则来排序token。通常来说,以升序来排序token能够提高该方法的效率。除此方法外,还有其他类似方法的变种方法例如positional filtering。

引用:
《Similarity Joins in Relational Databases》第六章
《Mining Massive Datasets》第三章

  1. 地区敏感的哈希LSH(使用MinHash)
    想法:与其直接考虑token,该方法用K种不同的哈希函数来哈希化token,并且标注每种哈希函数的最小哈希值。为了计算Jaccard相似度,仅需要计算最小哈希值匹配的次数与K的商。为了减少我们需要考虑的数据对的数量,一次考虑r类特征。

提醒:
与前缀过滤法相似,这种方法仅考虑那些Jaccard相似度很有可能大于某阈值的数据对。这种方法可能既导致错误正相关和错误负相关。比如很有可能丢弃了需要被考虑的数据对。同时这里有几个参数需要考虑,分别是:(1) 哈希函数的种类,(2)使用哈希函数的数量,(3)在地区敏感哈希方法的过程中放置最小哈希签名的行数和类数。

引用:
《Similarity Joins in Relational Databases》第六章:从该章节大体了解minHash和地区敏感哈希。
CSE344(Washing 大学),小节10:这有一个问题,该问题大大强化了我对minHash的理解。
哥伦比亚大学课程1“Dealing with Massive Dataset (Duplicate Detection)”:该资料帮助我理解哈希函数数量和Jaccard相似度计算过程中的错误的关系。

原文:Optimizing Jaccard Similarity Computation for Big Data

Say Something