基于图的半监督分类算法研究

发布时间：2018-01-27 09:59

本文关键词： 图的半监督分类测地距离局部和全局一致性算法 K均值聚类　出处：《陕西师范大学》2012年硕士论文　论文类型：学位论文

【摘要】：在机器学习和数据挖掘领域,半监督学习越来越受到科研人员的关注,逐步成为当前的研究热点。半监督学习中,半监督分类利用大量非标签数据辅助少部分标签数据进行监督学习,从而提高分类的性能。基于图的半监督分类是现在研究较多的方法,该类方法具有较好的分类性能。然而基于图的方法计算复杂度比较高,当图规模比较大时,需要的时间和存储代价都非常大,而且基于图的方法都是直推式的,对新数据无法进行分类,这在一定程度上限制了基于图的方法使用。本文主要针对基于图的半监督分类存在的这些问题,进行了分析与研究。本文主要针对基于局部和全局一致性算法进行研究,该算法的基本思想是基于已标记样本和未标记样本建立一个图,用边的权重来表示样本之间的相似度,然后让每个样本的标记信息迭代地向其邻近样本传播,直到达到全局稳定状态,该方法直观、灵活,但是计算复杂度大,且无法对新数据进行分类。本文针对该算法存在的不足之处进行了改进,应用于图像分类中,并和其他方法进行了比较与分析。本文的研究工作主要包括以下几方面： (1)介绍了图像分类的相关理论,半监督学习的基本理论,当前国内外研究现状,且对半监督学习中基于图的方法所涉及的理论基础、研究现状以及该方法中所存在的问题和难点进行了综述,对半监督学习的主要应用进行了阐述,并且重点介绍了基于局部和全局一致性算法。 (2)针对图像提出了一种基于图的半监督分类方法,该方法对图的相似矩阵的度量方法进行了改进,使用更能准确地反映样本间拓扑结构的测地距离对相似矩阵进行度量,并且运用了复合核的策略,结合了图像的谱信息和空间信息,进而使算法的分类性能有所提高。实验结果表明,采用该算法较之于原算法,获得了更好的分类性能。 (3)为解决基于图的半监督分类算法的计算复杂度比较高和对新数据无法分类的问题。本文提出了一种将K均值算法和基于图的方法相结合的分类算法,利用已标记样本的标签信息,通过K均值方法获取更多的已标记信息,减少基于图方法迭代过程的迭代次数,从而降低了图方法的计算复杂度；算法最终确定的类中心解决了基于图的分类算法无法对新数据进行分类的问题,增强了其对新数据分类的扩展性；通过设置参数取值的实验结果分析,找出了参数的最佳取值范围。实验结果表明,提出的算法在计算效率和分类正确率方面有明显的提高。
[Abstract]:In the field of machine learning and data mining, semi supervised learning has attracted more and more attention by the researchers, has gradually become a research hotspot. In semi supervised learning, semi supervised classification using large amounts of unlabeled data auxiliary part of unlabeled data for supervised learning, so as to improve the performance of classification. Graph based semi supervised classification is now on many methods, the method has good classification performance. However, the method based on the computational complexity is relatively high, when the graph size is large, the time and cost of storage are very large, and graph based methods are direct push, the new data can not be classified, which limits the use of a graph based approach to a certain extent. This paper mainly aimed at the existing semi supervised classification based on these problems, are analyzed and studied.
This paper studies the local and global consistency algorithm based on the basic idea of the algorithm is the labeled samples and unlabeled samples is established based on a graph, with edge weights representing the similarity between the samples, and then let the mark information iteration of each sample to its adjacent sample transmission, until it reaches the global stable state. This method is intuitive, flexible, but large computational complexity, and unable to classify new data. Aiming at the disadvantage of this algorithm is improved and applied to image classification, and other methods of comparison and analysis. The main research work of this paper includes the following aspects:
(1) introduces the related theory of image classification, semi supervised learning basic theory, the current research status at home and abroad, and the theoretical basis to the semi supervised graph based methods of study, research status and existing problems and difficulties in the method are reviewed, the main application of semi supervised learning is discussed, and emphatically introduces the local and global consistency based algorithm.
(2) the image presents a semi supervised classification method based on graph method, the method of similarity measure matrix diagram is improved, using a more accurate reflection of the sample geodesic topological structure of distance matrix of similarity measure, and using the compound nuclear strategy, combined with spectral information and the spatial information of the image, so that the algorithm improves the performance of the classification. The experimental results show that using this algorithm compared with the original algorithm to get better classification performance.
(3) to solve the calculation of semi supervised classification algorithm based on graph complexity is relatively high and the new data to the classification problem. This paper proposes a K means algorithm and graph method based on the combination of classification algorithm, using the labeled sample label information, to obtain more labeled information by K means method to reduce the number of iteration method based on iterative process, thus reducing the computational complexity of the algorithm graph method; final class center to solve the classification algorithm based on graph cannot be classified by the new data, enhance its expandability to new data classification; through the experiment analysis of the parameters and find out the optimal range of parameters. The experimental results show that the proposed algorithm in computational efficiency and classification accuracy can be improved significantly.

【学位授予单位】：陕西师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP311.13

【相似文献】