Open AccessRobust Similarity Measure for Spectral Clustering Based on Shared Neighbors
Author(s) -
Ye Xiucai,
Sakurai Tetsuya
Publication year - 2016
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.16.0115.0517
Subject(s) - spectral clustering , cluster analysis , similarity measure , computer science , pattern recognition (psychology) , closeness , similarity (geometry) , k nearest neighbors algorithm , correlation clustering , fuzzy clustering , data mining , artificial intelligence , cure data clustering algorithm , single linkage clustering , measure (data warehouse) , mathematics , image (mathematics) , mathematical analysis
Spectral clustering is a powerful tool for exploratory data analysis. Many existing spectral clustering algorithms typically measure the similarity by using a Gaussian kernel function or an undirected k ‐nearest neighbor ( k NN) graph, which cannot reveal the real clusters when the data are not well separated. In this paper, to improve the spectral clustering, we consider a robust similarity measure based on the shared nearest neighbors in a directed kNN graph. We propose two novel algorithms for spectral clustering: one based on the number of shared nearest neighbors, and one based on their closeness. The proposed algorithms are able to explore the underlying similarity relationships between data points, and are robust to datasets that are not well separated. Moreover, the proposed algorithms have only one parameter, k . We evaluated the proposed algorithms using synthetic and real‐world datasets. The experimental results demonstrate that the proposed algorithms not only achieve a good level of performance, they also outperform the traditional spectral clustering algorithms.