A Dep endence Maximization View of Clustering

A Dep endence Maximization View of Clustering
Le Song - National ICT Australia, Australia Alex Smola - National ICT Australia, Australia Arthur Gretton - MPI Tübingen, Germany Karsten M. Borgwardt - LMU München, Germany
We propose a family of clustering algorithms based on the maximization of dependence between the input variables and their cluster labels, as expressed by the Hilbert-Schmidt Independence Criterion (HSIC). Under this framework, we unify the geometric, spectral, and statistical dependence views of clustering, and subsume many existing algorithms as special cases (e.g. k -means and spectral clustering). Distinctive to our framework is that kernels can also be applied on the labels, which can endow them with particular structures. We also obtain a perturbation bound on the change in k -means clustering.

Le Song - National ICT Australia, Australia
Alex Smola - National ICT Australia, Australia
Arthur Gretton - MPI Tübingen, Germany
Karsten M. Borgwardt - LMU München, Germany

We propose a family of clustering algorithms based on the maximization of dependence between the input variables and their cluster labels, as expressed by the Hilbert-Schmidt Independence Criterion (HSIC). Under this framework, we unify the geometric, spectral, and statistical dependence views of clustering, and subsume many existing algorithms as special cases (e.g. k -means and spectral clustering). Distinctive to our framework is that kernels can also be applied on the labels, which can endow them with particular structures. We also obtain a perturbation bound on the change in k -means clustering.