A Statistical Framework for Clustering Representation Learning

Hassan Ashtiani, Shai Ben-David
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:900-909, 2015.

Abstract

We address the problem of communicating domain knowledge from a user to the designer of a clustering algorithm. We propose a protocol that is based on the user providing 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 so that $k$-means clustering under that representation 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-ashtiani15a, title = {A Statistical Framework for Clustering Representation Learning}, author = {Ashtiani, Hassan and Ben-David, Shai}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {900--909}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/ashtiani15a/ashtiani15a.pdf}, url = {https://proceedings.mlr.press/r13/ashtiani15a.html}, abstract = {We address the problem of communicating domain knowledge from a user to the designer of a clustering algorithm. We propose a protocol that is based on the user providing 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 so that $k$-means clustering under that representation 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Statistical Framework for Clustering Representation Learning %A Hassan Ashtiani %A Shai Ben-David %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-ashtiani15a %I PMLR %P 900--909 %U https://proceedings.mlr.press/r13/ashtiani15a.html %V R13 %X We address the problem of communicating domain knowledge from a user to the designer of a clustering algorithm. We propose a protocol that is based on the user providing 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 so that $k$-means clustering under that representation 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. %Z Reissued by PMLR on 04 October 2026.
APA
Ashtiani, H. & Ben-David, S.. (2015). A Statistical Framework for Clustering Representation Learning. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:900-909 Available from https://proceedings.mlr.press/r13/ashtiani15a.html. Reissued by PMLR on 04 October 2026.

Related Material