A Novel clustering method based on hybrid K-nearest-neighbor graph. (February 2018)

• Record Type: Journal Article
• Authors: Qin, Yikun; Yu, Zhu Liang; Wang, Chang-Dong; Gu, Zhenghui; Li, Yuanqing
• Is Part Of: Pattern recognition. Volume 74(2018:Feb.)
• Page Start: 1
• Page End: 14
• Publication Date: 2018-02
• Subjects: Graph clustering -- Hybrid k-nearest-neighbor graph -- Internal validity index -- Nonlinear data set -- Video clustering; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.09.008
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: A novel data model termed hybrid k-nearest-neighbor graph is proposed to represent the data sets. A clustering method is developed based on the hybrid k-nearest-neighbor graph. A novel internal validity index is proposed to evaluate the validity of nonlinear clustering results. Abstract: Most of the existing clustering methods have difficulty in processing complex nonlinear data sets. To remedy this deficiency, in this paper, a novel data model termed Hybrid K-Nearest-Neighbor (HKNN) graph, which combines the advantages of mutual k-nearest-neighbor graph and k-nearest-neighbor graph, is proposed to represent the nonlinear data sets. Moreover, a Clustering method based on the HKNN graph (CHKNN) is proposed. The CHKNN first generates several tight and small subclusters, then merges these subclusters by exploiting the connectivity among them. In order to select the optimal parameters for CHKNN, we further propose an internal validity index termed K-Nearest-Neighbor Index (KNNI), which can also be used to evaluate the validity of nonlinear clustering results by varying a control parameter. Experimental results on synthetic and real-world data sets, as well as that on the video clustering, have demonstrated the significant improvement on performance over existing nonlinear clustering methods and internal validity indices.