Tata Institute of Fundamental Research
Adaptive Sampling for k-means Clustering
Student Seminar
Speaker:
Amit Deshpande
Microsoft Research
Scientia, 196/36, 2nd Main,
Sadashivnagar, Bangalore 560080
Date:
Friday, 25 Sep 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
k-means clustering is a theoretically hard problem but in practice it is often solved efficiently using a simple heuristic due to Lloyd. In this talk, we will modify Lloyd's method to get a simple, fast algorithm for k-means clustering with provable guarantee, i.e., constant factor approximation. Our algorithm is randomized and improves upon a previous result by Arthur and Vassilvitskii (joint work with Ankit Aggarwal and Ravindran Kannan.)
| Speaker: | Amit Deshpande Microsoft Research Scientia, 196/36, 2nd Main, Sadashivnagar, Bangalore 560080 |
| Date: | Friday, 25 Sep 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
k-means clustering is a theoretically hard problem but in practice it is often solved efficiently using a simple heuristic due to Lloyd. In this talk, we will modify Lloyd's method to get a simple, fast algorithm for k-means clustering with provable guarantee, i.e., constant factor approximation. Our algorithm is randomized and improves upon a previous result by Arthur and Vassilvitskii (joint work with Ankit Aggarwal and Ravindran Kannan.)