A parameter-free graph reduction for spectral clustering and SpectralNet

Array

John Stavrakakis¹  Mashaan Alshammari²  Masahiro Takatsuka³ 

[1] Corresponding author.;College of Computer Sciences and Engineering, University of Hail, Hail 81411, Saudi Arabia;School of Computer Science, The University of Sydney, NSW 2006, Australia;

关键词: Spectral clustering;    SpectralNet;    Graph reduction;    Local scale similarity;   

DOI  :  

来源: DOAJ

【 摘 要 】

Graph-based clustering methods like spectral clustering and SpectralNet are very efficient in detecting clusters of non-convex shapes. Unlike the popular k-means, graph-based clustering methods do not assume that each cluster has a single mean. However, these methods need a graph where vertices in the same cluster are connected by edges of large weights. To achieve this goal, many studies have proposed graph reduction methods with parameters. Unfortunately, these parameters have to be tuned for every dataset. We introduce a graph reduction method that does not require any parameters. First, the distances from every point p to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. Second, the similarities with close neighbors are computed and only high similarities are kept. The edges that survive these two filtering steps form the constructed graph that was passed to spectral clustering and SpectralNet. The experiments showed that our method provides a stable alternative, where other methods’ performance fluctuated according to the setting of their parameters.

【 授权许可】

Unknown