半监督学习入门与图基算法详解

### 半监督学习入门与图基算法详解 #### 1. 半监督学习基础概念 半监督学习在处理数据时，结合了有标签样本和无标签样本的信息。在进行半监督学习时，有几个重要的假设需要了解： - **平滑性假设**：在监督和半监督分类器的工作中，平滑性假设十分重要，它能保证模型具有合理的泛化能力。简单来说，就是在特征空间中距离相近的样本应该具有相同的标签。 - **聚类假设**：该假设与数据集的几何结构密切相关，允许在强结构条件下处理密度估计问题。即数据会自然地形成不同的聚类，同一聚类中的样本倾向于具有相同的标签。 - **流形假设**：此假设有助于避免维度灾难。它认为高维数据实际上位于一个低维的流形上，在这个流形上进行学习可以更有效地处理数据。 除了这些假设，还有一些重要的模型和算法： - **生成高斯混合模型**：这是一种生成式和归纳式模型，基于先验概率由多元高斯分布建模的假设，对有标签和无标签样本进行聚类。 - **对比悲观似然估计**：这是一种归纳式的半监督分类框架，可与任何监督分类器一起使用。其核心是基于软标签（表示无标签样本的概率）定义对比对数似然，并施加悲观条件以最小化对软标签的信任，从而找到使对数似然最大化的最佳配置。 - **S³VM算法**：是经典SVM方法的扩展，基于两个额外的优化约束来处理无标签样本。该方法相对强大，但具有非凸性，因此对用于最小化目标函数的算法非常敏感。 - **TSVM算法**：试图通过基于可变标签的条件来最小化目标。问题分为监督部分（与标准SVM完全相同）和半监督部分（结构相似但没有固定的y标签）。同样具有非凸性，需要评估不同的优化策略以找到准确性和计算复杂度之间的最佳平衡。 #### 2. 图基半监督学习概述 图基半监督学习基于从数据集得到的图以及样本之间的现有关系。主要解决两个问题： - **类标签传播到无标签样本** - **基于流形假设的非线性技术降低原始数据集的维度** 具体涉及的算法如下： | 类别 | 算法 | | ---- | ---- | | 标签传播算法 | 基于权重矩阵的标签传播、Scikit - Learn中的标签传播（基于转移概率）、标签扩散、基于马尔可夫随机游走的传播 | | 流形学习算法 | Isomap算法和多维缩放方法、局部线性嵌入、拉普拉斯谱嵌入、t - SNE | #### 3. 标签传播算法 ##### 3.1 算法原理 标签传播是基于数据集的图表示的半监督算法家族。假设有N个有标签点（双极标签+1和 - 1）和M个无标签点（y = 0），可以基于样本之间的几何亲和度构建无向图。图G = {V, E}，顶点集V = { - 1, +1, 0}，边集基于亲和矩阵W（当图为无权图时通常称为邻接矩阵），仅依赖于X值，与标签无关。 亲和矩阵W可以通过以下常见方法获得： - **k近邻（k - Nearest Neighbors）**：参数k控制作为邻居考虑的样本数量。 - **径向基函数核（Radial basis function kernel）**：参数γ有时表示为2σ²的倒数。小的γ值对应大的方差，会增加半径，包括更远的点并平滑类；大的γ值会将边界限制在趋于单个样本的子集。 同时，还需要引入度矩阵D，它是一个对角矩阵，每个非零元素表示对应顶点的度。标签传播的基本思想是让每个节点将其标签传播给邻居，并迭代该过程直到收敛。 ##### 3.2 算法步骤 标签传播算法的完整步骤如下： 1. 选择亲和矩阵类型（KNN或RBF）并计算W。 2. 计算度矩阵D。 3. 定义Y⁽⁰⁾ = Y。 4. 定义Yₗ = {y₀, y₁, ..., yₙ}。 5. 迭代以下步骤直到收敛： - 第一次更新对有标签和无标签点进行传播步骤，每个标签通过节点的出边传播，相应的权重经度归一化后增加或减少每个贡献的影响。 - 第二次命令重置所有有标签样本的y值。 最后，最终标签可以通过取符号函数得到。 ##### 3.3 算法收敛性证明 将矩阵D⁻¹W根据有标签和无标签样本的关系进行划分，对于无标签样本部分，更新规则可以转换为迭代过程，可识别为截断矩阵几何级数（Neumann级数），且Aᵤᵤ的所有特征值|λᵢ| < 1，因此该级数收敛。 ##### 3.4 Python实现示例 ```python from sklearn.datasets import make_classification nb_samples = 100 nb_unlabeled = 75 X, Y = make_classification(n_samples=nb_samples, n_features=2, n_informative=2, n_redundant=0, random_state=1000) Y[Y==0] = -1 Y[nb_samples - nb_unlabeled:nb_samples] = 0 from sklearn.neighbors import kneighbors_graph nb_neighbors = 2 W_knn_sparse = kneighbors_graph(X, n_neighbors=nb_neighbors, mode='connectivity', include_self=True) W_knn = W_knn_sparse.toarray() import numpy as np def rbf(x1, x2, gamma=10.0): n = np.linalg.norm(x1 - x2, ord=1) return np.exp(-gamma * np.power(n, 2)) W_rbf = np.zeros((nb_samples, nb_samples)) for i in range(nb_samples): for j ```