KNN-SC: Novel Spectral Clustering Algorithm Using k-Nearest Neighbors

Jeong-Hun Kim

doi:10.1109/ACCESS.2021.3126854

KNN-SC: Novel Spectral Clustering Algorithm Using k-Nearest Neighbors

2021-01-01

12

OA

AI

DOI：10.1109/ACCESS.2021.3126854

Original

Original request for help

Save

Abstract

En 中文

Spectral clustering is a well-known graph-theoretic clustering algorithm. Although spectral clustering has several desirable advantages (such as the capability of discovering non-convex clusters and applicability to any data type), it often leads to incorrect clustering results because of high sensitivity to noise points. In this study, we propose a robust spectral clustering algorithm known as KNN-SC that can discover exact clusters by decreasing the influence of noise points. To achieve this goal, we present a novel approach that filters out potential noise points by estimating the density difference between data points using k-nearest neighbors. In addition, we introduce a novel method for generating a similarity graph in which various densities of data points are effectively represented by expanding the nearest neighbor graph. Experimental results on synthetic and real-world datasets demonstrate that KNN-SC achieves significant performance improvement over many state-of-the-art spectral clustering algorithms.

Keywords:

Clustering algorithms

Partitioning algorithms

Symmetric matrices

Laplace equations

Optimization

Minimization

Licenses

k-nearest neighbors

nearest neighbor graph

potential noise detection

spectral clustering

KNN-SC: Novel Spectral Clustering Algorithm Using k-Nearest Neighbors

Abstract

Journal

Organization