基于局部聚类的自适应线性近邻传递分类算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于局部聚类的自适应线性近邻传递分类算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对线性近邻传递（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分类算法先进行局部聚类，形成点簇集，以点簇集为节点建立图模型，减小矩阵规模，大大降低运算时间。同时采用邻域信息来重构权值，更好地保护图像内部结构，并且使其自适应选择近邻数目；能够更好地保护边缘，达到提高分类效果的目的。
5结语
本文提出了一种基于局部聚类的自适应LNP图像分类方法。该方法首先通过局部quickshift算法将图像进行局部聚类，形成点簇集，然后以点簇集为节点建立图模型。通过将整个图模型裁剪成一个个局部线性小区域，而后将所有的局部线性区域重组来近似整个图模型，邻域数目的选择通过自适应算法实现。实验结果表明，与LNP分类算法相比，本文方法降低了计算复杂度，并且很好地保留了图像的内在结构信息以及边缘，使用更少的时间得到了较好的分类结果。
参考文献：
[1]ZHOUZH，WANGJ.Machinelearningandapplication[M].Beijing：TsinghuaUniversityPress，2007.（周志华，王珏.机器学习及其应用[M].北京：清华大学出版社，2007.）
[2]CHAPELLEO，SCHOLKOPFB，ZIENA.Semisupervisedlearning[M].Cambridge：TheMITPress，2006：237-273.
[3]ZHUXJ.Semisupervisedlearningliteraturesurvey[EB/OL].[20120805].http：//pages.cs.wisc.edu/～jerryzhu/pub/ssl_survey.pdf.
[4]ZHOUD，BOUSQUETO，LALTN，etal.Learningwithlocalandglobalconsistency[C]//Proceedingsofthe2003AdvancesinNeuralInformationProcessingSystems.Cambridge，MA：MITPress，2004：321-328.
[5]WANGF，ZHANGC.Labelpropagationthroughlinearneighborhoods[J].IEEETransactionsonKnowledgeandDataEngineering，2008，20（1）：55-67.
[6]BELKINM，NIYOGIP，SINDHWANIV.Manifoldregularization：ageometricframeworkforlearningfromlabeledandunlabeledexamples[J].JournalofMachineLearningResearch，2006，7（11）：2399-2434.
[7]ZHUXJ，GHAHARMANIZ，LAFFERTYJ.SemisupervisedlearningusingGaussianfieldsandharmonicfunctions[C]//Proceedingsofthe20thInternationalConferenceonMachineLearning.Madison：AAAIPress，2003：912-919.
[8]YONGL.Manifoldregularizedmultitasklearningforsemisupervisedmultilabelimageclassification[J].IEEETransactionsonImageProcessing，2013，22（2）：523-536.
[9]BIJRALAS，RATLIFFN，SREBRON.Semisupervisedlearningwithdensitybaseddistances[EB/OL].[20130101].http：///abs/1202.3702.
[10]GONGYC，CHENCL.Graphbasedsemisupervisedlearningwithmanifoldpreprocessingforimageclassification[C]//SMC2008：Proceedingsofthe2008IEEEInternationalConferenceonSystems，ManandCybernetics.Piscataway，NJ：IEEEPress，2008：391-395.
[11]LIUW，HEJF，CHANGSF.Largegraphconstructionforscalablesemisupervisedlearning[C]//Proceedingsofthe27thInternationalConferenceonMachineLearning.Haifa，Israel：[s.n.]，2010：679-686.
[12]ZHUXJ.Semisupervisedlearningwithgraphs[D].Pittsburgh：CarnegieMellonUniversity，LanguageTechnologiesInstitute，SchoolofComputerScience，2005.
[13]GOMEZCHOVAL.Meanmapkernelmethodsforsemisupervisedcloudclassification[J].IEEETransactionsonGeoscienceandRemoteSensing，2010，48（1）：207-220.
[14]ZHANHR.Researchongraphbasedsemisupervisedlearning[D].Wuhan：HuazhongUniversityofScienceandTechnology，2009.
[15]WULX.Researchandimplementationoftimeseriesclassificationbasedonsemisupervisedlearning[D].Dalian：DalianUniversityofTechnology，2011.
[16]XUPP.LNPbasedsemisupervisedlearningalgorithms[D].Xian：XidianUniversity，2009.
[17]VEDALDIA，SOATTOS.Quickshiftandkernelmethodsformodeseeking[J].ECCV2008：Proceedingsofthe10thEuropeanConferenceonComputerVision，Marseille，LNCS5305.Berlin：SpringerVerlag，2008：705-718.
[18]COMANICIUD，MEERP，MEMBERS.Meanshift：arobustapproachtowardfeaturespaceanalysis[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2002，24（5）：603-619.
[19]HAOJB.Researchongraphbasedsemisupervisedlearningmodelandclassifierdesign[D].Hefei：UniversityofScienceandTechnologyofChina，2009.
[20]TENENBAUMJB，deSILVAV，LANGFORDJC.Aglobalgeometricframeworkfornonlineardimensionalityreduction[J].Science，2000，290（5500）：2319-2323.
[21]BELKINM，NIYOGIP.Laplacianeigenmapsandspectraltechniquesforembeddingandclustering[C]//Proceedingsofthe2002AdvancesinNeuralInformationProcessingSystems.Cambridge，MA：MITPress，2001：585-591.
[22]GOLUBGH，vanLOANCF.Matrixcomputations[M].3rded.London：TheJohnsHopkinsUniversityPress，1996.
[23]TAOWB，JINH，ZHANGYM.Colorimagesegmentationbasedonmeanshiftandnormalizedcuts[J].IEEETransactionsonSystems，Man，andCybernetics，PartB：Cybernetics，2007，37（5）：1382-1389.
[24]ZHOUD，BOUSQUETO，LALTN，etal.Learningwithlocalandglobalconsistency[C]//Proceedingsofthe2003AdvancesinNeuralInformationProcessingSystems.Cambridge，MA：MITPress，2004：321-328.