Global Kernel K-Means with Convex Mixture Models
Algorithms AIMech:ConvexMixtureInitializedGlobalKernelKMeans DRAFT
Aliases: CMM-Initialized Global Kernel K-Means
An incremental kernel clustering algorithm that fits a convex mixture over datum exemplars once, restricts each new-cluster seed search to its selected high-weight exemplars, and retains the lowest-error local kernel k-means fit.
Identity Notes & Concept Scope
This is the Tzortzis-Likas2009 global kernel k-means with CMM procedure, including its positive observation-weight extension. It uses mixture weights to restrict initialization candidates, while final partitions optimize kernel variance over all observations. It is not the original CMM hard-clustering output, all-datum global search, fast bound maximization, or multiview mixture weighting. 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
5 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
#mixture-candidate-fit
For a supplied positive beta, set S_ij=exp(-beta*(K_ii+K_jj-2*K_ij)). With empirical p_i=a_i/sum_l a_l and positive simplex q over eligible exemplars, form z_i=sum_j S_ij*q_j and update q_j<-q_j*sum_i p_i*S_ij/z_i. The unweighted case has p_i=1/N. Fit this finite positive-affinity log-mixture criterion once, then select the P highest-weight exemplars. The source stops when their identities and ordering stay unchanged for a number of consecutive iterations, rather than requiring objective convergence; that iteration count and tie policies need specification.
Mechanism
#restricted-global-stages
Starting from one cluster, for each k=2,...,M try each of the selected P exemplar data as a new singleton removed from its previous group, run local kernel k-means on all N observations, and retain the least-error fit. The source recommends M<P much smaller than N when useful, with P supplied. Restricting seeds reduces local fits but does not guarantee the same trajectory or objective as all-datum global search; singleton-source and later empty clusters still require conventions.
Limitation
#mixture-scale-and-stopping
The source beta reference is N*H(p)/sum_ij p_i*distance(i,j)^2, reducing to N^2*log(N)/sum_ij distance(i,j)^2 for uniform p; it is an empirical scale guide and is undefined for a zero denominator. Stable top-P ranking does not certify an optimized mixture or globally optimal final partition. The finite log-affinity criterion is meaningful without assuming a normalized Gaussian density on an arbitrary RKHS; atomic-to-continuous KL language needs a common measure. Duplicate zero-distance observations also qualify the appendix identification of zero-distortion rate with H(p).
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