Minimum spectral connectivity projection pursuit. Divisive clustering using optimal projections for spectral clustering

DOI10.1007/S11222-018-9814-6MaRDI QIDQ2329774zbMATH OpenOpenAlexFDO

Authors David P. Hofmeyr, Nicos G. Pavlidis, Idris Eckley

Publication date 18 October 2019

Published in Statistics and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.01546

zbMATH Keywords

dimension reductionmaximum marginprojection pursuitspectral clustering

Mathematics Subject Classification ID

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

Abstract: We study the problem of determining the optimal low dimensional projection for maximising the separability of a binary partition of an unlabelled dataset, as measured by spectral graph theory. This is achieved by finding projections which minimise the second eigenvalue of the graph Laplacian of the projected data, which corresponds to a non-convex, non-smooth optimisation problem. We show that the optimal univariate projection based on spectral connectivity converges to the vector normal to the maximum margin hyperplane through the data, as the scaling parameter is reduced to zero. This establishes a connection between connectivity as measured by spectral graph theory and maximal Euclidean separation. The computational cost associated with each eigen-problem is quadratic in the number of data. To mitigate this issue, we propose an approximation method using microclusters with provable approximation error bounds. Combining multiple binary partitions within a divisive hierarchical model allows us to construct clustering solutions admitting clusters with varying scales and lying within different subspaces. We evaluate the performance of the proposed method on a large collection of benchmark datasets and find that it compares favourably with existing methods for projection pursuit and dimension reduction for data clustering.

Recommendations

• scientific article; zbMATH DE number 7255049
• Optimality of spectral clustering in the Gaussian mixture model
• A variational approach to the consistency of spectral clustering
• Partitioning well-clustered graphs: spectral clustering works!
• Spectral clustering and its use in bioinformatics

Cites work

• 10.1162/153244303321897735
• A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
• Cluster Identification Using Projections
• Consistency of Cheeger and ratio graph cuts
• Empirical and theoretical comparisons of selected criterion functions for document clustering
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• scientific article; zbMATH DE number 1333614 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 967335 (Why is no real title available?)
• scientific article; zbMATH DE number 3061616 (Why is no real title available?)
• Incremental spectral clustering by efficiently updating the eigen-system
• Learning spectral clustering, with application to speech separation
• Manopt, a Matlab toolbox for optimization on manifolds
• Minimum density hyperplanes
• Nonsmooth optimization via quasi-Newton methods
• On the Convergence of Gradient Methods under Constraint
• Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
• Relative perturbation bounds for eigenvalues of symmetric positive definite diagonally dominant matrices
• The dip test of unimodality
• The Geometry of Algorithms with Orthogonality Constraints

Cited in

(2)

• scientific article; zbMATH DE number 7255049 (Why is no real title available?)
• Greedy recursive spectral bisection for modularity-bound hierarchical divisive community detection

Describes a project that uses

Uses Software

• UCI
• Manopt
• ElemStatLearn
• GradSamp

This page was built for publication: Minimum spectral connectivity projection pursuit. Divisive clustering using optimal projections for spectral clustering

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