基于随机游走的标签传播算法（Label Propagation with Random Walk）的原理与迭代计算过程
字数 3746 2025-12-22 10:28:49

基于随机游走的标签传播算法（Label Propagation with Random Walk）的原理与迭代计算过程

我将为你详细讲解一个基于图论和概率模型的半监督学习算法。这个算法非常适合在只有少量标注数据和大量未标注数据的情况下进行分类任务。

题目描述

假设我们有一个数据集，其中大部分样本没有标签（未标注数据），只有一小部分样本有已知的标签（标注数据）。我们的目标是通过某种机制，将这些已知的标签“传播”到整个数据集，从而为所有未标注样本预测出标签。基于随机游走的标签传播算法就是解决这类问题的经典方法之一。

核心思想：将整个数据集建模成一个图（Graph）。图中的节点（Node）代表每一个数据样本。如果两个样本在特征空间中“相似”（例如，特征向量之间的距离很近），我们就在它们对应的节点之间连一条边（Edge）。这个算法的核心直觉是：在图上进行“随机游走”时，游走者从某个未标注节点出发，最终“走到”某个标注节点的概率，就可以作为这个未标注节点属于该标签的概率。换句话说，一个未标注点的标签，应该与其在图中的“邻居”的标签最有可能一致。

解题过程（循序渐进）

让我们把这个复杂的算法分解成几个清晰的步骤，并详细阐述每一步的数学原理和直观解释。

第一步：构建相似图

这是整个算法的根基。我们首先需要将数据点（样本）之间的关系用图的形式表达出来。

  1. 节点：每个数据点（无论是否标注）都对应图中的一个节点。假设我们有 \(n\) 个数据点，那么就有 \(n\) 个节点。我们用集合 \(V = \{1, 2, ..., n\}\) 表示所有节点。
  2. 边与权重：我们需要定义节点之间的连接关系。通常采用两种建图方式：
    • k-近邻图：对于每个节点 \(i\)，找到它的 \(k\) 个最相似的邻居节点（例如，用欧氏距离度量相似度），并与它们建立连接。
    • 全连接图：连接所有节点，但边的权重是相似度的函数，当两个节点不相似时，权重趋近于0。
  3. 相似度与权重矩阵：定义节点 \(i\) 和节点 \(j\) 之间的相似度 \(w_{ij}\)。一个最常用的方法是使用高斯核函数（也称RBF核）：

\[ w_{ij} = \exp(-\frac{||x_i - x_j||^2}{2\sigma^2}) \]

其中，$x_i$ 是样本 $i$ 的特征向量，$||\cdot||$ 是欧氏距离，$\sigma$ 是一个控制相似度衰减速度的带宽参数。$w_{ij}$ 越大，表示两个节点越相似，连接越紧密。
  1. 权重矩阵：我们用矩阵 \(W \in \mathbb{R}^{n \times n}\) 来记录所有节点之间的相似度/权重，其元素 \(W_{ij} = w_{ij}\)。通常，我们令 \(W_{ii} = 0\)（节点不自连）。
  2. 度矩阵：节点 \(i\) 的度（Degree）\(d_i\) 是所有连接到它的边的权重之和：\(d_i = \sum_{j=1}^n w_{ij}\)。将所有节点的度放在一个对角矩阵中，就得到了度矩阵 \(D\)：

\[ D = \text{diag}(d_1, d_2, ..., d_n) \]

目标：这一步之后，我们得到了图的数学表示：权重矩阵 \(W\) 和度矩阵 \(D\)。图的结构捕获了数据的内在几何和流形信息。

第二步：定义概率转移矩阵

这是“随机游走”的核心。我们需要定义在图上进行一步随机游走的规则。

  1. 转移概率：想象一个粒子（游走者）当前位于节点 \(i\)。在下一步，它会随机跳到一个邻居节点 \(j\)。跳转到节点 \(j\) 的概率应该与边 \(i \rightarrow j\) 的权重 \(w_{ij}\) 成正比。因此，从节点 \(i\) 转移到节点 \(j\) 的一步转移概率 \(P_{ij}\) 为：

