Relating clustering stability to properties of cluster boundaries (2009)
Shai Ben-david, Ulrike Von Luxburg
In this paper, we investigate stability-based methods for cluster model selection, in particular to select the number K of clusters. The scenario under consideration is that clustering is performed...
Ulrike Von Luxburg, Aus Tübingen, Von Fakultät, Iv Elektrotechnik Informatik, Vorsitzender Prof, Dr. F. Wysotzki, ...
vorgelegt von
Ecole Nationale des Ponts et Chaussées (2008)
Matthias Hein, Jean-yves Audibert, Ulrike Von Luxburg, Sanjoy Dasgupta
Given a sample from a probability measure with support on a submanifold in Euclidean space one can construct a neighborhood graph which can be seen as an approximation of the submanifold. The graph...
Ulrike Von Luxburg, Stefanie Jegelka, Sébastien Bubeck, Michael Kaufmann
Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the...
Ulrike Von Luxburg, Stefanie Jegelka, Sébastien Bubeck, Michael Kaufmann
Clustering is often formulated as a discrete optimization problem. The objective is to find, among all partitions of the data set, the best one according to some quality measure. However, in the...
◮ Stability for model selection- general principle ◮ Literature review: how is it used in practice? ◮ Criticism from theoretical point of view: does not always do what people believe? ◮ Three...
Cluster Identification in Nearest-Neighbor Graphs (2007)
Markus Maier, Matthias Hein, Ulrike Von Luxburg, Markus Maier, Matthias Hein, Ulrike Von Luxburg
Abstract. Assume we are given a sample of points from some underlying distribution which contains several distinct clusters. Our goal is to construct a neighborhood graph on the sample points such...
A sober look at clustering stability (2006)
Shai Ben-david, Ulrike Von Luxburg, Dávid Pál
Abstract. Stability is a common tool to verify the validity of sample based algorithms. In clustering it is widely used to tune the parameters of the algorithm, such as the number k of clusters. In...
From graphs to manifolds - weak and strong pointwise consistency of graph Laplacians (2005)
Matthias Hein, Jean-yves Audibert, Ulrike Von Luxburg
Abstract. In the machine learning community it is generally believed that graph Laplacians corresponding to a finite sample of data points converge to a continuous Laplace operator if the sample size...
From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians (2005)
Matthias Hein, Jean-yves Audibert, Ulrike Von Luxburg
In the machine learning community it is generally believed that graph Laplacians corresponding to a finite sample of data points converge to a continuous Laplace operator if the sample size...
Towards a statistical theory of clustering (2005)
Ulrike Von Luxburg, Shai Ben-david
Abstract. The goal of this paper is to discuss statistical aspects of clustering in a framework where the data to be clustered has been sampled from some unknown probability distribution. Firstly,...
Limits of spectral clustering (2005)
Ulrike Von Luxburg, Olivier Bousquet, Mikhail Belkin
An important aspect of clustering algorithms is whether the partitions constructed on finite samples converge to a useful clustering of the whole data space as the sample size increases. This paper...
Statistical learning with similarity and dissimilarity functions / (2004)
Zugl.: Berlin, Techn. University, Diss. 2004.
A compression approach to support vector model selection (2004)
Ulrike Von Luxburg, Olivier Bousquet, Bernhard Schölkopf
This report is available in PDF–format via anonymous ftp at
A compression approach to support vector model selection (2004)
Ulrike Von Luxburg, Olivier Bousquet, Bernhard Schölkopf
Editor: John Shawe-Taylor In this paper we investigate connections between statistical learning theory and data compression on the basis of support vector machine (SVM) model selection. Inspired by...
Limits of spectral clustering (2004)
Ulrike Von Luxburg, Mikhail Belkin, Ulrike Von Luxburg, Mikhail Belkin, Olivier Bousquet
Abstract. Consistency is a key property of statistical algorithms, when the data is drawn from some underlying probability distribution. Surprisingly, despite decades of work, little is known about...
Limits of spectral clustering (2004)
Ulrike Von Luxburg, Mikhail Belkin, Olivier Bousquet
Consistency is a key property of statistical algorithms when the data is drawn from some underlying probability distribution. Surprisingly, despite decades of work, little is known about consistency...
On the convergence of spectral clustering on random samples: the normalized case (2004)
Ulrike Von Luxburg, Olivier Bousquet, Mikhail Belkin
Abstract. Given a set of n randomly drawn sample points, spectral clustering in its simplest form uses the second eigenvector of the graph Laplacian matrix, constructed on the similarity graph...
Limits of spectral clustering (2004)
Ulrike Von Luxburg, Ulrike Von Luxburg
Abstract. In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra...
On the convergence of spectral clustering on random samples: the normalized case (2004)
Ulrike Von Luxburg, Olivier Bousquet, Mikhail Belkin
Abstract. Given a set of n randomly drawn sample points, spectral clustering in its simplest form uses the second eigenvector of the graph Laplacian matrix, constructed on the similarity graph...
Limits of spectral clustering (2004)
Ulrike Von Luxburg, Olivier Bousquet, Mikhail Belkin
An important aspect of clustering algorithms is whether the partitions constructed on finite samples converge to a useful clustering of the whole data space as the sample size increases. This paper...
Distance-based classification with lipschitz functions (2003)
Ulrike Von Luxburg, Olivier Bousquet, Kristin Bennett, Nicolò Cesa-bianchi
The goal of this article is to develop a framework for large margin classification in metric spaces. We want to find a generalization of linear decision functions for metric spaces and define a...
Distance-based classification with lipschitz functions (2003)
Ulrike Von Luxburg, Olivier Bousquet
Abstract. The goal of this article is to develop a framework for large margin classification in metric spaces. We want to find a generalization of linear decision functions for metric spaces and...
Distance-based classification with lipschitz functions (2003)
Ulrike Von Luxburg, Olivier Bousquet, Kristin Bennett, Nicolò Cesa-bianchi
The goal of this article is to develop a framework for large margin classification in metric spaces. We want to find a generalization of linear decision functions for metric spaces and define a...