Scholarlink

<p>This article analyzes and generalizes the classical Single-Linkage clustering algorithm, which performs hierarchical clustering by iteratively merging the two closest clusters. Single-Linkage and its robust version are still widely used in modern clustering techniques like the state-of-the-art HDBSCAN. Single-Linkage can be understood from three perspectives: (i) it conducts <i>persistent analysis</i> on geometric graphs; (ii) it identifies high-density clusters using the 1-Nearest Neighbor density estimator; and (iii) it is implemented via the minimum spanning tree of the data. This paper extends Single-Linkage to higher-order interactions by replacing geometric graphs with hypergraphs and introducing a stricter notion of connected components, named <i>K</i>-polyhedra. Specifically, for <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(K=2\)</EquationSource> </InlineEquation>, our method employs “triangle connectivity”. We prove that <i>K</i>-polyhedra correspond to high-density clusters of the <i>K</i>-Nearest Neighbors density estimator. In practice, this approach is implemented by identifying a minimum <i>K</i>-tree. The paper also introduces original geometric optimizations for efficiently computing the 2-generalization of Single-Linkage in low-dimensional Euclidean spaces. Experimental results demonstrate that even when <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(K=2\)</EquationSource> </InlineEquation> is used, the proposed method already surpasses the state-of-the-art clustering methods on synthetic and real-world datasets.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Generalization of single-linkage with higher-order interactions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月18日

查看全文
  • Louis Hauseux,
  • Konstantin Avrachenkov,
  • Josiane Zerubia

摘要

This article analyzes and generalizes the classical Single-Linkage clustering algorithm, which performs hierarchical clustering by iteratively merging the two closest clusters. Single-Linkage and its robust version are still widely used in modern clustering techniques like the state-of-the-art HDBSCAN. Single-Linkage can be understood from three perspectives: (i) it conducts persistent analysis on geometric graphs; (ii) it identifies high-density clusters using the 1-Nearest Neighbor density estimator; and (iii) it is implemented via the minimum spanning tree of the data. This paper extends Single-Linkage to higher-order interactions by replacing geometric graphs with hypergraphs and introducing a stricter notion of connected components, named K-polyhedra. Specifically, for \(K=2\) , our method employs “triangle connectivity”. We prove that K-polyhedra correspond to high-density clusters of the K-Nearest Neighbors density estimator. In practice, this approach is implemented by identifying a minimum K-tree. The paper also introduces original geometric optimizations for efficiently computing the 2-generalization of Single-Linkage in low-dimensional Euclidean spaces. Experimental results demonstrate that even when \(K=2\) is used, the proposed method already surpasses the state-of-the-art clustering methods on synthetic and real-world datasets.