\[ P_{ij} = \frac{w_{ij}}{d_i} \]

这个公式很直观：与 $i$ 连接越强的邻居，被访问的概率越大。
  1. 概率转移矩阵：将所有转移概率 \(P_{ij}\) 组织成一个矩阵，就得到了概率转移矩阵 \(P\)：

\[ P = D^{-1}W \]

其中 $D^{-1}$ 是度矩阵 $D$ 的逆矩阵。矩阵 $P$ 的每一行元素之和为1（因为 $\sum_j P_{ij} = 1$），满足概率分布的性质，因此它是一个**随机矩阵**。

目标：有了矩阵 \(P\)，我们就完全定义了这个图上随机游走的动态规则。\(P_{ij}\) 精确描述了从任意节点 \(i\) 出发，经过一步到达任意节点 \(j\) 的概率。

第三步：定义标签矩阵与初始化

我们需要用数学形式表示已知标签和待传播的标签。

  1. 标签类别：假设我们有 \(C\) 个不同的类别（例如，猫、狗、鸟）。
  2. 标签矩阵：定义一个标签矩阵 \(Y \in \mathbb{R}^{n \times C}\)。矩阵的每一行对应一个节点（样本）的标签概率分布。
  3. 初始化：
    • 对于有标注的节点（假设有 \(l\) 个），其标签分布是确定的。如果节点 \(i\) 的真实标签是第 \(c\) 类，则我们设置 \(Y_{ic} = 1\)，并且该行其他元素为0。这称为**“独热编码”**。
    • 对于未标注的节点（有 \(u = n - l\) 个），我们不知道它的标签，所以初始时我们可以将其标签分布设为均匀分布，或者更简单地，设为一个全零向量。
  4. 软标签：在迭代传播过程中，每个节点（无论是已标注还是未标注）的标签都会被表示为一个 \(C\) 维的概率向量（软标签），其元素表示属于各个类别的概率。最终，我们取概率最大的类别作为该节点的预测标签。

目标：准备好初始的标签信息 \(Y^{(0)}\)。已标注节点的标签是固定（“吸收态”或“锚点”），未标注节点的标签是待更新的变量。

第四步：迭代传播（核心算法）

这是标签从已知节点扩散到未知节点的过程，其背后的数学正是随机游走。

  1. 算法迭代公式：标签传播算法的核心是一个极其简洁的迭代公式：

\[ Y^{(t+1)} = P \cdot Y^{(t)} \]

然后，在每次迭代后，**我们将已标注节点的标签重置为其真实标签**。这一步至关重要！
  1. 直观理解：
    • 从行视角看：\(Y^{(t+1)}\) 的第 \(i\) 行（节点 \(i\) 的新标签分布），等于 \(P\) 的第 \(i\) 行（从节点 \(i\) 出发到所有节点的概率）与矩阵 \(Y^{(t)}\) 的乘积。这恰恰是计算一个“期望标签”：节点 \(i\) 的新标签，是其所有邻居节点当前标签的加权平均，权重就是随机游走到该邻居的概率。
    • \(Y^{(t+1)}_{i} = \sum_j P_{ij} \cdot Y^{(t)}_{j}\)
    • 这就像一个“投票”过程：在时刻 \(t\)，每个节点 \(j\) 都有一张“选票”（它的当前标签分布 \(Y^{(t)}_j\)），节点 \(i\) 收集它所有邻居的选票，并根据连接强度（\(P_{ij}\)）来加权汇总，形成自己在 \(t+1\) 时刻的标签。
  2. 重置标注节点：在每次计算 \(Y^{(t+1)}\) 后，我们强行将前 \(l\) 个（已标注）节点对应的行，重新设置回它们初始的、真实的独热编码标签。这保证了已标注节点的标签在传播过程中始终是正确且固定的，它们像“源头”一样，不断将正确的信息注入到传播过程中。
  3. 收敛性：可以证明，在上述迭代规则下，未标注节点的标签概率分布最终会收敛到一个唯一的稳定解。从随机游走的角度看，这个稳定解就是：从未标注节点出发，在图上随机游走，首次到达一个已标注节点时，该已标注节点所属类别的概率分布。本质上，算法计算的是“吸收概率”。
  4. 算法伪代码： 
    输入: 相似度矩阵 W, 已标注数据标签 (l个), 类别数 C, 最大迭代次数 T
