图解Mean-Shift聚类算法

雨点打透心脏的1/2处 2023-02-11 08:59 6阅读 0赞

**前期回顾**

[K-Means聚类算法 — 算法原理、质心计算、距离度量、聚类效果评价及优缺点][K-Means_ _]

与K-Means算法不一样的是，Mean Shift 算法可以自动决定类别的数目。与K-Means算法一样的是，两者都用集合内数据点的均值进行中心点的移动。

--------------------

**声明**

以下部分内容来源于：[meanshift算法][meanshift]

--------------------

#### Mean Shift算法原理 ####

meanshift 算法其实通过名字就可以看到该算法的核心，mean(均值)，shift(偏移)，简单的说，也就是有一个点  x x x,它的周围有很多个点 x i x\_i xi 我们计算点 x x x移动到每个点  x i x\_i xi，所需要的偏移量之和，求平均，就得到平均偏移量，（该偏移量的方向是周围点分布密集的方向）该偏移量是包含大小和方向的。然后点 x x x就往平均偏移量方向移动，再以此为新的起点不断迭代直到满足一定条件结束。

**图解如下:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]  
   中心点  x x x 周围的小红点就是  x i x\_i xi，黄色的箭头就是我们求解得到的平均偏移向量。那个“圆圈”就是我们的限制条件，或者说在图像处理中，就是我们搜索迭代时的窗口大小。不过在opencv中，我们一般用的是矩形窗口，而且是图像，2维的。这里其实不是圆，而是一个高维的球。

**步骤：**

1.  首先设定起始点 x x x，我们说了，是球，所以有半径 h h h， 所有在球内的点就是  x i x\_i xi , 黑色箭头就是我们计算出来的向量 , 将所有的向量 进行求和计算平均就得到我们的meanshift 向量，也就是图中黄色的向量。
2.  以meanshift向量的重点为圆心，再做一个高维的球，如下图所示，重复上面的步骤，最终就可以收敛到点的分布中密度最大的地方  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]  
    最终结果如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]

--------------------

[Mean-Shift聚类流程：][Mean-Shift](点击查看原博客)

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]

开始
    	1. 在未被标记的数据点中随机选择一个点作为中心center；
    	
    	    2. 找出离center距离在bandwidth之内的所有点，记做集合M，认为这些点属于簇c。同时，把这个球内部点(属于这个类)的概率加1，这个参数将用于最后步骤的分类
    	
    	    3. 以center为中心点，计算从center开始到集合M中每个元素的向量，将这些向量相加，得到向量shift。
    	
    	    4. center = center+shift。即center沿着shift的方向移动，移动距离是||shift||。
    	
    	5. 重复步骤2、3、4，直到shift的大小很小（就是迭代到收敛），记住此时的center。注意，这个迭代过程中遇到的点都应该归类到簇c。
    
    6、如果收敛时当前簇c的center与其它已经存在的簇c2中心的距离小于阈值，那么把c2和c合并。否则，把c作为新的聚类，增加1类。
    
    7、重复1、2、3、4、5直到所有的点都被标记访问。
    
    8、分类：根据每个类，对每个点的访问频率，取访问频率最大的那个类，作为当前点集的所属类。

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

[K-Means_ _]: https://blog.csdn.net/weixin_43283397/article/details/105241340
[meanshift]: https://blog.csdn.net/csdnforyou/article/details/81161840?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159013694319725211956076%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=159013694319725211956076&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v28-1-81161840.first_rank_v2_rank_v28&utm_term=meanshift%E7%AE%97%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200522190614683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200522191202780.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020052219122286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70#pic_center
[Mean-Shift]: https://blog.csdn.net/hjimce/article/details/45718593
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200717115826709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw==,size_16,color_FFFFFF,t_70