Discriminative Graph Based Similarity Boosting

Similarity measurement is crucial for unsupervised learning and semi-supervised learning. Unsupervised methods need a similarity to do clustering. Semi-supervised algorithms need a similarity to take advantage of unlabeled data. In this paper, we develop a boosted similarity learning algorithm. The ensemble similarity is the weighted sum of a few component similarities. Each component similarity is learned form a graph G(V, E), where \(V=\{x_1, x_2,\ldots ,x_n\}\) represent the data and the edges E represent the distance (or similarity) between them. For a given graph, we propose “within graph-cluster scatter \(S_{w}\)” and “between graph-cluster scatter \(S_{b}\)” to analyze the discrimination of the graph. So the contributions of this paper are: (i) we develop a boosting similarity learning strategy based on a few graphs, so the proposed strategy can take advantage of a few graphs rather than only one; (ii) we propose “within graph-cluster scatter \(S_{w}\)” and “between graph-cluster scatter \(S_{b}\)” to measure the discrimination of a graph. Experimental results on both synthetic and public available data sets show that the proposed method outperforms the sate-of-the-arts.