深入剖析Mean Shift聚类算法原理

转自：http://www.360doc.com/content/19/0623/22/99071_844418459.shtml

Mean Shift（均值漂移）是基于密度的非参数聚类算法，其算法思想是假设不同簇类的数据集符合不同的概率密度分布，找到任一样本点密度增大的最快方向（最快方向的含义就是Mean Shift），样本密度高的区域对应于该分布的最大值，这些样本点最终会在局部密度最大值收敛，且收敛到相同局部最大值的点被认为是同一簇类的成员。

Mean Shift在计算机视觉领域的应用非常广，如图像分割，聚类和视频跟踪，小编曾经用Mean Shift实现目标跟踪，效果还不错。本文详细的总结了Mean Shift算法原理。

目录

1.核密度估计

2.Mean Shift算法

3.图解Mean Shift算法

4.带宽对Mean Shift算法的影响

5.图像分割

6.聚类

7.Mean Shift算法优缺点

1.核密度估计

Mean Shift算法用核函数估计样本的密度，最常用的核函数是高斯核。它的工作原理是在数据集上的每一个样本点都设置一个核函数，然后对所有的核函数相加，得到数据集的核密度估计（kernel density estimation）。

 

图像分割代码请参考github：

https://github.com/mattnedrich/MeanShift_py。

6.聚类

我们构建1000例4个簇类的样本数据：

#%% 产生样本数据
from sklearn.datasets import make_blobs
from itertools import cycle
from sklearn.cluster import MeanShift, estimate_bandwidth
centers = [[1, 1], [-.75, -1], [1, -1], [-3, 2]]
X, _ = make_blobs(n_samples=10000, centers=centers, cluster_std=0.6)

利用函数estimate_bandwidth估计核函数的带宽：

bandwidth = estimate_bandwidth(X, quantile=.1,n_samples=500)

运行mean shift算法，并可视化聚类结果：

8.Mean Shift算法的优缺点

优点：

不需要设置簇类的个数；

可以处理任意形状的簇类；

算法只需设置带宽这一个参数，带宽影响数据集的核密度估计

算法结果稳定，不需要进行类似K均值的样本初始化

缺点：

聚类结果取决于带宽的设置，带宽设置的太小，收敛太慢，簇类个数过多；带宽设置的太大，一些簇类可能会丢失。

对于较大的特征空间，计算量非常大。

参考：

https://spin.atomicobject.com/2015/05/26/mean-shift-clustering/

http://efavdb.com/mean-shift/