PaperlayerView exact revision on arXiv

Source-linked AI summary

DK-GBMKKM: Dynamic Kernel-Space Granular-Ball Multiple Kernel $k$-Means Clustering

Xiaoyu Lian, Yuchao Zhang, Shuyin Xia, Siqi Zhong, Xuzhao Xiang

arXiv:2609.00647v1cs.LG

TL;DR

Multiple kernel k-means needs a more stable and scalable representation because sample-centric optimization is sensitive to noisy and boundary samples, while fixed input-space balls can conflict with evolving fused-kernel geometry. DK-GBMKKM dynamically generates balls in the current fused kernel space, alternates membership and kernel-weight updates, and constructs size-weighted positive-semidefinite ball kernels. Across 12 public datasets, it ranks first on all four average clustering metrics, with consistent gains over the second-best averages.

  • Problem

    Multiple kernel k-means remains sensitive to noisy and boundary samples and repeatedly operates on sample-scale kernel matrices, while fixed input-space balls may mismatch evolving fused-kernel geometry.

  • Method

    DK-GBMKKM dynamically generates granular balls in the current fused kernel space and alternates kernel-weight learning with granular-ball membership updates.

  • Results

    0.6717 ACC, 0.5929 NMI, 0.6848 Purity, and 0.4647 ARI are DK-GBMKKM's average results over 12 datasets, ranking first on all four metrics.

  • Takeaways & Limitations

    The method's leading averages and consistent gains across most datasets support its effectiveness, while revealing dependence on data geometry.

  • Takeaways & Limitations

    DK-GBMKKM is not uniformly superior on every dataset, with RMKKM and MKKM-SR remaining strongest on specific datasets or metrics.

Abstract

from arXiv · show

Multiple kernel $k$-means integrates complementary nonlinear similarities by learning a combination of base kernels. Its pointwise optimization, however, is sensitive to noisy and boundary samples and repeatedly operates on sample-scale kernel matrices. Granular-ball representations organize local sample groups into mesoscopic units, but granular balls generated once in the input space may be inconsistent with the fused-kernel geometry that evolves during multiple kernel learning. We propose dynamic kernel-space granular-ball multiple kernel $k$-means (DK-GBMKKM). The method generates granular balls in the current fused kernel space and alternates kernel-weight learning with granular-ball membership updates, allowing the representation to adapt to changes in the fused-kernel geometry. A sample-size-weighted granular-ball kernel is further constructed to preserve the contributions of balls of different sizes, and its positive semidefiniteness and related equivalence properties are established. Experiments on 12 public datasets demonstrate the strong overall clustering performance of DK-GBMKKM. The code has been open-sourced for reproducibility: https://github.com/lianxiaoyu724/DK-GBMKKM.

I. INTRODUCTION

Multiple kernel clustering improves nonlinear similarity modeling but remains sample-centric and costly, while input-space granular balls may not match evolving kernel-space geometry. DK-GBMKKM addresses these issues by dynamically updating kernel-space balls and jointly optimizing their structure, spectral representation, and kernel weights.

  • Motivation: Multiple kernel k-means learns task-adaptive similarities from several base kernels but remains sensitive to noisy, boundary, and outlying samples.Existing methods also repeatedly operate on large sample-level kernel matrices.
  • Granular-ball representation: Granular-ball computing replaces many samples with fewer mesoscopic units characterized by centers, radii, and sample coverage.The representation is described as improving efficiency, robustness, and interpretability.
  • Research gap: Input-space granular balls can mismatch kernel-space structure because nonlinear mappings may substantially change neighborhood relations.Fixed partitions also cannot adapt as kernel weights and fused-kernel geometry evolve.
  • Proposed method: DK-GBMKKM constructs and updates granular balls directly in the current fused kernel space while keeping the ball number fixed.This fused-kernel-driven mechanism aligns the representation with the geometry used for multiple kernel clustering.
  • Optimization and evaluation: DK-GBMKKM alternates updates of granular-ball structure, spectral representation, and kernel weights in compressed ball space.Experiments on 12 public datasets report performance exceeding seven representative methods across four clustering metrics.

II. DYNAMIC KERNEL-SPACE GRANULAR-BALL MULTIPLE KERNEL k-MEANS

DK-GBMKKM performs multiple kernel clustering on granular-ball units rather than directly on sample-level kernel matrices, using mesoscopic representations of local structure.

  • Mesoscopic representation: The method constructs multiple granular-ball kernels and clusters mesoscopic units encoding local structure.This replaces direct multiple kernel clustering on sample-level kernel matrices.

A. Motivation

