Timezone: »
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.
Author Information
Shai Ben-David (University of Waterloo)
Margareta Ackerman (Florida State University)
Related Events (a corresponding poster, oral, or spotlight)
-
2008 Oral: Measures of Clustering Quality: A Working Set of Axioms for Clustering »
Tue. Dec 9th 03:45 -- 04:05 AM Room
More from the Same Authors
-
2016 Poster: Clustering with Same-Cluster Queries »
Hassan Ashtiani · Shrinu Kushagra · Shai Ben-David -
2016 Oral: Clustering with Same-Cluster Queries »
Hassan Ashtiani · Shrinu Kushagra · Shai Ben-David -
2015 : Domain Adaptation for Binary Classification »
Shai Ben-David -
2015 : Discussion Panel »
Tim van Erven · Wouter Koolen · Peter Grünwald · Shai Ben-David · Dylan Foster · Satyen Kale · Gergely Neu -
2015 : Clustering Is Easy When... »
Shai Ben-David -
2014 Poster: Incremental Clustering: The Case for Extra Clusters »
Margareta Ackerman · Sanjoy Dasgupta -
2013 Workshop: New Directions in Transfer and Multi-Task: Learning Across Domains and Tasks »
Urun Dogan · Marius Kloft · Tatiana Tommasi · Francesco Orabona · Massimiliano Pontil · Sinno Jialin Pan · Shai Ben-David · Arthur Gretton · Fei Sha · Marco Signoretto · Rajhans Samdani · Yun-Qian Miao · Mohammad Gheshlaghi azar · Ruth Urner · Christoph Lampert · Jonathan How -
2010 Poster: Towards Property-Based Classification of Clustering Paradigms »
Margareta Ackerman · Shai Ben-David · David R Loker -
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh -
2008 Workshop: New Challanges in Theoretical Machine Learning: Data Dependent Concept Spaces »
Maria-Florina F Balcan · Shai Ben-David · Avrim Blum · Kristiaan Pelckmans · John Shawe-Taylor -
2006 Poster: Analysis of Representations for Domain Adaptation »
John Blitzer · Shai Ben-David · Yacov Crammer · Fernando Pereira