输出: 所有节点的预测标签
步骤:
1. 计算度矩阵 D (D_ii = sum_j W_ij)
2. 计算转移矩阵 P = D^{-1} W
3. 初始化标签矩阵 Y (l行已知，u行全零)
4. 对 t=1 到 T:
    a. 执行传播: Y = P * Y
    b. 重置标签: 将Y的前l行重置为原始真实标签
    c. 检查Y的变化是否小于阈值? 是则跳出循环
5. 对每个节点i，取 argmax(Y_i) 作为其预测标签类别

第五步：收敛性与预测

  1. 收敛：迭代过程最终会稳定下来。在实践中，当连续两次迭代的标签矩阵 \(Y\) 的变化（如Frobenius范数）小于一个预设的极小阈值 \(\epsilon\) 时，我们就认为算法已经收敛。
  2. 做出预测：对于收敛后最终的标签矩阵 \(Y^*\)，其中每个未标注节点 \(i\) 都对应一个 \(C\) 维向量 \(Y^*_i = (p_{i1}, p_{i2}, ..., p_{iC})\)。我们选择其中概率值最大的那个类别作为节点 \(i\) 的预测标签：

\[ \hat{y}_i = \arg\max_{c} p_{ic} \]

总结

基于随机游走的标签传播算法，巧妙地将半监督学习问题转化为图上的概率传播问题。其强大之处在于，它完全利用了数据点之间的相似性关系（体现在图结构中）和少数已知标签。算法通过模拟随机游走过程，让信息沿着高相似度的边流动，最终使得相似的点倾向于拥有相同的标签。这个方法计算高效，直观易懂，并且能有效处理流形结构的数据，是图上半监督学习的经典基石之一。