Existing granular-ball multiple kernel methods build balls in input space even though clustering is optimized in fused kernel space, and fixed partitions cannot follow changing kernel weights. DK-GBMKKM generates balls in the current induced kernel space to address both mismatches.

  • Motivation: Input-space granular-ball methods create a space mismatch because clustering is optimized in the fused kernel space.Their ball boundaries may not reflect local density and cluster structure after nonlinear kernel mappings.
  • Motivation: DK-GBMKKM builds a fused kernel from current weights, generates kernel-space balls, and computes ball-level kernels before spectral embedding and weight learning.The framework then supports dynamic reassignment as the fused-kernel geometry changes.

B. Problem Formulation and Base Model

The base model defines granular balls in the RKHS of the current fused kernel, derives their geometry and consistency from kernel distances, and constructs size-weighted positive-semidefinite ball kernels for compressed clustering.

  • Kernel-space granular balls: A kernel-space granular ball consists of covered samples, size, center, radius, and a center-consistency measure in the current fused-kernel RKHS.Its center is the mean of mapped samples, although computations use kernel values without explicitly forming the center vector.
  • Center consistency: Kernel-space center consistency replaces unavailable label purity with radius-normalized density ratios based on mean and maximum radii.Singleton or zero-radius balls receive consistency 1.
  • Shared partition: The current fused kernel induces one granular-ball partition shared across all base kernels because fused-space center relations decompose into weighted base-kernel relations.The same sample index sets are therefore used for every base kernel.
  • Ball-kernel construction: The size-weighted granular-ball kernel preserves center similarity while encoding the number of samples represented by each ball.Symmetric square-root size scaling prevents larger balls from being underweighted.
  • Theoretical properties: The original n × n multiple-kernel representation becomes an M × M representation, and the fused granular-ball kernel remains positive semidefinite.These properties allow direct use in kernel clustering and multiple kernel learning.
  • Spectral representation: Ball-level spectral optimization projects sample-level spectral optimization onto the subspace induced by the granular-ball partition.Samples within one ball share an embedding vector scaled by n^-1/2.

C. Objective and Optimization of DK-GBMKKM

DK-GBMKKM alternates synchronized spectral and kernel-weight updates with fixed-count membership reassignment in the current fused kernel space. This keeps the granular-ball partition, weights, embedding, and objective aligned as the fused geometry evolves.

  • Objective and alternating optimization: The ball-level spectral embedding is obtained from the c largest eigenvectors of the current fused granular-ball kernel.The embedding is constrained by Z^⊤Z = I_c.
  • Objective and alternating optimization: For fixed spectral embedding, kernel weights are updated by solving a convex quadratic program over the probability simplex.Residuals are lower-bounded numerically when they approach zero.
  • Objective and alternating optimization: Each dynamic iteration recomputes the embedding and objective after the weight update, keeping all optimization variables in the same state.This synchronized block update precedes any membership update.
  • Dynamic membership update: Membership reassignment updates only sample memberships while keeping the number of balls fixed, repairs empty balls, and rebuilds the ball-level representations.Samples with large assignment distances are reassigned to repair empty balls.
  • Dynamic membership update: Alternating kernel-weight learning with fixed-count reassignment enables the partition to track the evolving fused kernel space.After convergence, the final ball-level embedding is lifted to the sample level, normalized, and clustered with Euclidean k-means.

III. EXPERIMENTAL DESIGN AND RESULTS

The experiments compare DK-GBMKKM with recent multiple kernel clustering baselines on 12 public datasets and assess convergence through objective-value changes.

  • Experimental design: DK-GBMKKM is compared with recent multiple kernel clustering baselines on 12 public datasets.The experiments use MATLAB R2025b.
  • Experimental design: Convergence is examined through changes in the DK-GBMKKM objective value.
  • Experimental design: All experiments were conducted in MATLAB R2025b.

A. Setup

The setup evaluates eight methods on 12 public datasets using standardized inputs, 12 base kernels, and four clustering metrics. Baselines share preprocessing, kernels, and cluster counts.

  • Datasets: Experiments cover 12 public datasets spanning gene expression, object, speech, and face data.Ground-truth labels determine the number of clusters and evaluation metrics only.
  • Datasets: Inputs are cleaned by zero-filling missing values, z-score standardization, and sample-wise ℓ2 normalization.Dataset statistics are provided in Table II of the Appendix.
  • Base kernels: The study constructs 12 base kernels: seven RBF, four polynomial, and one cosine kernel.
  • Compared methods and parameters: DK-GBMKKM is compared with seven representative baselines using the same preprocessing, 12 base kernels, and number of clusters.Baseline parameters follow recommended settings from the corresponding papers or public implementations.
  • Evaluation metrics: Clustering quality is measured by ACC, NMI, Purity, and ARI, with higher values indicating better performance.

B. Clustering Performance

