Abstract: In order to get a good clustering performance in data set with a small number of labeled samples, a semi supervised clustering algorithm based on graph contraction was proposed in this paper. At first, the whole data in sample space was represented as an edgcwcighted graph. Then the graph was modified by contraction according to must link constraints and graph theory. On this basis, we projected sample space into a subspace by combining graph laplacian with cannot-link constraints. Data clustering was conducted over the modified graph. Experimental results show that the method indeed reaches its goal for complex datasets, and it is acceptable when there has small amount of pairwise constrants.

Key words: Semi supervised cluster, Graph laplacian, Clustering analysis, Sample space, Machine learning