Clustering with Interactive Feedback
Abstract
In this paper, we initiate a theoretical study of the problem of clustering data under interactive feedback. We introduce a query-based model in which users can provide feedback to a clustering algorithm in a natural way via split and merge requests. We then analyze the "clusterability" of different concept classes in this framework -- the ability to cluster correctly with a bounded number of requests under only the assumption that each cluster can be described by a concept in the class -- and provide efficient algorithms as well as information-theoretic upper and lower bounds.
Cite
Text
Balcan and Blum. "Clustering with Interactive Feedback." International Conference on Algorithmic Learning Theory, 2008. doi:10.1007/978-3-540-87987-9_27Markdown
[Balcan and Blum. "Clustering with Interactive Feedback." International Conference on Algorithmic Learning Theory, 2008.](https://mlanthology.org/alt/2008/balcan2008alt-clustering/) doi:10.1007/978-3-540-87987-9_27BibTeX
@inproceedings{balcan2008alt-clustering,
title = {{Clustering with Interactive Feedback}},
author = {Balcan, Maria-Florina and Blum, Avrim},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2008},
pages = {316-328},
doi = {10.1007/978-3-540-87987-9_27},
url = {https://mlanthology.org/alt/2008/balcan2008alt-clustering/}
}