Graph-Based Semisupervised Learning 

Culp, M.; Michailidis, G.;
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume: 30 , Issue: 1
Digital Object Identifier: 10.1109/TPAMI.2007.70765 
Publication Year: 2008 , Page(s): 174 - 179

IEEE Journals

Abstract  |  Full Text: PDF (1241 KB)

这篇文章解决所谓的“半监督学习方法”：在一堆样本中，只有一部分已经标记了类别，其他的要预测他们是哪个类的。

本质上说，这还是一种“标签传播“的方法(LABEL PROPAGATION)，所谓的标签传播，

1.先定义样本两两间的关系矩阵S，若相邻则有权值；

2.根据关系矩阵，用迭代的方法，从上次的标签下下次传播：Y ^k=S×Y ^k-1

3.每次传播一次后，把Y ^k中已经标记了类别的标签替换成正确的，再迭代下一次；直到上下两次的标签相差不大为止。

这种方法在“基于图转换的上下文相关的形状相似度”中也用了，只不过这里不是标签，而是到query的距离，并且已知的“标签”实际上只有到query自己的距离（为1）。可见是一种广泛应用的方法。

通过这篇文章，也算是触类旁通了吧。

下面是作者的创新点，作者认为：

要扩散可以，但是离已标记样本比较近的近亲样本，或者嫡系（这里作者用的是到已标记烟本的最近距离小于某阈值的，那些样本），比离自己远的样本靠得住，应该先同化近亲嫡系，再和嫡系一起同化远处的蛮夷！

为了能区分近亲和远夷，作者提出了分化政策：

1. 最高级的是所有已经标记的样本（自己V0）
2. 凡是离自己最近路径小于d1的是一级(V1)；小于d2的是第二级(V2)……直到最后一级，包括所有样本（Vk）
3. 标签扩散的时候，先从V0扩散到V1，然后以V1的为已标记样本向V2扩散……直到没一级都扩散完毕。

方法说完了。作者没用图把这个意思说出来，我帮他画了一个：比较丑，凑活这看吧。

启发:

1. 可以用于分级的距离测度扩散； 

2. 归一化的亲和力矩阵可以用“线性近邻扩散”离的权值来做 

最后说一下作者：美国佬一个。

个人网站http://stat.wvu.edu/~mculp/