Clustering Redemption–Beyond the Impossibility of Kleinberg’s Axioms
Authors: Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Kleinberg [20] stated three axioms that any clustering procedure should satisfy and showed there is no clustering procedure that simultaneously satisfies all three. In this work, we take a different approach, based on the observation that the consistency axiom fails to be satisfied when the correct number of clusters changes. We modify this axiom by making use of cost functions to determine the correct number of clusters, and require that consistency holds only if the number of clusters remains unchanged. We show that single linkage satisfies the modified axioms, and if the input is well-clusterable, some popular procedures such as k-means also satisfy the axioms, taking a step towards explaining the success of these objective functions for guiding the design of algorithms. |
| Researcher Affiliation | Academia | Vincent Cohen-Addad Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 vincent.cohen-addad@lip6.fr Varun Kanade: University of Oxford varunk@cs.ox.ac.uk Frederik Mallmann-Trenn; MIT mallmann@mit.edu |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not mention using datasets for empirical experiments, therefore no public dataset information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments, thus no dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, thus no software dependencies are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no specific experimental setup details are provided. |