http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=
Clustering is a useful method for learning the intrinsic structure of data. In this talk I will describe a novel, highly efficient approach to determine all salient clusters, at all different scales, and that builds them into a hierarchical structure. Our algorithm, Clustering by Weighted Aggregation, is derived from algebraic multi-grid solvers for physical systems. The algorithm finds, given pairwise similarities between data elements, an approximate solution to a normalized cut measure in a weighted graph in time that is linear in the number of edges in the graph and in the number of nodes when similarity neighborhoods are bounded. The algorithm detects the clusters by applying a recursive coarsening in which the minimization problem is represented with fewer and fewer variables producing an irregular pyramid. Each variable represents an aggregate of fine variables. As aggregates increase in size, their structures increase in complexity. Aggregates of various sizes, which may or may not overlap, are revealed as salient, without predetermining their number or scale. The coarsening procedure provides a platform in which statistics of the emerging aggregates can be computed, and then be used to further affect the aggregation of larger clusters, or in a top-down manner to reshape the boundaries of clusters. Finally, I will show examples in which the algorithm is applied to data from computer vision, graphics, and computational biology. Joint work with Ya’ara Goldschmidt, Meirav Galun, Ronen Basri and Achi Brandt.
See other events that are part of Brains & Machines Seminar Series Spring 2004
See other events happening in March 2004
