Mean shift 算法

常用的聚类算法除了K-means外，还包括MeanShift和AP算法。在此基础上，我们来系统地介绍MeanShift的基本原理和应用。

Mean shift基本思想

Mean shift将特征空间视为满足某种概率分布的概率密度函数这一假设，则输入样本点被视为服从该分布的一组独立样本点。这种情形下，在特征空间中数据最密集的区域对应着概率密度最大的区域范围，并且该区域内概率密度的质心位置即为该区域的概率密度函数的局部最优解，也就是我们所求取的聚类中心位置。

对于每个样本点x_i，在其周围区域内计算所有其他样本点x_j（j≠i）的均值\frac{1}{N}\sum_{j≠i}x_j作为新的中心位置x_i'。通过不断迭代更新位置直至达到稳定状态（即收敛条件满足）。每一次迭代都会使各中心位置逐渐向数据密度更高的区域靠拢。

伪代码可以写成：

    重复移动直至收敛｛
    对每一个数据点，固定一个窗口（数据范围）：
    计算窗口内数据的中心；
    移动窗口至新的中心
    ｝

###完成中心的平移过程？### 可以通过计算概率密度的梯度来实现其方向即为概率密度增长最快的方向从而也就指向了数据分布最密集的方向 ####预备知识#### - 核 Kernels : 核是满足如下条件的函数：

1.

2.

常见的核函数包括 :

1. Rectangular

2. Gaussian

3. Epanechnikov

- 核密度估计 Kernels Density Estimation :

核密度估计算法是一种基于非参数统计方法用于估算概率密度分布的技术，
亦称Parzen窗技术。
给定一个核函数Kernel以及带宽 h（简称为bandwidth），对于d维数据样本点
x₁, x₂, ..., xₙ，
核密度估计算法的具体表达式描述如下：

- Mean shift的梯度下降计算

对概率密度求梯度 ,

令梯度为0,

最后可得到中心的变化

总结

将每个样本点视为窗口的核心位置，并继而确定最终核心位置；属于同一核心位置的所有样本即被视为同一类别。

记

, 有

就是 mean shift. 所以mean shift过程可被总结为 : 对每一个样本点

1. 计算mean shift 向量

2. 移动概率估计窗

3. 重复上述过程直至收敛

以高斯核为例,

1.

2.

Mean shift VS. K-Means

K-Means 作为一种广为人知的聚类技术，并且具有良好的适用性。接下来可以从参数数量的角度比较这两种聚类方法。

K-Means 作为一种广为人知的聚类技术，并且具有良好的适用性。接下来可以从参数数量的角度比较这两种聚类方法。

对于K-means算法而言，它不仅要求提供指定数量的聚类中心，并且其生成的聚类结果通常呈现出较为规则的几何形态；相比之下，在不必要提供预先设定的数量化指导的同时也不需考虑特定的几何形态的情况下，则是Mean shift方法作为一种基于非参数估计的技术。

在使用K-means算法时需预先设定聚类中心位置，并且不同的初始设置会导致最终形成的聚类结果有所差异；相比之下, Mean shift算法由于其独特的机制——即从每个数据点或者在特征空间中均匀采样来选择初始中心——表现出很强的鲁棒性；值得注意的是,K-means算法较为容易受到异常数据的影响,而Mean Shift则表现出较好的抗噪声能力

K-means 速度比较快，时间复杂度为

其中 k 表示聚类中心的数量, n 表示样本点的数量, T 表示迭代次数. 一般而言, mean shift算法在计算时间上的消耗较大,其时间复杂度为 O(n^2kT)

.

带宽参数的选择对Mean shift影响很大,带宽

选的小时收敛速度慢；

选的大时虽然会加速收敛但是聚类效果不会很好. 对于

在scikit-learn中包含有多种实现方式和带宽选择技巧。