Fast Global Kernel K-Means
Algorithms AIMech:FastGlobalKernelKMeans DRAFT
An incremental kernel clustering algorithm that chooses each new singleton seed by maximizing a computable lower bound on error reduction, then runs one local kernel k-means fit for that stage.
Identity Notes & Concept Scope
This is the Tzortzis-Likas2009 fast variant with its positive observation-weight extension. It maximizes a bound over datum seeds and performs one local fit per stage, rather than evaluating final errors for every seed or fitting a CMM exemplar shortlist. Maximizing the bound need not select the seed with greatest actual final improvement. Compared all 442 pinned AIO IDs, labels and scoped synonyms with all 492 prior native IDs, names and aliases; no normalized identity collision. Full searches of both checkouts include ignored and hidden files, returning 62 worktree and 62 main matched lines. All 47 distinct matched texts were inspected as neighboring method mentions, query/frontier references or rendered copies. Eleven annotated AIO nodes, eleven generated YAMLs and seven native neighbors were examined. Nine unchanged annotated nodes, their generated YAMLs, all 442 class labels and 139 semantic rows reuse byte-verified earlier readings; two additional annotated targets and eight new semantic rows were read (147 rows total). Absence is bounded to this pin and corpus.
Claims & Grounded Evidence
4 Claims
Mechanism
#weighted-kernel-local-fit
For a fixed PSD Gram matrix K, supplied cluster count M and positive observation weights a_i, represent each center as the weighted mean of its assigned RKHS features. For cluster C with A_C=sum_j_in_C a_j, compute squared distance K_ii - 2*sum_j_in_C a_j*K_ij/A_C + sum_j,l_in_C a_j*a_l*K_jl/A_C^2. Alternate synchronous nearest-center assignments and mean recomputation. Unit observation weights give unweighted kernel k-means. Scaling every a_i by the same positive constant preserves distances and fits while scaling the objective; these weights are not learned view weights.
Mechanism
#fast-seed-bound
At each stage after the one-cluster start, let d_i be the squared distance to the retained old feature mean. For each datum n compute b_n=sum_i a_i*max(d_i-(K_ii+K_nn-2*K_in),0). Select a maximizer, create the corresponding singleton initialization, and run one local kernel-k-means fit. Unit weights recover the unweighted criterion. Candidate-scoring work remains even though only one local fit is performed per stage.
Limitation
#bound-scope
For converged old assignments, positive residual cluster weights and well-defined exact nonempty local updates, the source bound is E_new<=E_old-b_n. Although removing the seed changes its previous cluster mean, a weighted RKHS comparison shows that this shift does not raise the aggregate comparison cost, so the bound extends to the displayed singleton-removal initialization under those conditions. It is a bound on one stage, not a global approximation guarantee or proof that the selected seed maximizes actual final improvement. Empty-cluster repairs, indefinite similarities or approximate updates need separate justification.
Scope
#graph-objective-specializations
For a symmetric nonnegative graph affinity A, ratio association uses unit observation weights and K=A. Normalized-cut optimization uses positive degrees d_i=sum_j A_ij as observation weights and K=D^(-1) A D^(-1). For fixed M these choices identify partition objective orderings, not all graph algorithms or their outputs. A sufficiently large shift lambda*I for ratio association, or lambda*D^(-1) for normalized cut, can ensure PSD. Either adds the partition-independent lambda*(N-M) to the corresponding weighted kernel objective while potentially changing local update paths. Zero-degree vertices require a convention. The source graph experiments used small shifts not necessarily ensuring PSD, so their observed convergence is not a general guarantee for indefinite similarities.
⚠️ Curated Limitations & Negative Results
- PSD kernels, positive cluster weight and well-defined nonempty updates are conditions for the RKHS distance and descent arguments. Arbitrary similarities or arbitrary sigmoid-kernel parameters do not automatically satisfy them. Ties, empty clusters and stopping need explicit implementation conventions.
- Dense Gram storage is quadratic in N. Kernel choice, supplied cluster count and initialization affect results. No global optimum, approximation ratio, universal empirical superiority or biological causal interpretation is asserted.
- The primary papers use particular synthetic, digit, face, expression or graph settings, chosen kernels and parameters, and supplied cluster counts. Their finite comparisons do not establish universal performance. No historical implementation or benchmark was reproduced.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | This fixed-kernel clustering algorithm performs the inspected unlabeled clustering task. The relation does not equate algorithm and task or assert an upstream subclass. KernelLayer, PCA, neural graph models and a nested cluster hierarchy have different scopes. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
global-source
|
Grigorios Tzortzis, Aristidis Likas
|
primary paper
full_text
|
ID: doi:10.1109/TNN.2009.2019722
sha256:7a5bbe6bfbb9…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-12T06:20:54Z
Updated: 2026-10-12T06:20:54Z
Source File:
data/curated/FastGlobalKernelKMeans.yaml