DK-GBMKKM ranks first on all four average clustering metrics across 12 datasets and records the most dataset-level wins. Its advantage is consistent but not universal, with performance depending on data geometry.

  • Average performance: 0.6717 ACC, 0.5929 NMI, 0.6848 Purity, and 0.4647 ARI are DK-GBMKKM’s best average results across 12 datasets.These exceed the second-best averages by 0.0574, 0.0521, 0.0522, and 0.0590, respectively.
  • Average performance: DK-GBMKKM records the most dataset-level wins, indicating that its improvement is consistent rather than dataset-specific.
  • Dataset-level performance: DK-GBMKKM achieves the best results on all four metrics for orlraws10P, pixraw10P, warpAR10P, and warpPIE10P.
  • Dataset-level performance: On warpPIE10P, DK-GBMKKM improves over MKKM-SR by 0.2558 ACC, 0.1916 NMI, 0.2028 Purity, and 0.2402 ARI.
  • Dataset-level performance: DK-GBMKKM is not uniformly superior: RMKKM leads NMI and Purity on COIL20, while MKKM-SR remains competitive on lung discrete and ORL.The authors relate the varying benefit of dynamic updates to data geometry.

C. Convergence Analysis

The convergence analysis tracks objective changes during dynamic granular-ball reassignment across all 12 datasets. Objective changes approach zero quickly, with no observable late-stage oscillation under the tested settings.

  • The analysis records objective changes over the first 30 iterations on all 12 datasets, using a symmetric logarithmic scale for positive and negative changes.
  • After iteration 20, objective changes remain below 5 × 10−14 on every dataset, with no sustained oscillation above this scale.Under the current datasets and parameter settings, reassignment causes no observable late-stage objective oscillation.
  • Objective-change curves approach zero within the first few iterations.

IV. CONCLUSION

DK-GBMKKM dynamically constructs granular balls in the fused kernel space, couples ball-level multiple kernel learning with membership updates, and reduces repeated spectral computation to mesoscopic matrices. The method establishes fused- and base-kernel equivalence properties and reports experiments on 12 datasets, while retaining full sample kernels in its current implementation.

  • Method: DK-GBMKKM dynamically constructs and updates granular balls in the fused kernel space while keeping the ball number fixed.
  • Evaluation and scope: The experiments cover 12 public datasets, and the current implementation is not a linear-memory method because it retains full sample kernels.
  • Theoretical properties: A single fused-space partition is shared across all base kernels because fused-space center relations are weighted combinations of corresponding base-space relations.
  • Optimization: The algorithm alternates spectral embedding, residual-based kernel-weight updates, objective evaluation, and fixed-count sample reassignment with empty-ball repair.
  • Complexity: O(T(Pn^2 + M^3 + n^2 + nM)) time and O(Pn^2 + PM^2 + nM) space are reported, with M^3 replaceable by M^2c using a partial eigensolver.

APPENDIX H STATISTICAL TESTS AND SIGNIFICANCE ANALYSIS

Nonparametric testing rejects equal performance across the eight methods for all four metrics. DK-GBMKKM achieves the best average rank on every metric, with significant advantages over several baselines while other strong methods remain competitive.

  • Statistical testing: The Friedman and Iman–Davenport procedure ranks methods within each dataset, tests equal overall performance, and applies Nemenyi post hoc comparisons after rejection.Tied results receive average ranks; the analysis covers eight methods and 12 datasets.
  • Statistical testing: 3.71 × 10^-13, 6.27 × 10^-14, 7.20 × 10^-11, and 1.10 × 10^-13 are the Iman–Davenport p-values for ACC, NMI, Purity, and ARI, respectively.Each value is below 0.05, so equal performance is rejected for every metric.
  • Figures: Fig. 4 compares eight methods across 12 datasets using NMI, Purity, and ARI, complementing the ACC comparison.NMI is shown on top, Purity in the middle, and ARI at the bottom.
  • Average ranks: DK-GBMKKM records the best average ranks: 1.42 for ACC, 1.67 for NMI, 1.58 for Purity, and 1.42 for ARI.These ranks indicate that its advantage is consistent across datasets rather than driven by isolated datasets or metric scales.
  • Figures: Fig. 5 uses Nemenyi critical-difference diagrams with CD = 3.031; lower average ranks are better, and thick lines mark nonsignificant differences.DK-GBMKKM has the lowest average rank for ACC, ARI, Purity, and NMI.
  • Significance comparisons: Rank gaps exceed the critical difference against MKKM, GB-MKKM, and AASC for all four metrics, but differences from several strong baselines are mostly nonsignificant.The difference from RMKKM is significant only for ACC; SMKC, MKKM-SR, and SimpleMKKM remain competitive.
Loading 2609.00647v1…