Kernel K-Means
Algorithms AIMech:KernelKMeans DRAFT
Aliases: Kernelized K-Means
A clustering algorithm that alternates nearest-feature-mean assignments and mean updates to minimize within-cluster squared distances in a kernel-defined feature space, with an observation-weighted extension.
Identity Notes & Concept Scope
This record covers the fixed-kernel Lloyd procedure and its positive observation-weight parameterization. Linear kernels with unit weights recover input-space k-means; general valid kernels need not give the same partition. It does not specify the incremental global, fast or CMM seed-selection procedures, learn multiview kernel weights, or perform kernel PCA. Weighted and unit-weight cases share the same parameterized update rather than receiving duplicate local IDs. 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.
Scope
#discrete-versus-spectral-relaxation
With W=diag(a), the objective is tr(W*K)-tr(Y^T*W^(1/2)*K*W^(1/2)*Y), where the nonzero indicator entries are Y_ij=sqrt(a_i)/sqrt(A_Cj). Replacing that discrete indicator constraint by arbitrary orthonormal columns yields a leading-eigenvector relaxation. Discretizing its solution need not attain the best discrete objective; the resulting partition can instead initialize further kernel k-means. An objective connection is not equality of all spectral and kernel-k-means algorithms.
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
#descent-and-cost
Exact assignment and mean updates do not increase the nonnegative PSD-kernel objective, but initialization can lead to different fixed points and need not yield a global optimum. Unspecified tie and empty-cluster handling prevents an unconditional termination or unique-result claim. With a dense Gram matrix and cached cluster terms, the source describes quadratic work per local pass in addition to kernel construction; spectral initialization and optional triangle-distance pruning are separate choices.
⚠️ 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
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
core-source
|
Inderjit S. Dhillon, Yuqiang Guan, Brian Kulis
|
primary paper
full_text
|
sha256:48c2db70020e…
|
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/KernelKMeans.yaml