Measures of Clustering Quality: A Working Set of Axioms for Clustering
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 Kelinberg, (Kleinberg) 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. As opposed to previous work focusing on clustering functions, we propose to address clustering quality measures as the primitive 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 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') that express these requirement and extend the translation of Kleinberg's axioms to our framework. We propose several natural clustering quality measures, all satisfying the proposed axioms. In addition, we show that the proposed clustering quality can be computed in polynomial time.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringTranslationSimilar Papers 제목 키워드 기반
Towards an Axiomatic Approach to Hierarchical Clustering of Measures
We propose some axioms for hierarchical clustering of probability measures and investigate their ramifications. The basic idea is to let the user stipulate the clusters for some elementary measures. This is done without …
ClusteringAxioms for graph clustering quality functions
We investigate properties that intuitively ought to be satisfied by graph clustering quality functions, that is, functions that assign a score to a clustering of a graph. Graph clustering, also known as network community…
ClusteringCommunity DetectionGraph ClusteringSanity Check for External Clustering Validation Benchmarks using Internal Validation Measures
We address the lack of reliability in benchmarking clustering techniques based on labeled datasets. A standard scheme in external clustering validation is to use class labels as ground truth clusters, based on the assump…
BenchmarkingClusteringClustering Redemption–Beyond the Impossibility of Kleinberg’s Axioms
Kleinberg (2002) stated three axioms that any clustering procedure should satisfy and showed there is no clustering procedure that simultaneously satisfies all three. One of these, called the consistency axiom, requires …
ClusteringCategorization Axioms for Clustering Results
Cluster analysis has attracted more and more attention in the field of machine learning and data mining. Numerous clustering algorithms have been proposed and are being developed due to diverse theories and various requi…
ClusteringGeneral Classification