文档介绍：华中科技大学硕士学位论文基于图的半监督学****算法研究姓名:占惠融申请学位级别:硕士专业:计算机应用技术指导教师:宋恩民 20090528 华中科技大学硕士学位论文 I 摘要半监督学****是当前机器学****研究中最受关注的问题之一。半监督学****只利用少量的标记数据和大量未标记数据进行学****在减少人工标注代价和提高学****器性能方面,半监督学****具有较突出的优势,其研究成果已逐渐用于解决实际问题。图方法是半监督学****中研究比较多的一种方法,其理论基础比较健全。图方法可以很好的刻画数据自身的结构特征,而不需带有某种分布的偏向,该方法直观、灵活,但是其计算量很大,成为实际应用中的屏障。对基于图的半监督学****方法进行了系统的分析研究,特别针对局部和全局一致性学****方法( Learning from Local and Global Consistency , LLGC )中计算量大的问题进行了深入分析,提出了基于 quick shift 的图构建方法。首先,按照 quick shift 方法对原始数据进行局部范围的聚类;然后,在聚类后的簇上构造一个新的无向连通图; 最后,在新图上利用 LLGC 方法进行分类。由于 quick shift 方法以非参数密度估计理论为基础,具有保持原始数据分布状况的良好属性,因此,对数据进行聚类,并不会降低图方法的准确性。另一方面,聚类后簇的数目较样本点的数目少很多,即新图的节点数目远远少于原始图的节点数目,从而大大提升了 LLGC 分类的运算速度。对茶壶图像、手写数字和英文字符 3 类实用数据分别进行了实验,结果表明, 改进后的方法不仅在分类准确度方面与 LLGC 方法相当,而且在计算速度方面,要明显优于 LLGC 方法。关键字: 半监督学****非参数估计,密度估计,聚类,图方法华中科技大学硕士学位论文 II Abstract Semi-supervised learning (SSL) has drawn wide attention in the machine learning fields. bines information from both la rge number of unlabeled data and limited amount of labeled data. As SSL has an advantage in improving the classifier’s performance and reducing the cost of artificia l annotation, it has been gradually applied to solve real world problems. The graph-based method, which has perfect theoretical basis, has been the most popular methods in SSL. The graph-based method is very good at depi cting the intrinsic structural of data, and has little dependen ce on distribution assumption. It’s intuitive and flexible. But plexity is too high for many real world problems. This paper first reviews the SSL schemes, especially on the graph-based methods. Then we discuss the problem of plexity in graph-based methods. In order to fix the problem, we propose a new method for graph construction which uses quick shift to cluster the data locally first and then constructs a graph on the clusters. As quick shift is a non-parametric density estim ation method, which can keep the original data distribution, it won’t reduce the accuracy of the graph-based method. On the other hand, the numb