大数据挖掘--两个角度理解相似度计算理论

0 相似度计算可以转换成什么问题

相似度计算是数据分析和机器学习领域中一项关键任务，它可以帮助我们理解和分析不同对象之间的相似性。然而，相似度计算本身可以通过转换成其他类型的问题来更加有效地处理和解决。

首先，我们来看一种常见的相似度度量——Jaccard相似度。Jaccard相似度将相似度计算视为集合之间的比较问题。具体来说，它关注两个集合之间的交集相对于并集的大小。这种方法特别适合用于需要比较集合相似性的场景，比如在文本分析中，我们可以将文档表示为一组词的集合，Jaccard相似度帮助我们评估两份文档的相似程度。通过计算交集和并集，我们将相似度问题转化为集合运算问题，这种方法简洁而有效，尤其在需要处理大量数据时，利用集合操作的高效性可以显著提高计算速度。

另一方面，相似度计算也可以转换为距离测度的问题。在这种情况下，我们将对象视为几何空间中的点，计算这些点之间的距离来推断相似性。欧氏距离是一种直观的衡量方式，它通过计算两点之间的直线距离来评估它们的接近程度。这种方法在需要空间可视化的场合中非常有用。此外，还有曼哈顿距离，它通过计算路径总长来反映两点的差异，这在某些离散空间中表现出色。余弦相似度则提供了另一种转换视角，通过考察向量之间的夹角来确定它们的相似性，这在高维向量空间中，尤其在文本分析和推荐系统中，被广泛使用。

1 集合相似度的应用

1.1 集合相似度

1.1文档相似度

在文本分析中，我们常常需要衡量两篇文档之间的相似性，这可以通过集合相似度来实现。一个常用的方法是Jaccard相似度。假设有两个文档 $A$ 和 $B$，我们可以将它们表示为词的集合，分别记为 $S_A$ 和 $S_B$。Jaccard相似度计算公式如下：

$$J(S_A,S_B)=\frac{|S_A\cap S_B|}{|S_A\cup S_B|}$$

其中，$|S_A\cap S_B|$ 是两个集合的交集的大小，$|S_A\cup S_B|$ 是两个集合的并集的大小。Jaccard相似度的值在 0 到 1 之间，值越大表示两个文档越相似。

算法：在实际应用中，计算文档相似度时，我们可以进行如下步骤：

1. 将每个文档转换为词集合。
2. 计算每对文档集合的交集和并集大小。
3. 应用Jaccard公式计算相似度。

这种方法简单高效，特别适合于初步的文本聚类和分类问题。

1.2 协同过滤

在推荐系统中，协同过滤是一种广泛使用的方法。这里我们主要探讨基于集合相似度的协同过滤，包括用户-用户和物品-物品协同过滤。

用户-用户协同过滤

在用户-用户协同过滤中，我们通过比较用户之间的兴趣相似性来进行推荐。假设我们有用户 $u_i$ 和 $u_j$，它们的兴趣集合分别为 $I_i$ 和 $I_j$。我们可以使用Jaccard相似度来计算用户相似性：

$$J(I_i,I_j)=\frac{|I_i\cap I_j|}{|I_i\cup I_j|}$$

通过计算用户之间的Jaccard相似度，我们可以为用户推荐那些相似用户喜欢的物品。

物品-物品协同过滤

类似地，在物品-物品协同过滤中，我们比较物品之间的相似性。假设有物品 $p_a$ 和 $p_b$，它们的用户集合分别为 $U_a$ 和 $U_b$，我们计算物品的Jaccard相似度：

$$J(U_a,U_b)=\frac{|U_a\cap U_b|}{|U_a\cup U_b|}$$

物品相似性可以帮助我们推荐用户可能喜欢的其他相似物品。

算法：协同过滤的基本步骤包括：

1. 构建用户-物品矩阵。
2. 根据需要选择用户-用户或物品-物品的相似度计算。
3. 计算相似度矩阵。
4. 根据相似度为用户生成推荐列表。

通过利用集合相似度，我们能够有效地实现协同过滤，使推荐系统更加智能化和个性化。这些方法不仅提高了推荐的准确性，还提升了用户的参与感和满意度。

1.2 文档的shingling–将文档表示成集合

