Skip to content
W3S101

Mean Shift Algorithm

Clustering Algorithms - Mean Shift Algorithm

Section titled “Clustering Algorithms - Mean Shift Algorithm”

Introduction to Mean Shift Algorithm

Section titled “Introduction to Mean Shift Algorithm”

Mean Shift is a powerful, centroid-based clustering algorithm used in unsupervised learning. Unlike K-Means, Mean Shift is a non-parametric algorithm, meaning it doesn’t require assumptions about the underlying data distribution or the number of clusters beforehand.

The core idea of Mean Shift is to iteratively shift data points towards the densest region in their vicinity. Essentially, points climb towards the nearest peak (mode) in the data’s density landscape. Points converging to the same peak are assigned to the same cluster.

A key difference from K-Means is that Mean Shift automatically determines the number of clusters based on the data structure and a parameter called bandwidth, which defines the size of the neighborhood to consider for density estimation.

How Mean Shift Works

Section titled “How Mean Shift Works”

The Mean Shift clustering process can be summarized as follows:

  • Step 1: Start with each data point acting as an initial candidate centroid.
  • Step 2: For each candidate centroid, define a region (window) around it, determined by the ‘bandwidth’ parameter.
  • Step 3: Calculate the mean of the data points falling within the window.
  • Step 4: Shift the window’s center (the candidate centroid) to this calculated mean.
  • Step 5: Repeat steps 2-4 until the centroids converge, meaning they stop shifting significantly or reach a maximum number of iterations.
  • Step 6: Points whose centroids converge to nearby locations (modes of the density) are grouped into the same cluster.

The ‘bandwidth’ parameter is crucial. A smaller bandwidth might lead to more clusters (over-segmentation), while a larger bandwidth might merge distinct clusters (under-segmentation). Scikit-learn provides estimate_bandwidth to help find a reasonable starting value.

Implementation in Python

Section titled “Implementation in Python”

This example demonstrates Mean Shift clustering. First, we generate a 2D dataset with distinct blobs using make_blobs from Scikit-learn. Then, we apply the Mean Shift algorithm and visualize the resulting clusters.

# Import necessary libraries
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.cluster import MeanShift, estimate_bandwidth
from sklearn.datasets import make_blobs


# Generate sample data
centers = [[1, 1], [5, 5], [3, 10]]
X, _ = make_blobs(n_samples=500, centers=centers, cluster_std=0.8, random_state=42)


# Visualize the original data
plt.figure(figsize=(8, 6))
sns.scatterplot(x=X[:, 0], y=X[:, 1], s=50)
plt.title('Original Data Points')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()


# --- Mean Shift Clustering ---


# Estimate bandwidth (optional but recommended)
# quantile controls the proportion of data points used for estimation
bandwidth = estimate_bandwidth(X, quantile=0.2, n_samples=500)
print(f"Estimated bandwidth: {bandwidth:.2f}")


# If bandwidth estimation is low or high, you might need to adjust it manually
# For this example, let's use the estimated bandwidth or a slightly adjusted value
# bandwidth = 1.8 # Example of manual adjustment if needed


# Initialize and fit MeanShift
# bandwidth: Radius of the kernel density estimation window
# bin_seeding=True: Speeds up computation by discretizing points
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
ms.fit(X)


# Get cluster labels and centers
labels = ms.labels_
cluster_centers = ms.cluster_centers_
n_clusters_ = len(np.unique(labels))


print(f"\nCluster Centers Found:\n{cluster_centers}")
print(f"\nEstimated number of clusters: {n_clusters_}")


# Visualize the results
plt.figure(figsize=(8, 6))
sns.scatterplot(x=X[:, 0], y=X[:, 1], hue=labels, palette='viridis', s=50, legend='full')
# Plot the cluster centers
sns.scatterplot(x=cluster_centers[:, 0], y=cluster_centers[:, 1], marker='X', s=200, color='red', label='Cluster Centers')
plt.title(f'Mean Shift Clustering Results ({n_clusters_} clusters)')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.show()

Interpreting the Output

Section titled “Interpreting the Output”

The first plot shows the raw, unclustered data points. The console output will display the estimated bandwidth, the coordinates of the found cluster centers, and the total number of clusters identified by the algorithm. The final plot shows the original data points colored according to their assigned cluster, with the identified cluster centers marked (usually with an ‘X’ or similar). Ideally, the clusters found by Mean Shift should correspond to the dense regions in the original data.

Advantages and Disadvantages

Section titled “Advantages and Disadvantages”

Advantages

Section titled “Advantages”

Mean Shift offers several benefits:

  • No need to pre-specify the number of clusters.
  • Can find clusters of arbitrary shapes (non-convex).
  • Robust to outliers, as they are unlikely to form dense regions.
  • Only requires one main parameter: the bandwidth.

Disadvantages

Section titled “Disadvantages”

However, it also has limitations:

  • Performance is sensitive to the choice of bandwidth. Finding the optimal bandwidth can be challenging.
  • Computationally expensive for large datasets, as it involves density estimation and iterative shifts for potentially many points (O(N^2) in naive implementations, though optimizations exist).
  • May struggle with high-dimensional data due to the curse of dimensionality affecting density estimation.
  • Might merge nearby clusters if the bandwidth is too large or create spurious small clusters if too small.

Further Resources: