Spectral Clustering Explained: How Eigenvectors Reveal Complex Cluster Structures

and eigenvectors are key concepts in linear algebra that also play a crucial role in data science and machine learning. Previously, we discussed how dimensionality reduction may be performed with eigenvalues and eigenvectors of the covariance matrix.

Today, we’re going to debate one other interesting application: How eigenvalues and eigenvectors may be used to perform spectral clustering, which works well with complex cluster structures.

In this text, we’ll explore how eigenvalues and eigenvectors make spectral clustering possible and why this method can outperform traditional K-means.

We’ll begin with an easy visualization that can show you the importance of spectral clustering and motivate you to proceed learning how spectral clustering may be performed with eigenvalues and eigenvectors.

Motivation for Spectral Clustering

An important solution to learn spectral clustering is to check it with a conventional clustering algorithm like K-means on a dataset where K-means struggles to perform well. 

Here, we use an artificially generated two-moon dataset where clusters are curved. The Scikit-learn algorithm generates two moons in 2-dimensional space. Then, we use Scikit-learn and algorithms to perform K-means and spectral clustering. Finally, we compare the cluster visualizations.

Making moon data

# Make moon data
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=400, noise=0.05,
                  random_state=0)

plt.figure(figsize=[4.2, 3])
plt.scatter(X[:,0], X[:,1], s=20)
plt.title("Original Moon Data")
plt.savefig("Moon data.png")

The unique dataset has two curved cluster structures called . That’s why we call it . 

Applying K-means to the moon data

# Apply K-means
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=2, random_state=0)

# Predict cluster index for every data point
labels_kmeans = kmeans.fit_predict(X)

# Visualize Clusters
plt.figure(figsize=[4.2, 3])
plt.scatter(X[:,0], X[:,1], c=labels_kmeans, s=20)
plt.title("K-Means Clustering")
plt.savefig("K-means.png")

K-means often groups the moon data incorrectly (it incorrectly mixes the info points).

Applying spectral clustering to the moon data

# Apply spectral clustering
from sklearn.cluster import SpectralClustering

spectral = SpectralClustering(n_clusters=2,
                              affinity='nearest_neighbors',
                              random_state=0)

# Predict cluster index for every data point
labels_spectral = spectral.fit_predict(X)

# Visualize Clusters
plt.figure(figsize=[4.2, 3])
plt.scatter(X[:,0], X[:,1], c=labels_spectral, s=20)
plt.title("Spectral Clustering")
plt.savefig("Spectral.png")

Now the info points are appropriately assigned to the moons, which look much like the unique data. Spectral clustering works well on complex cluster structures. It’s because the eigenvectors of the Laplacian matrix allow it to detect complex cluster structures.

To this point, we now have implemented spectral clustering using the built-in algorithm in Scikit-learn. Next, you’ll learn find out how to implement spectral clustering from scratch. This can enable you understand how eigenvalues and eigenvectors work behind the scenes within the algorithm.

What’s Spectral Clustering?

Spectral clustering groups data points based on their similarities as a substitute of distances. This enables it to disclose non-linear, complex cluster structures without following the assumptions of traditional k-means clustering.

The intuition behind performing spectral clustering is as follows:

Steps to perform spectral clustering

1. Get data
2. Construct the similarity matrix
3. Construct the degree matrix
4. Construct the Laplacian matrix (graph Laplacian)
5. Find eigenvalues and eigenvectors of the Laplacian matrix. Eigenvectors reveal cluster structure (how data points group together), acting as recent features, and eigenvalues indicate the strength of cluster separation
6. Select an important eigenvectors to embed the info in a lower dimension (dimensionality reduction)
7. Apply K-means on the brand new feature space (clustering)

Spectral clustering combines dimensionality reduction and K-means clustering. We embed the info in a lower-dimensional space (where clusters are easier to separate) after which perform K-means clustering on the brand new feature space. In summary, K-means clustering works in the unique feature space while spectral clustering works in the brand new reduced feature space.

Implementing Spectral Clustering — Step by Step

We’ve summarized the steps of performing spectral clustering with eigenvalues and eigenvectors of the Laplacian matrix. Let’s implement these steps with Python. 

1. Get data

We’ll use the identical data as previously used.

from sklearn.datasets import make_moons

X, y = make_moons(n_samples=400, noise=0.05,
                  random_state=0)

2. Construct the similarity (affinity) matrix

Spectral clustering groups data points based on their similarities. Due to this fact, we want to measure similarity between data points and include these values in a matrix. This matrix known as the . Here, we measure similarity using a .

If you’ve got n number of information points, the form of W is (n, n). Each value represents similarity between two data points. Higher values within the matrix mean points are more similar.

from sklearn.metrics.pairwise import rbf_kernel

W = rbf_kernel(X, gamma=20)

3. Construct the degree matrix

The degree matrix (D) accommodates the sum of similarities for every node. This can be a diagonal matrix and every diagonal value shows the full similarity of that time to all other points. All off-diagonal elements are zero. The form of the degree matrix can be (n, n).

import numpy as np

D = np.diag(np.sum(W, axis=1))

np.sum(W, axis=1)sums each row of the similarity matrix.

4. Construct the Laplacian matrix

The Laplacian matrix (L) represents the structure of the similarity graph, where nodes represent each data point, and edges connect similar points. So, this matrix can be called the and is defined as follows. 

In Python, it’s 

L = D - W

D — W for L mathematically ensures that spectral clustering will find groups of information points which can be strongly connected throughout the group but weakly connected to other groups.

The Laplacian matrix (L) can be an (n, n) square matrix. This property is significant for L as eigendecomposition is defined just for square matrices.

