Injecting randomness into graphs: An ensemble semi-supervised learning framework
Authors: Zhang, Q., Sun, J., Zhong, G., Dong, J., Gao, F., Yang, H. and Saeeda, H.
Many traditional graph-based semi-supervised learning methods have been applied in many domains to deal with applications including a large number of unlabeled samples and very expensive manual annotated samples. These methods in general need O(n ) time complexity to construct the graph, and O(n ) time complexity to solve the label inference problem. In result, it limits their application on big and high dimensional data sets. Another weakness of traditional semi-supervised learning algorithms is the low classification accuracy. In this chapter, a novel framework is proposed to solve these two problems. Anchors, which are a special subset chosen from the original data set, are used to reduce the complexity of graph construction and label inference. And the idea of injecting randomness into graphs is utilized to improve the classification accuracy and to deal with the high dimensionality issue. It is empirically verified that the randomness can be viewed as a kind of regularization technique. The proposed method is evaluated on eight real data sets to show its effectiveness. Furthermore, to test the performance of the proposed method on high dimensional data, it is tested and applied to solve the hyperspectral image classification problem. 2 3