mean-shift clustering algorithm

the mean-shift clustering algorithm is a non-parametric clustering algorithm that works by iteratively shifting the mean of a data point towards the densest area of the data. the densest area of the data is determined by the kernel function, which is a function that assigns weights to the data points based on their distance from the mean. the kernel function used in mean-shift clustering is usually a gaussian function.

the mean-shift clustering algorithm is a powerful clustering algorithm used in unsupervised learning. unlike k-means clustering, it does not make any assumptions; hence it is a non-parametric algorithm.

the difference between k-means algorithm and mean-shift is that later one does not need to specify the number of clusters in advance because the number of clusters will be determined by the algorithm w.r.t data.

working of mean-shift algorithm

we can understand the working of mean-shift clustering algorithm with the help of following steps −

step 1 − first, start with the data points assigned to a cluster of their own.
step 2 − next, this algorithm will compute the centroids.
step 3 − in this step, location of new centroids will be updated.
step 4 − now, the process will be iterated and moved to the higher density region.
step 5 − at last, it will be stopped once the centroids reach at position from where it cannot move further.

the mean-shift clustering algorithm is a density-based clustering algorithm, which means that it identifies clusters based on the density of the data points rather than the distance between them. in other words, the algorithm identifies clusters based on the areas where the density of the data points is highest.

implementation of mean-shift clustering in python

the mean-shift clustering algorithm can be implemented in python programming language using the scikit-learn library. the scikit-learn library is a popular machine learning library in python that provides various tools for data analysis and machine learning. the following steps are involved in implementing the mean-shift clustering algorithm in python using the scikit-learn library −

step 1 − import the necessary libraries

the numpy library is used for scientific computing in python, while the matplotlib library is used for data visualization. the sklearn.cluster library contains the meanshift class, which is used for implementing the mean-shift clustering algorithm in python.

the estimate_bandwidth function is used to estimate the bandwidth of the kernel function, which is an important parameter in the mean-shift clustering algorithm.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import meanshift, estimate_bandwidth

step 2 − generate the data

in this step, we generate a random dataset with 500 data points and 2 features. we use the numpy.random.randn function to generate the data.

# generate the data
x = np.random.randn(500,2)

step 3 − estimate the bandwidth of the kernel function

in this step, we estimate the bandwidth of the kernel function using the estimate_bandwidth function. the bandwidth is an important parameter in the mean-shift clustering algorithm, which determines the width of the kernel function.

# estimate the bandwidth
bandwidth = estimate_bandwidth(x, quantile=0.1, n_samples=100)

step 4 − initialize the mean-shift clustering algorithm

in this step, we initialize the mean-shift clustering algorithm using the meanshift class. we pass the bandwidth parameter to the class to set the width of the kernel function.

# initialize the mean-shift algorithm
ms = meanshift(bandwidth=bandwidth, bin_seeding=true)

step 5 − train the model

in this step, we train the mean-shift clustering algorithm on the dataset using the fit method of the meanshift class.

# train the model
ms.fit(x)

step 6 − visualize the results

# visualize the results
labels = ms.labels_
cluster_centers = ms.cluster_centers_
n_clusters_ = len(np.unique(labels))
print("number of estimated clusters:", n_clusters_)

# plot the data points and the centroids
plt.figure(figsize=(7.5, 3.5))
plt.scatter(x[:,0], x[:,1], c=labels, cmap='viridis')
plt.scatter(cluster_centers[:,0], cluster_centers[:,1], marker='*', s=300, c='r')
plt.show()

in this step, we visualize the results of the mean-shift clustering algorithm. we extract the cluster labels and the cluster centers from the trained model. we then print the number of estimated clusters. finally, we plot the data points and the centroids using the matplotlib library.

complete example

here is the complete implementation example of mean-shift clustering algorithm in python −

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import meanshift, estimate_bandwidth

# generate the data
x = np.random.randn(500,2)

# estimate the bandwidth
bandwidth = estimate_bandwidth(x, quantile=0.1, n_samples=100)

# initialize the mean-shift algorithm
ms = meanshift(bandwidth=bandwidth, bin_seeding=true)

# train the model
ms.fit(x)

# visualize the results
labels = ms.labels_
cluster_centers = ms.cluster_centers_
n_clusters_ = len(np.unique(labels))
print("number of estimated clusters:", n_clusters_)

# plot the data points and the centroids
plt.figure(figsize=(7.5, 3.5))
plt.scatter(x[:,0], x[:,1], c=labels, cmap='summer')
plt.scatter(cluster_centers[:,0], cluster_centers[:,1], marker='*',
s=200, c='r')
plt.show()

output

when you execute the program, it will produce the following plot as the output −

example

it is a simple example to understand how mean-shift algorithm works. in this example, we are going to first generate 2d dataset containing 4 different blobs and after that will apply mean-shift algorithm to see the result.

%matplotlib inline
import numpy as np
from sklearn.cluster import meanshift
import matplotlib.pyplot as plt
from matplotlib import style
style.use("ggplot")
from sklearn.datasets import make_blobs
centers = [[3,3,3],[4,5,5],[3,10,10]]
x, _ = make_blobs(n_samples = 700, centers = centers, cluster_std = 0.5)
plt.scatter(x[:,0],x[:,1])
plt.show()

output

ms = meanshift()
ms.fit(x)
labels = ms.labels_
cluster_centers = ms.cluster_centers_
print(cluster_centers)
n_clusters_ = len(np.unique(labels))
print("estimated clusters:", n_clusters_)
colors = 10*['r.','g.','b.','c.','k.','y.','m.']
for i in range(len(x)):
    plt.plot(x[i][0], x[i][1], colors[labels[i]], markersize = 3)
plt.scatter(cluster_centers[:,0],cluster_centers[:,1],
    marker=".",color='k', s=20, linewidths = 5, zorder=10)
plt.show()

output

[[ 4.03457771  5.03063843  4.92928409]
 [ 3.01124859  2.9957586   2.981767  ]
 [ 2.94969928 10.00712673 10.01575558]]
estimated clusters: 3

applications of mean-shift clustering

the mean-shift clustering algorithm has several applications in various fields. some of the applications of mean-shift clustering are as follows −

computer vision − mean-shift clustering is widely used in computer vision for object tracking, image segmentation, and feature extraction.
image processing − mean-shift clustering is used for image segmentation, which is the process of dividing an image into multiple segments based on the similarity of the pixels.
anomaly detection − mean-shift clustering can be used for detecting anomalies in data by identifying the areas with low density.
customer segmentation − mean-shift clustering can be used for customer segmentation in marketing by identifying groups of customers with similar behavior and preferences.
social network analysis − mean-shift clustering can be used for clustering users in social networks based on their interests and interactions.

advantages and disadvantages

let's discuss some advantages and disadvantages of the means-shift clustering algorithm.

advantages

the following are some advantages of mean-shift clustering algorithm −

it does not need to make any model assumption as like in k-means or gaussian mixture.
it can also model the complex clusters which have nonconvex shape.
it only needs one parameter named bandwidth which automatically determines the number of clusters.
there is no issue of local minima as like in k-means.
no problem generated from outliers.

disadvantages

the following are some disadvantages of mean-shift clustering algorithm −

mean-shift algorithm does not work well in case of high dimension, where number of clusters changes abruptly.
we do not have any direct control on the number of clusters but in some applications, we need a specific number of clusters.
it cannot differentiate between meaningful and meaningless modes.

Save or share this article