基于图的半监督学习算法研究

《基于图的半监督学习算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学硕士学位论文基于图的半监督学习算法研究姓名：占惠融申请学位级别：硕士专业：计算机应用技术指导教师：宋恩民20090528华中科技大学硕士学位论文摘要半监督学习是当前机器学习研究中最受关注的问题之一。半监督学习只利用少量的标记数据和大量未标记数据进行学习。在减少人工标注代价和提高学习器性能方面，半监督学习具有较突出的优势，其研究成果已逐渐用于解决实际问题。图方法是半监督学习中研究比较多的一种方法，其理论基础比较健全。图方法可以很好的刻画数据自身的结构特征，而不需带有某种分布的偏向，该方法直观、灵活，但是其计算量很大，成为实际应用中

2、的屏障。对基于图的半监督学习方法进行了系统的分析研究，特别针对局部和全局一致性学习方法（LearningfromLocalandGlobalConsistency，LLGC）中计算量大的问题进行了深入分析，提出了基于quickshift的图构建方法。首先，按照quickshift方法对原始数据进行局部范围的聚类；然后，在聚类后的簇上构造一个新的无向连通图；最后，在新图上利用LLGC方法进行分类。由于quickshift方法以非参数密度估计理论为基础，具有保持原始数据分布状况的良好属性，因此，对数据进行聚类，并不会降低图方法的准确性。另一方面

3、，聚类后簇的数目较样本点的数目少很多，即新图的节点数目远远少于原始图的节点数目，从而大大提升了LLGC分类的运算速度。对茶壶图像、手写数字和英文字符3类实用数据分别进行了实验，结果表明，改进后的方法不仅在分类准确度方面与LLGC方法相当，而且在计算速度方面，要明显优于LLGC方法。关键字：半监督学习，非参数估计，密度估计，聚类，图方法I华中科技大学硕士学位论文AbstractSemi-supervisedlearning(SSL)hasdrawnwideattentioninthemachinelearningfields.Itcombin

4、esinformationfrombothlargenumberofunlabeleddataandlimitedamountoflabeleddata.AsSSLhasanadvantageinimprovingtheclassifier’sperformanceandreducingthecostofartificialannotation,ithasbeengraduallyappliedtosolverealworldproblems.Thegraph-basedmethod,whichhasperfecttheoreticalba

5、sis,hasbeenthemostpopularmethodsinSSL.Thegraph-basedmethodisverygoodatdepictingtheintrinsicstructuralofdata,andhaslittledependenceondistributionassumption.It’sintuitiveandflexible.Butitscomputationalcomplexityistoohighformanyrealworldproblems.ThispaperfirstreviewstheSSLsch

6、emes,especiallyonthegraph-basedmethods.Thenwediscusstheproblemofhighcomputationalcomplexityingraph-basedmethods.Inordertofixtheproblem,weproposeanewmethodforgraphconstructionwhichusesquickshifttoclusterthedatalocallyfirstandthenconstructsagraphontheclusters.Asquickshiftisa

7、non-parametricdensityestimationmethod,whichcankeeptheoriginaldatadistribution,itwon’treducetheaccuracyofthegraph-basedmethod.Ontheotherhand,thenumberofclustersisfarlessthanoforiginalinstances,thereforethenodesofgrapharereducedandthecomputationaltimeisimprovedgreatly.Inthis

8、paper,wedidexperimentsonthreerealworldproblems:teapotimage,handwrittennumberclassificatio