Measures of Clustering Quality: A Working Set of Axioms for Clustering Export

@inproceedings{citeulike:3680075, abstract = {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, ([1]) 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 [1]. 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 consistency. 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.}, author = {Ackerman, Margareta and Ben-David, Shai}, booktitle = {Proceedings of the 22nd Annual Conference on Neural Information Systems Processing}, citeulike-article-id = {3680075}, citeulike-linkout-0 = {http://books.nips.cc/papers/files/nips21/NIPS2008_0383.pdf}, comment = {A response to Kleinberg's impossibility result for clustering.}, keywords = {clustering}, posted-at = {2008-11-24 00:17:35}, priority = {4}, title = {Measures of Clustering Quality: A Working Set of Axioms for Clustering}, url = {http://books.nips.cc/papers/files/nips21/NIPS2008_0383.pdf}, year = {2008} }

TY - CONF ID - citeulike:3680075 L3 - citeulike-article-id:3680075 N2 - 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, ([1]) 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 [1]. 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 consistency. 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. TI - Measures of Clustering Quality: A Working Set of Axioms for Clustering T2 - Proceedings of the 22nd Annual Conference on Neural Information Systems Processing KW - clustering N1 - A response to Kleinberg's impossibility result for clustering. AU - Ackerman, Margareta AU - Ben-David, Shai PY - 2008/// UR - http://books.nips.cc/papers/files/nips21/NIPS2008_0383.pdf ER -