Scikit Learn - Clustering Methods

Scikit-learn - Clustering Methods

Clustering is a fundamental unsupervised machine learning task that involves grouping a set of objects (samples) in such a way that objects in the same group (called a cluster) are more similar to each other than to those in other groups. This chapter explores various clustering algorithms available in Scikit-learn’s sklearn.cluster module.

Clustering methods are vital for discovering intrinsic structures and patterns in unlabeled data. They help in tasks like customer segmentation, anomaly detection, and image compression.

K-Means

The K-Means algorithm aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster centroid). It’s an iterative algorithm that minimizes the within-cluster sum of squares (inertia). The number of clusters, k, must be specified beforehand.

Scikit-learn provides sklearn.cluster.KMeans. Key parameters include n_clusters (the number of clusters, k), init (method for initialization, ‘k-means++’ is default and recommended), and n_init (number of times the k-means algorithm will be run with different centroid seeds, the best result is taken). The sample_weight parameter allows assigning different weights to samples during centroid computation.

Strengths: Simple, computationally efficient for large datasets. Works well for spherical, well-separated clusters of similar size.

Weaknesses: Requires k to be specified. Sensitive to initial centroid placement (though ‘k-means++’ mitigates this). Struggles with non-spherical clusters, clusters of varying densities, or uneven sizes.

Affinity Propagation

Affinity Propagation creates clusters by sending messages between pairs of samples until convergence. Unlike K-Means, it does not require the number of clusters to be specified beforehand. It identifies ‘exemplars’ that represent clusters.

Scikit-learn provides sklearn.cluster.AffinityPropagation. Key parameters include damping and preference. A significant drawback is its time complexity, typically O(N^2 * T) where N is samples and T is iterations, making it unsuitable for very large datasets.

Strengths: Does not require specifying k. Can find non-flat geometry clusters.

Weaknesses: Computationally expensive. Performance depends on message passing parameters.

Mean Shift

Mean Shift is a centroid-based algorithm that aims to discover ‘blobs’ in a smooth density of samples. It works by updating candidates for centroids to be the mean of the points within a given region (defined by bandwidth). This process is iterated until convergence. The number of clusters is determined automatically.

Scikit-learn provides sklearn.cluster.MeanShift. The bandwidth parameter is crucial; it dictates the size of the region to search through. If not set, it’s estimated using estimate_bandwidth.

Strengths: Does not assume a specific cluster shape. Automatically determines the number of clusters.

Weaknesses: Performance is sensitive to the bandwidth parameter. Can be computationally expensive for large feature spaces.

Spectral Clustering

Spectral Clustering performs dimensionality reduction on the similarity matrix (or affinity matrix) of the data using its eigenvalues (spectrum) before clustering in fewer dimensions (typically using K-Means). It’s useful for finding non-convex clusters.

Scikit-learn provides sklearn.cluster.SpectralClustering. Key parameters include n_clusters and affinity (how to construct the affinity matrix, e.g., ‘rbf’, ‘nearest_neighbors’). It’s not advisable for a very large number of clusters.

Strengths: Effective for non-flat geometry (e.g., concentric circles). Can handle complex cluster shapes.

Weaknesses: Can be computationally intensive for large datasets. Performance depends on the choice of affinity matrix.

Hierarchical Clustering

Hierarchical clustering builds a hierarchy of clusters, often represented as a tree (dendrogram). There are two main types:

• Agglomerative: A ‘bottom-up’ approach where each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.
• Divisive: A ‘top-down’ approach where all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

Scikit-learn provides sklearn.cluster.AgglomerativeClustering for agglomerative hierarchical clustering. Key parameters include n_clusters (or distance_threshold to cut the dendrogram), linkage (‘ward’, ‘complete’, ‘average’, ‘single’), and affinity (metric used to compute linkage).

Strengths: Produces a dendrogram, which can be useful for understanding data structure. Does not require specifying k if using distance_threshold.

Weaknesses: Can be computationally expensive (typically O(N^2 log N) or O(N^3) depending on linkage and implementation). Decisions made early in merging/splitting are irreversible.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN groups together points that are closely packed (points with many nearby neighbors), marking as outliers points that lie alone in low-density regions. It can find arbitrarily shaped clusters and does not require k to be specified.

Scikit-learn provides sklearn.cluster.DBSCAN. Key parameters are eps (maximum distance between two samples for one to be considered as in the neighborhood of the other) and min_samples (number of samples in a neighborhood for a point to be considered as a core point).

Strengths: Can find arbitrarily shaped clusters. Robust to outliers (identifies them as noise). Does not require specifying k.

Weaknesses: Performance is sensitive to eps and min_samples. Struggles with clusters of varying densities.

OPTICS (Ordering Points To Identify the Clustering Structure)

OPTICS is similar to DBSCAN but addresses one of its main weaknesses: detecting meaningful clusters in data of varying density. It creates an augmented ordering of the database representing its density-based clustering structure. This ordering can then be used to extract clusters.

