韩灵珊

摘要：提出一种基于自然近邻搜索的构图方法，通过自然近邻图得到图中节点边的权值及邻接矩阵，并应用于标签传播算法中。构图过程中对最近邻居的搜索过程是一种自适应的无参数过程，从而减少了标签传播算法的参数个数。UCI数据集的实验结果表明，基于自然近邻图的标签传播算法能够提高分类准确率，是一种较好的分类方法。

关键字：半监督学习；标签传播算法；自然近邻；

近年来，半监督学习[1]在机器学习理论广泛应用的背景下得到了长足的发展[2-3]，它集合了监督学习和无监督学习，利用有标签样本和大量含有有效信息的未标签样本进行训练和分类。基于图的半监督学习[4-7]依靠强大的数学理论支撑，依据图方法很好的刻画了数据自身的结构特征，以方法的直观性和良好的分类性能得到了研究学者们的高度关注。标签传播算法[8]是基于图的半监督学习算法中最具代表性的算法之一。它将标签数据和未标签数据表示成图模型中的节点，根据数据间的距离关系构建连接节点之间的边的权重，进而从图谱的角度出发设计算法对节点进行分类。可以说，对于基于图的半监督学习而言，图的构造对于算法性能有着较大的影响。常用的图包括全连接图和k近邻图[9]及基于稀疏分解[10]的构图方法。

本文提出一种无参数、自适应的被动寻找近邻的构图方法来尝试应用到标签传播算法中，对算法进行重新构图，再通过计算图中节点间的权值得到其邻接矩阵，从而使标签平滑的在整个图上传播，直到达到一个稳定状态。通过实验结果证明本文提出的构图方法是一种有效的构图方法，算法不仅收敛速度加快并且减少了事先需要确定的参数的个数，使用简单。

1.自然最近邻

1.1自然最近邻居

最近邻居概念在早先就被提出，并广泛用于机器学习和模式识别等领域。其中最著名的两个概念是K-最近邻和-最近邻。K-最近邻的思想是对于给定的数据集中的每一个数据对象找出K个与其相似度最大或者说距离最小的数据对象，其中K是事先人为给出的参数。而-最近邻的思想是对于给定的一个数据集，找出每个数据对象在其扫面半径内的近邻个数，其中同样为人为给定的扫面半径参数，使用这种方法得到的数据对象在扫面半径内的最近邻的个数有可能不同。从一方面而言，由于K和都是人为给定的参数而不是结合数据对象自身的特点进行搜索最近邻居，导致后续算法有可能因为参数设置不同而出现分类效果偏差较大；从另外一方面而言，K-最近邻和-最近邻对于数据密度非常敏感，当数据分布差异较大，在数据分布稀疏区域可能出现由于参数设置不当而造成搜索最近邻居有大的偏差。自然最近邻[5]的概念不同于传统的最近邻居概念，它是一种新的邻居概念。寻找自然最近邻的过程不需要设置参数，是一种无尺度，被动寻找近邻的过程。这也是与寻找K-最近邻和-最近邻过程方法最大的不同点。

自然最近邻[11]的主要思想是对于数据集中稠密区域的数据对象有较多的最近邻居或者说在稠密区域的数据对象有较高的能量，而在稀疏区域中的数据对象则拥有较少的最近邻居，即有较低的能量，对于数据对象中最离群的数据而言，只有一个最近邻居也就是说这个最离群点具有最低能量。自然最近邻的搜索过程实际上也可以看作是一种特殊的K-最近邻搜索过程，它为每个点赋予了不同的K值并且保证每个数据对象至少有一个最近邻，不同点在于自然最近邻的搜索过程是一种自适应的、被动搜索最近邻居的过程。

定义1.1 自然最近邻居（3N邻居） 在给定的数据集中，对于数据对象X，若有数据对象Y认为X是其最近邻居，并且对于数据集中最离群的数据对象Z而言，有一个数据对象认为Z是其最近邻居，那么我们称数据对象Y为数据对象X的自然最近邻居。

定义1.2 自然特征域（supk） 由公式1.1 自适应得到的supk的值称为数据集的自然特征域。

supk= （1.1）

其中表示点y的第r最近邻域。

由公式1.1可以得到一个简单的计算方法来搜索数据集的自然最近邻居，算法描述如下：

输入数据集X

1、r=1，flag=0，before=size of X， after=0

2、

3、while flag=0

4、If before-after==0 then flag=1 else

5、For

5.1 計算i的第r个最近邻居

5.2

5.3

Endfor

If

before=after

Endif

6、r=r+1，after=the number of X that

7、Endif

8、Endwhile

9、

算法1 确定supk的值，并且计算出每个数据点的3N邻域最近邻域。

1.2自然最近邻域图

根据算法1可知，自然近邻的选择过程是自动的一个过程，可以搜索到数据集中每个数据对象的自然最近邻，并产生出每个数据点对应的最近邻居数据集，因而可以根据数据点的连接来构造自然最近邻域图。

自然最近邻域图就是连接数据集中每个自然最近邻居所形成的自适应邻域图，并且图中任意节点i和节点j之间存在一条边，当且仅当i是j的自然邻居或j是i的自然邻居。

2.基于自然最近邻的标签传播算法

2.1概念定义

标签传播算法的主要思想是使每个样本的标签信息迭代传递给它的近邻样本，直到达到全局稳定的状态。我们假设样本数据集为，其中：n表示样本的总数；表示所有样本的类别标签集合。表示某一样本的类别，c表示样本的总的类别个数。已标记样本为，其类标为，；未标记样本集合为，即X中剩下n-l个样本为未标签样本，且。期望学得函数f： X→Y可以准确地对示例x预测其标记y。