5. Eigendecomposition of the Laplacian matrix

Eigendecomposition of the Laplacian matrix is the technique of decomposing (factorizing) that matrix into eigenvalues and eigenvectors [ref: Eigendecomposition of a Covariance Matrix with NumPy]

If the Laplacian matrix (L) has n eigenvectors, we will decompose it as:

Where:

• X = matrix of eigenvectors
• Λ = diagonal matrix of eigenvalues

The matrices X and Λ may be represented as follows:

The vectors x1, x2 and x3 are eigenvectors and λ1, λ2 and λ3 are their corresponding eigenvalues. 

The eigenvalues and eigenvectors are available in pairs. Such a pair is referred to as an eigenpair. So, matrix L can have multiple eigenpairs [ref: Eigendecomposition of a Covariance Matrix with NumPy]

The next eigenvalue equation shows the connection between L and one in all its eigenpairs.

Where:

• L = Laplacian matrix (ought to be a square matrix)
• x = eigenvector
• λ = eigenvalue (scaling factor)

Let’s calculate all eigenpairs of the Laplacian matrix.

eigenvalues, eigenvectors = np.linalg.eigh(L)

6. Select an important eigenvectors

In spectral clustering, the algorithm uses the smallest eigenvectors of the Laplacian matrix. So, we want to pick the smallest ones within the matrix. 

The smallest eigenvalues correspond to the smallest eigenvectors. The function returns eigenvalues and eigenvectors in ascending order. So, we want to have a look at the primary few values of vector. 

print(eigenvalues)

We concentrate to the difference between consecutive eigenvalues. This difference is referred to as eigengap. We select the eigenvalue that maximizes the eigengap. It represents the variety of clusters. This method known as the eigengap heuristic. 

Based on the eigengap heuristic, the optimal variety of clusters is chosen at the purpose where the most important jump occurs between successive eigenvalues.

If there are very small eigenvalues, there might be clusters! In our example, the primary two small eigenvalues suggest two clusters, which is precisely what we expect. That is the role of eigenvalues in spectral clustering. They’re very useful to determine the variety of clusters and the smallest eigenvectors! 

We select the primary two eigenvectors corresponding to those small eigenvalues.

k = 2
U = eigenvectors[:, :k]

These two eigenvectors within the matrix represent a brand new feature space called spectral embedding, where clusters change into linearly separable. Here is the visualization of spectral embedding. 

import matplotlib.pyplot as plt

plt.figure(figsize=[4.2, 3])
plt.scatter(U[:,0], U[:,1], s=20)
plt.title("Spectral Embedding")
plt.xlabel("Eigenvector 1")
plt.ylabel("Eigenvector 2")
plt.savefig("Spectral embedding.png")

This plot shows how eigenvectors transform the unique data right into a recent space where clusters change into linearly separable. 

7. Apply K-means on spectral embedding

Now, we will simply apply K-means in spectral embedding (recent eigenvector space) to get cluster lables after which we assign those labels to the unique data to create clusters. K-means works well here because clusters are linearly separable in the brand new eigenvector space. 

import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=k)
labels_spectral = kmeans.fit_predict(U)
# U represents spectral embedding

plt.figure(figsize=[4.2, 3])
# Assign cluster labels to original data
plt.scatter(X[:,0], X[:,1], c=labels_spectral, s=20)
plt.title("Spectral Clustering")
plt.savefig("Spectral Manual.png")

This is similar as what we got from the Scikit-learn version! 

Selecting the Right Value for Gamma

When creating the similarity matrix or measuring similarity using a Gaussian kernel, we want to define the appropriate value for the hyperparameter, which controls how quickly similarity decreases with distance between data points.

from sklearn.metrics.pairwise import rbf_kernel

W = rbf_kernel(X, gamma=?)

For small gamma values, similarity decreases slowly, and plenty of points appear similar. Due to this fact, this leads to incorrect cluster structures.

For big gamma values, similarity decreases very fast, and only very close points are connected. Due to this fact, clusters change into highly separated. 

For medium values, you’ll get balanced clusters.

It is best to try multiple values, similar to 0.1, 0.5, 1, 5, 10, 15, and visualize the clustering results to decide on the perfect.

Closing Thoughts

In spectral clustering, a dataset is represented as a graph as a substitute of a set of points. In that graph, each data point is a node and the lines (edges) between nodes define how similar points connect together.

The spectral clustering algorithm needs this graph representation in a mathematical form. That’s why we’ve constructed a similarity (affinity) matrix (W). Each value in that matrix measures the similarity between data points. Large values within the matrix mean two points are very similar, while small values mean two points are very different.

Next, we’ve built the degree matrix (D), which is a diagonal matrix where each diagonal value shows the full similarity of that time to all other points.

Using the degree matrix and the similarity matrix, we’ve constructed the graph Laplacian matrix, which captures the structure of the graph and is important for spectral clustering. 

We’ve computed the eigenvalues and eigenvectors of the Laplacian matrix. The eigenvalues help to decide on the perfect variety of clusters and the smallest eigenvectors. In addition they indicate the strength of cluster separation. The eigenvectors reveal the cluster structure (cluster boundaries or how data points group together) and are used to acquire a brand new feature space where strongly-connected points within the graph change into close together on this space. Clusters change into easier to separate, and K-means works well in the brand new space.

Here is the entire workflow of spectral clustering. 

Dataset → Similarity Graph → Graph Laplacian → Eigenvectors → Clusters

That is the tip of today’s article.

Please let me know if you’ve got any questions or feedback.

See you in the subsequent article. Glad learning to you!

Designed and written by: 
Rukshan Pramoditha

2025–03–08