相似性算法

发表于 2025-08-15 更新于 2025-08-19 分类于 Python 杂项本文字数： 8.2k 阅读时长 ≈ 15 分钟

前言：

相似性算法用于衡量两个对象（如文本、图像、向量等）之间的相似程度，广泛应用于搜索、推荐、聚类、自然语言处理等领域。

基于向量的相似性算法

适用于将对象表示为向量（如词向量、特征向量）后的相似度计算。

余弦相似度（Cosine Similarity）

公式：计算两个向量的夹角余弦值，范围 [-1, 1]，值越大越相似。
特点：
- 忽略向量长度，适合文本相似性（如TF-IDF、词向量）
- 几何上表示两向量间的夹角
- 值域为[-1,1]，1表示完全相似，-1表示完全相反
应用：
- 文档检索、用户画像匹配
- 推荐系统中的用户/物品相似度计算
- 文本聚类和分类任务

欧氏距离（Euclidean Distance）

公式：向量间的几何距离，值越小越相似。
特点：
- 对数值绝对大小敏感，适合低维空间（如图像特征）
- 满足距离度量的三个基本性质：非负性、同一性、对称性、三角不等式
- 在高维空间中可能失效（维度诅咒）
应用：
- KNN、聚类、异常检测
- 图像处理和计算机视觉
- 机器学习中的特征空间距离计算

点积相似度（Dot Product）

公式：向量内积，受向量长度影响。
特点：
- 结果与向量的模长和夹角有关：
- 若向量已归一化，则点积等于余弦相似度
- 对向量长度敏感，不适合直接用于比较不同尺度的向量
应用：
- 推荐系统中的矩阵分解（如隐语义模型）
- 神经网络中的权重计算
- 向量空间模型中的相似性初筛

曼哈顿距离（Manhattan Distance）

公式：各维度绝对差之和。
特点：
- 对异常值不敏感，适合高维稀疏数据
- 几何上等价于“城市街区”距离（只能沿坐标轴移动）
- 比欧氏距离更鲁棒，常用于文本、特征工程
应用：
- KNN 算法中的距离度量
- 文本分类、推荐系统
- 高维空间下的聚类分析

基于集合的相似性算法

适用于集合（如用户兴趣标签、关键词集合）的相似度计算。

Jaccard 相似度

公式：计算两个集合交集大小与并集大小的比值，范围 [0, 1]，值越大越相似。
特点：
- 只关注元素是否出现，不考虑频率或顺序
- 对集合大小敏感，适合稀疏数据（如标签、关键词）
- 当两个集合完全相同时，值为 1；无交集时为 0
应用：
- 文本相似性（如关键词集合比较）
- 推荐系统中的用户兴趣匹配
- 聚类分析（如基于标签的聚类）
- 信息检索中的文档去重

重叠系数（Overlap Coefficient）

公式：计算两个集合交集大小与较小集合大小的比值，范围 [0, 1]，值越大越相似。
特点：
- 只关注元素是否出现，不考虑频率或顺序
- 对集合大小差异敏感，适合比较大小不同的集合
- 当一个集合完全包含另一个时，值为 1；无交集时为 0
- 与 Jaccard 不同，它不会因并集变大而降低得分
应用：
- 用户兴趣标签匹配（如小众用户 vs 大众用户）
- 文本关键词重合度分析
- 生物信息学中的基因集合比较
- 推荐系统中冷启动用户的相似性评估

基于字符串的相似性算法

用于文本、序列的相似性比较。

编辑距离（Levenshtein Distance）

定义：将一个字符串转换为另一个所需的最少单字符编辑（插入、删除、替换）次数。
特点：
- 满足距离度量的所有性质
- 计算复杂度较高，为O(mn)
- 对字符串的局部变化敏感
应用：
- 拼写纠错、DNA序列比对
- 数据清洗和去重
- 代码相似度检测

Jaro-Winkler 距离

特点：
- 考虑字符顺序和前缀匹配，适合短文本（如人名匹配）
- 对字符串开头的匹配给予更高权重
- 结果范围在 [0,1] 之间，1表示完全匹配
应用：
- 记录链接和数据去重
- 姓名和地址匹配
- 数据库清洗

最长公共子序列（LCS）

定义：两个序列共有的最长子序列长度。
特点：
- 不要求连续，但保持相对顺序
- 常用于衡量序列相似性
- 可以通过动态规划高效计算
应用：
- 版本控制（如代码差异比较）
- 生物信息学中的序列比对
- 文本相似性分析

基于概率分布的相似性算法

用于比较概率分布（如语言模型、生成数据）。

KL 散度（Kullback-Leibler Divergence）

