DBSCAN Is Semi-Spectral Clustering
Yewang Chen · 2020
Spectral clustering and DBSCAN are two famous clustering methods, the former reduces data dimensionality by spectrum of similarity matrix, and then utilizes kmeans to cluster data in low dimensional space. While DBSCAN performs clustering by finding different density regions that depart from each other, which makes it seems quite different from spectral clustering, and there is little literal discusses the relationship between them. In this paper, we revisit DBSCAN from Similarity Graph and Graph Cut point of views, uncover the underlying relationship between DBSCAN and spectral clustering, which proves that DBSCAN can be explained and rewritten under the framework of spectral clustering. Furthermore, eigenvectors are often approximately resolved, and k-means is usually used in the final stage, often converges in local optimization. Hence, we rewrite spectral clustering by using nearest neighbor query instead of k-means to obtain exact result. Experimental results address that the revised spectral clustering method can obtain the same result as DBSCAN on core point set. Therefore, we come to the conclusion that DBSCAN is semi-spectral clustering. The work of this paper theoretically illustrates that spectral clustering is as good as DBSCAN, and both algorithms can be replaced with each other to avoid their own disadvantages.