【作者】 郝建柏；

【导师】 陈贤富；

【作者基本信息】 中国科学技术大学 ， 电路与系统， 2009， 硕士

【摘要】 在机器学习领域,有监督学习和无监督学习是两种常用的学习算法,但是他们在处理由于类别标注困难带来的标签数据极少、未标签数据众多的分类问题时效果往往不佳。针对此类问题,半监督学习近来被提出并获得广泛的研究。半监督学习结合两种传统学习算法的优势,能同时采用标签数据和未标签数据构造分类器,且一般能够获得较传统学习算法更好的学习效果。本文对半监督分类算法开展了较深入的研究,具体工作如下:文章首先对半监督学习中的典型算法进行了分析,并将其与有监督学习进行比较,发现半监督分类器的分类精度与其模型假设密切相关。只有在算法模型假设能够较好符合数据的真实结构时,未标签数据的采用能够帮助提升分类精度;否则,未标签数据可能不起作用,甚至起反作用。其次,本文通过对标签传递算法的实验研究,发现用随机选择的数据作为训练集会造成算法分类精度的较大波动。这说明可通过主动选择较优训练集去提升标签传递算法的分类精度。而在主动学习中,分类器可根据当前状态主动挑选能最大程度提升自身性能的待标注数据。通过引入此思想,本文提出了结合主动学习的标签传递算法,并对算法模型及待标注数据选择策略开展了研究,使得该算法可动态选择能最大程度降低标签传递算法当前分类风险的数据,提高训练集的质量。在UCI等数据集上的实验结果显示,训练数据数量相同时,该算法的分类精度超越了随机选择训练集数据的标签传递算法。实验中,我们发现该算法经常选择聚类中心的数据,因此,这些数据适合于作为标签传递算法的训练集。基于图的半监督分类算法需构造一个以数据为顶点、以数据间相似性值为边的图。在这种构造图的方法中相似性度量函数及其参数不易控制,数据的近邻个数也难以选择。通过对局部线性嵌入算法的研究,我们发现该算法构造线性近邻时不采用相似性函数,并且通过对数据局部流形的估算,判断数据是否位于分类间隙附近,可动态调整数据的近邻个数,达到减少不同类数据间连接的目的,进而减少标签误传递的概率。结合这两个优点,本文提出了基于局部线性嵌入算法构建图的标签传递算法。在UCI等数据等集上的实验结果表明,该算法中的图较传统图更容易使用,与典型标签传递算法相比,基于该图的标签传递算法分类精度更高。更多还原

【Abstract】 In traditional machine learning area, there are two commonly used learning algorithms, supervised learning and unsupervised learning, but neither of them is suitable for dealing with the situation where there are few labeled data and large amount of unlabeled data. To this problem, semi-supervised learning was proposed recently and has attracted great research interest. Semi-supervised learning combines the advantage of both traditional learning methods, it can build a better classifier by using the unlabeled data together with the labeled data. This paper does some research on semi-supervised classification algorithms, the main work is as follows:Firstly, this paper analyses the typical semi-supervised classification algorithms, by comparing it to supervised ones, finds that the classifier’s accuracy is closely related to its model assumption. Only when the model assumption matches the problem structure well, the unlabeled data can help to improve the classifier’s accuracy; otherwise, unlabeled data may be of no use, or even have bad affect on the classifier.Secondly, by doing experiment of label propagation algorithm (LP), we find that LP is sensitive to the quality of training set which are randomly chosen by traditional ways. This means that LP can be improved by actively selected good training set. In active learning, classifier can query unlabeled data that improve its performance most. By combining active learning thought, an active learning based LP algorithm (AL-LP) is proposed. This algorithm can actively select unlabeled data that can degrade the classification risk most so as to make the accuracy increase faster. Promising experimental results of UCI et al data sets show that, when labeled data number is the same, AL-LP can achieve higher accuracy than LP by randomly selected training set. Through the analysis of the frequently queried data, we find AL-LP is prone to select the cluster center nearby data. This means that it is very meaningful to select the cluster center data as the training set for LP.Graph-based semi-supervised learning first construct a graph where labeled and unlabeled data are represented as vertices, and edges encode the similarity between data. But this kind of graph-constructing method often faces the difficulty of choosing the similarity function, as well as its parameters, and the number of nearest neighbors. Aiming at this, we investigate locally linear embedding algorithm (LLE), and find LLE doesn’t use similarity function when constructing linear neighbors, and by detecting the local manifold and judging whether the data is near the classification margin, we could easily rectify the number of data’s nearest neighbors so as to decrease the connections between data of different classes and reduce the mis-label-propagating probability. Based on these two points, this paper proposes LLE based graph-constructing method, and applies it to LP. Experimental results of UCI et al data sets show that this method is easy to use, and that LP based on this kind of graph performs better than LP based on traditional graph.更多还原