《 Mining of Massive Datasets》学习笔记之 Finding Similar Items

本文综述《Mining of Massive Datasets》一书中第三章所述内容及其相关算法

该算法旨在解决数据挖掘中的相似对象搜索问题。例如，在互联网上查找两篇相互类似的网页，并通过一张图片来发现与其相匹配的照片以解决其他相关问题。本算法采用的方法是在海量文档库中检索相关且相似的文章。这些文章可能包含大量完全相同或高度重叠的内容段落，在不同文章或网页中的顺序可能存在差异

算法的整体流程如下：将长文本视为一个整体长序列，并聚焦于识别多篇文章间具有共同特性的部分，并对这些特性进行提取与归类。为此目的，则需将待处理的文章划分为长度均为K的不同子串集合；该集合包含所有不同位置上出现过的长度为K的连续子串，并去重处理；随后利用数据压缩技术生成一个二进制向量序列；通过对这些二进制向量进行比较分析来识别具有相同属性的部分以确定原始文本中存在的共有特征；最终可从中提取出海量文档间存在的相似度信息。

一、 Shingling of Documents

首先考虑一种直观的方法：从文库中逐一选取每对文章进行比较。这种方法存在两个主要问题：第一，在没有优化的情况下（即直接两两配对），计算量会急剧上升；第二，在无法借助语义理解的情况下（即计算机无法单纯通过词句比对来判断），对于经过修改的抄袭或盗版文章（如改变行文顺序或替换部分词汇），计算机难以准确判断其相似性。基于此需求，我们需要开发一种能够自动识别文章之间相似性的方法。Shingling算法正是用来解决这个问题的一种方法。其核心思想在于将一篇文章视为一个连续的长字符串，并通过滑动窗口的方式提取k-克（k-shingles）。例如，在k=2时，字符串"thisisacourse"会被分解为["th", "hi", "is", "sa", "cu", "ur", "rc"]等子串。

k-shingle： any substring of length k found within the document

然后

在Shingling过程中存在一个关键问题：如何确定参数K的大小？如果K值过大，则会导致该方法退化为原始算法而降低效率；反之亦然。具体而言，在实践中若将K设为过小（例如取K=1），则几乎每篇文章都将包含全部1-shingles（即单个字母），这样一来所有文章间的相似度计算结果将趋于相同而失去实际意义。因此，在选择K值时需要遵循一定的指导原则：

k should be selected sufficiently large to ensure that the probability of any given shingle appearing in any given document is sufficiently low.

此外，在日常邮件和工作文件中将K设置为5；而对于学术论文这类专业文档，则将K定为9。

二、 Minhashing

在完成第一步操作后

在提供解决方案之前，请先认识Jaccard similarity这一概念。Jaccard相似性系数用于衡量两个集合之间的相似程度，在信息检索、生物多样性评估等领域有着广泛的应用。该指标通过计算两个集合中共同拥有的元素数量与所有不同元素总量的比例来反映它们之间的相似性程度。具体而言，在数学上它等于两个集合交集的大小除以其并集元素总数目。

The Jaccard similarity of sets S and T is | S ∩ T | / | S ∪ T |

通常情况下，在两个集合之间如果其相似度越高（即包含的相同元素数量越多），其Jaccard相似性指数值也随之提高。因此我们通常使用Jaccard相似性指数来衡量两个集合之间的相似程度。

让我们了解Minhashing算法的基本原理。该算法通过选择N个独立的哈希函数来进行计算，在每次操作中都能获得一组独特的特征向量数据。每个哈希函数都定义为对横坐标轴的一种重新排列方式，在每次置换操作后沿着矩阵纵列方向依次检查每一个位置，在首次遇到数值为1的位置时其对应的位置索引即代表该次哈希运算下第j列的独特标识符。经过N次独立重复的操作后，在每一次操作中都能获得一组独特的特征向量数据，并最终形成一个具有N行M列特异性映射关系的空间表征矩阵S（其中M表示文档库中实际存在的文章数量）。因此，在构建完整个M x N维度的空间映射关系后就可以根据这一矩阵得出每一篇文档的独特标识信息并将其归纳总结成统一形式的数据载体——signature

Minhashing算法的核心优势在于其能够有效保留原文库中文章间的相似性特征。

The probability that the minwise hashing technique results in identical values for a randomly permuted set of rows equals the Jaccard similarity of those sets.

该结论的证明如下：

When limiting our analysis to the columns corresponding to sets S₁ and S₂, we observe that the rows fall into three distinct categories:

• Rows of Type X exhibit a value of 1 in both corresponding columns.
• Rows of Type Y show a single occurrence of 1 across their respective two columns.
• Rows of Type Z display a value of 0 in both corresponding positions.

由于矩阵稀疏，在大多数情况下为类型Z的行。

Let's examine the probability that h(S_1) equals h(S_2). Imagine all rows being randomly permuted and proceeding from top to bottom. The chance of encountering a Type X row before a Type Y row is \frac{x}{x + y} . However, if the very first non-Type Z row encountered from the top is of Type X, then certainly h(S_1) = h(S_2). Conversely, if the next non-Type Z row following this one is also of Type X, then it must be concluded that h(S_1) does not equal h(S_2).

值得留意的是，在Minhashing过程中若N取值过小可能带来偶然性和不准确性。同时需要确保N足够大，并采用随机选取的哈希函数这样才能确保之前的推论得以成立。一般而言,N的取值常设为100。经过Minhashing处理后,矩阵的横坐标范围由之前的2×1e+5变为1×1e+2。虽然矩阵所要保存的内容从二进制形式转换为k-shingle表示,但整体上矩阵的数据量已经得到了显著减少

三、 Locality-Sensitive Hashing for Documents（LSH）

在完成前两个步骤后，在知识库中文章数量非常庞大，在这种情况下逐一配对比较内容仍然是一个庞大的工作量。参考以下案例：

但有一个观察事实是

LSH 的可行性主要归因于两个方面: 首先, 对于真正高度相关的两篇文章, 它们在 b 个长度均为 r 的向量通常不会同时出现在同一个桶中; 而对于不相关性较高的文章, 则可能有一个长度为 r 的向量会出现在同一桶中, 这样的情况发生的可能性并非特别高。因此, 该算法能够较为高效地识别出大部分的相关文章, 同时又能有效限制计算规模的增长幅度。然而, 这一现象的发生机制仍需进一步探讨, 具体内容可参阅教材中的相关章节。

四、总结
主要步骤则已成功地实现了对海量文档库中相似文章的有效搜索。这一思想则可延伸至处理其他类别的相似对象。通过对目标进行分解并压缩数据，在有限资源下实现了有效的查找。关于算法效率与优化方面的探讨仍需进一步深入；如有机会进一步学习与研究，则将在未来更新