Algorithms Seminar/Spring09

From ResearchWiki

Spring 2009: CS 7936: Clustering

Fri 10:45 - 12:05 | WEB 1460

Contents 1 Course Materials 2 Seminar format and grading 3 Participants 4 Schedule 5 Topics Not Covered 6 Useful Links 7 Paper Summaries 8 Past Semesters

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, PhD Student, School of Computing
• John Moeller, PhD 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
• Adam R. Teichert, MS Student, School of Computing
• Piyush Rai, PhD Student, School of Computing
• Jagadeesh Jagarlamudi, PhD Student, School of Computing
• Seth Juarez, PhD Student, School of Computing
• Jiarong Jiang, PhD Student, School of Computing
• Scott Alfeld, MS Student, School of Computing
• Thanh Nguyen, PhD Student, School of Computing
• John Meier, BS/MS Student, School of Computing
• Amit Goyal, PhD Student, School of Computing
• Pravin Chandrasekaran, MS Student, School of Computing
• Avishek Saha, 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	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
Meta-clustering
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

• Fall 2007: Approximate High Dimensional Geometry
• Spring 2008: The Geometry of Information Spaces
• Fall 2008: Randomization