Clustering advice has collapsed into one sentence: throw it at K-means and move on. Try that on non-linear structure, the “two moons” dataset being the classic case, and K-means hands back a split that looks confident and is wrong. This is spectral clustering explained from the graph up, and why eigenvectors handle geometry that distance alone cannot.
Where K-means breaks on non-linear data
K-means assumes clusters are convex and isotropic, which means it goes looking for balls of data. Give it interlaced moons or concentric circles and it slices them right down the middle, because it measures Euclidean distance in the original feature space. On a non-linear manifold that assumption is the whole problem.
Spectral clustering ignores global shape. It reads the dataset as a graph, with nodes connected by local similarity, and the Laplacian matrix projects that graph into a lower-dimensional space where the awkward structures come apart along straight lines. As I argued in Machine Learning at Scale, matching the algorithm to the geometry of the data is half the job.
Building the Laplacian matrix by hand
The mechanism underneath is the eigendecomposition of the graph Laplacian, so it pays to build one yourself once before reaching for a library. Here is the naive version of the similarity matrix and the Laplacian in NumPy.
import numpy as np
from sklearn.metrics.pairwise import rbf_kernel
# 1. Build the Similarity (Affinity) Matrix using RBF Kernel
# gamma controls how "local" the similarity is
W = rbf_kernel(X, gamma=20)
# 2. Build the Degree Matrix (Sum of rows)
D = np.diag(np.sum(W, axis=1))
# 3. Construct the Laplacian Matrix
L = D - WThe Laplacian L = D - W pushes the algorithm toward groups that are strongly connected inside and weakly connected to everything else. Put another way, it minimizes the cut between clusters.
What the eigenvectors give you
With L in hand, run the eigendecomposition. The smallest eigenvectors, leaving out the one that belongs to the zero eigenvalue, trace the cluster boundaries. Take k of them and you have a new feature space. It is dimensionality reduction with one job: making the final K-means pass easy.
# 4. Eigendecomposition
eigenvalues, eigenvectors = np.linalg.eigh(L)
# 5. Select the k smallest eigenvectors (excluding the first one)
k = 2
U = eigenvectors[:, :k]
# Now we run K-means on the reduced space U
from sklearn.cluster import KMeans
labels = KMeans(n_clusters=k).fit_predict(U)The eigengap heuristic is how you pick k. Look for a clear jump between successive eigenvalues. It is a sturdier answer than the elbow plot people squint at with plain K-means.
Gamma is the parameter that will bite you
In production the gamma parameter in the affinity kernel is the hard part. Set it too small and everything looks similar, so you get one blob. Set it too high and only near-identical points stay connected. The official Scikit-learn documentation is where I go for the tuning details.
If spectral clustering work is eating up your dev hours, I can take it on. I have been wrestling with WordPress and complex backend logic since the 4.x days.
What to do with this
Spectral clustering is graph theory meeting linear algebra to reach problems that distance-based algorithms cannot touch. So stop pushing K-means into spaces where it does not belong. Build the Laplacian, watch the eigengap, and run the final K-means on the eigenvectors instead of the raw features.
