第12.2节 Label Propagation标签传播算法
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
12.2 Label Propagation标签传播算法 12.2.1 算法思想 12.2.2 算法原理 12.2.3 计算示例 12.2.4 示例代码 12.2.5 从零实现标签传播算法之迭代法 12.2.6 收敛性证明 12.2.7 从零实现标签传播算法之非迭代法 12.2.8 小结 引用
12.2 Label Propagation标签传播算法
在上一节内容中，笔者详细地介绍了半监督学习算法中出现地最早也是最简单的一种用于分类问题的Self-Training算法，其核心思想是先通过少量的标注数据来训练一个弱分类器，其次再通过这个弱分类器来对无标签样本进行标注并选择其中的有效部分作为样本的真实标签，然后再次以当前已有的标注数据来训练模型并对无标签的样本进行标注并反复迭代，最后直到达到停止条件时结束。
在接下来的这节内容中，笔者将会介绍另外一种基于图结构的半监督学习模型——标签传播算法（Label Propagation）。
12.2.1 算法思想
标签传播算法的基本思想认为，在样本空间中距离越是相近的样本点越有可能具有相同的样本标签[1]，而这一点也非常符合现实直觉。在这样的假设一下，可以通过构建一个有向完全图来表示样本点之间的位置关系，其中图上的结点表示样本点，边表示两个结点之间的权重（样本点相距越近，则其对应的权重值便越大）。进一步，根据该权重图可以构造得到一个概率转移矩阵，其中表示样本点转移到样本点的概率。如果结点是一个无标签的样本点，结点是一个有标签的样本点，那么此时便可以根据的大小来判断样本点是否与具有相同的样本标签。
如图12-2所示，黑色圆点和白色圆点分别表示已知标签和未知标签的样本点，箭头表示传播方向，数值表示转移概率。根据标签传播算法的思想，白色样本点的所属类别可以通过黑色样本点到白色样本点的转移概率来进行确定。例如对于图12-2中间的白色样本点来说，其所属类别最有可能便是由右下角的黑色样本点所确定，因为此时对应的转移概率0.76在所有可能的转移情况中最大。
可以看出，标签传播算法的关键在于建立任意两个样本点之间转移的概率，然后通过已知标签的样本点来推断未知标签的样本点。
12.2.2 算法原理
设为已知标签的数据样本，其中是样本点对应的标签；同时样本的类别数为，并且假定所有的类别均出现在中。继续，设为不含标签的样本点，其中未知，且通常情况下。此时有，且。
根据标签传播算的思想可知，首先需要构建一个有向完全图，并完成任意两个样本点之间的权重计算，计算公式如式(12.1)所示：
其中为控制权重的超参数，表示样本点和之间的距离权重。
通过式(12.1)计算任意两个样本点之间的距离权重后便可以得到一个结点与边之间的权重矩阵，并且我们还可以知道是一个的对称矩阵阵。同时，值得一提的是这里还可以用其它距离来计算两个结点之间的距离权重。
进一步，定义形状为的概率转移矩阵，且任意两个结点之间的转移概率计算公式为：
其中表示结点转移到结点的概率，同时需要注意的是并不是一个对称矩阵。
接着，再定义一个形状为的标签矩阵，其每一行用于表示每个样本属于各个类别的概率分布。
最后，只需要迭代如下3个步骤便可以求解得到未知标签样本的预测结果：
第一步：计算更新后的
第二步：行标准化
第三步：将中已知标签位置上的结果替换为原始的正确标签，然后重复前面两步直到收敛。
12.2.3 计算示例
在介绍完标签传播算法的基本原理之后，下面再通过一个实际的计算示例来展示其中的计算细节，同时也好从感官上来认识什么是标签传播算法。假设现在一共有a,b,c,d,e这5个样本点，类别标签分别为[0,1,1,-1,-1]，其中-1表示无标签，如图12-3所示。
如图12-3所示，5个样本点的左边分别为[[0.5, 0.5], [1.5, 1.5], [2.5, 1.5], [1.5, 2.5], [3.5, 2.5]]。此时，根据式(12.1)可以计算得到权重矩阵，如图12-4所示。
从图12-4中可以看出，样本b与样本d和样本c之间的距离最近，因此图12-4中对应的权重也是所有权重中最大的，为0.268。进一步，根据式(12.2)可以计算得到概率转移矩阵如图12-5所示。
接着，初始化标签矩阵并根据式(12.3)和式(12.4)可以计算得到更新后的标签矩阵，如图12-6所示。
如图12-6所示便是标签矩阵的计算过程，其中最右边的矩阵便是更新后的标签矩阵（已归一化），不过这两个矩阵相乘的意义在哪里呢？
以样本点d为例，根据概率转移矩阵可知，样本a转移到d的概率为0.006，其含义便是样本d的标签有0.6%的可能性和样本a的标签相同。同理，b转移到d的概率为0.196，c到d的概率为0.082，d到d的概率为0.654，e到d的概率为0.016。从图12-2也可以看出，b是所有样本点中距离d最近的样本点，因此样本d的标签最有可能和样本b的相同，计算过程如图12-7所示。
从图12-7可以看出，对于样本d来说，其最终的类别概率分布就等于每种情况下的转移概率乘以对应样本类别的概率分布并进行求和。所以，图12-6中的计算过程本质上就是将各个转移概率分配到每个样本标签上的过程，而这也类似于深度学习中的注意力机制。
12.2.4 示例代码
在sklearn中，我们可以从sklearn.semi_supervised中来导入标签传播算法LabelPropagation模块。接下来，需要构造半监督学习所需要使用到的训练集，即将部分样本的标签置为-1（这是由模型在实现时所确定），实现代码如下所示：
1 def load_data():
2 x, y = load_iris(return_X_y=True)
3 x_train, x_test, y_train, y_test = \
4 train_test_split(x, y, test_size=0.3, random_state=2022)
5 rng = np.random.RandomState(20)
6 random_unlabeled_points = rng.rand(y_train.shape[0]) < 0.8
7 y_mixed = deepcopy(y_train)
8 y_mixed[random_unlabeled_points] = -1
9 return x_train, x_test, y_train, y_test, y_mixed
在上述代码中，第2~4行是导入原始并进行训练集和测试集的划分；第5~8行则是将训练集中样本的标签重置为-1，同时也保留了原始重置之前的标签便于后续在训练集上测试模型的效果；第9行是返回最后各个部分的结果。
进一步，便可以导入LabelPropagation进行模型训练和测试，代码如下：
1 from sklearn.semi_supervised import LabelPropagation
2 def test_label_propagation():
3 x_train, x_test, y_train, y_test, y_mixed = load_data()
4 model = LabelPropagation(gamma=20,max_iter=1000)
5 model.fit(x_train, y_mixed)
6 y_pred = model.predict(x_train)
7 print(f"模型在训练集上的准确率为: {accuracy_score(y_pred, y_train)}")
8 y_pred = model.predict(x_test)
9 print(f"模型在测试集上的准确率为: {accuracy_score(y_pred, y_test)}")
10
11 if __name__ == '__main__':
12 test_label_propagation()
在上述代码中，第1行便是导入标签传播算法模块；第4行是实例化LabelPropagation模型，其中gamma便是式(12.1)中的，max_iter指的是模型（第12.2.2节中计算标签矩阵）的迭代次数；第5行是模型的拟合过程；第6~9行是分别在训练集和测试集上的预测结果。上述代码运行结束后便可以得到类似如下所示的输出结果：
1 模型在训练集上的准确率为: 0.9619047619047619
2 模型在测试集上的准确率为: 1.0
上述完整代码可参见Book/Chapter12/C03_label_propagation.py文件。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！