随着信息技术的快速发展，各个行业收集到的数据越来越多，如何有效地从这些数据中挖掘出有帮助作用的信息，可以极大地促进这些行业的发展。机器学习是数据挖掘、知识发现的基础之一，它是当前及未来计算机科学中的一个热点方向。传统的机器学习主要针对监督式学习问题，要求训练样本的标记齐全，处理的数据维度一般不高。然而，随着数据采集技术的发展和广泛使用，采集到的样本不仅属性数量多、属性之间高度相关，而且有标记的样本极少，传统的机器学习方法难以在这些样本上进行有效地学习，急需能够综合利用大量无标记样本和少量有标记样本的机器学习模式。半监督学习能够综合利用有标记样本和无标记样本来提高学习器的泛化能力，近年来成为机器学习领域的热点方向之一。当前的半监督学习方法，特别是基于图的半监督学习方法，很多都只关注如何平衡利用无标记样本和有标记样本，却忽视了另一个更基础和更重要的问题，那就是如何在这些样本上构造能够真实反映样本之间相似关系的图，特别是在高维样本上。因为随着样本维度的增多，噪声特征和冗余特征也被大量引入，很多常用的距离度量并不能较好地刻画样本之间的相似性关系，基于这些距离也不能定义结构良好的图，而基于图的半监督学习中正是通过图来综合利用有标记样本和无标记样本。因此，如何在高维样本上构造图，是基于图的半监督学习方法在高维数据上有效性的关键，这也是其它基于图的学习方法成败的关键。本文针对高维数据上基于图的半监督学习存在的问题，以如何在高维数据上构图为出发点，以提高半监督学习的精度为目标，以度量学习和集成学习为基本手段，对基于图的半监督维数约减、半监督分类和半监督多标记分类展开深入研究，提出了一些构图方案，并把它们结合到基于图的半监督学习中。全文的主要贡献包括：1、提出一种增强型保局投影方法(ELPP)及其半监督版本(SELPP)。ELPP针对经典的保局投影方法(LPP)在高维数据上降维效果不佳和参数敏感的问题，利用鲁棒路径相似性度量构图，并应用到LPP的目标方程中。实验分析表明，ELPP不仅获得了较原始LPP更高的分类精度，而且对噪声特征和各种参数输入鲁棒，这也说明图结构在图嵌入方法中的重要性。SELPP继承了ELPP的所有优点，可以利用同类约束进一步提高降维结果的质量。实验表明，SELPP优于其它相关的半监督维数约减方法。2、提出一种混合图构造策略并把它应用到基于边信息的半监督维数约减中，进而提出基于混合图的半监督维数约减方法(MGSSDR)。MGSSDR不仅可以利用同类约束和未标记数据，它还可以利用异类约束进行维数约减。分析表明，MGSSDR的时间复杂度低于ELPP，它降维后的分类精度也高于其它相关方法，对噪声特征和近邻参数的输入也较鲁棒。混合图构建策略还可以应用到其它基于图的学习方法中。3、提出一种基于随机子空间降维的半监督分类方法(SSC-RSDR)。SSC-RSDR首先在多个随机生成的子空间上进行基于图的半监督维数约减，其次在这些维数约减后的子空间上构造多个k近邻图，再在这些图上分别训练半监督非线性分类器，最后融合这些分类器为一个集成分类器。实验结果表明，SSC-RSDR的分类精度不仅高于其它相关方法，而且对很多输入参数都很鲁棒，它较好地平衡了基础分类器之间的精确性和差异性，同时也克服了混合图依赖于子空间大小的不足。SSC-RSDR的图构造策略还可以应用到其它基于图的半监督学习方法中。4、提出一种子空间上的半监督集成分类方法(SSEC)，该方法在多个划分的子间上构造多个k近邻图，再在这些图上训练半监督线性分类器(SSLC)，最后把这些分类器进行投票集成。理论分析表明SSEC的时间复杂度低于SSC-RSDR。在高维人脸图像数据集上的实验结果表明，SSEC避免了随机子空间方法可能丢失重要特征的风险，它无需复杂的图优化过程，分类精度超过多种基于图优化的半监督分类方法，对多个输入参数也很鲁棒。子空间上的SSLC比原始空间上的SSLC拥有更高的精度，这证实了高维数据中的确存在大量的冗余特征和在子空间进行集成分类的合理性。5、提出一种有向双关系图，它可以克服无向双关系图容易出现标签覆盖的不足，基于有向双关系图提出一种直推多标记分类方法(TMC)和直推多标记集成分类方法(TMEC)，并把它们应用到异构多数据源的蛋白质功能预测中。实验结果表明有向双关系图比无向双关系图效果要好，基于分类器集成的方法比基于多核集成的方法更适合蛋白质功能预测任务。