ML之LP：标签传递算法（Label Propagation）的简介(半监督学习)、使用方法、案例应用之详细攻略

背景

标签传递算法（Label Propagation）起源于图论和社交网络分析领域。最早引入这一概念的研究可以追溯到2002年，由Xiaojin Zhu等人在论文《Learning from Labeled and Unlabeled Data with Label Propagation》中提出。

这个算法是由Zhongzhi Shi和Ji Z. Wang在2000年发起提出的。

简介

标签传递算法是一种半监督学习方法，适用于存在少量标记数据和大量未标记数据的情况，它可以从未标注样本中学习新的知识。其核心思想是通过在相似性图上传播标签信息，实现对未标记数据进行标签预测。这一算法通过迭代传递标签，借助已标记样本的信息，逐步扩展到未标记样本。

实践中，可以使用标签传递算法，将标记样本的标记通过一定的相似度传递给未标记样本，直到最终收敛。

标签传递算法在半监督学习中的应用更侧重于从已标记样本中传递信息，以预测未标记样本的标签。总体而言，标签传递算法更倾向于解决半监督学习问题，而不是直接用于聚类任务。

核心思想

标签传递算法的基本思想是：如果两个样本在特征空间很相似，那么它们更可能拥有相同的标签。

算法首先会随机或基于一定规则为所有样本赋予标签，然后循环地更新每个样本的标签，使其标签趋于与近邻样本相同。

具体来说，每个样本的新标签将是其K个近邻样本标签的平均值。通过重复这个传播过程，样本标签将逐渐趋于稳定，代表整体数据分布的模式。

本质

标签传递算法的本质是基于样本之间的相似性关系，通过迭代更新未标记样本的标签，从而实现标签信息的传递和传播。该方法充分利用了标记数据的信息，通过样本之间的连接关系进行标签扩散，形成对未标记样本标签的合理预测。

从本质上说，标签传递算法利用了数据之间的局部相似结构来传播标签信息。它假设相似样本更可能属于同一类，进而利用分类边界附近样本的标签来传播学习全局分类模式。

原理

相似性图构建： 建立一个图，其中节点表示样本，边表示样本之间的相似性。相似性可以基于特征空间距离或其他相似性度量。

标签初始化： 将已标记样本的标签作为初始标签，未标记样本标签初始化为空。

标签传递： 通过迭代计算，利用相似性图传递标签信息，更新未标记样本的标签。

收敛判定： 当标签的变化趋于稳定或达到预定迭代次数时，算法收敛。

应用场景

标签传递算法在社交网络分析、图像分类、文本分类等领域广泛应用。特别适用于数据标记成本高昂或存在大量未标记数据的情境下，能够有效提高模型性能。

标签传递算法适用于未标注样本较多，但其间存在明显类内联系的场景。它要求数据存在明显的局部结构，否则标签很难得到有效传播。但这也是它的优点，就像热传导一样，可以从局部信息中学习全局模式。

例如社交网络中的用户分类、图片网格中的图像分类等。