在文本处理和分析过程中，将文档转换为集合的形式可以帮助我们更好地进行相似度分析和其他文本操作。其中，shingling 是一种将文档转化为集合的方法，通过将文档分割为一系列短的连续子序列（或称为“片段”）来实现。以下是关于 k-shingling 和基于停用词的 shingling 的详细介绍。

1.2.1 k-shingling

k-shingling 是一种将文档转化为子序列集合的方法，通过将文档中的文本分割为长度为 k 的连续子字符串（或子词）来实现。每一个长度为 k 的子串称为一个“shingle”。这种方法的核心在于选择合适的 k 值，以确保文档可以被合理地分割。

步骤：

1. 选择 k 值：通常，k 的选择取决于具体应用和文档长度。较小的 k 值可以捕捉到更多的局部信息，而较大的 k 值更能反映文档的全局结构。

2. 生成 shingles：从文档中提取所有可能的 k-shingles。对于每一个连续的 k 个字符或词，记录为一个 shingle。

3. 构建集合：将所有提取的 shingles 组成一个集合。此集合可以用来比较不同文档的相似性。

示例：对于字符串 “The quick brown fox” 和 k = 2，可能的 shingles 为 {“Th”, “he”, "e “, " q”, “qu”, “ui”, “ic”, “ck”, "k “, " b”, “br”, “ro”, “ow”, “wn”, "n “, " f”, “fo”, “ox”}。

1.2.2 基于停用词的 shingling

基于停用词的 shingling 是一种改进的 shingling 方法，它通过忽略文档中的停用词（例如 “the”, “is”, “at”, “on” 等），来生成更具意义的 shingles。这种方法可以帮助减少噪声，提高文档相似度计算的精确度。

步骤：

1. 移除停用词：在进行 shingling 之前，首先从文档中移除常见的停用词。这可以通过预定义的停用词列表实现。

2. 生成 shingles：在移除停用词后，使用类似 k-shingling 的方法生成 shingles。这样生成的 shingles 更能体现文档的核心内容。

3. 构建集合：将生成的 shingles 组成一个集合，用于进一步的相似度计算。

优点：通过忽略停用词，基于停用词的 shingling 能够更专注于文档的主题词汇，减少不必要的干扰。

好的，以下是关于如何使用最小哈希签名将大文档压缩成小的签名，以及如何利用局部敏感哈希（LSH）算法处理这些签名，以保持文档间的相似度。

1.3 最小哈希签名

最小哈希签名是一种将大集合（如文档中的术语集合）压缩成较小的签名的技术，同时保留集合之间的相似度。这是通过一组哈希函数实现的，它们将集合中的元素映射到整数，并选取最小的数值作为签名。

步骤：

1. 选择哈希函数：选择一组不同的哈希函数 $h_1,h_2,\dots ,h_n$。每个哈希函数将文档中的shingle（子字符串）映射到一个整数。

2. 生成签名：对于每个文档和每个哈希函数，计算所有shingle的哈希值，并记录最小的哈希值。重复此过程n次（使用n个不同的哈希函数），形成一个长度为n的签名向量。

3. 保持相似度：两个文档的最小哈希签名相同元素的比例，接近于这两个文档的Jaccard相似度，即 $J(A,B)=\frac{|A\cap B|}{|A\cup B|}$。

1.4 局部敏感哈希算法（LSH）

LSH 是一种用于快速查找相似文档的算法，特别适用于处理最小哈希签名。这种方法通过将签名分段，并使用哈希函数将相似的签名段映射到相同的桶中，从而实现高效的近似最近邻搜索。

步骤：

1. 分段签名：将最小哈希签名分成若干段，每段包含若干个哈希值。例如，每个签名被分成b个段，每段包含r个哈希值。

2. 映射到桶：对每个段，使用一个哈希函数将其映射到一个哈希桶。相似的文档由于签名段的相似性，很可能被映射到同一个桶中。

3. 查找相似文档：当需要查找与某个文档相似的文档时，可以仅查找与其签名段映射到相同桶中的文档，这大大缩小了查找范围。

优势：通过结合最小哈希签名和 LSH，能够有效地处理和比较大规模文档集合。最小哈希签名减少了需要处理的数据量，而 LSH 提供了快速的相似性检索机制，使得处理大规模数据集的效率得以提升。

1.5 最小哈希签名和局部敏感哈希（LSH）的概念结合示例

