SciPy - Cluster

SciPy - Cluster Analysis

Cluster analysis, or clustering, is the task of grouping a set of objects 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. K-means clustering is a popular method for partitioning a dataset into K distinct, non-overlapping clusters. The algorithm aims to find cluster centers (centroids) that minimize the within-cluster sum of squares (inertia).

The K-means algorithm iteratively performs two steps:

• Assignment step: Each data point is assigned to the cluster whose centroid is closest (e.g., using Euclidean distance).
• Update step: The centroid of each cluster is recalculated as the mean of all data points assigned to that cluster.

These steps are repeated until the centroids no longer change significantly, or a maximum number of iterations is reached. Once the algorithm converges, new data points can be assigned to the nearest cluster centroid. The scipy.cluster.vq module (Vector Quantization) in SciPy provides an efficient implementation of K-means.

K-Means Implementation in SciPy

Let’s walk through how to implement K-means using scipy.cluster.vq.

Import Necessary Functions

We’ll primarily use kmeans for finding cluster centroids, vq for assigning observations to clusters, and whiten for data normalization.

import numpy as np
from scipy.cluster.vq import kmeans, vq, whiten

Data Generation

Let’s generate some synthetic 2D data with two distinct clusters for demonstration.

# Set a seed for reproducibility
np.random.seed(42)

# Generate data for two clusters
# Cluster 1: 50 points around [0, 0]
cluster1_data = np.random.randn(50, 2) + np.array([0, 0])

# Cluster 2: 50 points around [5, 5]
cluster2_data = np.random.randn(50, 2) + np.array([5, 5])

# Combine the data into a single array
# The `features` array will have shape (100, 2)
data_points = np.vstack((cluster1_data, cluster2_data))

print("Shape of the data:", data_points.shape)
print("First 5 data points:\n", data_points[:5])

The output will show the shape of our data array and a sample of the points:

Shape of the data: (100, 2)
First 5 data points:
 [[ 0.49671415 -0.1382643 ]
 [ 0.64768854  1.52302986]
 [-0.23415337 -0.23413696]
 [ 1.57921282  0.76743473]
 [-0.46947439  0.54256004]]

Data Whitening (Normalization)

Before applying K-means, it’s often beneficial to normalize the data, a process called ‘whitening’ in scipy.cluster.vq. Whitening rescales each feature (column) to have unit variance. This ensures that features with larger values don’t dominate the distance calculations.

# Whiten the data
whitened_data = whiten(data_points)

print("\nFirst 5 whitened data points:\n", whitened_data[:5])
# You can verify that each column now has a standard deviation close to 1
# print("\nStandard deviation of whitened data columns:", np.std(whitened_data, axis=0))

Whitening scales each feature by its standard deviation. This is a common preprocessing step.

Compute K-Means with Two Clusters

Now, let’s apply the K-means algorithm. We expect two clusters, so we set k=2.

# Compute K-Means with k=2 (for two clusters)
# The `kmeans` function returns the centroids and the distortion (average distance)
centroids, distortion = kmeans(whitened_data, 2) # k=2 for two clusters

print("\nCalculated Centroids (for whitened data):\n", centroids)

The kmeans function performs the K-means algorithm on the (whitened) data to find k cluster centroids. The distortion value represents the average Euclidean distance between the observations and their assigned centroids.

The output for centroids will be coordinates in the whitened data space:

Calculated Centroids (for whitened data):
 [[-0.02539932 -0.01228082]
 [ 1.5908165   1.65607801]]

These centroids correspond to the centers of the two clusters found by the algorithm in the normalized feature space.

Assign Each Observation to a Cluster

Once we have the centroids, we can assign each data point to its closest cluster using the vq function.

# Assign each whitened data point to a cluster based on the calculated centroids
# `vq` returns cluster assignments (indices) and distances to centroids
cluster_assignments, distances_to_centroids = vq(whitened_data, centroids)

print("\nCluster assignments for the first 10 data points:", cluster_assignments[:10])
# print("\nDistances for the first 10 data points:", distances_to_centroids[:10])

The vq function takes the data and the centroids, and returns an array where each element is the index of the cluster the corresponding data point belongs to. It also returns the distances of each point to its assigned centroid.

The output will show the cluster index (0 or 1) for each of the first 10 points:

Cluster assignments for the first 10 data points: [0 0 0 0 0 0 0 0 0 0]

In this example, since the first 50 points belonged to cluster1_data (centered near origin), they are mostly assigned to one cluster (e.g., cluster 0), and the next 50 points from cluster2_data (centered near [5,5]) to the other cluster (e.g., cluster 1). The exact assignment indices (0 or 1) might swap depending on the run, but the grouping should be consistent. You can check cluster_assignments[45:55] to see the transition.

Practical Applications

K-means clustering is widely used in various fields, including:

• Customer Segmentation: Grouping customers based on purchasing behavior.
• Document Clustering: Organizing text documents into topics.
• Image Segmentation: Partitioning an image into regions with similar characteristics.
• Anomaly Detection: Identifying outliers that don’t fit well into any cluster.

While scipy.cluster.vq provides a basic K-means, libraries like scikit-learn (sklearn.cluster.KMeans) offer more feature-rich implementations with additional options and evaluation metrics.