聚类算法汇总

1 MeanShift（均值偏移）算法

1.1 基本思想

核心概念：沿着密度上升方向寻找聚簇点（爬山算法）。
均值偏移（Mean shift）聚类算法是一种基于滑动窗口（sliding-window）的算法，它试图找到密集的数据点。它还是一种基于中心的算法，它的目标是定位每一组群/类的中心点，通过更新中心点的候选点来实现滑动窗口中的点的平均值。这些候选窗口在后期处理阶段被过滤，以消除几乎重复的部分，形成最后一组中心点及其对应的组。

1.2 算法描述

设想在一个有N个样本点的特征空间

1.初始确定一个中心点center，可以随机选取。

2.计算在设置半径为D的整个圆形空间内所有向量（即包括中心点center）的平均值，得到一个偏移均值。

3.将中心点center移动到偏移均值位置。

4.重复移动，直到满足一定条件结束。

如下图为使用许多滑动窗口完成的MeanShift聚类：

1.3 优势和缺点：

优点：
1）与K-Means聚类相比，MeanShift聚类不需要选择聚类的数量，因为它会自动地发现所有的类别。这是一个巨大的优势。聚类中心收敛于最大密度点的事实也是非常可取的，因为它非常直观地理解并适合于一种自然数据驱动。

缺点：
1）缺点是选择窗口大小/半径r是非常关键的，所以不能疏忽。