1.北方民族大学 计算机科学与工程学院 银川 750021。2.Université Michel de Montaigne-Bordeaux 3, Bordeaux 33607 Pessac Cedex, France
Semi-supervised Classification Algorithm Based on l1-Norm and KNN Superposition Graph
ZHANG Yunbin1, ZHANG Chunmei1, ZHOU Qianqian1, DAI Mo2
1.College of Computer Science and Engineering, Beifang University of Nationalities, Yinchuan 750021.2.Université Michel de Montaigne-Bordeaux 3, Bordeaux 33607 Pessac Cedex, France
Abstract：A framework is proposed to construct a graph revealing the intrinsic structure of the data and improve the classification accuracy. In this framework, a l1-norm graph is constructed as the main graph and a k nearest neighbor (KNN) graph is constructed as auxiliary graph. Then, the l1-norm and KNN superposition (LNKNNS) graph is achieved as the weighted sum of the l1-norm graph and the KNN graph. The classification performance of LNKNNS-graph is compared with that of other graphs on USPS database, such as exp-weighted graph, KNNgraph, low rank graph and l1-norm graph, and 5% to 25% of the labeled samples are selected in experiments. Experimental results show that the classification accuracy of LNKNNS-graph algorithm is higher than that of other algorithms and the proposed framework is suitable for graph-based semi-supervised learning.
[1] ZHU X J, GOLDBERG A B, BRACHMAN R, et al. Introduction to Semi-supervised Learning. San Rafael, USA: Morgan and Claypool Publishers, 2009. [2] Zhu X J. Semi-supervised Learning // SAMMUT C, WEBB G I, eds. Encyclopedia of Machine Learning. Cambridge, USA: Springer, 2011. [3] LIU W, HE J F, CHANG S F. Large Graph Construction for Sca- lable Semi-supervised Learning // Proc of the 27th International Conference on Machine Learning. Madison, USA: Omnipress, 2010: 679-686. [4] CHEN K, WANG S H. Semi-supervised Learning via Regularized Boosting Working on Multiple Semi-supervised Assumptions. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 33(1): 129-143. [5] JEBARA T, WANG J, CHANG S F. Graph Construction and b-Matching for Semi-supervised Learning // Proc of the 26th International Conference on Machine Learning. Madison, USA: Omnipress, 2009: 441-448. [6] ZHUANG L S, GAO H Y, LIN Z C, et al. Non-negative Low Rank and Sparse Graph for Semi-supervised Learning // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA: IEEE, 2012: 2328-2335. [7] CHENG B, YANG J C, YAN S C, et al. Learning with l1-Graph for Image Analysis. IEEE Trans on Image Processing, 2010, 19(4): 858-866. [8] LIU G C, LIN Z C, YU Y. Robust Subspace Segmentation by Low-Rank Representation // Proc of the 27th International Conference on Machine Learning. Madison, USA: Omnipress, 2010: 663-670. [9] ZHOU D Y, BOUSQUET O, LAL T N, et al. Learning with Local and Global Consistency // THRUN S, SAUL L K, SCHLKOPF B, eds. Advances in Neural Information Processing Systems 16. Cambridge, USA: MIT Press, 2004: 321-328. [10] HAN S C, HUANG H, QIN H, et al. Locality-Preserving L1-Graph and Its Application in Clustering // Proc of the 30th Annual ACM Symposium on Applied Computing. New York, USA: ACM, 2015: 813-818. [11] ZHU X J. Semi-supervised Learning with Graphs. Ph.D Dissertation. Pittsburgh, USA: Carnegie Mellon University, 2005. [12] TANG J H, HONG R C, YAN S C, et al. Image Annotation by KNN-Sparse Graph-Based Label Propagation over Noisily Tagged Web Images. ACM Trans on Intelligent Systems and Technology, 2011, 2(2). DOI: 10.1145/1899412.1899418
2016, Vol. 29 
