第12.3节 LabelSpreading算法
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
12.3 Label Spreading 标签传播算法 12.3.1 算法原理 12.3.2 示例代码 12.3.3 从零实现标签传播算法之迭代法 12.3.4 收敛性证明 12.3.5 从零实现标签传播算法之非迭代法 12.3.6 小结 引用
12.3 Label Spreading 标签传播算法
在上一节内容中，笔者介绍了一种基于图结构的标签传播算法（Label Propagation）。标签传播算法的核心思想认为，在样本空间中距离越相近的样本点越有可能具有相同的标签。因此，对于样本空间中的所有样本点，可以通过构建一个有向完全图来表示样本点之间的位置关系，并以此为基础构建一个概率转移矩阵来确定未知标签的所属类别。
在本节内容中，我们将继续来学习另外一种同样也是基于图结构的标签传播算法（Label Spreading）[1]，为了区分两者下文分别用LP和LS来进行指代。从本质上来讲，LP和LS这两种算法在思想上并没有太大的差别，都是基于样本点的空间位置来构造得到概率转移矩阵，然后通过概率转移矩阵用已知标签的样本点来确定未知标签样本点的类别。相比较于LP标签传播算法来说，LS算法的改进点表现在两个方面：①使用了标准化的拉普拉斯矩阵来作为概率转移矩阵；②加入了类似于正则化策略的惩罚参数来增加模型的泛化能力。由于LS算法在思想上与LP算法并没有什么本质区别，下面我们就直接来看LS算法的原理部分。
12.3.1 算法原理
设为已知标签的数据样本，其中是样本点对应的标签；同时样本的类别数为，并且假定所有的类别均出现在中。继续，设为不含标签的样本点，其中未知，且通常情况下。此时有，且。
首先，我们同样需要先计算任意两个点之间的权重距离，如式(12.20)所示
从式(12.20)中可以看出，当时，即同一个样本点之间的权重距离为0，这样处理是为了避免样本点自身权重过大的问题。同时可以知道，是一个形状为的对称矩阵。
进一步，根据式(12.21)来构造样本点之间概率转移矩阵
其中为一个对角矩阵，对角线上每个值为权重中对应行所有所有元素的和，即。同时，是标准化后的拉普拉斯矩阵，形状与权重矩阵相同。
接着，再定义一个形状为的标签矩阵，其每一行用于表示每个样本属于各个类别的概率分布。
最后，只需要迭代式(12.22)便可以求解得到未知标签样本的预测结果：
其中，用来平衡模型在迭代过程中对于初始标签矩阵的依赖程度，越大则表示模型更加依赖于样本的分布情况（即式(12.22)中等式右边的第一项），这样可以一定程度上增强模型的泛化能力。
12.3.2 示例代码
在sklearn中，我们可以从sklearn.semi_supervised中来导入标签传播算法LabelSpreading模块。接下来，需要构造半监督学习所需要使用到的训练集，即将部分样本的标签置为-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行是返回最后各个部分的结果。
进一步，便可以导入LabelSpreading进行模型训练和测试，代码如下：
1 def test_label_spreding():
2 x_train, x_test, y_train, y_test, y_mixed = load_data()
3 ls = LabelSpreading(alpha=0.2)
4 ls.fit(x_train, y_mixed)
5 print("Label Spreading")
6 print(f"训练集上的准确率为：{ls.score(x_train, y_train)}")
7 print(f"测试集上的准确率为：{ls.score(x_test, y_test)}")
上述代码运行结束后便会得到类似如下所示的结果：
1 训练集上的准确率为：0.9714285714285714
2 测试集上的准确率为：1.0
上述代码可参见Book/Chapter12/C06_label_spreading.py文件。
在学会LabelSpreading模块的使用后，我们再来对比一下LS和LP算法各自在包含噪音数据上的表现。下面以sklearn中的手写体数据集为例来构造相应的训练和测试样本，代码如下：
1 from sklearn.datasets import load_digits
2 from sklearn.preprocessing import StandardScaler
3
4 def load_data(noise_rate=0.1):
5 n_class = 10
6 x, y = load_digits(n_class=n_class, return_X_y=True)
7 x_train, x_test, y_train, y_test = \
8 train_test_split(x, y, test_size=0.3, random_state=2022)
9 rng = np.random.RandomState(20)
10 random_unlabeled_points = rng.rand(y_train.shape[0]) < 0.8
11 y_mixed = deepcopy(y_train)
12 y_mixed[random_unlabeled_points] = -1
13 for i in range(len(y_mixed)):
14 if y_mixed[i] == -1:
15 continue
16 if rng.random() < noise_rate: # 在训练集中，将有标签的样本中的noise_rate替换为随机标签
17 candidate_ids = np.random.permutation(n_class).tolist()
18 candidate_ids.remove(y_mixed[i])
19 y_mixed[i] = candidate_ids[0]
20 ss = StandardScaler()
21 x_train = ss.fit_transform(x_train)
22 x_test = ss.transform(x_test)
23 return x_train, x_test, y_train, y_test, y_mixed
在上述代码中，第1~2行是导入手写体数据集和特征标准化模块；第5~8行是导入10个类别的数据集，并将其中用作训练集；第9~12行是将训练集中的样本重置为无标签样本；第13~19行则是将训练样本中，有真实标签样本中的noise_rate替换为随机标签（即制造噪音样本）；第20~22行是对训练集和测试集进行标准化处理；第23行是返回最后处理完成的结果。
进一步，可以定义一个函数来对两个模型的结果进行对比，实现代码如下：
1 def comp(p=0.1):
2 x_train, x_test, y_train, y_test, y_mixed = load_data(noise_rate=p)
3 lp = LabelPropagation(max_iter=200)
4 lp.fit(x_train, y_mixed)
5 print("LabelPropagation")
6 print(f"训练集上的准确率为：{lp.score(x_train, y_train)}")
7 print(f"测试集上的准确率为：{lp.score(x_test, y_test)}")
8
9 ls = LabelSpreading(max_iter=200)
10 paras = {'alpha': np.arange(0.01, 1, 0.02)}
11 gs = GridSearchCV(ls, paras, verbose=1, cv=3)
12 gs.fit(x_train, y_mixed)
13 print("LabelSpreading")
14 print('最佳模型:', gs.best_params_ )
15 print(f"训练集上的准确率为：{gs.score(x_train, y_train)}")
16 print(f"测试集上的准确率为：{gs.score(x_test, y_test)}")
17
18 if __name__ == '__main__':
19 comp()
在上述代码中，第2行是载入手写体数据集，并将训练集中有标签样本的设定为随机标签；第3-7行是LP算法分别在训练集和测试集上的表现结果；第9~16行分别是LS算法在训练集和测试集上的结果，同时这里使用了网格搜索与交叉验证来寻找超参数（这部分内容可以参考第5.3.2节内容）。
在上述代码中运行结束后便会得到类似如下所示的结果：
1 LabelPropagation
2 训练集上的准确率为：0.8408910103420844
3 测试集上的准确率为：0.8240740740740741
4 Fitting 3 folds for each of 50 candidates, totalling 150 fits
5 LabelSpreading
6 最佳模型: {'alpha': 0.9899999999999999}
7 训练集上的准确率为：0.8575974542561655
8 测试集上的准确率为：0.8444444444444444
从上述结果可以看出，无论是在训练集上还是测试集上LS算法的表现结果都要明显好于LP算法。同时，经过网格搜索后可知，当时模型的效果最优。上述代码可参见Book/Chapter12/C07_label_spreading_comp.py文件。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！