FindShine分享 http://blog.sciencenet.cn/u/fs302 Find Your Way

博文

Science上发表的简单快速的聚类方法

已有 10814 次阅读 2014-8-25 23:37 |系统分类:科研笔记| 聚类

工作以后发现自己学习和研究的时间变得少得可怜。

前两周因为一个同事的交流,关注了一下canopy辅助Kmeans聚类确定簇数目。然后想起最近很火的一篇Science文章:Clustering by fast search and find of density peak,据说非常简单而优美。然后上网上搜了一下,评论的文章也就那样转来转去,其实就是把人家论文拿来翻译一下,有些关键点根本没讲清楚,真不知道翻译者是不是自己实现过那个算法。

我之所以对这个算法感兴趣,主要是因为看到论文中可以识别那么奇形怪状的点簇,然后又只有两个指标,好像很有道理又很好算的样子。没想到被坑惨了,我用了差不多两个星期,偶尔下班后有时间看论文、写代码,才把这个简单的算法实现下来。其中依然还有一个参数需要手工调整,就是delta的阈值(下面有讲)。

图1 聚合点簇Aggregation(共7个聚类,采用Cut off kernel)Aggregation-Cut off Kernel


这个算法,其实是对所有坐标点,基于相互距离,提出了两个新的属性,一是局部密度rho,即与该点距离在一定范围内的点的总数,二是到更高密度点的最短距离delta。作者提出,类簇的中心是这样的一类点:它们被很多点围绕(导致局部密度大),且与局部密度比自己大的点之间的距离也很远。

图2 A sets(20个聚类,算法分出19个,采用Cut off kernel)A sets-Cut off Kernel


聚类过程,这篇文章讲的还不错,首先我们要把所有点的两个属性算出来,可以画出一个平面决策图;根据决策图,选出rho和delta都大的点作为聚类中心;选定中心后,让周围的点采取“跟随”策略,归类到密度比自己大的最近邻居所在的簇。 我更想说的是两点,第一点关于聚类中心的选择,我翻看了几篇文章(包括作者原文),都没有明确指出一个很好地自动确定中心数目的方法,较多的做法是画出决策图后进行人工选定范围。我的做法是,按rho排序,然后根据决策图人工对delta取一个合适的值,大于这个delta值的,才能被选为中心。这种做法很人肉,让我一直有没完结的感觉,继续探索一下有没有自动确定这个阈值的方法。文章提及可以利用r = rho*delta 或者 rho和delta的联合分布来进行分析判断。但在实际应用中,却不一定可以自动化。

图3 火焰形状(2个聚类,采用Cut off kernel)Flame-Cut off Kernel


第二点是关于rho的计算,其实论文中只提到一个计算公式,是通过截断距离做线性判断,即rho=sigma(sign(dij-dc)),这个计算方法对一般的球状簇,如图1,图2,有不错的效果,而且计算快速,但是对图3的异形图(类簇形状并不呈球状分布),效果就不好了。这时候翻看作者给出的matlab源码,了解到还可以使用高斯核(Gaussian Kernel)函数来定义局部密度,引入以后就完全handle了异形的问题,见图4,我觉得高斯核函数确实是强大,对于这个问题,@范涛-中科大 给出的解释是:“cut-off-函数是把小于dc的都看成一样,而高斯核函数是根据距离衰减的。一个节点周围都是距离略小于dc的点(有点球状感觉 ),和一个节点周围被距离呈衰减的点围绕(类似火焰型数据),这个在cut-off函数算密度时候,两种节点是不区分的,但是用高斯核函数算有区别,这就是为什么火焰型数据高斯核函数相对更好点。”同样的问题我也请教了邵俊明老师,他给出了这样的解释:“高斯核函数是从中心到外围有权重的距离公式,因此比较适合计算球形状的密度估计,当然只要能表明中心比局部更重要的数据都可以用这个核函数。而欧式距离是没有考虑权重的。即欧式距离是线性衰减的,而高斯核函数时指数衰减的。”说得我豁然开朗。

具体实现可以参看python代码(两种rho的计算都有)。

图4 火焰形状(2个聚类,采用Gaussian kernel)Flame-Gaussian kernel


DATA来源:http://cs.joensuu.fi/sipu/datasets/

[CODE:flame_GaussianKernel.py]



http://blog.sciencenet.cn/blog-588923-822281.html

上一篇:Learned from Jure's PhD defense
下一篇:Bandit:一种简单而强大的在线学习算法

4 吴世凯 陆泽橼 彭友松 窦杰

该博文允许注册用户评论 请点击登录 评论 (3 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-8-12 12:42

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部