Wide Gaps and Clustering Axioms
Mieczysław A. Kłopotek
The widely applied k-means algorithm produces clusterings that violate our
expectations with respect to high/low similarity/density and is in conflict
with Kleinberg's axiomatic system for distance based clustering algorithms that
formalizes those expectations in a natural way. k-means violates in particular
the consistency axiom. We hypothesise that this clash is due to the not
explicated expectation that the data themselves should have the property of
being clusterable in order to expect the algorithm clustering hem to fit a
clustering axiomatic system. To demonstrate this, we introduce two new
clusterability properties, variational k-separability and residual
k-separability and show that then the Kleinberg's consistency axiom holds for
k-means operating in the Euclidean or non-Euclidean space. Furthermore, we
propose extensions of k-means algorithm that fit approximately the Kleinberg's
richness axiom that does not hold for k-means. In this way, we reconcile
k-means with Kleinberg's axiomatic framework in Euclidean and non-Euclidean
settings. Besides contribution to the theory of axiomatic frameworks of
clustering and for clusterability theory, practical contribution is the
possibility to construct {datasets for testing purposes of algorithms
optimizing k-means cost function. This includes a method of construction of
{clusterable data with known in advance global optimum.