机器学习作为智能信息处理的代表性方法在近几十年中取得了飞跃式的发展。然而经典的监督学习需要大量人工标记的数据作为训练样本；由于标记样本往往代价高昂，从而大大提高了监督学习方法的使用成本。因此，人们转而寻求能够使用少量标记样本和大量无标记样本的学习方法，由此产生了对半监督学习问题的广泛关注。　　 早期对半监督学习的研究集中于如何在统一的框架内使用标记样本和无标记样本，如何建立新的模型以及新的学习方法；往往忽视了半监督学习方法的实用性。这具体表现在多数半监督学习方法的计算复杂度过高，而且在实际应用中的性能不稳定。本文的研究目的在于通过改进模型、使用近似算法等手段，提出实用有效的半监督学习算法，使其在精度、鲁棒性、计算复杂性方面达到应用的要求。具体地，本文针对半监督学习中最具代表性的基于图的半监督学习方法进行了全面的研究，并在构图、标记学习算法等方面提出了改进方法。本文的主要内容和贡献包括：　　 1.提出一种针对保持数据局部性的构图方法(LPGC)。将欧式距离作为距离度量，LPGC通过最小化所有的节点间加权距离和来构造图。经过求解一个二次规划问题，LPGC可以同时学习图上的连接关系和边上的权重。由于该二次规划问题的解通常是稀疏的，我们利用这一性质设计了基于切平面方法的优化算法，从而大大提高了效率。经过聚类和分类实验，LGPC方法表现出了比常用的k近邻图和ε近邻图更出色的性能。　　 2.提出一种基于自适应图的直推学习方法(TLAG)，它的最大特点是同时学习样本标记和构造图。这样做的意义在于，TLAG方法可以利用样本的标记信息指导图的构造。TLAG使用一个迭代算法优化目标函数。每轮迭代完成两个操作：第一步，基于当前图和当前的预测标记，学习一张新图；第二步，使用新图，重新预测数据标记。实验表明，TLAG方法相比传统基于图的方法在精度方面有一定的提升。　　 3.提出一种基于最小张成树的快速、鲁棒的直推学习方法(MTC)，并证明最小张成树结构对图参数选取的鲁棒性。MTC方法由两步构成：首先，使用最小张成树近似表示图；然后，通过割最小化准则对张成树进行标定。除去最小张成树构造简单之外，它对于图的构造十分鲁棒。对于ε近邻图和径向基权重函数，我们严格地证明了最小张成树的连接结构对于ε的选取具有不变性。更重要地，基于树的最小割标记算法具有线性的时间和空间复杂度，使MTC方法非常适宜在大规模问题中使用。大量的实验表明，MTC方法在鲁棒性和速度方面相对传统方法有明显改善。　　 4.在半监督学习中使用低维嵌入假设，提出子空间正则化方法以及基于子空间正则化的半监督学习算法。方法的出发点在于：通过将高维数据投影到低维空间，缓解了维度灾难的影响，使分类器的训练更为简单。具体的，我们提出了一个优化准则用于同时学习降维子空间和定义在子空间上的分类器。优化目标含有两个部分：数据拟合项用于评价不同类别的标记样本在降维子空间中的可分程度；而正则项用于评价在降维过程中数据信息的损失程度。相比使用平滑假设的基于图的方法，新方法在处理图同类别相互重叠等情况时具有明显优势。