文档介绍：Local Learning and Global Preserving Based
Semi-supervised Algorithm for Large Scale Classification
Problems
A Dissertation Submitted for the Degree of Master
Candidate：Li Yuhan
Supervisor：Prof. Wu Guangchao
South China University of Technology
Guangzhou, China
摘 要
在现实分类问题中，人们常常面临有标记样本很少而无标记样本很多的情况，这使
得半监督分类算法成为模式识别和机器学****领域的重要研究内容。然而伴随着信息时代
的发展，人们获得的数据规模日益庞大，传统的半监督分类算法因较高的时间和空间复
杂度无法解决大规模分类任务。因此大规模半监督分类算法的研究在相关领域变得越来
越重要。
本文基于局部学****和全局保持的思想提出了一种有效的大规模半监督分类算法
LLGP。首先从局部学****的角度考虑，利用所有的无标记样本构造一颗聚类特征树，利
用该树的层次聚类功能将原始的大量样本划分为一定数量的小规模样本子集，称为局部
子集；然后结合所有有标记样本使用传统基于图的半监督方法对各个局部进行分类，从
而降低学****的规模，使大规模问题得以解决。
另一方面，单纯地使用有标记样本和各局部内的样本学****存在一个潜在问题：局部
内的样本无法保持原始样本的整体结构，即样本全局结构遭到破坏。在半监督的基本假
设下，这会导致某些距离同类有标记样本远的局部样本因距离他类有标记样本更近而被
错分，最终的分类精度会大大降低。因此本文提出了全局保持的思想，指将样本的
k-means 聚类中心作为框架点加入到各个局部学****问题中，从而保持样本的全局结构，
减缓样本结构破坏对局部学****的影响。此外，为能够利用 k-means 算法获取大规模样本
的框架点，本文利用了聚类特征树的数据压缩存储功能，通过对压缩后的样本进行
k-means 聚类而避免直接对原始大规模样本聚类从而加快框架点的获取。对应的参数分
析结果表明了框架点的重要性和有效性。
在中等规模数据集上的对比实验表明，本文提出的 LLGP 算法能够在取得同传统算
法相当的精度的同时加快学****速度。在大规模数据集上的对比实验表明，LLGP 算法能
够取得比现有基于图的大规模半监督算法更高的精度，且时间相当，当样本规模达到一
定程度后，其他算法变得不可行而 LLGP 依然表现良好。
关键词：大规模；半监督；局部学****聚类特征树；全局保持
I
Abstract
I n many classification problems, people are often faced with the case that there are very
few labeled samples and many unlabeled samples. It makes semi-supervised classification
algorithm become an important research content in the areas of pattern recognition and
machine learning. However, along with the development of internet in the information age,
the scale of data becomes larger and larger in many pro