机器学习(十)Mean Shift 聚类算法

机器学习(十)Mean Shift 聚类算法一、mean shift 算法理论Mean shift 算法是基于核密度估计的爬山算法,可用于聚类、图像分割、跟踪等,因为最近搞一个项目,涉及到这个算法的图像聚类实现,因此这里做下笔记。(1)均值漂移的基本形式给定d维空间的n个数据点集X,那么对于空间中的任意点x的mean shift向量基本形式可以表示为:这个向量就是漂移向量,其中Sk表示的是数据集的点到x的距离小于球半径h

Mean Shift 聚类算法

原文地址:http://blog.csdn.net/hjimce/article/details/45718593 

作者:hjimce

一、mean shift 算法理论

Mean shift 算法是基于核密度估计的爬山算法,可用于聚类、图像分割、跟踪等,因为最近搞一个项目,涉及到这个算法的图像聚类实现,因此这里做下笔记。

(1)均值漂移的基本形式

给定d维空间的n个数据点集X,那么对于空间中的任意点xmean shift向量基本形式可以表示为:

机器学习(十)Mean Shift 聚类算法

这个向量就是漂移向量,其中Sk表示的是数据集的点到x的距离小于球半径h的数据点。也就是:

机器学习(十)Mean Shift 聚类算法

而漂移的过程,说的简单一点,就是通过计算得漂移向量,然后把球圆心x的位置更新一下,更新公式为:

机器学习(十)Mean Shift 聚类算法

使得圆心的位置一直处于力的平衡位置。

 机器学习(十)Mean Shift 聚类算法

机器学习(十)Mean Shift 聚类算法

总结为一句话就是:求解一个向量,使得圆心一直往数据集密度最大的方向移动。说的再简单一点,就是每次迭代的时候,都是找到圆里面点的平均位置作为新的圆心位置。

(2)加入核函数的漂移向量

这个说的简单一点就是加入一个高斯权重,最后的漂移向量计算公式为:

机器学习(十)Mean Shift 聚类算法

因此每次更新的圆心坐标为:

机器学习(十)Mean Shift 聚类算法

不过我觉得如果用高斯核函数,把这个算法称为均值漂移有点不合理,既然叫均值漂移,那么均值应该指的是权重相等,也就是(1)中的公式才能称之为真正的均值漂移

我的简单理解mean shift算法是:物理学上力的合成与物体的运动。每次迭代通过求取力的合成向量,然后让圆心沿着力的合成方向,移动到新的平衡位置。

二、mean shift 聚类流程:

假设在一个多维空间中有很多数据点需要进行聚类,Mean Shift的过程如下:

1、在未被标记的数据点中随机选择一个点作为中心center

2、找出离center距离在bandwidth之内的所有点,记做集合M,认为这些点属于簇c同时,把这些求内点属于这个类的概率加1,这个参数将用于最后步骤的分类

3、以center为中心点,计算从center开始到集合M中每个元素的向量,将这些向量相加,得到向量shift

4center = center+shift。即center沿着shift的方向移动,移动距离是||shift||

5、重复步骤234,直到shift的大小很小(就是迭代到收敛),记住此时的center。注意,这个迭代过程中遇到的点都应该归类到簇c

6如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值,那么把c2c合并。否则,把c作为新的聚类,增加1类。

6、重复12345直到所有的点都被标记访问。

7、分类:根据每个类,对每个点的访问频率,取访问频率最大的那个类,作为当前点集的所属类。

简单的说,mean shift就是沿着密度上升的方向寻找同属一个簇的数据点。

三、mean shift 聚类实现

Mean shift 算法不需要指定聚类个数,贴一下用matlab实现的聚类结果:


在图像分割、图像跟踪,需要加入核函数。

机器学习(十)Mean Shift 聚类算法机器学习(十)Mean Shift 聚类算法

聚类结果                                                                                           圆心漂移轨迹

*********作者:hjimce     联系qq:1393852684   更多资源请关注我的博客:http://blog.csdn.net/hjimce                原创文章,转载请保留本行信息。*****************

今天的文章机器学习(十)Mean Shift 聚类算法分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/13242.html

(0)
编程小号编程小号

相关推荐

发表回复

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