基于局部聚类自适应线性近邻传递分类算法.doc

基于局部聚类自适应线性近邻传递分类算法 　　摘要：针对线性近邻传递（LNP）分类算法中，由于图像过大时计算复杂度高，以及近邻数目选择不当导致图像分类结果不精确的问题，提出了基于局部聚类的自适应LNP分类算法。该方法对LNP分类算法的改进主要体现在两方面，首先运用quickshift进行局部聚类，得到点簇集，以此点簇集作为建图节点，达到缩小矩阵规模的目的；其次，采用测地距离和欧氏距离之间的关系来动态确定每个点的近邻数。实验结果表明，所提方法在得到较好的分类结果的同时，也极大地缩短了运行时间，提高了效率。 　　关键词： 半监督； 图模型； 局部聚类； 自适应； 图像分类 　　中图分类号： TP391.41 文献标志码： A 　　0引言 　　图像分类是图像处理的一个非常重要的研究方向。目前在机器学习[1]领域有很多方法来解决图像分类问题，半监督学习（SemiSupervisedLearning，SSL）[2-3]是其中重要的一种。半监督学习通过标签数据和未知标签数据结合学习，利用大量的未标记样本和少量的标记样本来建立分类器，通过利用未标记样本中隐藏的数据信息来提高分类器性能 于图的半监督学习是目前半监督学习领域的一个主流方向。在当今研究领域中，已有很多方法[4-7]，并在图像分类问题上取得了一定的效果。这类方法具有直观、可解释性，且分类能力比监督的分类方法强。该类算法建立在图论基础上[8-13]，在图像分类中，基于图的半监督方法以图像中的像素点作为节点，像素点之间的空间距离作为边，将图像映射为一个无向加权图，通过构造图上目标函数来实现分类。线性近邻传递（LinearNeighborhoodPropagation，LNP）[5]作为基于图的半监督方法中的一种，计算复杂度为O（n3），其中n为样本个数。图像的大小直接影响计算复杂度的高低；同时，近邻参数k的选择是否恰当将会直接影响最终分类结果。近年来对LNP算法的改进大多都集中图的构造上，如何充分利用近邻信息来提高分类效果成为大家共同关注的问题[14-16]。本文则在LNP中引入局部聚类和自适应近邻选取思想来解决以上问题。局部聚类的目的是将相同类别的样本聚到一起，形成点簇集，从而大大减少建图时的顶点数目，带来计算上的优势。同时，对于每一个节点的近邻数目，采用测地距离和欧氏距离之间的关系来动态确定，达到提高分类精度的目的。最后通过LNP算法实现图像分类。实验结果验证了此方法的有效性和可行性，适于解决较大且复杂的图像分类问题。 　　从表1可看出：随着图像的增大，LNP分类算法运行时间将大大增加；虽然本文方法也是如此，但相对LNP来说，能够大大缩短运行时间，同时在分类结果上有更好的表现。从表1中可以发现，本文方法比LNP方法在正确率上均有所提高，horse230、horse252正确率提高比较大，而horse109、horse263的正确率上提高较小。这是因为在horse230、horse252中目标内部颜色信息、相似区域跳跃点较多，在手工标记样本时，并不能完全涵盖所有颜色信息。LNP分类时，在这些区域并不能取得很好的效果，而本文方法局部聚类时，得到至多包含一种标记点簇的点簇集，并且将其标记信息扩散到整个点簇内，形成建图的顶点集，这样能够去除跳跃点，保护目标内在结构信息。并且近邻参数k的自适应选择，能够更好地保护边缘，因此取得了更好的分类效果。而horse109、horse263图像简单，颜色信息较少，且目标与背景差异明显，因此正确率提高较小。使用quickshift局部聚类大大减少了建图时的顶点数目，降低了矩阵规模，在矩阵相乘求逆等运算中用时更少，提高了运算效率；同时，k的自适应选择，能够很好地保护图像内在结构和边缘，去除相邻相似区域的一些跳跃点，提高了分类正确率。这在图1中有更为直观的体现。 　　图1表示的是分别运用LNP方法及本文方法对表1中对应的8幅图像进行分类的结果。从图1可看出，本文方法在目标内部区域基本上可以正确分类，而边缘、背景与目标外观相似的地方会有错分，而LNP方法在目标内部、边缘以及背景均会出现明显的错分。特别地，在目标内部颜色信息较多、背景与目标相似信息较多的情况下，本文方法在边缘、背景以及目标内部均有更好的分类结果。因为本文方法在局部聚类时，得到的点簇作为建图时的顶点，这样能够去除局部区域的跳跃点，减少局部颜色信息；同时自适应选择近邻参数k，更好地保护图像内在结构以及边缘，得到更好的分类结果。这在图1中（d）和（f）的对比中可以清楚地看到。因此，实验结果表明，基于局部聚类的自适应LNP分类算法在分类正确率和运行时间上，均要明显优于LNP分类算法 于局部聚类的自适应LNP分类算法先进行局部聚类，形成点簇集，以点簇集为节点建立图模型，减小矩阵规模，大大降低