Improving Spectral Clustering Using Path-Based Connectivity

Abstract

Spectral clustering is a recently popular clustering method, not limited to spherical-shaped clusters and capable of finding elongated arbitrary-shaped clusters. This graph theoretical clustering method can use Euclidean distance between each pair of examples as well as connectivity-based similarity measures based on shortest path or paths that do not travel over examples with big distances on the graph. In this paper, a hybrid method is proposed that utilizes distances used by spectral and path-based spectral clustering algorithms. The proposed hybrid methodis shown to be more robust than both methods.