# Representation Learning for Clustering: A Statistical Framework

arXiv: https://arxiv.org/abs/1506.05900 · HTML: https://mlsanity.com/paper/1506.05900/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2015.

## Built on by (most cited first, 2 of 2)

- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [Unsupervised Optimisation of GNNs for Node Clustering](https://mlsanity.com/paper/2402.07845/) (2024)

## Abstract (arXiv)

We address the problem of communicating domain knowledge from a user to the designer of a clustering algorithm. We propose a protocol in which the user provides a clustering of a relatively small random sample of a data set. The algorithm designer then uses that sample to come up with a data representation under which k-means clustering results in a clustering (of the full data set) that is aligned with the user's clustering. We provide a formal statistical model for analyzing the sample complexity of learning a clustering representation with this paradigm. We then introduce a notion of capacity of a class of possible representations, in the spirit of the VC-dimension, showing that classes of representations that have finite such dimension can be successfully learned with sample size error bounds, and end our discussion with an analysis of that dimension for classes of representations induced by linear embeddings.