Spectral Relaxation for K-means Clustering

By Hongyuan Zha, Xiaofeng He, Chris H. Q. Ding, Ming Gu, Horst D. Simon. Neural Information Processing Systems, 2001

733 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/01cbff216f2888f96151fb490338af40a09a0c30

How researchers see this paper

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

Citations in the corpus

Supervised patient similarity measure of heterogeneous patient records (2012, unknown): “(Ky Fan)[31].”
Evolutionary spectral clustering by incorporating temporal smoothness (2007, methodology): “They have been successfully applied to many areas such as document clustering [22, 15], imagine segmentation [19, 21], and Web/blog clustering [9, 18].”
Weighted Graph Cuts without Eigenvectors A Multilevel Approach (2007, result): “In this paper, we generalize and extend recent results [8], [9], [10], [11] on connections between vector-based and graph-based clustering to provide a unifying mathematical connection between kernel k-means and graph clustering objectives.”
Orthogonal nonnegative matrix t-factorizations for clustering (2006, methodology): “In fact, PCA is effectively doing K-means clustering[8, 34].”
Minimum Sum-Squared Residue Co-Clustering of Gene Expression Data (2004, background): “Minimizing the squared residues can be viewed as certain constrained trace maximization problems [19].”
Spectral Clustering for Speech Separation (2009, background): “The term e⊤r fs simply counts the number of data points which belong to the r-th cluster of E and the s-th cluster of F.”
Spectral Embedded Clustering: A Framework for In-Sample and Out-of-Sample Spectral Clustering (2011, methodology): “Spectral relaxation can also be used to solve the K -means clustering problem [41].”
Convex and Semi-Nonnegative Matrix Factorizations (2010, methodology): “that this is identical to (kernel-) K-means clustering ( 31 ; 32).”
Image Clustering Using Local Discriminant Models and Global Integration (2010, background): “In [40], it is proven that the objective function of K-means can be rewritten as:”
Deep k-Means: Re-Training and Parameter Sharing with Harder Cluster Assignments for Compressing Deep Convolutions (2018, methodology): “The spectral relaxation technique of k -Means was introduced in (Zha et al., 2002), by ﬁrst equivalently re-formulating sum-of-squares into a trace form with special constraints.”
Kernel k-means: spectral clustering and normalized cuts (2004, background): “In [14], the authors show that the traditional k -means objective function can be recast as a trace maximization problem of the Gram matrix for the original data.”
Document clustering by concept factorization (2004, methodology): “On the other hand, data partitioning methods decompose the data set into a given number of disjoint clusters which are usually optimal in terms of some prede.ned criterion functions.”
Learning Spectral Clustering, With Application To Speech Separation (2006, background): “The following theorem, inspired by the spectral relaxation of K-means presented by Zha et al. (2002), shows that the cost function can be interpreted as a weighted distortion measure: Theorem 3 Let W be a similarity matrix and let U =(u1, . . . , uP ) >, where up ∈ RR, be an orthonormal basis of…”
Name disambiguation in author citations using a K-way spectral clustering method (2005, methodology): “It was shown in [52] that the minimization of the above sum-of-square cost function can be formulated as a relaxed maximization problem where X T X = I k and X can be an arbitrary orthonormal matrix.”
Clustered Multi-Task Learning Via Alternating Structure Optimization (2011, background): “For a given W = [w1, · · · , wm], the sum-of-square error (SSE) function in K-means clustering is given by [19, 20]:”