Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, November 03, 2005, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Ulrike von Luxburg (Fraunhofer IPSI, Darmstadt)

Clustering is a basic tool in exploratory data analysis which tries to identify meaningful groups among given data points. As for all sample based algorithms it is an important question whether a clustering algorithm is consistent: the more data points we get, the more stable and reliable the constructed partition should be. We want to discuss the question of consistency for the class of spectral clustering algorithms. Starting with a similarity graph representing the sample points, those algorithms use the first eigenvectors of the graph Laplacian matrix to construct a partition of the data points. By combining methods from graph theory, functional analysis, and empirical process theory we can show that different versions of the Laplace matrix (``normalized'' or ``unnormalized'') have very different large sample behavior: while the spectral properties of the normalized Laplacian always converge for increasing sample size, for the unnormalized Laplacian the same is only true under strong additional requirements which are often not satisfied in practice. Hence, from a statistical point of view, we advocate the use of normalized rather than unnormalized graph Laplacians.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login