算法简介

标签传播算法（LPA）是由Zhu等人于2002年提出，它是一种基于图的半监督学习方法，其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。利用样本间的关系建立关系完全图模型，在完全图中，节点包括已标注和未标注数据，其边表示两个节点的相似度，节点的标签按相似度传递给其他节点。标签数据就像是一个源头，可以对无标签数据进行标注，节点的相似度越大，标签越容易传播。由于该算法简单易实现，算法执行时间短，复杂度低且分类效果好，引起了国内外学者的关注，并将其广泛地应用到多媒体信息分类、虚拟社区挖掘等领域中。本文利用关键字labelpropagation、标签传播、标签传递、标记传播、标记传递等词作为关键词，对国内外数据库及网络资源进行了检索，结果发现，目前国内外相关文献期刊论文约有90篇，其中国外82篇，国内8篇，国内外硕博论文3篇。

标签传播算法( LPA)算法如下：

令( x1，y1) …( xl，yl) 是已标注数据，YL={ y1…yl} ∈{ 1…C} 是类别标签，类别数 C 已知，且均存在于标签数据中。令( xl + 1，yl + 1) …( xl + u，yl + u) 为未标注数据，YU={ yl + 1…yl + u} 不可观测，l << u，令数据集 X = { x1…xl + u} ∈R。问题转换为: 从数据集 X 中，利用YL的学习，为未标注数据集YU的每个数据找到对应的标签。

将所有数据作为节点( 包括已标注和未标注数据) ，创建一个完全连接图，其边的权重计算式如下:

其中: dij表示任意两个节点的欧氏距离，权重 wij受控于参数 σ。

为衡量一个节点的标注通过边传播到其他节点的概率，在此定义一个( l + u) × ( l + u) 概率传递矩阵 T 如下所示:

其中: Tij是节点 j 到 i 的传播概率。

算法描述如下：

1. 所有节点传播标签一步： Y← TY；

2. 行标准化矩阵 Y 来维持类别的概率；

3. 夹逼标注数据，重复步骤 2 直到 Y 收敛。

步骤 3 可以使得节点标签的类别分布集中在给定的类别。该算法的缺点在于需要预先标注数据，而且需要预先知识知道分类的类别个数。

算法基本理论

根据LPA算法基本理论，每个节点的标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标注数据的标签不变，使其像一个源头把标签传向未标注数据。最终，当迭代过程结束时，相似节点的概率分布也趋于相似，可以划分到同一个类别中，从而完成标签传播过程。

优缺点：LPA算法的优点是简单、高效、快速；缺点是每次迭代结果不稳定，准确率不高。

在LPA算法中节点的Label有同步更新与异步更新2种更新方法。同步更新方法在二分图中可能出现产生震荡情况。为了避免循环和保证收敛，LPA算法采用异步的策略更新节点的标签，并在每次迭代前对节点重新进行随机排序。