Applied Mathematics Colloquium **SPECIAL TIME/LOCATION**

Monday February 25, 2013 3:00 PM

Cluster Trees, Near-Neighbor Graphs, and Continuum Percolation

Speaker: Sanjoy Dasgupta, Computer Science and Engineering, UC San Diego
Location: Guggenheim 133 (Lees-Kubota Lecture Hall)

What information does the clustering of a finite data set reveal about the underlying distribution from which the data were sampled? This basic question has proved elusive even for the most widely-used clustering procedures. One natural criterion is to seek clusters that converge (as the data set grows) to regions of high density. When all possible density levels are considered, this is a hierarchical clustering problem where the sought limit is called the "cluster tree". We give a simple algorithm for estimating this tree that implicitly constructs a multiscale hierarchy of near-neighbor graphs on the data points. We show that the procedure is consistent, answering an open problem of Hartigan. We also obtain rates of convergence, using a percolation argument that gives insight into how near-neighbor graphs should be constructed.

Series Applied Mathematics Colloquium Series

Contact: Sydney Garstang at x4555 sydney@caltech.edu
For more information visit: http://www.cms.caltech.edu