随着网络和信息技术的快速发展,数据的获取和存储能力极大提高,面对海量的数据,传统的以标记数据为基础的机器学习模型已经远远不能满足数据分析和处理的要求,半监督学习只需少量的已标记数据,同时利用大量的未标记数据进行学习获得较好的分类效果,使机器学习模型从体量巨大、结构繁多的数据中挖掘出潜在的规律。半监督学习模型解决了监督学习模型泛化能力不强和无监督学习模型不精确等问题,成为近年来机器学习领域值得研究的方向之一。基于图的半监督分类是半监督学习中一个重要的分支,充分利用了数据之间的关系,具有坚实的理论基础和明确的目标函数,算法性能良好且易于求解。它主要包含两个步骤:(1)使用已标记和未标记样本构造能够表达数据内在结构的图,(2)利用图推导算法对未标记样本进行标记推断。本文研究的重点是更加有效地探索新的图构造方式和扩展的图推导算法,在此基础上提出新的基于图的半监督分类方法。与此同时,研究大规模数据分类问题,设计适用于大规模数据的基于图的半监督学习方法,扩展基于图的半监督分类算法的应用领域。主要工作概括如下:1.提出了基于概率近邻的图半监督分类算法。该算法对结点之间成为近邻的概率建模,基于l2范数构造目标函数,使得满足局部聚类约束的结点成为近邻的概率增大。结合分类任务特性求解目标函数得到优化的概率近邻矩阵,将该矩阵直接作为后续标签传播的概率转移矩阵。该算法对概率转移矩阵计算的步骤进行了简化,增强了图构造和图推导的关联性,扩大了转移概率矩阵的值的差异性,使该矩阵更加适合后续的分类任务。同时,实现了在给定预设近邻数的前提下,自适应确定近邻个数,通过理论分析和相关实验,证明了该算法具有较低的时间复杂度,能够更好地适应分类任务。2.提出了基于动态构图的半监督分类算法。实现一种无参的选边算法,该算法能够捕捉数据的分布,在数据稠密区域连接更多的边,在数据稀疏区域连接较少的边。在图上边权值计算阶段,综合考虑了数据之间的距离度量和数据的分布,针对图中点的度数差异较大的情况,提出自适应度加权算法。通过将该构图算法和经典的构图算法进行对比实验,在合成方数据集和图像数据集中分类实验证明了提出的方法的有效性。3.提出了结合结构相似性进行构图的方法及一种扩展的标签传播算法,基于此提出融合局部和全局特征的图半监督分类方法。针对现有的图的构造只利用了样本的自身特征,未考虑图的结构相关性这一问题,本文提出了基于链路预测算法的图构造方法,该方法分别采用局部和全局链路预测算法刻画图的局部和全局结构特征,将其融合优化图结构。针对标签传播算法中未反映已标记样本之间的类别信息相关性这一问题,提出了扩展的标签传播算法。实验结果表明了该图半监督分类方法提高了分类的准确率,并通过理论分析和实验结果分析和验证了算法的时间复杂度。4.提出了增强的锚点图半监督分类方法。基于锚点的构图算法扩展了传统基于图的半监督分类方法,扩大了数据处理规模。该算法框架的核心是要构建一个表达二部图关系的Z矩阵,该矩阵的定义直接影响分类结果。本文提出了基于锚点的概率近邻算法对Z矩阵进行构建。与此同时,针对锚点的选择问题,根据不同的应用场景提出了锚点的选取准则,在像素级分类和图像集分类两种不同的应用场景中,设计SLIC和K-Means两种算法选择锚点。该算法框架具有较低的时间复杂度,在大规模像素级分类问题和图像级分类问题两种应用背景下进行实验,证明了该算法框架的有效性和高效性。