Algorithms Seminar/Spring09
From ResearchWiki
Spring 2009: CS 7936: Clustering
Fri 10:45 - 12:05 | WEB 1460
Contents |
Course Materials
Seminar format and grading
- Student presentations on material selected by me. Please read, reflect upon, and follow these presentation guidelines
- One week before presentation is scheduled: student meets with me to discuss content of the presentation
- Day before presentation: student submits summary (either notes, or slides for presentation)
- Day before presentation: non-presenters submit questions on the material
- Day after presentation: questions are addressed by presenter or questioner (on the wiki talk page)
Participants
- Suresh Venkatasubramanian, Assistant Professor, School of Computing
- Parasaran Raman, MS Student, School of Computing
- John Moeller, Non-matriculated Student, School of Computing
- Nathan Gilbert, PhD Student, School of Computing
- Raj Varma Kommaraju, MS Student, School of Computing
- Ruihong Huang, PhD Student, School of Computing
- Hal Daumé III, Assistant Professor, School of Computing
- Arvind Agarwal, PhD Student, School of Computing
Schedule
| Date | Paper(s) | Presenter |
|---|---|---|
| Clustering via proximity | ||
| Jan 16 | Introduction to Clustering. Understanding different distance measures. | Suresh |
| Jan 23 | K-means: Lloyd's algorithm, worst-case behaviour, and an asymptotic analysis | |
| Jan 30 | Hierarchical Methods 1 2; (This chapter from the IR book) | Parasaran |
| Clustering via (dis)similarity | ||
| Feb 6 | Correlation clustering: the original paper, and an improved algorithm (only the clustering section). Also see Claire Mathieu's blog post | |
| Feb 13 | Spectral Clustering; Link on Wikipedia | Nathan |
| Clustering as model building | ||
| Feb 20 | EM, a two-round variant for Gaussians | Piyush |
| Feb 27 | Choosing k: the elbow method, the A,B,D information criteria, and an information-theoretic approach (how humans estimate k) | |
| Mar 6 | Information-theoretic clustering: IB, RIC | Arvind |
| Large-Data clustering | ||
| Mar 13 | BIRCH and CURE | |
| Mar 27 | Stream Clustering; Better Streaming Algorithms; Clustering Data Streams | |
| Comparing Clusterings | ||
| Apr 3 | Metrics on Clusterings | Ruihong |
| Apr 10 | Consensus Clustering : Cluster Ensembles, Approximations for Consensus Clustering?, | Parasaran |
| Meta-clustering | ||
| Apr 17 | Axioms of Clustering: Problems, and a working set | |
| Apr 24 | Cluster Stability; Sober look at Cluster Stability; Stability for Finite Samples | |
| May 1 | Clusterability and the efficency of clustering | |
Topics Not Covered
- Clustering with differently shaped clusters (subspace/projective clustering)
- methods for soft clustering
- high and low dimensional approximation schemes for clustering problems.
- manifold clustering
Paper Summaries
Past Semesters
- Fall 2007: Approximate High Dimensional Geometry
- Spring 2008: The Geometry of Information Spaces
- Fall 2008: Randomization