基于随机游走的标签传播算法（Label Propagation with Random Walk）的原理与迭代计算过程 我将为你详细讲解一个基于图论和概率模型的半监督学习算法。这个算法非常适合在只有少量标注数据和大量未标注数据的情况下进行分类任务。 题目描述 假设我们有一个数据集，其中大部分样本没有标签（未标注数据），只有一小部分样本有已知的标签（标注数据）。我们的目标是通过某种机制，将这些已知的标签“传播”到整个数据集，从而为所有未标注样本预测出标签。基于随机游走的标签传播算法就是解决这类问题的经典方法之一。 核心思想 ：将整个数据集建模成一个 图 （Graph）。图中的 节点 （Node）代表每一个数据样本。如果两个样本在特征空间中“相似”（例如，特征向量之间的距离很近），我们就在它们对应的节点之间连一条 边 （Edge）。这个算法的核心直觉是：在图上进行“随机游走”时，游走者从某个未标注节点出发，最终“走到”某个标注节点的概率，就可以作为这个未标注节点属于该标签的概率。换句话说，一个未标注点的标签，应该与其在图中的“邻居”的标签最有可能一致。 解题过程（循序渐进） 让我们把这个复杂的算法分解成几个清晰的步骤，并详细阐述每一步的数学原理和直观解释。 第一步：构建相似图 这是整个算法的根基。我们首先需要将数据点（样本）之间的关系用图的形式表达出来。 节点 ：每个数据点（无论是否标注）都对应图中的一个节点。假设我们有 \(n\) 个数据点，那么就有 \(n\) 个节点。我们用集合 \(V = \{1, 2, ..., n\}\) 表示所有节点。 边与权重 ：我们需要定义节点之间的连接关系。通常采用两种建图方式： k-近邻图 ：对于每个节点 \(i\)，找到它的 \(k\) 个最相似的邻居节点（例如，用欧氏距离度量相似度），并与它们建立连接。 全连接图 ：连接所有节点，但边的权重是相似度的函数，当两个节点不相似时，权重趋近于0。 相似度与权重矩阵 ：定义节点 \(i\) 和节点 \(j\) 之间的 相似度 \(w_ {ij}\)。一个最常用的方法是使用 高斯核函数 （也称RBF核）： \[ w_ {ij} = \exp(-\frac{||x_ i - x_ j||^2}{2\sigma^2}) \] 其中，\(x_ i\) 是样本 \(i\) 的特征向量，\(||\cdot||\) 是欧氏距离，\(\sigma\) 是一个控制相似度衰减速度的带宽参数。\(w_ {ij}\) 越大，表示两个节点越相似，连接越紧密。 权重矩阵 ：我们用矩阵 \(W \in \mathbb{R}^{n \times n}\) 来记录所有节点之间的相似度/权重，其元素 \(W_ {ij} = w_ {ij}\)。通常，我们令 \(W_ {ii} = 0\)（节点不自连）。 度矩阵 ：节点 \(i\) 的 度 （Degree）\(d_ i\) 是所有连接到它的边的权重之和：\(d_ i = \sum_ {j=1}^n w_ {ij}\)。将所有节点的度放在一个对角矩阵中，就得到了 度矩阵 \(D\)： \[ D = \text{diag}(d_ 1, d_ 2, ..., d_ n) \] 目标 ：这一步之后，我们得到了图的数学表示：权重矩阵 \(W\) 和度矩阵 \(D\)。图的结构捕获了数据的内在几何和流形信息。 第二步：定义概率转移矩阵 这是“随机游走”的核心。我们需要定义在图上进行一步随机游走的规则。 转移概率 ：想象一个粒子（游走者）当前位于节点 \(i\)。在下一步，它会随机跳到一个邻居节点 \(j\)。跳转到节点 \(j\) 的概率应该与边 \(i \rightarrow j\) 的权重 \(w_ {ij}\) 成正比。因此，从节点 \(i\) 转移到节点 \(j\) 的 一步转移概率 \(P_ {ij}\) 为： \[ P_ {ij} = \frac{w_ {ij}}{d_ i} \] 这个公式很直观：与 \(i\) 连接越强的邻居，被访问的概率越大。 概率转移矩阵 ：将所有转移概率 \(P_ {ij}\) 组织成一个矩阵，就得到了 概率转移矩阵 \(P\)： \[ P = D^{-1}W \] 其中 \(D^{-1}\) 是度矩阵 \(D\) 的逆矩阵。矩阵 \(P\) 的每一行元素之和为1（因为 \(\sum_ j P_ {ij} = 1\)），满足概率分布的性质，因此它是一个 随机矩阵 。 目标 ：有了矩阵 \(P\)，我们就完全定义了这个图上随机游走的动态规则。\(P_ {ij}\) 精确描述了从任意节点 \(i\) 出发，经过 一步 到达任意节点 \(j\) 的概率。 第三步：定义标签矩阵与初始化 我们需要用数学形式表示已知标签和待传播的标签。 标签类别 ：假设我们有 \(C\) 个不同的类别（例如，猫、狗、鸟）。 标签矩阵 ：定义一个 标签矩阵 \(Y \in \mathbb{R}^{n \times C}\)。矩阵的每一行对应一个节点（样本）的标签概率分布。 初始化 ： 对于有标注的节点（假设有 \(l\) 个），其标签分布是确定的。如果节点 \(i\) 的真实标签是第 \(c\) 类，则我们设置 \(Y_ {ic} = 1\)，并且该行其他元素为0。这称为** “独热编码”** 。 对于未标注的节点（有 \(u = n - l\) 个），我们不知道它的标签，所以初始时我们可以将其标签分布设为均匀分布，或者更简单地，设为一个全零向量。 软标签 ：在迭代传播过程中，每个节点（无论是已标注还是未标注）的标签都会被表示为一个 \(C\) 维的概率向量（软标签），其元素表示属于各个类别的概率。最终，我们取概率最大的类别作为该节点的预测标签。 目标 ：准备好初始的标签信息 \(Y^{(0)}\)。已标注节点的标签是固定（“吸收态”或“锚点”），未标注节点的标签是待更新的变量。 第四步：迭代传播（核心算法） 这是标签从已知节点扩散到未知节点的过程，其背后的数学正是 随机游走 。 算法迭代公式 ：标签传播算法的核心是一个极其简洁的迭代公式： \[ Y^{(t+1)} = P \cdot Y^{(t)} \] 然后，在每次迭代后， 我们将已标注节点的标签重置为其真实标签 。这一步至关重要！ 直观理解 ： 从 行视角 看：\(Y^{(t+1)}\) 的第 \(i\) 行（节点 \(i\) 的新标签分布），等于 \(P\) 的第 \(i\) 行（从节点 \(i\) 出发到所有节点的概率）与矩阵 \(Y^{(t)}\) 的乘积。这恰恰是计算一个“期望标签”：节点 \(i\) 的新标签，是其所有邻居节点当前标签的加权平均，权重就是随机游走到该邻居的概率。 \(Y^{(t+1)} {i} = \sum_ j P {ij} \cdot Y^{(t)}_ {j}\) 这就像一个“投票”过程：在时刻 \(t\)，每个节点 \(j\) 都有一张“选票”（它的当前标签分布 \(Y^{(t)} j\)），节点 \(i\) 收集它所有邻居的选票，并根据连接强度（\(P {ij}\)）来加权汇总，形成自己在 \(t+1\) 时刻的标签。 重置标注节点 ：在每次计算 \(Y^{(t+1)}\) 后，我们强行将前 \(l\) 个（已标注）节点对应的行，重新设置回它们初始的、真实的独热编码标签。这保证了已标注节点的标签在传播过程中始终是正确且固定的，它们像“源头”一样，不断将正确的信息注入到传播过程中。 收敛性 ：可以证明，在上述迭代规则下，未标注节点的标签概率分布最终会收敛到一个唯一的稳定解。从随机游走的角度看，这个稳定解就是：从未标注节点出发，在图上随机游走， 首次到达一个已标注节点时，该已标注节点所属类别的概率分布 。本质上，算法计算的是“吸收概率”。 算法伪代码 ： 第五步：收敛性与预测 收敛 ：迭代过程最终会稳定下来。在实践中，当连续两次迭代的标签矩阵 \(Y\) 的变化（如Frobenius范数）小于一个预设的极小阈值 \(\epsilon\) 时，我们就认为算法已经收敛。 做出预测 ：对于收敛后最终的标签矩阵 \(Y^ \)，其中每个未标注节点 \(i\) 都对应一个 \(C\) 维向量 \(Y^ i = (p {i1}, p_ {i2}, ..., p_ {iC})\)。我们选择其中概率值最大的那个类别作为节点 \(i\) 的预测标签： \[ \hat{y} i = \arg\max {c} p_ {ic} \] 总结 基于随机游走的标签传播算法，巧妙地将半监督学习问题转化为图上的 概率传播 问题。其强大之处在于，它完全利用了数据点之间的 相似性关系 （体现在图结构中）和 少数已知标签 。算法通过模拟随机游走过程，让信息沿着高相似度的边流动，最终使得相似的点倾向于拥有相同的标签。这个方法计算高效，直观易懂，并且能有效处理流形结构的数据，是图上半监督学习的经典基石之一。