基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法
字数 1979 2025-11-11 03:20:43

基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法

题目描述
词移距离是一种基于词嵌入的文本相似度计算算法，旨在解决传统方法（如TF-IDF、词袋模型）忽略语义信息的问题。WMD的核心思想是将文本相似度计算转化为运输问题：将一篇文档中的每个词视为“供给点”，另一篇文档中的每个词视为“需求点”，词与词之间的语义距离通过词嵌入（如Word2Vec）计算，最终求解将所有词从一篇文档“移动”到另一篇文档的最小累积成本。

解题过程详解

步骤1：问题形式化

  1. 文档表示：

    • 将两篇文档 \(D_1\) 和 \(D_2\) 表示为词袋模型（Bag-of-Words），并归一化为概率分布。
    • 例如，\(D_1\) 的归一化向量为 \(\mathbf{d}_1 = [w_{1}^{(1)}, w_{2}^{(1)}, ..., w_{n}^{(1)}]\)，其中 \(w_{i}^{(1)}\) 是第 \(i\) 个词的权重（通常用词频或TF-IDF加权）。
    • 同理，\(D_2\) 的向量为 \(\mathbf{d}_2 = [w_{1}^{(2)}, w_{2}^{(2)}, ..., w_{m}^{(2)}]\)。

  2. 词嵌入距离矩阵：

    • 构建一个 \(n \times m\) 的矩阵 \(\mathbf{C}\)，其中元素 \(c_{ij}\) 表示 \(D_1\) 中第 \(i\) 个词与 \(D_2\) 中第 \(j\) 个词的语义距离，通常用词嵌入的欧氏距离计算：

\[ c_{ij} = \| \mathbf{v}_i - \mathbf{v}_j \|_2 \]

  • 这里 \(\mathbf{v}_i\) 和 \(\mathbf{v}_j\) 是对应词的预训练词向量（如Word2Vec或GloVe）。

步骤2：运输问题建模

  1. 目标函数：
    • 定义运输矩阵 \(\mathbf{T} \in \mathbb{R}^{n \times m}\)，其中 \(t_{ij}\) 表示将 \(D_1\) 中词 \(i\) 的权重分配到 \(D_2\) 中词 \(j\) 的比例。
    • WMD的目标是最小化总运输成本：

\[ \text{WMD}(D_1, D_2) = \min_{\mathbf{T} \geq 0} \sum_{i=1}^{n} \sum_{j=1}^{m} t_{ij} \cdot c_{ij} \]

  1. 约束条件：
    • 从 \(D_1\) 中每个词 \(i\) 流出的总权重等于其原始权重：

\[ \sum_{j=1}^{m} t_{ij} = w_i^{(1)} \quad \forall i \in \{1, ..., n\} \]

  • 流入 \(D_2\) 中每个词 \(j\) 的总权重等于其目标权重：

\[ \sum_{i=1}^{n} t_{ij} = w_j^{(2)} \quad \forall j \in \{1, ..., m\} \]

步骤3：求解优化问题

  1. 线性规划求解：

    • 上述问题是一个经典的地球移动距离（Earth Mover‘s Distance）问题，可通过线性规划（Linear Programming）求解。
    • 使用优化库（如SciPy的linprog或专用求解器）找到最优运输矩阵 \(\mathbf{T}^*\)。

  2. 计算复杂度优化：

    • 直接求解的复杂度为 \(O(p^3 \log p)\)（其中 \(p = \max(n, m)\)），对长文本效率低。
    • 常用加速方法：
      • 词嵌入剪枝：仅使用高频词或关键词降低维度。
      • 近似算法：如基于Word Centroid Distance的松弛估计（WCD下界）。

步骤4：相似度计算与归一化

  1. 最终距离：

    • 得到最小运输成本后，WMD值即为两篇文档的语义距离。值越小，相似度越高。

  2. 可选归一化：

    • 若需将距离映射到 \([0, 1]\) 区间，可使用指数核函数：

\[ \text{Similarity} = e^{-\gamma \cdot \text{WMD}} \]

  • 其中 \(\gamma\) 为调节参数。

关键特点与局限性

  • 优点：
    • 充分利用词嵌入的语义信息，优于传统词袋模型。
    • 无需对齐短语或句法结构，对短文本效果显著。
  • 缺点：
    • 计算复杂度高，难以直接应用于长文档。
    • 依赖词嵌入质量，未考虑词序信息。

通过以上步骤，WMD将文本相似度问题转化为可求解的优化问题，显著提升了语义相似度计算的准确性。

