Kernel k-means: spectral clustering and normalized cuts

By Inderjit S. Dhillon, Yuqiang Guan, Brian Kulis. 2004

1,465 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Molecular Biology

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

In Molecular Biology

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “Recovering a pre-image is considered necessary in some applications such as image denoising using kernel PCA (Kwok and Tsang 2004, Kim et al. 2005) and visualizing the clustering solutions of a kernel-based clustering algorithm (Dhillon et al. 2004, Jegelka et al. 2009).”
Kernel Mean Estimation and Stein's Effect (2013, positive): “The kernel K-means algorithm performs clustering in feature space using mean functions as the representatives of the clusters [3].”
Facetnet: a framework for analyzing communities and their evolutions in dynamic networks (2008, methodology): “One effective method in this area is the spectral clustering algorithm [4, 5, 18, 25] where the eigenvectors of certain normalized similarity matrices are used for the clustering purpose.”
Kernel Methods and Machine Learning (2014, background): “[48, 117]), and density-estimation models (e.”
A survey of kernel and spectral methods for clustering (2008, methodology): “To show the direct equivalence between kernel and spectral clustering methods we introduce the weighted version of the kernel K-means [11].”
Foreground Focus: Unsupervised Learning from Partially Matching Images (2009, methodology): “1To further improve efficiency for larger datasets, we could employ the equivalent kernel k-means formulation developed in Dhillon et al. (2004), which also minimizes the normalized cut but does not require eigen-decomposition.”
Analyzing communities and their evolutions in dynamic social networks (2009, methodology): “For example, Flake et al. [2000] defined Web communities as “a set of sites that have more links to members of the community than to non-members,” and proposed algorithms to identify Web communities based on a maximum flow/minmum cut framework. Newman and Girvan [2004] defined a metric called modula”
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients (2015, methodology): “Spectral clustering has been shown to be equivalent to ﬁrst doing KPCA and then perform k -means algorithms on the embedding ( e.g. , [13]).”
Top 10 algorithms in data mining (2007, background): “[19] have shown a close connection between kernel k-means and spectral clustering.”
A survey of dimensionality reduction techniques (2014, background): “Some authors [Girolami2002, Dhillon2004, Yu2012] have proposed to use a non ‐ linear embedding of the input vectors   Φ x into a higher dimensional space (dimensionality expansion, instead of reduction), and then perform the vector quantization in this higher dimensional space (this kind of…”
Silhouette Analysis for Performance Evaluation in Machine Learning with Applications to Clustering (2021, methodology): “NMI is a supervised method, i.e., we need a training set for calculating NMI to evaluate the performance of a clustering method.”
Secrets of GrabCut and Kernel K-Means (2015, methodology): “We test our kernel-based segmentation (14) with fixed Gaussian kernel (KKM), its weighted version (wKKM) corresponding to basic Normalized Cuts, see [11], and adaptive bandwidth version (aKKM), see Sec.”
Weighted Graph Cuts without Eigenvectors A Multilevel Approach (2007, methodology): “Preliminary versions of our work have appeared in [9], [30].”
Image Clustering Using Local Discriminant Models and Global Integration (2010, background): “While the connection between K-means and NCut has been discovered in [ 7 ] in terms of a kernel view, this work presents another new perspective to understand and explain the relationships between K-means (or DisKmeans) and spectral clustering algorithms.”