快速聚类方法
快速聚类方法
1.概要
2.背景
2.1传统的聚类分析
2.2本文创新点
3.本文聚类分析
4.实验
4.1 论文中算法
4.2 改进方法
5.分析总结
6.参考文献
1.概要
本文算法的核心：聚类中心点的密度大于周围的点，高密度之间具有很大的距离。论文下
载点这
2.背景
2.1传统的聚类分析
kmeans之类的没法解决非球面类型
很明显效果很差1
2.2本文创新点
非球形数据不方便聚类，基于密度的方法很方便的可以检测到任意形状的簇。
于是本文重新定义了簇的概念，聚类算法的依据：簇就是点密度较高的峰值，即概率分布的
峰值
Clusters=peaks in the density of points =peaks in the “mother” probability
distribution 本文算法的基础假设：聚类中心被周围具有低密度的邻点包围，和周围具有高局部
密度的点有着很大的相对距离,点的局部密度计算如下：
通常等于周围距离小于点的个数。的选取很重要
通过观察，通过计算点与其他任意具有更高密度的点：
对于密度最大的点, 设置. 注意只有那些密度是局部或者全局最大的点才会有
远大于正常的相邻点间距.
由上图可知
上图是所有点在二维空间的分布, 右图是以为横坐标, 以为纵坐标, 这种图称作决策图
(decision tree). 可以看到, 1和10两个点的和都比较大, 作为类簇的中心点. 26, 27, 28三个点的也比较大, 但是较小, 所以是异常点.
3.本文聚类分析
在聚类分析中, 通常需要确定每个点划分给某个类簇的可靠性. 在该算法中, 可以首先为每个
类簇定义一个边界区域(border region), 亦即划分给该类簇但是距离其他类簇的点的距离小
于的点. 然后为每个类簇找到其边界区域的局部密度最大的点, 令其局部密度为. 该类簇
中所有局部密度大于的点被认为是类簇核心的一部分(亦即将该点划分给该类簇的可靠性
很大), 其余的点被认为是该类簇的光晕(halo), 亦即可以认为是噪音. 图例如下
A图为生成数据的概率分布, B, C二图为分别从该分布中生成了4000, 1000个点. D, E分别是
B, C两组数据的决策图(decision tree), 可以看到两组数据都只有五个点有比较大的和很大的. 这些点作为类簇的中心, 在确定了类簇的中心之后, 每个点被划分到各个类簇(彩色点),
或者是划分到类簇光晕(黑色点). F图展示的是随着抽样点数量的增多, 聚类的错误率在逐渐
下降, 说明该算法是鲁棒的.
4.实验
4.1 论文中算法
计算数据后的决策图，手工选取的过程,通过框选认可的类簇中心
不同的有不同的效果，预期达到分类效果，需要选取合适的阈值
当阈值选的偏差过大，聚类效果不明显，由此可以阈值的选取很重要
4.2 改进方法
原文作者提供的程序运行比较慢，改进主要是利用高斯核距离代替线性距离计算，
但是没有实现文献中提到的利用熵来动态划分的选取2
5.分析总结
在本文中阈值的选取及其重要，直接影响了聚类的效果，但是本文中是人工手动选择，
缺乏普适性，还有一点就是本文中的密度的距离的划分是线性距离。在文献中，作者提出
了针对本文算法的一些改进方法，首先就是使用高斯核距离代替线性
距离划分，通过加权可以更好的区分边缘点和簇内点,另一篇文献中通过热力图来计算密
度，基于热力图的有限域，该方法在划分和核密度边界评估(Kernel density estimation)有
着很好效果。本文的核心思想在于用密度划分簇，在数据量充足的情况下接近数据真实分
布，在查阅一些资料后，有人认为本文算法虽然可以不对数据分布做预期假设，对于高维不
充足的数据密度估计不准确，但是这似乎并没有问题，在本文另一项试验中是对人脸进行聚
类，表现很好，关键点在于metric的选择，通过改变metric可以提高本文的鲁棒性。本算法
还有个好处，没有优化过程，没有多变量参数，簇是直接从数据中广义的获得。
6.参考文献
1. Alex Rodriguez, Alessandro Laio.Clustering by fast search and find of density peaks2
3
.Science 27 Jun 2014: ↩
2. S Wang，D Wang，C Li，Y Li.Comment on “Clustering by fast search and find of
density peaks”.《Computer Science》, 2015 ↩
3. Rashid Mehmooda, b, , Guangzhi Zhanga, , Rongfang Biea, Hassan
Dawoodd,Haseeb Ahmadc.Clustering by fast search and find of density peaks via
heat diffusion.doi:10.1016/j.neucom.2016.01.102 ↩