Spectral Clustering
๐ Introduction
Spectral Clustering is an advanced unsupervised machine learning algorithm that clusters data using concepts from graph theory and linear algebra. Instead of directly grouping observations based on distances, Spectral Clustering transforms the dataset into a graph, computes its spectral (eigenvalue) representation, and then performs clustering in the transformed space.
Information
Spectral Clustering is especially effective for discovering non-convex, complex-shaped, and interconnected clusters that traditional algorithms such as K-Means struggle to identify.
๐ฏ Learning Objectives
- Understand the principles of Spectral Clustering.
- Learn how similarity graphs are constructed.
- Understand the role of graph Laplacians and eigenvectors.
- Compare Spectral Clustering with K-Means and DBSCAN.
๐ What is Spectral Clustering?
Spectral Clustering converts the dataset into a graph where each observation is represented as a node and the similarity between observations forms weighted edges. The algorithm computes the graph Laplacian, extracts important eigenvectors, and finally applies a clustering algorithm such as K-Means in this lower-dimensional spectral space.
| Characteristic | Spectral Clustering |
|---|---|
| Learning Type | Unsupervised |
| Based On | Graph Theory & Linear Algebra |
| Handles Complex Shapes | Yes |
| Uses Eigenvectors | Yes |
๐ Key Concepts
| Concept | Description |
|---|---|
| Similarity Graph | Represents observations as connected graph nodes. |
| Adjacency Matrix | Stores pairwise similarities between observations. |
| Degree Matrix | Diagonal matrix containing node degrees. |
| Graph Laplacian | Captures graph connectivity. |
| Eigenvectors | Reveal the intrinsic cluster structure. |
๐ Step 1: Build a Similarity Graph
The first step is constructing a graph where similar observations are connected. Similarity can be measured using several approaches.
| Method | Description |
|---|---|
| k-Nearest Neighbors (k-NN) | Connect each observation to its nearest neighbors. |
| ฮต-Neighborhood | Connect observations within a fixed radius. |
| RBF (Gaussian) Kernel | Similarity decreases smoothly with distance. |
Gaussian Similarity Function
Where:
- S(xแตข,xโฑผ) โ Similarity between two observations.
- ฯ โ Controls how quickly similarity decreases with distance.
๐ Step 2: Construct the Graph Laplacian
The Graph Laplacian combines graph connectivity and node degrees.
Where:
- D โ Degree matrix.
- W โ Adjacency (similarity) matrix.
- L โ Graph Laplacian.
Remember
The eigenvectors of the Graph Laplacian reveal the hidden cluster structure of the dataset.
โ๏ธ How Spectral Clustering Works
Construct a similarity graph.
Create the adjacency and degree matrices.
Compute the Graph Laplacian.
Calculate the smallest eigenvectors of the Laplacian.
Project observations into the spectral space.
Apply K-Means (or another clustering algorithm) to the transformed data.
๐ณ Spectral Clustering Workflow
Input Dataset
Build Similarity Graph
Compute Graph Laplacian
Extract Eigenvectors
Transform Data
Apply K-Means
๐ Spectral Clustering vs K-Means vs DBSCAN
| Feature | Spectral Clustering | K-Means | DBSCAN |
|---|---|---|---|
| Cluster Shape | Complex | Spherical | Arbitrary |
| Requires Number of Clusters | Yes | Yes | No |
| Graph-Based | Yes | No | No |
| Outlier Detection | Limited | No | Yes |
| Scalability | Moderate | Excellent | Good |
๐๏ธ Important Hyperparameters
| Hyperparameter | Description |
|---|---|
| n_clusters | Number of clusters. |
| affinity | Similarity graph construction method. |
| gamma | Controls similarity for the RBF kernel. |
| n_neighbors | Number of neighbors for k-NN graphs. |
| assign_labels | Method used for final cluster assignment. |
๐ Evaluation Metrics
- Silhouette Score
- Davies-Bouldin Index
- Calinski-Harabasz Index
- Adjusted Rand Index (when ground-truth labels are available).
โ๏ธ Advantages and Limitations
Advantages
Limitations
- Handles complex and non-convex clusters.
- Captures nonlinear relationships.
- Strong theoretical foundation in graph theory.
- Works well with similarity-based data.
- Flexible graph construction methods.
- Requires specifying the number of clusters.
- Computationally expensive for large datasets.
- Requires storing the similarity matrix.
- Sensitive to affinity and similarity parameters.
๐ Real-World Applications
| Application | Purpose |
|---|---|
| ๐ผ๏ธ Image Segmentation | Separate complex image regions. |
| ๐ Social Network Analysis | Identify communities in networks. |
| ๐งฌ Bioinformatics | Cluster genes and proteins. |
| ๐ Document Clustering | Group related documents. |
| ๐ Computer Vision | Object and scene segmentation. |
| ๐ก Sensor Networks | Discover connected sensor regions. |
๐ป Practical Example
Spectral Clustering Using Scikit-learn
from sklearn.cluster import SpectralClustering
import numpy as np
# Sample data
X = np.array([
[1, 2], [1, 3], [2, 2],
[8, 8], [9, 8], [8, 9]
])
# Create Spectral Clustering model
model = SpectralClustering(
n_clusters=2,
affinity="nearest_neighbors",
random_state=42
)
# Predict clusters
labels = model.fit_predict(X)
print("Cluster Labels:")
print(labels)โ ๏ธ Common Mistakes
- Choosing an inappropriate similarity function.
- Using Spectral Clustering for extremely large datasets without considering memory requirements.
- Ignoring feature scaling before computing similarities.
- Selecting an incorrect number of clusters.
- Using default affinity parameters without validation.
Best Practice
Standardize numerical features before clustering, carefully choose the similarity graph (nearest_neighbors or rbf) based on the dataset, tune gamma and n_neighbors, and use Spectral Clustering when clusters exhibit complex nonlinear structures that traditional algorithms cannot separate effectively.
๐ Summary
Summary
Spectral Clustering is a graph-based clustering algorithm that transforms data into a spectral space using the eigenvectors of the Graph Laplacian before performing clustering. This approach enables it to discover complex, non-convex cluster structures that are difficult for centroid-based algorithms such as K-Means. Although it requires more computation and memory, Spectral Clustering is widely used in image segmentation, social network analysis, bioinformatics, computer vision, and document clustering due to its ability to uncover intricate relationships within data.