Kernel K-Means in R: Geometry Before Clusters

Kernel k-means replaces Euclidean distances in the original input space with squared distances in an implicit feature space.

It is useful when the geometry induced by a kernel is more appropriate than raw Euclidean geometry.

It does not make clusters objectively true or automatically linearly separable.

Kernel feature spaces

A positive semidefinite kernel satisfies

for some feature map $\phi$ into a Hilbert space $\mathcal H$.

Kernel methods work with inner products $k(x,z)$ without explicitly constructing $\phi(x)$.

Kernel k-means objective

Ordinary k-means minimizes within-cluster squared Euclidean distance.

Kernel k-means instead minimizes

The distance to a feature-space centroid can be written entirely in terms of kernel evaluations.

For point $x_i$ and cluster $C_c$,

That is the kernel trick applied to the k-means objective.

RBF kernel

A common choice is

The bandwidth parameter $\gamma$ controls the geometry.

If $\gamma$ is too small, most points look similar.

If $\gamma$ is too large, similarities become extremely local.

Cluster assignments can therefore change dramatically with bandwidth.

Scaling still matters

Using a kernel does not eliminate feature-scaling issues.

The RBF kernel depends on Euclidean distance before exponentiation.

If one feature has much larger numerical scale than the others, it can dominate $|x-z|^2$.

Standardization should be justified by the measurement scales, not applied automatically.

A corrected synthetic example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
library(kernlab)

set.seed(123)

theta <- seq(0, pi, length.out = 100)
upper <- cbind(cos(theta), sin(theta))
lower <- cbind(1 - cos(theta), 0.5 - sin(theta))

x <- rbind(upper, lower)
x <- x + matrix(rnorm(length(x), sd = 0.06), ncol = 2)
x_scaled <- scale(x)

fit <- kkmeans(
  x_scaled,
  centers = 2,
  kernel = "rbfdot",
  kpar = list(sigma = 1)
)

cluster_id <- as.integer(fit)
plot(x_scaled, col = cluster_id, pch = 19)

The old construction using $\sqrt{9-x^2}$ generated two noisy semicircles rather than intertwined spirals. The geometry should be described accurately.

Initialization

Kernel k-means remains a non-convex partitioning algorithm.

Different starts can lead to different local minima.

One reproducible run is not enough to establish stability.

Use multiple seeds and compare assignments or objective values.

Kernel validity

Not every arbitrary similarity function is a valid positive semidefinite kernel.

If a method assumes a kernel inner product, the kernel matrix should satisfy the required mathematical properties.

Domain-specific similarities may need spectral correction or a different clustering method if they are indefinite.

Choosing K

Kernelization does not solve the number-of-clusters problem.

Silhouette scores, stability, external usefulness, and subject-matter interpretation can all help, but no one criterion reveals a universally true K.

Validation

Internal validation in feature space is useful for comparing candidate kernel settings.

External validation is stronger when possible.

For customer segmentation, for example, test whether segments predict future behavior or treatment response rather than merely looking visually separated.

Complexity

A full kernel matrix requires $O(n^2)$ storage.

That can become the main limitation before the clustering algorithm itself.

Approximate kernels, Nyström methods, random Fourier features, or subsampling may be needed for large datasets.

Kernel k-means and spectral clustering

The two methods are closely related under particular graph and normalization choices.

That connection does not make them identical in every implementation.

Kernel k-means starts from a feature-space distortion objective, while spectral clustering is often derived from relaxed graph-partition objectives.

Conclusion

Kernel clustering is useful when a carefully chosen kernel expresses a better similarity geometry than raw Euclidean distance.

The key modeling decisions are

Those choices should be treated as part of the clustering model, not as implementation details.

References

• Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels.
• Dhillon, I. S., Guan, Y., & Kulis, B. (2004). Kernel k-means, spectral clustering and normalized cuts.