半监督学习是当前机器学习研究中最受关注的问题之一。半监督学习只利用少量的标记数据和大量未标记数据进行学习。在减少人工标注代价和提高学习器性能方面,半监督学习具有较突出的优势,其研究成果已逐渐用于解决实际问题。图方法是半监督学习中研究比较多的一种方法,其理论基础比较健全。图方法可以很好的刻画数据自身的结构特征,而不需带有某种分布的偏向,该方法直观、灵活,但是其计算量很大,成为实际应用中的屏障。对基于图的半监督学习方法进行了系统的分析研究,特别针对局部和全局一致性学习方法(Learning from Local and Global Consistency,LLGC)中计算量大的问题进行了深入分析,提出了基于quick shift的图构建方法。首先,按照quick shift方法对原始数据进行局部范围的聚类;然后,在聚类后的簇上构造一个新的无向连通图;最后,在新图上利用LLGC方法进行分类。由于quick shift方法以非参数密度估计理论为基础,具有保持原始数据分布状况的良好属性,因此,对数据进行聚类,并不会降低图方法的准确性。另一方面,聚类后簇的数目较样本点的数目少很多,即新图的节点数目远远少于原始图的节点数目,从而大大提升了LLGC分类的运算速度。对茶壶图像、手写数字和英文字符3类实用数据分别进行了实验,结果表明,改进后的方法不仅在分类准确度方面与LLGC方法相当,而且在计算速度方面,要明显优于LLGC方法。