Benefits of Hypergraphs for Density-Based Clustering
Louis Hauseux, Konstantin E. Avrachenkov, Josiane B. Zerubia · 2024
Many of clustering algorithms are based on density estimates in${\mathbb{R}^{d}}$. Building geometric graphs on the dataset$\mathcal{X}$is an elegant way of doing this. In fact, the connected components of a geometric graph match exactly with the high-density clusters of the 1-Nearest Neighbor density estimator. In this paper, We show that the natural way to generalize geometric graphs is to use hypergraphs with a more restrictive notion of connected component called$K$-Polyhedron. Herein, we prove that$K$-polyhedra correspond to high-density clusters of K-Nearest Neighbors density estimator. Furthermore, the percolation phenomenon is omnipresent behind the family of clustering algorithms we look at in this paper.