탐욕적(Greedy) 검색이 최적의 클러스터링 결과를 생성하는 이유는 무엇인가? 고정 코어 할당 이론

Why does Greedy Search produce Optimal Clustering Outcomes? A Fixed-Core Assignment Theory

기존의 많은 클러스터링 방법은 집합 기반 정의에 따라 설계됩니다. 즉, 클러스터는 유사한 점들의 집합이며, 각 점 간의 유사성을 측정하는 함수를 사용하여 유사한 점들을 찾습니다. 이러한 방식은 콤팩트한 클러스터에서는 잘 작동하지만, 클러스터의 모양이 불규칙하거나 클러스터 간의 밀도나 크기가 다를 경우 클러스터링 성능이 크게 저하될 수 있습니다. 최근에 개발된 '클러스터를 분포로 표현하는(Cluster-as-Distribution, CaD) 방식'은 각 클러스터를 독립적이고 동일하게 분포된 점들의 집합으로 취급하고, 탐욕적 검색을 통해 이러한 클러스터들을 찾아내어 실제적으로 다양한 형태의 클러스터를 발견할 수 있습니다. 이 방식은 스펙트럴 클러스터링과 유사한 목표를 달성하지만, 고유값 분해 없이 더 나은 클러스터링 결과를 얻을 수 있습니다. 그러나 이러한 현상에 대한 이론적인 분석은 아직 부족합니다. 본 연구에서는 두 가지 관점에서 분석을 수행했습니다. 첫째, 실제 분포와 경험적 분포의 임베딩 간의 근사 오차를 분석했습니다. 둘째, CaD 클러스터링 목표를 달성하기 위해 사용되는 탐욕적 검색이 파티션 매트라이드(partition matroid)로 변환될 수 있음을 보여줌으로써, 탐욕적 최적성이 달성됨을 증명합니다. 이러한 분석은 CaD 클러스터링 목표에 대한 거의 최적의 보장을 제공하며, 후회(regret)는 근사 오차에 의해 제어됩니다. 본 연구는 추정된 클러스터 임베딩이 기본 클러스터 분포를 충실하게 반영할 때, 탐욕적 검색을 통해 CaD 클러스터링이 임의의 모양, 밀도 및 크기를 가진 클러스터를 발견할 수 있는 이유를 설명하는 최초의 분석입니다. (기존의 모든 집합 기반 클러스터링 방법은 이러한 능력이 부족했습니다.)

Many existing clustering methods are designed based on a set-oriented definition---a cluster is a set of similar points---relying a point-to-point similarity function to find similar points. This works well for compact clusters, but clustering performance can deteriorate badly when cluster shapes are irregular, and densities or sizes vary between clusters. Recent `Cluster-as-Distribution' (CaD) clustering has been shown to discover these generic types of clusters in practice by treating each cluster as a set of independent and identically distributed points generated from some unknown distribution via a greedy search, achieving a clustering objective equivalent to that of Spectral Clustering, but with better clustering outcomes without eigen-decomposition. However, a theoretical analysis of this phenomenon is still lacking. Our analyses are from two angles. First, we analyze the approximation error between the true and empirical distribution embeddings. Second, we show that the greedy search employed to achieve the CaD clustering objective can be mapped to a partition matroid---yielding greedy optimality. These yield a near-optimality guarantee for the CaD clustering objective, with regret controlled by the approximation error. This is the first analysis that explains why CaD clustering via greedy search can discover clusters of arbitrary shapes, densities and sizes (where all set-oriented clustering methods have failed to discover) when the estimated cluster embeddings faithfully approximate the underlying cluster distributions.