基于词移距离（Word Mover's Distance, WMD）的文本相似度计算算法 题目描述 词移距离是一种基于词嵌入的文本相似度计算算法，旨在解决传统方法（如TF-IDF、词袋模型）忽略语义信息的问题。WMD的核心思想是将文本相似度计算转化为 运输问题 ：将一篇文档中的每个词视为“供给点”，另一篇文档中的每个词视为“需求点”，词与词之间的语义距离通过词嵌入（如Word2Vec）计算，最终求解将所有词从一篇文档“移动”到另一篇文档的最小累积成本。 解题过程详解 步骤1：问题形式化 文档表示 ： 将两篇文档 \( D_ 1 \) 和 \( D_ 2 \) 表示为词袋模型（Bag-of-Words），并归一化为概率分布。 例如，\( D_ 1 \) 的归一化向量为 \( \mathbf{d} 1 = [ w {1}^{(1)}, w_ {2}^{(1)}, ..., w_ {n}^{(1)}] \)，其中 \( w_ {i}^{(1)} \) 是第 \( i \) 个词的权重（通常用词频或TF-IDF加权）。 同理，\( D_ 2 \) 的向量为 \( \mathbf{d} 2 = [ w {1}^{(2)}, w_ {2}^{(2)}, ..., w_ {m}^{(2)} ] \)。 词嵌入距离矩阵 ： 构建一个 \( n \times m \) 的矩阵 \( \mathbf{C} \)，其中元素 \( c_ {ij} \) 表示 \( D_ 1 \) 中第 \( i \) 个词与 \( D_ 2 \) 中第 \( j \) 个词的语义距离，通常用词嵌入的欧氏距离计算： \[ c_ {ij} = \| \mathbf{v}_ i - \mathbf{v}_ j \|_ 2 \] 这里 \( \mathbf{v}_ i \) 和 \( \mathbf{v}_ j \) 是对应词的预训练词向量（如Word2Vec或GloVe）。 步骤2：运输问题建模 目标函数 ： 定义运输矩阵 \( \mathbf{T} \in \mathbb{R}^{n \times m} \)，其中 \( t_ {ij} \) 表示将 \( D_ 1 \) 中词 \( i \) 的权重分配到 \( D_ 2 \) 中词 \( j \) 的比例。 WMD的目标是最小化总运输成本： \[ \text{WMD}(D_ 1, D_ 2) = \min_ {\mathbf{T} \geq 0} \sum_ {i=1}^{n} \sum_ {j=1}^{m} t_ {ij} \cdot c_ {ij} \] 约束条件 ： 从 \( D_ 1 \) 中每个词 \( i \) 流出的总权重等于其原始权重： \[ \sum_ {j=1}^{m} t_ {ij} = w_ i^{(1)} \quad \forall i \in \{1, ..., n\} \] 流入 \( D_ 2 \) 中每个词 \( j \) 的总权重等于其目标权重： \[ \sum_ {i=1}^{n} t_ {ij} = w_ j^{(2)} \quad \forall j \in \{1, ..., m\} \] 步骤3：求解优化问题 线性规划求解 ： 上述问题是一个经典的 地球移动距离（Earth Mover‘s Distance） 问题，可通过线性规划（Linear Programming）求解。 使用优化库（如SciPy的 linprog 或专用求解器）找到最优运输矩阵 \( \mathbf{T}^* \)。 计算复杂度优化 ： 直接求解的复杂度为 \( O(p^3 \log p) \)（其中 \( p = \max(n, m) \)），对长文本效率低。 常用加速方法： 词嵌入剪枝 ：仅使用高频词或关键词降低维度。 近似算法 ：如基于Word Centroid Distance的松弛估计（WCD下界）。 步骤4：相似度计算与归一化 最终距离 ： 得到最小运输成本后，WMD值即为两篇文档的语义距离。值越小，相似度越高。 可选归一化 ： 若需将距离映射到 \([ 0, 1 ]\) 区间，可使用指数核函数： \[ \text{Similarity} = e^{-\gamma \cdot \text{WMD}} \] 其中 \( \gamma \) 为调节参数。 关键特点与局限性 优点 ： 充分利用词嵌入的语义信息，优于传统词袋模型。 无需对齐短语或句法结构，对短文本效果显著。 缺点 ： 计算复杂度高，难以直接应用于长文档。 依赖词嵌入质量，未考虑词序信息。 通过以上步骤，WMD将文本相似度问题转化为可求解的优化问题，显著提升了语义相似度计算的准确性。