基于l^1范数和k近邻叠加图的半监督分类算法

Semi-supervised Classification Algorithm Based on l^1-Norm and KNN Superposition Graph

为了构造一个能够较好反映数据真实分布的图以提高分类性能,文中提出基于l1范数和k近邻叠加图的半监督分类算法.首先构造一个l1范数图,作为主图,然后构造一个k近邻图,作为辅图,最后将二者按一定比例叠加,得到l1范数和k近邻叠加(LNKNNS)图.实验中选择标记样本比例从5%到25%,将基于LNKNNS图的半监督分类算法在USPS数据库上对比其它图(指数权重图、k近邻图、低秩表示图和l1范数图)的算法.实验表明,文中算法的分类识别率更高,更适合基于图的半监督学习.

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 ak 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.