基于图的半监督学习与流形学习算法解析

### 基于图的半监督学习与流形学习算法解析 在机器学习领域，半监督学习和流形学习是两个重要的研究方向。半监督学习利用少量有标签样本和大量无标签样本进行学习，而流形学习则致力于处理高维数据的降维问题。本文将详细介绍基于马尔可夫随机游走的标签传播算法以及几种流形学习算法，包括 Isomap、局部线性嵌入（LLE）和拉普拉斯谱嵌入。 #### 基于马尔可夫随机游走的标签传播 基于马尔可夫随机游走的标签传播算法旨在给定混合数据集的情况下，找到无标签样本的目标标签的概率分布。该算法通过模拟随机过程来实现这一目标，每个无标签样本在图中游走，直到到达一个静态吸收状态（即有标签样本），并获取相应的标签。 ##### 算法步骤 1. **构建图和权重矩阵**：首先，使用所有样本构建 k 近邻图，并基于 RBF 核定义权重矩阵 W。 2. **计算转移概率矩阵**：转移概率矩阵 P 可以表示为 P = D⁻¹W，其中 D 是度矩阵。 3. **计算标签概率**：对于无标签样本，通过求解线性系统 (Duu - Wuu)Pu = WulPl 来计算其属于类别 y = 1 的概率。 ##### 代码示例 ```python from sklearn.datasets import make_blobs import numpy as np from sklearn.neighbors import kneighbors_graph # 生成数据集 nb_samples = 2000 nb_unlabeled = 1950 nb_classes = 2 X, Y = make_blobs(n_samples=nb_samples, n_features=2, centers=nb_classes, cluster_std=2.5, random_state=500) Y[nb_samples - nb_unlabeled:] = -1 # 定义 RBF 核函数 def rbf(x1, x2, sigma=1.0): d = np.linalg.norm(x1 - x2, ord=1) return np.exp(-np.power(d, 2.0) / (2 * np.power(sigma, 2))) # 创建图和权重矩阵 W = kneighbors_graph(X, n_neighbors=15, mode='connectivity', include_self=True).toarray() for i in range(nb_samples): for j in range(nb_samples): if W[i, j] != 0.0: W[i, j] = rbf(X[i], X[j]) # 计算未归一化图拉普拉斯矩阵的无标签部分和矩阵 W 的无标签 - 有标签部分 D = np.diag(np.sum(W, axis=1)) L = D - W Luu = L[nb_samples - nb_unlabeled:, nb_samples - nb_unlabeled:] Wul = W[nb_samples - nb_unlabeled:, 0:nb_samples - nb_unlabeled,] Yl = Y[0:nb_samples - nb_unlabeled] # 求解线性系统 Yu = np.round(np.linalg.solve(Luu, np.dot(Wul, Yl))) Y[nb_samples - nb_unlabeled:] = Yu.copy() ``` ##### 算法优缺点 - **优点**：该算法和标签传播算法都可以使用闭式解，即使样本数量很大，计算速度也非常快。 - **缺点**：RBF 核的 σ/γ 的选择是一个基本问题，没有标准的解决方案。可以考虑 σ → 0 和 σ →