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.
About author:: ZHANG Yunbin, born in 1988, master student. His research interests include graph and image processing and machine learning.ZHANG Chunmei(Corresponding author), born in 1964, master, professor. Her research interests include image proce-ssing, machine learning and pattern recognitionZHOU Qianqi, born in 1989, master student. Her research interests include remote sensing image classification and machine learning.DAI Mo, born in 1945, Ph.D., professor. His research interests include pattern recognition and digital image processing and analysis.)
[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 
