Algorithms Seminar/Spring09

From ResearchWiki

Jump to: navigation, search

Spring 2009: CS 7936: Clustering

Fri 10:45 - 12:05 | WEB 1460


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)



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 Adam
Jan 30 Hierarchical Methods 1 2; (This chapter from the IR book) Avishek
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 Jagadeesh
Feb 13 Spectral Clustering; Link on Wikipedia Applications of Graph Laplacians Nathan
Feb 20 Spectral Clustering; Link on Wikipedia Applications of Graph Laplacians (continued) Thanh
Clustering as model building
Feb 27 Gaussian Mixture Models and EM, a two-round variant for Gaussians Piyush
Mar 6 Information-theoretic clustering: IB, RIC Arvind
Mar 13 Choosing k: the elbow method, the A,B,D information criteria, and an information-theoretic approach (how humans estimate k) John M & Pravin C
Large-Data clustering
Mar 27 BIRCH and CURE Raj Varma
Apr 3 Stream Clustering; Better Streaming Algorithms; Clustering Data Streams Amit
Comparing Clusterings
Apr 10 Metrics on Clusterings Comparing Clusterings - an information based distance Ruihong
Apr 17 Consensus Clustering : Cluster Ensembles, Approximations for Consensus Clustering?, Parasaran
Apr 24 Axioms of Clustering: Problems, and a working set Seth
May 1 Cluster Stability; Sober look at Cluster Stability; Stability for Finite Samples Jiarong

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
  • "reclustering": given a clustering, find a new one that has some relationship to it.
  • biclustering (or co-clustering): cluster the rows and columns of a matrix.
  • Clustering with Outliers

Useful Links

NIPS 2005 workshop on Theoretical Foundations of Clustering

Paper Summaries

Past Semesters

Personal tools