An efficient semi-supervised graph based clustering

Clustering is one of the most important tools in data mining and knowledge discovery from data. In recent years, semi-supervised clustering, that integrates side information (seeds or constraints) in the clustering process, has been known as a good strategy to boost clustering results. In this article, a new semi-supervised graph based clustering (SSGC) is presented. Using a graph of the k-nearest neighbors and a measure of local density for the similarity between vertex, SSGC integrates the seeds in the process of building clusters and hence can improve the quality of clustering. More over, SSGC can deal with noise, differential density of data, and uses only one parameter (i.e. the number of nearest neighbors). Experiments conducted on real data sets from UCI show that our method can produce good clustering results compared with the related techniques such as semi-supervised density based clustering (SSDBSCAN). Moreover, the computational cost of SSGC is much less than that of SSDBSCAN.