公式：衡量分布相对于分布的信息损失，非对称，值越大表示差异越大。
特点：
- 非对称性：
- 非负性：，当且仅当时等于 0
- 不是距离度量（不满足对称性和三角不等式）
- 可解释为“用 Q 来编码 P 所需的额外比特数”
应用：
- 信息检索中的文档相似性评估
- 模型拟合优度（如训练模型与真实分布的差距）
- 生成模型（如变分自编码器 VAE、GAN 中的判别器）
- 自然语言处理中的语言模型比较

JS 散度（Jensen-Shannon Divergence）

特点：
- KL 散度的对称化版本，范围 [0, 1]
- 满足对称性，是对衡量分布差异更好的选择
- 基于KL散度定义，保持了良好的理论性质
应用：
- 分布相似性度量
- 聚类分析中的距离计算
- 生成模型评估

交叉熵（Cross-Entropy）

公式：衡量两个概率分布和之间的差异，常用于分类任务的损失函数。
特点：
- 非对称性：
- 当时，交叉熵最小（等于，即的熵）
- 可解释为“用分布来编码来自分布的数据所需的平均比特数”
- 在深度学习中，常作为分类模型的损失函数（如 softmax + cross-entropy）
应用：
- 分类模型训练（如神经网络、逻辑回归）
- 语言模型评估
- 生成模型中的目标函数
- 信息检索中的排序优化

基于深度学习的相似性算法

利用神经网络提取高阶特征后计算相似度。

Siamese Networks

特点：
- 双塔结构共享权重，输出隐向量计算相似度
- 通过端到端训练学习相似性度量
- 可以处理各种类型的数据（图像、文本等）
应用：
- 人脸识别、签名验证
- 问答系统中的答案选择
- 推荐系统中的用户/物品匹配

Sentence-BERT

特点：
- BERT模型微调后生成句向量，计算余弦相似度
- 解决了BERT直接计算句向量效果不佳的问题
- 比原始BERT计算效率更高
应用：
- 语义搜索、问答系统
- 文本聚类和分类
- 语义文本相似性任务

Contrastive Loss

目标：
- 拉近相似样本的向量距离，推开不相似样本
- 通过损失函数直接优化相似性度量
应用：
- 表征学习
- 人脸识别和验证
- 无监督和自监督学习

其他专用算法

Pearson相关系数

特点：
- 衡量线性相关性，范围 [-1, 1]
- 对变量的线性变换具有不变性
应用：
- 用户评分预测
- 特征选择和相关性分析

SimHash

特点：
- 局部敏感哈希（LSH）的一种，用于海量文本去重
- 将相似文本映射到相近的哈希值
- 计算效率高，适合大规模应用
应用：
- 网页和文档去重
- 抄袭检测
- 大规模相似性搜索

Word Mover’s Distance

特点：
- 基于词嵌入的文档距离度量
- 考虑词语间的语义相似性
- 计算复杂度较高但语义效果好
应用：
- 文档相似性计算
- 短文本匹配
- 语义搜索

选择依据

数据类型
- 文本（编辑距离/Jaccard）
- 向量（余弦/欧氏）
- 分布（KL散度）
- 集合（Jaccard/重叠系数）
计算效率
- 编辑距离较慢，Jaccard适合大规模集合
- 近似算法可提升大规模计算效率
语义需求
- 深度学习模型能捕捉语义，但需要训练成本
- 传统方法计算快但语义表达能力有限

PostgreSQL 相似性算法

Levenshtein 距离

计算两个字符串之间的编辑距离（需要多少次单字符编辑才能使字符串相同）：

1	SELECT levenshtein('kitten', 'sitting'); -- 返回 3

Jaro 和 Jaro-Winkler 距离

计算两个字符串的相似度（0-1之间，1表示完全相同）：

1 2	SELECT jaro_similarity('MARTHA', 'MARHTA'); -- 返回约 0.944 SELECT jaro_winkler_similarity('MARTHA', 'MARHTA'); -- 返回约 0.961

Trigram 相似度 (pg_trgm 扩展)

基于三元组的相似度计算：

-- 首先安装扩展
CREATE EXTENSION pg_trgm;

SELECT similarity('word', 'words');  -- 返回 0.75
SELECT 'word' % 'words';  -- 简写形式，返回 true 如果相似度超过阈值

双字母组相似度 (dmetaphone)

基于发音的相似度计算：

1	SELECT dmetaphone('phonetics'), dmetaphone('fonetix'); -- 可能返回相同的编码

全文搜索相关度

使用 tsvector 和 tsquery 进行相关度计算：

1 2	SELECT ts_rank_cd(to_tsvector('english', 'The quick brown fox'), to_tsquery('english', 'fox & quick'));

余弦相似度

可以通过自定义函数实现向量相似度计算：

