Global Kernel K-Means
Algorithms AIMech:GlobalKernelKMeans DRAFT
An incremental kernel clustering algorithm that adds a singleton datum cluster at each stage, runs kernel k-means from each such candidate partition, and retains the candidate with the smallest feature-space clustering error.
Identity Notes & Concept Scope
This is the Tzortzis-Likas2009 global kernel k-means procedure, including its positive observation-weight extension. It tries all datum candidates at each stage, unlike the fast one-candidate procedure or CMM-selected subset. Adding clusters is not an asserted nested hierarchy because local fitting can reassign all observations. The algorithm name does not certify a globally optimal partition. 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
#incremental-all-datum-search
Begin with all N observations in one cluster. For k=2,...,M, use the retained (k-1)-cluster partition and try each datum x_n as a new singleton, removing it from its previous cluster while retaining the other groups. Run the local kernel-k-means procedure from each candidate and retain the least final weighted error for this stage. Observation weights change means and errors, not the stated all-datum candidate enumeration.
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.
Limitation
#global-search-boundary
This is a greedy sequence of local fits: it explores datum seeds conditional on the previously retained partition, not every partition or feature-space center. The source explicitly leaves near-optimality theory as future work. A reproducible deterministic result requires fixed tie, candidate-order and stopping policies. Removing a seed from an already singleton source cluster makes that cluster empty; the paper pseudocode does not provide its handling. The all-candidate search multiplies local fitting cost across stages.
⚠️ 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/GlobalKernelKMeans.yaml