Timezone: »

 
Poster
Streaming k-means approximation
Nir Ailon · Ragesh Jaiswal · Claire Monteleoni

Mon Dec 07 07:00 PM -- 11:59 PM (PST) @
in Poster Session »

We provide a clustering algorithm that approximately optimizes the k-means objective, in the one-pass streaming setting. We make no assumptions about the data, and our algorithm is very light-weight in terms of memory, and computation. This setting is applicable to unsupervised learning on massive data sets, or resource-constrained devices. The two main ingredients of our theoretical work are: a derivation of an extremely simple pseudo-approximation batch algorithm for k-means, in which the algorithm is allowed to output more than k centers (based on the recent "k-means++"), and a streaming clustering algorithm in which batch clustering algorithms are performed on small inputs (fitting in memory) and combined in a hierarchical manner. Empirical evaluations on real and simulated data reveal the practical utility of our method.

[ PDF] 

Author Information

Nir Ailon (Technion)
Ragesh Jaiswal (Columbia University)
Claire Monteleoni (University of Colorado Boulder)

Claire Monteleoni is an associate professor of Computer Science at University of Colorado Boulder. Previously, she was an associate professor at George Washington University, and research faculty at the Center for Computational Learning Systems, at Columbia University. She did a postdoc in Computer Science and Engineering at the University of California, San Diego, and completed her PhD and Masters in Computer Science, at MIT. She holds a Bachelors in Earth and Planetary Sciences from Harvard. Her research focuses on machine learning algorithms and theory for problems including learning from data streams, learning from raw (unlabeled) data, learning from private data, and climate informatics: accelerating discovery in climate science with machine learning. Her work on climate informatics received the Best Application Paper Award at NASA CIDU 2010. In 2011, she co-founded the International Workshop on Climate Informatics, which is now in its fourth year, attracting climate scientists and data scientists from over 14 countries and 26 states.

More from the Same Authors