Workshop: New Frontiers in Graph Learning

Skeleton Clustering: Graph-Based Approach for Dimension-Free Density-Aided Clustering

Zeyu Wei · Yen-Chi Chen

Keywords: [ Graph learning ] [ k-means clustering ] [ Density Estimation ] [ high-dimensional clustering ] [ density-based clustering ]


Density-based clustering can identify clusters with irregular shapes and has intuitive interpretations, but struggles with large-dimensional data due to the curse of dimensionality.We introduce a graph-based clustering framework called \textit{Skeleton Clustering} to adopt density-based clustering idea to multivariate and even high-dimensional data. The proposed framework constructs a graph representation of the data as a first step and combines prototype methods, density-based clustering, and hierarchical clustering.We propose surrogate density measures based on the skeleton graph that are less dependent on the dimension and have meaningful geometric interpretations. We show by empirical studies that the proposed skeleton clustering method leads to reliable clusters in multivariate and even high-dimensional data with irregular shapes.

Chat is not available.