AI summaryⓘ
The authors study a newer way to group data points into clusters called Cluster-as-Distribution (CaD), which treats each cluster as a group of points coming from an unknown probability distribution. Unlike traditional methods that rely on measuring similarity between points and struggle with weirdly-shaped or uneven clusters, CaD uses a greedy search to find these clusters more effectively. They provide a theoretical explanation showing that the greedy method is nearly optimal because it works on a mathematical structure called a partition matroid, and the quality depends on how well the distribution is estimated. This helps understand why CaD can correctly find clusters even when shapes, sizes, and densities differ, where older methods fail.
ClusteringCluster-as-Distribution (CaD)Greedy searchPartition matroidDistribution embeddingSpectral clusteringApproximation errorCluster shapesDensity variationsSet-oriented clustering
Authors
Kai Ming Ting, Kaifeng Zhang, Sanjay Chawla
Abstract
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.