Timezone: »
Poster
Incremental Clustering: The Case for Extra Clusters
Margareta Ackerman · Sanjoy Dasgupta
The explosion in the amount of data available for analysis often necessitates a transition from batch to incremental clustering methods, which process one element at a time and typically store only a small subset of the data. In this paper, we initiate the formal analysis of incremental clustering methods focusing on the types of cluster structure that they are able to detect. We find that the incremental setting is strictly weaker than the batch model, proving that a fundamental class of cluster structures that can readily be detected in the batch setting is impossible to identify using any incremental method. Furthermore, we show how the limitations of incremental clustering can be overcome by allowing additional clusters.
Author Information
Margareta Ackerman (Florida State University)
Sanjoy Dasgupta (UC San Diego)
More from the Same Authors
-
2020 : Q & A and Panel Session with Tom Mitchell, Jenn Wortman Vaughan, Sanjoy Dasgupta, and Finale Doshi-Velez »
Tom Mitchell · Jennifer Wortman Vaughan · Sanjoy Dasgupta · Finale Doshi-Velez · Zachary Lipton -
2019 Poster: An adaptive nearest neighbor rule for classification »
Akshay Balsubramani · Sanjoy Dasgupta · yoav Freund · Shay Moran -
2019 Spotlight: An adaptive nearest neighbor rule for classification »
Akshay Balsubramani · Sanjoy Dasgupta · yoav Freund · Shay Moran -
2018 Poster: Learning from discriminative feature feedback »
Sanjoy Dasgupta · Sivan Sabato · Nicholas Roberts · Akansha Dey -
2014 Poster: Optimal rates for k-NN density and mode estimation »
Sanjoy Dasgupta · Samory Kpotufe -
2013 Poster: Moment-based Uniform Deviation Bounds for $k$-means and Friends »
Matus J Telgarsky · Sanjoy Dasgupta -
2010 Poster: Towards Property-Based Classification of Clustering Paradigms »
Margareta Ackerman · Shai Ben-David · David R Loker -
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh -
2008 Poster: Measures of Clustering Quality: A Working Set of Axioms for Clustering »
Shai Ben-David · Margareta Ackerman -
2008 Oral: Measures of Clustering Quality: A Working Set of Axioms for Clustering »
Shai Ben-David · Margareta Ackerman