均值漂移 (Mean Shift)

均值漂移 (Mean Shift)是一种定位密度函数最大值的非参数聚类算法。

Agreement

均值漂移（Mean Shift）是一种利用区域的质心与几何中心不同，沿着密度增加方向移动的聚类方法。

下图中蓝色圆形感兴趣区域内，几核中心用蓝色小圈表示，质心用黄色小圈表示，算法将沿着行心指向质心的向量移动

质心迁移

算法迭代过程如下，最终会收敛到区域密度极大处。

迁移过程

在数量为 $n$ 的 $d$ 维样本空间 $R^d$ 中，确定一个样本作为初始中心点 $x_{init}$
以中心点 $x^{iter}$ 为球心，$h$ 为半径的高维球 $S_h$ 将覆盖 $k$ 个样本点 $x_i$，其中 $i=1,2,....k$，计算高维球的行心与质心的偏移向量 $M$
1. $M(x^{iter}) = \frac{1}{k}\sum_{x_i\in S_h}(x^{iter}-x_i)$，其中 $S_h=\left\{ x:(x-x^{iter})_T(x-x^{iter})<h^2\right\}$
2. 使用核函数版本，$M_h(x^{iter})=\frac{\sum^k_{i=1}x_ig(||\frac{x^{iter}-x_i}{h}||^2)}{\sum^k_{i=1}g(||\frac{x^{iter}-x_i}{h}||^2)}-x^{iter}$，其中 $g$ 为对核函数的导数求负
迭代更新中心点 $x^{iter+1}$

$x^{iter+1}=x^{iter}+M(x^{iter})$
重复 2-3 步，直至收敛或迭代条件满足（2.2 为引入核函数的偏移向量计算形式）