1. Jaccard

定义 Jaccard 相似度计算公式：

定义 Jaccard 距离：

1.1 例题

• 不重复
• 重复 (bag)，最大值为 1 / 2

2. shingling

• 将文档用短字符集合来表示

2.1 k-shingle

• character 级别：包括空格
• word 级别：不包括空格和逗号句号符

2.2 k 值大小的选择

• 如果文档由邮件组成，那么选择 k = 5 比较合适。
• 如果文档比较大，选择 k = 9 比较合适

2.3 例题

• shingles
• 带停顿词的 shingles：需要包含停顿词
  

3. MinHashing

3.1 minhashing 作用：压缩

将文档 shingle 成很小的集合之后，就可以写出下面的特征矩阵了。
用下面的特征矩阵来计算复杂度还是很高，MinHashing算法可以用于压缩原始特征矩阵，但是不丢失相似性。

• 当 hash 出来所有列号不冲突时，称为真正的排列((true permutation)

3.2 算法步骤、例题

• ①对特征矩阵的列号，用 hash 进行重排
  

• ②初始化签名(signature)矩阵为无穷
  

• ③逐渐将特征矩阵填入签名矩阵
  首先，考虑①中的第0行，h1(0) = 1，h2(0) = 1，而只有S1和S4对应下来才是1.所以在签名矩阵中，(h1, S1) = 1，(h1, S4) = 1，(h2, S1) = 1，(h2, S4) = 1.因为1 ＜∞。
  
  其次，再考虑②中的第1行，h1(1) = 2，h2(1) = 4，而只有S3对应下来才是1，所以在签名矩阵中，(h1, S3) = 2，（h2, S3） = 4，因为 2 ＜ ∞，4 ＜ ∞。
  然后按部就班。
  
  最后的结果为。
  有可能还要求压缩后的 Jaccard 相似度：

• Col/Col:相同位置与求和/相同位置或求和

• Sig/Sig:相同的行数/总的行数
  
  小技巧：

• 如果是真正的排列，那么可以直接用肉眼看最小的列号，直接得出结果

• 如果列号由冲突，那么需要一步步推导

4. LSH 行条化策略的分析

称为候选对的概率为:

5. 距离测度

• 欧式距离
• 余弦距离
• Jaccard 距离
• 编辑距离：插入及删除操作的最小数目
• 海明距离：不同分量的个数