在传统机器学习中,学习器需要对大量标记数据进行学习从而建立模型来对未标记数据或未见数据进行预测。而实际应用中,海量的未标记数据是容易获取的,而对其进行准确标记往往较为困难。因此,人们尝试将大量的未标记数据加入到有限的标记数据中一起进行训练学习,期望能够改进学习性能,于是产生了半监督学习,旨在解决监督学习模型泛化能力不强、非监督学习的模型不精确等问题。其中,基于图的半监督学习算法因其良好的性能和易于求解的优点得到了广泛关注。基于图的半监督学习算法主要包括两个步骤:1)在输入数据上构造图;2)在构造的图上运用合适的学习算法推断图中未标记样本。本文主要针对这两个步骤,提出了两种图构造算法和两种半监督嵌入算法。论文主要工作如下:1.提出了一种基于数据自表示和拉普拉斯平滑约束的图构造算法(SRLS)及其多个变种。研究表明数据表示所得到的表示系数反映了数据之间的相似度关系,可作为一种相似度衡量。这种相似度衡量可用于图中数据之间连接边的权值。而数据自表示所得到的系数表示矩阵的每列可看成对应原数据一种新的表示,因此本文认为这种新的表示数据应当具备原始数据的某些特点。比如原始数据中两个较为接近的数据点所对应的新表示数据点之间应当具有较高相似度,这种约束关系在称为拉普拉斯平滑约束。SRLS图构造算法在l2范数最小化的数据自表示算法基础上,引入拉普拉斯平滑约束,并以此来构造图。由于l2范数最小化的数据自表示算法得到的系数表示矩阵往往是稠密的,为增加系数表示矩阵的稀疏度,本文又提出了一种基于SRLS图的两步算法。此外,分别将原线性空间扩展到希尔伯特空间和列生成空间,本文提出了两种核SRLS算法。核SRLS算法是通过迭代实现的,深入研究发现其优化问题在一定约束条件下可直接得到最优解,于是提出了一种约束核SRLS算法。2.提出了一种拉普拉斯平滑约束稀疏图算法(SGLS)及其多个变种。SGLS算法在稀疏图的基础上引入拉普拉斯平滑约束来构造图。稀疏图通过稀疏数据自表示得到,其核心是稀疏表示算法,通过l1范数优化问题得到稀疏表示系数。所提出的SGLS算法继承了稀疏图的许多特性,比如系数表示矩阵稀疏度高、对噪声鲁棒等。此外,本文也提出了核SGLS算法。同时,核SGLS算法所解决的优化问题在一定约束条件下可直接得到最优解,提出了一种约束核SGLS算法。3.提出了一种约束稀疏保持嵌入算法(CSPE)。稀疏保持投影算法(SPP)是一种经典的非监督嵌入算法,其通过在嵌入空间中保持原始数据空间中数据之间的稀疏表示结构。受其启发,本文提出了一种新的半监督嵌入算法,称其为带约束的稀疏保持嵌入(CSPE)。CSPE算法在嵌入空间中保持原有稀疏表示结构的同时,利用已标记样本信息在嵌入空间中聚集同类样本点。4.提出了一种弹性带约束稀疏保持嵌入算法(FCSPE)。所提出的CSPE算法是非线性直推式的算法,将训练集数据样本嵌入到一个低维空间中,无法直接对新进样本进行投影。FCSPE算法能在求解准则函数的同时得到一个近似的线性投影,克服了CSPE算法无法处理新进样本的缺点。