-- 通常需要安装 cube 扩展
CREATE EXTENSION cube;

-- 然后可以计算向量间的余弦相似度

使用建议

对于拼写相似性：Levenshtein 或 Jaro-Winkler
对于内容相似性：Trigram 或全文搜索
对于发音相似性：dmetaphone
对于向量相似性：余弦相似度

PostgreSQL 向量相似性算法

主要向量相似性算法

欧氏距离（L2 距离）
- 计算方式：衡量向量之间的直线距离。
- 适用场景：适用于需要精确距离计算的场景，如物体检测、空间数据分析。
- SQL 操作符：<->
- 索引访问方法：vector_l2_ops
余弦相似度
- 计算方式：衡量向量之间的夹角余弦值，范围 [-1, 1]，值越接近 1 表示越相似。
- 适用场景：适用于文本相似度、推荐系统等方向敏感的场景。
- SQL 操作符：<=>
- 索引访问方法：vector_cosine_ops
内积（点积）
- 计算方式：计算两个向量的点积，值越大表示相似性越高。
- 适用场景：适用于推荐系统、语义搜索等需要考虑向量强度和方向的场景。
- SQL 操作符：<#>
- 索引访问方法：vector_ip_ops
曼哈顿距离（L1 距离）
- 计算方式：计算向量各维度绝对差之和。
- 适用场景：适用于稀疏数据或需要计算绝对差异的场景。
- SQL 操作符：<+>
汉明距离
- 计算方式：计算二进制向量不同位的数量。
- 适用场景：适用于图像指纹、哈希值比较等二进制数据。
- SQL 操作符：<^>
Jaccard 距离
- 计算方式：衡量集合相似性，适用于稀疏向量。
- 适用场景：适用于文本去重、集合相似性计算。
- SQL 操作符：<~>

索引加速向量搜索

IVFFlat（倒排平面索引）
- 原理：将向量聚类，搜索时仅计算目标簇内的向量。
- 特点：
  - 构建速度快，适合大规模数据。
  - 召回率一般，需调整 lists 参数平衡速度与精度。
- 创建方式：
  1
  CREATE INDEX ON items USING ivfflat (embedding vector_cosine_ops) WITH (lists = 100);
HNSW（分层可导航小世界图）
- 原理：基于图结构，构建多层索引，实现高效近邻搜索。
- 特点：
  - 查询速度快，召回率高。
  - 索引构建较慢，占用更多内存。
- 创建方式：
  1
  CREATE INDEX ON items USING hnsw (embedding vector_l2_ops);

应用场景

推荐系统（余弦相似度）
语义搜索（余弦相似度）
图像检索（欧氏距离）
文本聚类（Jaccard 距离）
二进制数据匹配（汉明距离）

性能优化建议

调整 lists 和 probes（IVFFlat）：影响召回率和查询速度。
归一化向量：提高余弦相似度的计算精度。
并行查询：利用 PostgreSQL 的并行计算能力加速搜索

MongoDB 相似性算法

文本相似性搜索

文本索引和 $text 操作符：
- 支持文本搜索和相关性评分
- 使用词干分析和停用词过滤
- 返回按相关性排序的结果

示例

1 2	db.collection.createIndex({ content: "text" }); db.collection.find({ $text: { $search: "query terms" } }, { score: { $meta: "textScore" } });

向量相似性搜索 (MongoDB Atlas 功能)

$vectorSearch 操作符 (Atlas Search 功能)：
- 支持向量嵌入相似性搜索
- 使用余弦相似度、欧几里得距离或点积
- 适用于AI生成的内容搜索

示例

db.collection.aggregate([
  {
    $vectorSearch: {
      index: "vector_index",
      path: "embedding",
      queryVector: [0.1, 0.2, 0.3],
      numCandidates: 100,
      limit: 5
    }
  }
]);

近似相似性算法

$search (Atlas Search)：
- 支持多种相似性算法配置
- 包括模糊搜索、同义词扩展等

聚合框架中的相似性计算

虽然 MongoDB 聚合框架不直接提供相似性算法，但可以组合使用运算符来实现简单相似性计算：

db.collection.aggregate([
  {
    $addFields: {
      similarity: {
        $divide: [
          { $size: { $setIntersection: ["$setA", "$setB"] } },
          { $size: { $setUnion: ["$setA", "$setB"] } }
        ]
      }
    }
  }
]);

第三方集成

通过MongoDB的灵活性，可以集成外部相似性计算服务
使用变更流或触发器调用外部API进行相似性计算

MongoDB 向量相似性算法

支持的相似性度量算法

