An efficient semi-supervised graph based clustering

Article type: Research Article

Authors: Vu, Viet-Vu

Affiliations: Information Technology Institute, Vietnam National University, Hanoi, 144 Xuan Thuy Street, Cau Giay District, Hanoi, Vietnam | E-mail: vuvietvu@vnu.edu.vn

Abstract: 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.

Keywords: Semi-supervised clustering, seed, k-nearest neighbors graph

DOI: 10.3233/IDA-163296

Journal: Intelligent Data Analysis, vol. 22, no. 2, pp. 297-307, 2018