Measures of Clustering Quality: A Working Set of Axioms for Clustering
Speaker: Rita Ackerman
Aiming towards the development of a general clustering
theory, we discuss abstract axiomatization for clustering. In this
respect, we follow up on the work of Kleinberg, (Kleinberg, 2002) that
showed an impossibility result for such axiomatization. We argue that
an impossibility result is not an inherent feature of clustering, but
rather, to a large extent, it is an artifact of the specific formalism
used in (Kleinberg, 2002).
As opposed to previous work focusing on clustering functions, we
propose to address clustering quality measures as the object to be
axiomatized. We show that principles like those formulated in
Kleinberg's axioms can be readily expressed in the latter framework
without leading to inconsistency.
A clustering-quality measure (CQM) is a function that, given a data
set and its partition into clusters, returns a non-negative real
number representing how strong or conclusive the clustering is. We
analyze what clustering-quality measures should look like and
introduce a set of requirements (axioms) for such measures. Our axioms
capture the principles expressed by Kleinberg's axioms while retaining
We propose several natural clustering quality measures, all satisfying
the proposed axioms. In addition, we analyze the computational
complexity of evaluating the quality of a given clustering and show
that, for the proposed CQMs, it can be computed in polynomial time.