韩灵珊

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

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

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

本文提出一种无参数、自适应的被动寻找近邻的构图方法来尝试应用到标签传播算法中，对算法进行重新构图，再通过计算图中节点间的权值得到其邻接矩阵，从而使标签平滑的在整个图上传播，直到达到一个稳定状态。……