A dependence maximization view of clustering

By Le Song, Alex Smola, Arthur Gretton, Karsten M. Borgwardt. 2007

120 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “The MMD has been applied extensively in many applications, namely, clustering (Jegelka et al. 2009), density estimation (Song et al. 2007a; 2008), (conditional) independence tests (Fukumizu et al. 2008, Doran et al. 2014, Chwialkowski and Gretton 2014), causal discovery (Sgouritsa et al. 2013, Chen…”
Multiview Consensus Graph Clustering (2019, methodology): “Later, inspired by co-training, many unsupervised multiview learning methods use the Hilbert-Schmidt independence criterion (HSIC) [12], [13] to learn a global similarity graph [14]–[18] or an embedding matrix [19].”
Learning shared subspace for multi-label dimensionality reduction via dependence maximization (2015, methodology): “HSIC is proposed for measuring the statistical dependence of random variables and has been applied successfully for data clustering [43] and supervised feature selection [44].”
Kernel Measures of Independence for non-iid Data (2008, methodology): “Analogous to iid HSIC, structured HSIC can be applied to non-iid data in applications such as independent component analysis [12], independence test [6], feature selection [15], clustering [14], and dimensionality reduction [13].”
Taxonomic Prediction with Tree-Structured Covariances (2013, methodology): “We establish the equivalence between taxonomies and tree structured covariance matrices, and show that the latter constitute a natural way to encode taxonomies in structured prediction problems (indeed, the HSIC is a regularizer for structured output SVM when taxonomies are used).”
Large-scale kernel methods for independence testing (2016, methodology): “HSIC has also been applied to clustering and learning taxonomies (Song et al. 2007; Blaschko and Gretton 2009), feature selection (Song et al.”
A Hilbert-Schmidt Dependence Maximization Approach to Unsupervised Structure Discovery (2008, methodology): “In recent work by (Song et al., 2007), it has been proposed to perform clustering by maximizing a HilbertSchmidt independence criterion with respect to a predefined cluster structure Y , by solving for the partition matrix, Π.”
Supervised principal component analysis: Visualization, classification and regression on subspaces and submanifolds (2011, methodology): “The HSIC has been widely used in many practical applications such as feature selection [25], feature extraction [26], and clustering algorithms [27].”
Discriminative Clustering by Regularized Information Maximization (2010, background): “[22] also view clustering as maximization of the dependence between the input variable and output label variable.”