在许多机器学习的实际任务中,获得足够的有标记样本是非常昂贵和费时的,而大量的未标记样本容易获得。在少量有标记样本上使用监督式学习方法,训练出的学习器泛化能力不强,容易出现过拟合现象。另一方面,当使用无监督式学习方法时,会极大地浪费有标记样本包含的标签信息。半监督学习能够综合利用有标记样本和无标记样本来提高学习器的泛化能力,已经得到了广泛的研究与应用。基于图的半监督分类算法因为分类性能好、目标函数是凸函数、求解容易等优势获得了更多的关注。图构造是基于图的半监督分类的重要前提工作,图是决定基于图的半监督分类性能的关键因素之一。然而,如何构造一个能够真实地反映样本分布的图是相当困难的。稀疏表示最近被应用于图构造,基于稀疏表示构造的图对高维样本中的噪声特征表现鲁棒。但是,传统稀疏表示构造图采用全部样本作为字典集,时间花费大。此外,流形假设是基于图的半监督分类的基本假设之一。它的定义是:同一个局部邻域内的样本具有相似的性质,因此其标记也应该相似。然而,当两个样本相互靠近,跨越不同类别的边界时,流形假设可能不总适用。结果,仅仅基于流形假设的分类方法可能误分边界样本。针对基于图的半监督分类算法存在的上述问题,本文在现有研究成果基础上,提出三种基于图的半监督分类算法。论文的具体工作如下:(1)提出一种基于局部稀疏表示的半监督分类算法(SSC-LSR)。SSC-LSR首先使用样本的k近邻作为字典集去计算每个样本的稀疏重构系数,而不是将所有可用样本作为字典集,再基于这些稀疏重构系数构造一个局部稀疏表示图。最后在这个图上训练广泛使用的高斯随机场与和谐函数(GFHF)分类器,预测未标记样本的标记。在两个公共人脸数据集上的实验结果表明,SSC-LSR分类精度比传统方法高。(2)提出一种基于局部子空间稀疏表示的半监督分类算法(SSC-LSSR)。SSC-LSSR首先把样本分成若干个随机子空间,在每个随机子空间上构造局部稀疏表示图。然后,在构造的图上训练一个基于图的半监督分类器。最后把这些分类器通过投票策略集成一个分类器,预测未标记样本或新来样本的标记。在两个公共人脸数据集上的实验结果表明,SSC-LSSR分类精度比相关方法高,并且时间花费较少。(3)提出一种基于判别性正则化的半监督分类算法(SSCDR)。SSCDR首先分别构造一个k近邻图来捕捉样本的局部流形结构,和一个判别图来嵌入约束聚类学习的判别性信息。然后将两个图纳入设计的判别性正则化框架,预测未标记样本或新来样本的标记。在UCI和人脸数据集上的实验结果表明,SSCDR分类精度比相关方法高,并且对输入参数k鲁棒。