图解Mean-Shift聚类算法
前期回顾
基于K均值的聚类算法 — 核心概念与实现机制
基于K均值的聚类算法 — 核心概念与实现机制
基于K均值的聚类算法 — 核心概念与实现机制
不同于K-Means算法的是, Mean Shift 算法其主要优势在于能够自动决定类别的数目. 另一方面, 在于两者在核心机制上具有相似性, 它们都采用集合内数据点均值来进行中心点更新.
声明
以下具体内容源自[meanshift算法]文章
Mean Shift算法原理
meanshift 算法的核心可以从其名称中一目了然。其中mean表示均值、shift表示位移。也就是说存在一个点x，在其周围有多个点x_i；我们计算将该点x移动至每个邻近的x_i所需的所有位移矢量之和，并取这些位移矢量的算术平均得到一个总位移矢量。这个总位移矢量的方向指向周围密集区域的方向，并且这个总位移矢量化作为更新向量应用到当前的位置上。随后将这个总位移矢量化作为更新向量应用到当前的位置上，并不断更新位置直至满足预设终止条件结束这一过程
图解如下:
核心位置 x 旁边的红色标记点即为 x_i；该箭头代表了平均偏移方向。这个"圆圈"即为约束条件，在图像处理中通常被视为搜索区域的边界；然而，在OpenCV中，默认使用的通常是矩形窗口来处理二维图像问题。实际上，在高维空间中这是一个超球体而非传统的圆形。
步骤：
我们从起始点x开始设定，并说明这是一个球体形状的事物, 因此具有半径h的属性. 所有的位于这个球体内部的点即为x_i, 黑色箭头代表了我们通过计算得到的方向. 将所有的这些方向进行求和并取平均值, 从而得出我们的meanshift向量本身, 即为图中所示的黄色箭头.
以均值偏移向量的重点为中心，在此基础上构建一个高维球体（如图1所示），然后反复执行上述操作
最终结果如下：
Mean-Shift聚类流程：(点击查看原博客)
假设在一个高维空间中有大量数据点需要进行聚类分析，Mean-Shift算法的具体步骤如下：
假设在一个高维空间中有大量数据点需要进行聚类分析，Mean-Shift算法的具体步骤如下：
开始
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 即沿着数据密度递增的方向搜索属于同一簇的所有数据点。