余弦相似度 (Cosine Similarity)
- 公式:
- 特点: 测量向量之间的角度，忽略大小差异
- 范围: [-1, 1]，1表示完全相同，0表示正交，-1表示完全相反
- 适用场景: 文本相似性、推荐系统
欧几里得距离 (Euclidean Distance)
- 公式: $²$
- 特点: 测量向量之间的直线距离
- 范围: [0, ∞)，0表示完全相同
- 适用场景: 空间数据、物理距离测量
点积 (Dot Product)
- 公式:
- 特点: 受向量大小影响
- 范围: (-∞, ∞)
- 适用场景: 需要同时考虑方向和大小的情况

MongoDB Atlas 向量搜索实现

创建向量索引

db.collection.createIndex({
  "vectorField": "vector",  // 包含向量数据的字段
  "type": "vector",        // 索引类型
  "dimensions": 512,      // 向量维度
  "similarity": "cosine"  // 相似性算法 (可选: cosine, euclidean, dotProduct)
});

执行向量搜索 ($vectorSearch)

db.collection.aggregate([
  {
    $vectorSearch: {
      index: "vector_index",       // 向量索引名称
      path: "embedding",           // 包含向量的字段路径
      queryVector: [0.12, 0.34, ...], // 查询向量
      numCandidates: 100,          // 候选数量
      limit: 5,                    // 返回结果数量
      filter: { category: "books" } // 可选过滤条件
    }
  }
]);

性能优化技巧

维度选择:
- MongoDB Atlas 支持最高2048维的向量
- 通常100-1000维已能满足大多数应用场景

索引配置:

{
  "mappings": {
    "dynamic": true,
    "fields": {
      "embedding": {
        "dimensions": 512,
        "similarity": "cosine",
        "type": "knnVector"
      }
    }
  }
}

查询参数调优:
- numCandidates: 平衡精度与性能 (值越大越精确但越慢)
- 结合常规查询条件减少搜索空间

应用场景示例

语义搜索:

// 使用文本嵌入向量搜索相似文档
db.articles.aggregate([
  {
    $vectorSearch: {
      index: "semantic_search",
      path: "content_embedding",
      queryVector: getEmbedding("量子计算最新进展"),
      limit: 10
    }
  }
]);

图像检索:

// 使用图像特征向量搜索相似图片
db.images.aggregate([
  {
    $vectorSearch: {
      index: "image_similarity",
      path: "cnn_features",
      queryVector: uploadedImageVector,
      similarity: "euclidean",
      limit: 8
    }
  }
]);

限制与注意事项

Atlas专属功能: 向量搜索目前仅限MongoDB Atlas使用
性能考量: 高维向量搜索可能资源密集
精度权衡: 近似最近邻(ANN)搜索牺牲少量精度换取性能
数据准备: 需要预先计算和存储向量嵌入

基于向量的相似性算法

余弦相似度（Cosine Similarity）

欧氏距离（Euclidean Distance）

点积相似度（Dot Product）

曼哈顿距离（Manhattan Distance）

基于集合的相似性算法

Jaccard 相似度

重叠系数（Overlap Coefficient）

基于字符串的相似性算法

编辑距离（Levenshtein Distance）

Jaro-Winkler 距离

最长公共子序列（LCS）

基于概率分布的相似性算法

KL 散度（Kullback-Leibler Divergence）

JS 散度（Jensen-Shannon Divergence）

交叉熵（Cross-Entropy）

基于深度学习的相似性算法

Siamese Networks

Sentence-BERT

Contrastive Loss

其他专用算法

Pearson相关系数

SimHash

Word Mover’s Distance

选择依据

PostgreSQL 相似性算法

Levenshtein 距离

Jaro 和 Jaro-Winkler 距离

Trigram 相似度 (pg_trgm 扩展)

双字母组相似度 (dmetaphone)

全文搜索相关度

余弦相似度

使用建议

PostgreSQL 向量相似性算法

主要向量相似性算法

欧氏距离（L2 距离）

余弦相似度

内积（点积）

曼哈顿距离（L1 距离）

汉明距离

Jaccard 距离

索引加速向量搜索

IVFFlat（倒排平面索引）

HNSW（分层可导航小世界图）

应用场景

性能优化建议

MongoDB 相似性算法

文本相似性搜索

向量相似性搜索 (MongoDB Atlas 功能)

近似相似性算法

聚合框架中的相似性计算

第三方集成

MongoDB 向量相似性算法

支持的相似性度量算法

余弦相似度 (Cosine Similarity)

欧几里得距离 (Euclidean Distance)

点积 (Dot Product)

MongoDB Atlas 向量搜索实现

创建向量索引

执行向量搜索 ($vectorSearch)

性能优化技巧

维度选择:

索引配置:

查询参数调优:

应用场景示例

语义搜索:

推荐系统:

图像检索:

限制与注意事项