Scikit-learn provides sklearn.cluster.OPTICS. Key parameters include min_samples, max_eps, and xi. It can be seen as a generalization of DBSCAN.

Strengths: Handles varying density clusters better than DBSCAN. Produces a reachability plot useful for understanding cluster structure.

Weaknesses: Can be more complex to interpret than DBSCAN. Parameter tuning can be challenging.

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)

BIRCH is designed for very large datasets. It incrementally and dynamically clusters incoming multi-dimensional metric data points to try to produce the best quality clustering with available resources (memory and time). It builds a tree structure called a Clustering Feature Tree (CFT).

Scikit-learn provides sklearn.cluster.Birch. Key parameters include threshold, branching_factor, and n_clusters (can be set to None if global clustering is not desired or if another clustering algorithm is applied to CF subclusters).

Strengths: Efficient for large datasets (single pass). Handles outliers well.

Weaknesses: Only works with numerical data. Clusters tend to be spherical. Sensitive to the order of data points.

Comparing Clustering Algorithms

The choice of clustering algorithm depends on the dataset’s characteristics and the problem’s goals. Here’s a brief comparison:

Algorithm	Key Parameters	Scalability (n_samples)	Use Cases / Geometry
K-Means	n_clusters, init	Very good	Spherical, even-sized clusters.
Affinity Propagation	damping, preference	Poor (O(N^2))	Many clusters, non-flat geometry, when k is unknown.
Mean Shift	bandwidth	Poor to Medium	Finding blobs, when k is unknown.
Spectral Clustering	n_clusters, affinity	Medium	Non-flat geometry, complex shapes, few clusters.
Hierarchical (Agglomerative)	n_clusters/distance_threshold, linkage	Medium to Poor (O(N^2) to O(N^3))	Hierarchical structure, when k is unknown (with threshold).
DBSCAN	eps, min_samples	Good (O(N log N) or O(N^2))	Non-flat geometry, uneven sizes, presence of noise.
OPTICS	min_samples, xi, max_eps	Good (similar to DBSCAN)	Varying densities, presence of noise.
BIRCH	threshold, branching_factor, n_clusters	Very good	Large datasets, streaming data, spherical clusters.

K-Means Clustering on Digits Dataset Example

Let’s apply K-Means to the digits dataset. This dataset contains images of hand-written digits. We’ll try to cluster them without using the true labels, then compare the cluster assignments to the true labels to see how well K-Means groups similar digits.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import load_digits
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score, adjusted_rand_score, silhouette_score
from scipy.stats import mode

# Load digits dataset
digits = load_digits()
X, y_true = digits.data, digits.target
print(f"Data shape: {X.shape}") # (1797 samples, 64 features)

# Scale the data for better K-Means performance
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Apply K-Means clustering
# We know there are 10 digits (0-9), so set n_clusters=10
kmeans = KMeans(n_clusters=10, random_state=42, n_init='auto')
clusters_pred = kmeans.fit_predict(X_scaled)

print(f"Shape of cluster centers: {kmeans.cluster_centers_.shape}") # (10 clusters, 64 features)

# Evaluate clustering performance (if ground truth is available for reference)
# 1. Map predicted cluster labels to true labels
labels_mapped = np.zeros_like(clusters_pred)
for i in range(10):
    mask = (clusters_pred == i)
    # Assign the most frequent true label in that cluster
    if np.any(mask):
      labels_mapped[mask] = mode(y_true[mask], keepdims=True)[0]

accuracy = accuracy_score(y_true, labels_mapped)
print(f"Accuracy (after mapping clusters to true labels): {accuracy:.4f}")

# 2. Use clustering-specific metrics
ari_score = adjusted_rand_score(y_true, clusters_pred)
print(f"Adjusted Rand Index (ARI): {ari_score:.4f}")

# Silhouette Score (does not use true labels, measures cluster cohesion and separation)
sil_score = silhouette_score(X_scaled, clusters_pred)
print(f"Silhouette Score: {sil_score:.4f}")

# Note: Accuracy here is for illustrative purposes, showing how well clusters align with true classes.
# ARI and Silhouette Score are more standard for evaluating clustering itself.

Output (will vary slightly due to K-Means initialization if n_init is not ‘auto’ or random_state changes)

Data shape: (1797, 64)
Shape of cluster centers: (10, 64)
Accuracy (after mapping clusters to true labels): 0.7902
Adjusted Rand Index (ARI): 0.6570
Silhouette Score: 0.1880

This example demonstrates applying K-Means and evaluating its results. The cluster centers learned by K-Means would represent the ‘average’ image for each discovered digit group. Visualizing these centers (e.g., reshaping them to 8x8 images) could provide insight into what the algorithm learned. For more on evaluation, see the ‘Clustering Performance Evaluation’ chapter.