假设我们有两个文档，它们的 shingle 集合如下：

• 文档 A: {“shingle1”, “shingle2”, “shingle3”}
• 文档 B: {“shingle2”, “shingle3”, “shingle4”}

我们应用三组不同的哈希函数 $h_1(x)$, $h_2(x)$, $h_3(x)$，假设这些函数的输出如下：

• $h_1("shingle1")=5$, $h_1("shingle2")=3$, $h_1("shingle3")=7$, $h_1("shingle4")=6$
• $h_2("shingle1")=2$, $h_2("shingle2")=9$, $h_2("shingle3")=1$, $h_2("shingle4")=4$
• $h_3("shingle1")=8$, $h_3("shingle2")=6$, $h_3("shingle3")=5$, $h_3("shingle4")=3$

最小哈希签名步骤：

1. 计算最小哈希签名：

   • 对于文档 A:
     • $h_1$: 最小值是 3 (来自 “shingle2”)
     • $h_2$: 最小值是 1 (来自 “shingle3”)
     • $h_3$: 最小值是 5 (来自 “shingle3”)
   • 对于文档 B:
     • $h_1$: 最小值是 3 (来自 “shingle2”)
     • $h_2$: 最小值是 1 (来自 “shingle3”)
     • $h_3$: 最小值是 3 (来自 “shingle4”)

2. 生成最小哈希签名：

   • 文档 A 的签名: (3, 1, 5)
   • 文档 B 的签名: (3, 1, 3)

3. 比较签名：通过比较签名发现，文档 A 和 B 在三个哈希函数中有两个值相同，签名相同位置的值相同比例为 2/3。

局部敏感哈希 (LSH) 步骤：

1. 分段签名：

   • 将签名分成两段，每段包含一组哈希值：
     • 文档 A: (3, 1) 和 (5)
     • 文档 B: (3, 1) 和 (3)

2. 映射到桶：

   • 使用哈希函数对每一段进行哈希，映射到哈希桶：
     • 段 (3, 1) 的两文档都被映射到同一个桶，因此它们可能相似。
     • 段 (5) 和 (3) 被映射到不同的桶。

3. 查找相似文档：

   • 由于文档 A 和 B 在 (3, 1) 段中被映射到同一个桶，因此 LSH 会识别文档 B 作为文档 A 的相似候选者。

通过结合最小哈希签名和 LSH，我们大幅度降低了计算复杂度。最小哈希签名帮助我们压缩文档，同时保留相似度信息，而 LSH 则通过分段签名和桶映射，快速聚合可能相似的文档以进行进一步的精细比较。这种方法尤其适用于需要快速处理和比较的大规模数据集。

2 距离测度的应用

2.1 距离测度

1. 欧氏距离 (Euclidean Distance)

• 定义：欧氏距离是两点间的“直线”距离，用于度量两个点在欧几里得空间中的距离。对于两个n维向量 $A=(a_1,a_2,...,a_n)$ 和 $B=(b_1,b_2,...,b_n)$，其计算公式为：
  $\text{Euclidean Distance}=\sqrt{{\sum }_{i=1}^n(a_i-b_i{)}^2}$
• 应用：常用于几何空间中的距离计算，如图像处理、聚类分析（如k-means算法）。

2. 余弦距离 (Cosine Distance)

• 定义：余弦距离实际上测量的是两个向量之间的夹角余弦值，表示两个向量的方向相似度。计算公式为：
  $\text{Cosine Similarity}=\frac{A\cdot B}{\Vert A\Vert \Vert B\Vert }$
  余弦距离则为 $1-\text{Cosine Similarity}$。
• 应用：适用于文本分析和信息检索，因为它关注的是向量的方向而不是大小，比如在文档相似性计算中。

3. 编辑距离 (Edit Distance)

• 定义：编辑距离，又称Levenshtein距离，是将一个字符串转换成另一个字符串所需的最小编辑操作次数（包括插入、删除、替换的操作）。
• 应用：广泛用于拼写检查、DNA序列比对和自然语言处理中。

4. 海明距离 (Hamming Distance)

• 定义：海明距离用于衡量两个等长字符串之间的差异，即在相同位置上不同字符的数量。
• 应用：主要用于编码理论和信息技术中的错误检测和纠正，例如校验和比较二进制字符串。

3 LSH函数家族