(δ, ε)-K Segmentation for Characterizing Well-Clusterable Sets

Kleinberg (2002) introduced three axioms to formalize the behavior of clustering algorithms and presented that no clustering algorithm satisfies them. However, this result usually is inconsistent with the practical experience of clustering algorithms. In this article, we reformulate these axioms to fill the gap and verify the existence of clustering algorithms satisfying the modified axioms when the point set is well-clusterable. In particular, the concept of $(\delta ,\varepsilon)$ -K segmentation is proposed to characterize the set that has the potential to be clustered well. Then, we verify the existence and the uniqueness of $(\delta ,\varepsilon)$ -K segmentation of a set, respectively. Next, we demonstrate that the $(\delta ,\varepsilon)$ -K segmentation is compatible with K-means, Min-Cut, DBSCAN, and several clustering internal evaluation (CIE) indexes. In addition, the ratio $\delta / \varepsilon $ can be treated as the measure of not only characterizing well-clusterable sets but also of evaluating the performance of clustering results, respectively.