聚类算法之Mean Shift

56 sec read

K-Means算法中,最终的聚类效果受初始的聚类中心的影响,K-Means++算法的提出,为选择较好的初始聚类中心提供了依据,但是算法中,聚类的类别个数k仍需事先制定,对于类别个数事先未知的数据集,K-Means和K-Means++将很难对其精确求解,对此,有一些改进的算法被提出来处理聚类个数k未知的情形。Mean Shift算法,又被称为均值漂移算法,与K-Means算法一样,都是基于聚类中心的聚类算法,不同的是,Mean Shift算法不需要事先制定类别个数k。

Mean Shift的概念最早是由Fukunage在1975年提出的,在后来由Yizong Cheng对其进行扩充,主要提出了两点的改进:定义了核函数,增加了权重系数。核函数的定义使得偏移值对偏移向量的贡献随之样本与被偏移点的距离的不同而不同。权重系数使得不同样本的权重不同。

Mean Shift算法在很多领域都有成功应用,例如图像平滑、图像分割、物体跟踪等,这些属于人工智能里面模式识别或计算机视觉的部分;另外也包括常规的聚类应用。

  • 图像平滑:图像最大质量下的像素压缩;
  • 图像分割:跟图像平滑类似的应用,但最终是将可以平滑的图像进行分离已达到前后景或固定物理分割的目的;
  • 目标跟踪:例如针对监控视频中某个人物的动态跟踪;
  • 常规聚类,如用户聚类等。

Mean Shift算法理论

Mean Shift向量

对于给定的d维空间R^d中的n个样本点x_i,i=1,⋯,n,则对于x点,其Mean Shift向量的基本形式为:

    \[M_h(x)=\frac{1}{k}\sum_{x_i\in S_h}(x_i-x)\]

其中,S_h指的是一个半径为h的高维球区域,如上图中的圆形区域。S_h的定义为:

    \[S_h(x)=(y \mid (y-x)( y-x)^T \leqslant h^2)\]

里面所有点与圆心为起点形成的向量相加的结果就是Mean shift向量。下图黄色箭头就是 M_h(Mean Shift向量)。

对于Mean Shift算法,是一个迭代的步骤,即先算出当前点的偏移均值,将该点移动到此偏移均值,然后以此为新的起始点,继续移动,直到满足最终的条件。

Mean-Shift 聚类就是对于集合中的每一个元素,对它执行下面的操作:把该元素移动到它邻域中所有元素的特征值的均值的位置,不断重复直到收敛。准确的说,不是真正移动元素,而是把该元素与它的收敛位置的元素标记为同一类。

如上的均值漂移向量的求解方法存在一个问题,即在S_h的区域内,每一个样本点x对样本X的共享是一样的。而实际中,每一个样本点x对样本X的贡献是不一样的,这样的共享可以通过核函数进行度量。

核函数

在Mean Shift算法中引入核函数的目的是使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同。核函数是机器学习中常用的一种方式。核函数的定义如下所示:

X 表示一个d维的欧式空间,x 是该空间中的一个点x = \{x_1,x_2,x_3\cdots ,x_d\},其中,x的模\| x \|^2=xx^T,R表示实数域,如果一个函数K:X→R存在一个剖面函数k:[0,∞]→R,即

    \[K (x)=k (\| x \|^2)\]

并且满足:

  • k是非负的
  • k是非增的
  • k是分段连续的

那么,函数K(x)就称为核函数。

核函数有很多,下图中表示的每一个曲线都为一个核函数。

常用的核函数有高斯核函数。高斯核函数如下所示:

    \[N (x)=\frac{1}{\sqrt{2\pi }h}e^{-\frac{x^2}{2h^2}}\]

其中,h称为带宽(bandwidth),不同带宽的核函数如下图所示:

从高斯函数的图像可以看出,当带宽h一定时,样本点之间的距离越近,其核函数的值越大,当样本点之间的距离相等时,随着高斯函数的带宽h的增加,核函数的值在减小。

高斯核函数的Python实现:

引入核函数的Mean Shift向量

假设在半径为h的范围S_h范围内,为了使得每一个样本点x对于样本X的共享不一样,向基本的Mean Shift向量形式中增加核函数,得到如下改进的Mean Shift向量形式:

    \[M_h(x)=\frac{\sum_{i=1}^{n}G(\frac{x_i-x}{h_i})(x_i-x)}{\sum_{i=1}^{n}G(\frac{x_i-x}{h_i})}\]

其中,G(\frac{x_i-x}{h_i})为核函数。通常,可以取S_h为整个数据集范围。

计算M_h时考虑距离的影响,同时也可以认为在所有的样本点X中,重要性并不一样,因此对每个样本还引入一个权重系数。如此以来就可以把Mean Shift形式扩展为:

    \[M_h (x)=\frac{\sum_{i=1}^{n}G(\frac{x_i-x}{h_i})w(x_i)(x_i-x)}{\sum_{i=1}^{n}G(\frac{x_i-x}{h_i})w(x_i)}\]

其中,w(x_i) 是一个赋给采样点的权重。

聚类动画演示

Mean Shift的代码实现

算法的Python实现

以上代码实现了基本的流程,但是执行效率很慢,正式使用时建议使用scikit-learn库中的MeanShift。

scikit-learn MeanShift演示

执行效果:

scikit-learn MeanShift源码分析

源码地址:https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/cluster/mean_shift_.py

参考资料:

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

使用Python进行相关性分析

在数据分析时,经常会针对两个变量进行相关性分析。在Python中主要用到的方法是pandas中的corr()方
42 sec read

一维数组的聚类

需求:分析订单的价格分布 方案:按照100为梯度,分析不同价格区间的订单量 缺陷:现实生活中,定价存在一些自然
1 min read

Pandas学习笔记:Excel、CSV文件的读取与导出

在使用Pandas处理数据时,常见的读取数据的方式时从Excel或CSV文件中获取,另外有时也会需要将处理完的
2 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注