将基于自然最近邻的构图方法用于标签传播算法中，实际上是使用自然最近邻的搜索方法找到数据集中每个样本点的自然最近邻，并通过构造自然最近邻域图，将样本点作为图当中的节点，图中节点之间的边的权值表示样本与其自然最近邻之间的相似度。

与经典的标签传播算法一样，定义一个的非负矩阵F表示每个样本的标签概率矩阵，用来表示样本数据点属于某一标签类别的概率；例如，对于任意样本数据其对应的表示数据样本属于第类标签的概率，最终样本数据的预测标签信息选择使得样本数据属于第类的概率最大的标签类别；即。

初始状态阶段，若为已标记样本，即，则F的第j列元素的值定义为：

并将其记为；若为未标记样本，即，初始设定时将其每一列元素的值设置为-1，记为。

2.2算法描述

基于自然最近邻的标签传播算法的步骤描述如下：

1、根据算法1计算每个数据样本的最近邻居数据集，并构造自然最近邻域图。

2、计算邻接矩阵W，即

3、计算图的正则化拉普拉斯矩阵，其中D为对角矩阵，其对角线元素。

4、根据更新样本点的标签概率：

4.1

4.2 t=t+1，

4.3 令

5、重复步骤4.2和4.3，直到F收敛到确定的值，循环终止。

6、为未标签样本进行标签标记

2.3收敛性证明

为了证明算法最终能够收敛到一个确定的值，将图的拉普拉斯矩阵S分解为四个子矩阵，即

则有

根据可知，

当时，可以表示为

由于S的特征值区间为，所以当时有

因此可得出

由上式可以证明算法能够收敛到一个唯一的确定的值，同时也可以看出，在执行算法时，可不通过循环直接计算得出标签概率矩阵，并且其结果不依赖于的取值。

3、实验及其分析

为了测试算法的分类准确率，选择表1所示的5个UCI数据集作为实验对象。实验采用的计算机的硬件配置如下：i3 CPU主频3.5GHz，内存8GB，采用Python2.7.4编程软件。

分别采用监督学习K近邻（KNN）、基于K近邻图的标签传播算法和基于自然近邻图的标签传播算法解决这5个数据集的分类问题；监督学习K近邻的参数设为1；同时，各算法的共有参数均设为一致。具体对于每一个数据集中参数取值情况见表2。

对于每个实验数据集，采用随机抽取L个数据组成已标记样本数据集，并且规定已标签样本数据集中每一类标签已标签样本的个数相同。剩余的N-L个样本数据组成未标记样本数据集。以Iris数据集为例，由于该数据集中样本被分为三个类别，所以在选择已标签样本时，已标签样本的个数分别取3，6，9，12，15……。独立重复上述样本选取过程20次作为随机实验的输入样本数据集，并将这20次独立重复试验结果的平均值作为评价算法效果的最终依据。并以未标记样本最终分类的准确率作为算法有效性的衡量标准。各数据集的实验结果如图1所示。

从图中可以看出，当已标记数据较少时，标签传播算法的性能均优于K近邻算法，当已标记数据的数量增大时，标签传播算法和K近邻算法的准确性之间的差异逐渐减小；而基于自然近邻图的标签传播算法的分类准确率略优于基于K近邻图的标签传播算法。因此可以得到的结论是：当已标记数据的数量较少时，标签传播算法是一种有效的分类方法，并且基于自然近邻图的标签传播算法的算法性能略高于基于K近邻图的标签传播算法效率。

4、结论

标签传播算法是一种典型的半监督学习算法，将自然近邻选择的方法运用到标签传播算法的过程中，可以减少参数对算法分类准确率的影响，提高算法的收敛速度，是一种较有效的半监督学习算法。

参考文献

[1] Chapelle O， Scholkopf B. Semi-supervised learning[M].Cambridge： MIT Press， 2006： 193-196

[2] Nigam K，Mccallum A，Thrun S，et al.Text classification from labeled and unlabeled documents using EM[J].Machine Learning，2000，39（2/3）：103-134

[3] Mailard O A，Vayatis N.Complexity versus agreement for many views：Co-regularization for multi-view semi-supervised learning[J].Lecture Notes in Computer Science，2009，5809：232-246

[4] Blum A，Chawla S.Learning from labeled and unlabeled data using graph mincuts.Proceedings of the 18th International Conference on Machine Learning.Williamstorn，USA；Morgan Kaufmann Publisher，2001，19-26

[5] Zhu X J，Ghahramani Z，Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[C]，Proc of the 20th Int Conf on Machine Learning.Washington：AAAI Press，2003：912-919

[6] Fanhua Shang，L.C. Jiao，Yuanyuan Liu，Hanghang Tong. Semi-supervised learning with nuclear norm regularization[J]. Pattern Recognition . 2013 （8）

[7] Zhu X J，Ghahramani Z，Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[C]，Proc of the 20th Int Conf on Machine Learning.Washington：AAAI Press，2003：912-919

[8] Zhou D Y，Bousquet O，Lal T N，et al. Learning with local and global consistency[C].Proc of Advances in Neural Information Processing System.Massachusetts：MIT press，2003：321-328.

[9] 王雪松，張晓丽等，一种简洁局部全局一致性学习，控制与决策[J]，2011：26（11）1726-1734

[10] Cheng H， Liu Z C， Yang L. Sparsity induced similarity measure for label propagation. In： Proceedings of the 12th IEEE International Conference on Computer Vision. Kyoto，Japan： IEEE， 2009. 317？324

[11] 邹咸林；自然最近邻居在高维数据结构学习中的应用[D]；重庆大学；2011年