基于图的学习方法是二十一世纪初兴起的机器学习方法,经过近十年的发展,它在模式识别、数据挖掘和信息检索等领域已经有了一些有价值的应用。基于图的学习方法用一个图来表示数据的分布信息和关系信息,这意味着当今人们数据思维的一种转变,即更加注重数据间的相关关系,而非难以捉摸的因果关系。在众多基于图的学习方法中,本文以图划分准则为出发点,形成基于图的学习方法框架。现有的图划分准则下基于图的学习算法虽然能够在一定程度上解决各自领域中的任务,但是缺乏统一的学习框架。本文从理论分析入手,在数学上建立图划分准则下基于图的学习框架,并从统一的角度理解图划分准则下基于图的学习方法。主要工作是:在图划分准则下,通过基于图的学习方法研究机器学习中的三类基本学习问题,即无监督、半监督和监督学习问题。同时对基于图的学习进行了拓展,即考虑协同正则化、多重正则化和路径传播,以丰富基于图的学习方法研究内容。具体创新点及取得的研究成果包括:(1)提出了一种图划分准则下基于图的学习框架模型。总结了基于图的学习与两种机器学习中的基本假设的关系,分析归纳了不同图划分原问题的构成要素,通过更加恰当地放松图划分原问题(NP难问题)的约束条件,提出了一种合理的图划分准则下基于图的学习框架模型。该框架模型支持多种图划分准则,在约束条件的放松上选择严格保持非负性约束,并注重正交性约束和离散性约束。框架模型具有良好的可扩展性并可以衍生出基于图的无监督学习、半监督学习、监督学习、协同正则化学习和多重正则化学习等多种学习方法,这部分工作为图划分准则下基于图的学习建立了理论基础。(2)提出了一种图划分准则下基于图的无监督学习方法。在第二章框架模型的基础之上,通过实现约束条件的放松要求,提出了一种有效的图划分准则下基于图的无监督学习方法。该方法在约束条件中仅保留严格的非负性约束,并通过设计Logdet正则化项将解的正交性约束和离散性约束融入到目标函数中,最后实现对正交性约束和离散性约束的近似逼近。设计了相应的求解算法,分析了算法的计算复杂度,并证明了该算法的收敛性,实验验证了算法的无监督聚类效果。(3)提出了一种图划分准则下基于图的半监督学习方法。在第二章框架模型和第三章学习方法的基础之上,通过设计先验信息的融入方式,提出了一种有效的图划分准则下基于图的半监督学习方法。面向半监督分类问题和半监督聚类问题,共提出四种先验信息的融入方式,改善了传统方法融入先验信息受限制和低效的问题。回顾了以往的相关研究工作,设计了相应的求解算法,分析了算法的计算复杂度并展示了算法的收敛性,最后实验验证了算法的半监督分类和聚类效果。(4)提出了一种图划分准则下基于图的监督学习方法。分析了图划分准则下基于图的监督学习的关键步骤,提出一种有效的基于图的监督学习方法,实现对不同类别样本的等距投影,改进了传统的基于图的监督学习方法中不同类别样本投影后间隔可能无限大的弱点。具体地,通过设计不同的多变量标签矩阵,将岭回归拓展为一种基于图的监督学习方法。进一步考虑了投影中维度的平滑性和投影矩阵的稀疏性,提出了稀疏平滑岭回归方法,设计了相应的求解算法,实验验证了算法的监督分类效果。(5)提出了一种图划分准则下基于图的协同正则化学习方法。在第二章框架模型和第三章学习方法的基础之上,通过设计多种数据视图的融合方式,提出了一种有效的图划分准则下基于图的协同正则化学习方法,该方法提升了基于图的学习方法学习多视图的能力。面向基于图的无监督学习或半监督学习问题,提出了六种多视图融合的方式,丰富了基于图的协同正则化学习方法。设计了相应的求解算法,实验验证了算法的无监督聚类效果。(6)提出了一种图划分准则下基于图的多重正则化学习方法。基于非负矩阵分解天然非负性要求的观察,将非负矩阵分解作为多重正则化项融入到第二章框架模型中,提出一种有效的图划分准则下基于图的多重正则化学习方法。该方法提升了基于图的学习方法在数据表示上的能力,并且可以得到无(半)监督学习中的显式映射。回顾了以往的相关研究工作,设计了相应的求解算法,实验验证了算法在无监督聚类、半监督分类和和半监督聚类上的效果。(7)提出了一种基于图的面向公共视频场景聚集性度量和分析的学习方法。面向热点且难度较大的公共视频场景聚集性度量和分析问题,首先定义了聚集性运动的主题,然后利用路径传播和指数生成函数拓展了基于图的学习方法研究,提出了一种新的计算场景聚集度的学习方法,并在场景划分中检验了图划分准则下基于图的无监督学习方法的效果。场景划分为进一步理解场景内容打下基础,为下一步聚集性运动模式分类和异常检测提供了有效的高层特征。该部分内容对国家公共安全具有一定的意义,实验展示了该方法在聚集性度量和聚集性运动划分上的效果。