Multiway spectral clustering: a margin-based perspective

DOI10.1214/08-STS266MaRDI QIDQ908150zbMATH OpenFDO

Authors Zhihua Zhang, Michael Jordan

Publication date 3 February 2016

Published in Statistical Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.3768, https://projecteuclid.org/euclid.ss/1233153065

zbMATH Keywords

reproducing kernel Hilbert spacespectral clusteringgraph partitioningspectral relaxationGaussian intrinsic autoregressionlarge-margin classification

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: Spectral clustering is a broad class of clustering procedures in which an intractable combinatorial optimization formulation of clustering is "relaxed" into a tractable eigenvector problem, and in which the relaxed solution is subsequently "rounded" into an approximate discrete solution to the original problem. In this paper we present a novel margin-based perspective on multiway spectral clustering. We show that the margin-based perspective illuminates both the relaxation and rounding aspects of spectral clustering, providing a unified analysis of existing algorithms and guiding the design of new algorithms. We also present connections between spectral clustering and several other topics in statistics, specifically minimum-variance clustering, Procrustes analysis and Gaussian intrinsic autoregression.

Recommendations

• Consistency of spectral clustering
• Simple, direct and efficient multi-way spectral clustering
• Spectral clustering based on local PCA
• Modular-transform based clustering
• On clusterings: good, bad and spectral

Cites work

• scientific article; zbMATH DE number 3934272 (Why is no real title available?)
• scientific article; zbMATH DE number 954974 (Why is no real title available?)
• scientific article; zbMATH DE number 3673370 (Why is no real title available?)
• scientific article; zbMATH DE number 45848 (Why is no real title available?)
• scientific article; zbMATH DE number 3513115 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• scientific article; zbMATH DE number 1391247 (Why is no real title available?)
• scientific article; zbMATH DE number 5046126 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Consistency of spectral clustering
• Convexity, Classification, and Risk Bounds
• Generalization error for multi-class margin classification
• Graclus
• Graph Embeddings and Laplacian Eigenvalues
• Learning spectral clustering, with application to speech separation
• Lower Bounds for the Partitioning of Graphs
• Machine Learning: ECML 2004
• Matrix Analysis
• Multi-dimensional multivariate Gaussian Markov random fields with application to image processing
• On clusterings: good, bad and spectral
• Procrustes Problems
• The Geometry of Algorithms with Orthogonality Constraints

Cited in

(8)

• Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm
• Perturbation analysis for the normalized Laplacian matrices in the multiway spectral clustering method
• scientific article; zbMATH DE number 7255049 (Why is no real title available?)
• Modular-transform based clustering
• Cluster forests
• Non-negative and sparse spectral clustering
• The matrix ridge approximation: algorithms and applications
• Spectral clustering based on local PCA

Describes a project that uses

Uses Software

• Graclus
• spatial

This page was built for publication: Multiway spectral clustering: a margin-based perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908150)