계층적 클러스터링은 풍부성, 일관성, 스케일 불변성을 동시에 만족할 수 있다
Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
한국어 초록
클러스터링은 널리 사용되고 있음에도 불구하고, 클러스터가 무엇인지에 대해 보편적으로 받아들여지는 정의가 없다. Kleinberg의 불가능성 정리(Impossibility Theorem)는 어떤 평면(flat) 클러스터링 방법도 스케일 불변성(scale invariance), 풍부성(richness), 일관성(consistency)이라는 세 가지 자연스러운 공리를 동시에 만족할 수 없음을 보임으로써 이러한 어려움을 형식화한다. 본 논문에서는 출력이 단일 분할(partition)이 아니라 계층 구조(hierarchy)일 때에도 이러한 불가능성이 유지되는지를 묻는다. 우리는 평면 클러스터링의 경우와 달리, 이 공리들의 계층적 대응물은 동시에 만족될 수 있음을 보인다. 실제로 이러한 공리를 만족하는 계층적 클러스터링 방법은 셀 수 없이 많이 존재하며, 우리는 이를 허용 가능(admissible)한 방법이라 부른다. 우리는 잘 분리된 클러스터(well-separated clusters)에 기반한 방법과 단일 연결(single linkage)의 비이진(non-binary) 버전을 포함하여 여러 허용 가능한 방법을 명시적으로 구성한다. 특정한 허용 가능한 방법의 쌍에 대해서는, 한 방법이 생성한 계층 구조가 다른 방법이 생성한 계층 구조를 항상 세분(refine)한다. 이 세분 관계는 허용 가능한 방법들의 클래스 위에 부분 순서(partial order)를 정의한다. 이 부분 순서 집합은 최대 원소(greatest element)를 갖지 않으며, 셀 수 없이 많은 서로 양립할 수 없는 극대 원소(maximal element)들을 포함하여 허용 가능한 방법들 사이에 상당한 다양성이 존재함을 보여 준다. 그럼에도 불구하고 이러한 다양성에는 제약이 있다. 모든 허용 가능한 방법은 충분히 잘 분리된 클러스터로 이루어진 계층 구조를 포함하며, 허용 가능한 방법들의 모든 유한 집합은 이러한 자명하지 않은(nontrivial) 공통 뼈대(backbone)를 공유한다.
원문 초록
Despite its ubiquity, clustering lacks a universally accepted definition of what is a cluster. Kleinberg's Impossibility Theorem formalizes this difficulty by showing that no flat clustering method can simultaneously satisfy three natural axioms: scale invariance, richness, and consistency. In this paper, we ask whether this impossibility persists when the output is a hierarchy rather than a single partition. We show that, in contrast to the flat clustering setting, the hierarchical analog of these axioms are jointly satisfiable. In fact, there exist uncountably many hierarchical clustering methods satisfying these axioms, which we call admissible. We explicitly construct several admissible methods, including methods based on well-separated clusters and a non-binary version of single linkage. For certain pairs of admissible methods, the hierarchy produced by one always refines that produced by the other. This refinement relation defines a partial order on the class of admissible methods. This partially ordered set has no greatest element and contains uncountably many pairwise incompatible maximal elements, revealing substantial diversity among admissible methods. Nevertheless, this diversity is constrained: every admissible method contains a hierarchy of sufficiently well-separated clusters, and every finite collection of admissible methods shares such a nontrivial common backbone.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.11173v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.