Research map / Learning theory and algorithms / Clustering
Unified K-Means Clustering with Label-Guided Manifold Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a centerless, label-guided manifold-learning reformulation of K-Means (with kernel and fuzzy variants) that uses a cluster indicator matrix to build the similarity structure, adds an l2,1-norm balance regularizer, and evaluates four distance metrics on toy and ten benchmark datasets.
Problem
K-Means depends on centroid initialization, struggles with nonlinearly separable/manifold-structured data, and tends to produce unbalanced clusters.
Approach
Rewrites the K-Means objective as a pairwise-distance manifold term tr(G^T D G) with G = F P^{-1/2}, eliminating centroids; adds an l2,1-norm balance regularizer on the indicator matrix and four distance choices (Euclidean, KNN, Gaussian kernel, low-pass filter) to handle nonlinear structure.
Key results
- On Palm, the low-pass filter variant (Our-LF) reaches ACC 0.9055 vs. 0.8405 for the best baseline K-sum.
- On CMUPIE, Our-LF reaches ACC 0.6341 vs. 0.2150 for the best baseline K-sum.
- On the 400-point no-structure toy set with two clusters, Our-LF gives sizes 201/199 with SSe=2, versus SSe=162 for K-Means.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · CMUPIE | ACC: 0.2150 -> 0.6341 | Helped |
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · digits | ACC: 0.4368 -> 0.5073 | Helped |
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · FERET | ACC: 0.3121 -> 0.3257 | Helped |
| Use Euclidean distance instead of the strongest baseline's distance | Unified K-Means · Mpeg7 | ACC: 0.5393 -> 0.5714 | Helped |
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · olivetti | ACC: 0.4900 -> 0.8322 | Helped |
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · Palm | ACC: 0.8405 -> 0.9055 | Helped |
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · USPS | ACC: 0.6872 -> 0.8450 | Helped |
| Use K-nearest neighbor distance instead of the strongest baseline's distance | Unified K-Means · Pendigits | ACC: 0.7859 -> 0.8579 | Helped |
| Use K-nearest neighbor distance instead of the strongest baseline's distance | Unified K-Means · PEAL | ACC: 0.8770 -> 0.8919 | Helped |
| Use low-pass filtering distance instead of the strongest baseline's distance | Unified K-Means · STL10 | ACC: 0.9422 -> 0.9539 | Helped |
Surprising findings
- On STL10 the low-pass filter variant (ACC 0.9539) is only modestly above RKM (0.9422), while K-sum and others are close, indicating gains are dataset-dependent.
- On digits, the ACC of K-sum (0.1390) is far below its NMI (0.3416), and Our-LF is worse than Our-KNN on Mpeg7 and digits, suggesting metric-specific behavior.
Limitations
- Balance regularizer only yields approximate balance and relies on a Taylor-linearized l2,1 optimization
- Hyperparameters (lambda, sigma, a, K) are chosen per dataset and not shown to be robust
- Evaluated mainly on small image benchmarks with only six comparison methods
Experimental setup
Datasets: CMUPIE digits FERET Mpeg7 olivetti Palm1 Pendigits PEAL STL10 USPS
Benchmarks: CMUPIE digits FERET Mpeg7 olivetti Palm1 Pendigits PEAL STL10 USPS
Metrics: ACC NMI Purity SSe
Baselines: K-Means KKM RKM CDKM K-sum K-sum-x
Builds on: K-Means Kernel K-Means Fuzzy K-Means K-sum CDKM
Closest papers by meaning
- Large Scale Manifold Balanced Clustering (ICML 2026 · similarity 0.94)
- Efficient Clustering Based On A Unified View Of $K$-means And Ratio-cut (NeurIPS 2020 · similarity 0.88)
- Fast k-means Seeding Under The Manifold Hypothesis (ICML 2026 · similarity 0.87)
- Multiple Kernel k-Means Clustering with Matrix-Induced Regularization (AAAI 2016 · similarity 0.86)
- Multiple Kernel Clustering with Kernel k-Means Coupled Graph Tensor Learning (AAAI 2021 · similarity 0.86)
- Learning-Augmented $k$-means Clustering (ICLR 2022 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.