Date: Wed, 12 Apr 2000 09:05:15 -0400 From: Avrim Blum To: reinforcement@cs.cmu.edu Subject: Theory Seminar this Friday on clustering and fast approx SVD Santosh Vempala is giving this Friday's theory seminar, on clustering via fast approximate SVD-type methods. If all goes well, he'll give a demo on clustering web searches. Santosh is one of our former grad students, now on the faculty at MIT. (He's in town for Adam Kalai's thesis proposal.) -Avrim ======================================================================= Friday, April 14, 2000 3:30, Wean Hall 5409 Santosh Vempala, MIT Title: On Clusterings --- Good, Bad and Spectral. Abstract: Clustering, or partitioning into similar groups, is a classical problem in mathematics as well as in the applied sciences. The availability of vast amounts of data has revitalized research on the problem. There are two aspects to analyzing a clustering algorithm: (1) How good is the clustering produced? (quality)and (2) How fast can it be found? (speed). On the practical side, several clever heuristics have been invented. Theoreticians, meanwhile, have been busy analyzing quality measures that are seductively simple to define (e.g. k-median, min sum, min diameter, etc.). Both approaches have obvious shortcomings: the justification provided by practitioners is typically case-by-case and experimental (it works well on my data); the measures thus far analyzed by theoreticians are easy to fool, i.e. there are simple examples where it is clear what the right clustering is, but optimizing the measures defined produces undesirable solutions. We propose a new measure of the quality of a clustering. Then we analyze the quality of a popular clustering heuristic, spectral clustering, under this measure. Spectral clustering is the general technique of partitioning the rows of a matrix (say) according to their components in the top few singular vectors of the matrix. Our first result is that under some reasonable asumptions, the spectral algorithm finds nearly optimal solutions. Our second result, that spectral clustering can be made very fast, is based on randomized algorithms for approximating a given m x n matrix by a low-rank matrix. Standard methods to compute low-rank approximations via the singular value decomposition take time that is polynomial in m and n. This can be prohibitively expensive for applications such as information retrieval. In contrast, the running time of our first algorithm depends only on the quality of the desired approximation and not on the size of the matrix, but it assumes that the entries of the matrix can be sampled in a specific manner. Our second algorithm needs no assumptions and has a running time that is linear in the number of non-zero entries. The talk will be self-contained and will include a demo of clustering web searches in real-time. This is joint work with Alan Frieze (CMU), Ravi Kannan, Petros Drineas (Yale), and V.Vinay (IISc).