Clustering by fast search and find of density peak

william 发布于2019-07-30 14:42 / 3144人阅读

摘要：原文链接聚类算法介绍聚类是将数据对象的集合分成相似的对象类的过程。其中基于距离的聚类算法是用各式各样的距离来衡量数据对象之间的相似度。基于互连性的聚类算法通常基于图或超图模型，将高度连通的对象聚为一类。

原文链接 https://zhangmingemma.github....

聚类算法介绍

　　聚类是将数据对象的集合分成相似的对象类的过程。使得同一个簇（或类）中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。按照聚类的尺度，聚类方法可被分为以下三种：基于距离的聚类算法、基于密度的聚类方法、基于互连性的聚类算法。其中基于距离的聚类算法是用各式各样的距离来衡量数据对象之间的相似度。基于密度的聚类算法主要是依据合适的密度函数等。基于互连性的聚类算法通常基于图或超图模型，将高度连通的对象聚为一类。

本文介绍的是Alex Rodriguez和Alessandro Laio在Science上发表的《Clustering by fast search and find of density peaks》所提出的一种新型的基于密度的聚类算法。

算法思想

该算法的假设类簇的中心由一些局部密度比较低的点围绕, 并且这些点距离其他有高局部密度的点的距离都比较大.首先定义两个值：局部密度ρi以及到高局部密度点的距离δi，这两个值仅仅取决于两点之间的距离dij，且该距离满足三角不等式

其中dc是一个截断距离, 是一个超参数.所以ρi相当于距离点i的距离小于dc的点的个数.由于该算法只对ρi的相对值敏感,
所以对dc的选择比较鲁棒, δi用于描述点i到其他较高密度点之间的最小距离：

对于密度最大的点, 设置δi=maxj(dij).只有那些密度是局部或者全局最大的点才会远大于正常的相邻点间距.因此聚类中心被视为是δi值异常最大的点。

聚类过程

那些有着比较大的局部密度ρi和很大的δi的点被认为是类簇的中心. 局部密度较小但是δi较大的点是异常点.在确定了类簇中心之后, 所有其他点属于距离其最近的类簇中心所代表的类簇.具体的聚类过程可以从图1中看到，A图标识二维空间内的28个点，可以看到1和10两个点的密度最大，因此1和10被定义为聚类中心。右图是以ρi和为横坐标, 以δi为纵坐标, 这种图称作决策图。其中9和10两个点ρi值相似，但δi值却差异很大，因此9被归为点1的类簇，而10被归为另一类簇。所以，只有较高δi值和相对较高ρi值的点才会被视为聚类中心。26, 27, 28三个点的δi也比较大, 但是ρi较小, 所以是异常点.

聚类中心确定之后，剩余点被分配给与其具有较高密度的最近邻居相同的类簇。与其他迭代优化的聚类算法不同，类簇分配在单个步骤中执行。在聚类分析中, 通常需要确定每个点划分给某个类簇的可靠性. 在该算法中, 可以首先为每个类簇定义一个边界区域(border region), 亦即划分给该类簇但是距离其他类簇的点的距离小于dc的点. 然后为每个类簇找到其边界区域的局部密度最大的点, 令其局部密度为 . 该类簇中所有局部密度大于的点被认为是类簇核心的一部分(亦即将该点划分给该类簇的可靠性很大), 其余的点被认为是该类簇的光晕, 亦即可以认为是噪音

图A表示点分布，其中包含非球形点集和双峰点集。B和C分别表示4000和1000个点按照A中模式的分布，其中点根据其被分配的不同类簇着色，黑色的点属于类簇光晕。D和E是对应的决策图，而F表示的是不同点量下不正确聚类点的比率，误差线代表平均值的标准差

聚类结果

图3是分别利用点集和Olivetti脸部图片集的聚类结果

算法特点

算法具有以下特点：

A．该算法是一种基于密度的聚类算法，核心思想是认为类簇的中心由一些局部密度比较低的点围绕, 并且这些点距离其他有高局部密度的点的距离都比较大。

B．该算法将非聚类中心点的聚类过程分离成一个多带带的进程。使得聚类中心的选择和非聚类点的归类分离开来，增大了聚类精度。

C．该算法适用于图片、非球形点集的聚类。

云服务器 GPU云服务器 share-and-find density Clustering peaks

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/40863.html

机器学习——深度学习(Deep Learning)

摘要：有监督学习与无监督学习，分类回归，密度估计聚类，深度学习，，有监督学习和无监督学习给定一组数据，为，。由于不需要事先根据训练数据去聚类器，故属于无监督学习。 Deep Learning是机器学习中一个非常接近AI的领域，其动机在于建立、模拟人脑进行分析学习的神经网络，最近研究了机器学习中一些深度学习的相关知识，本文给出一些很有用的资料和心得。Key Words：有监督学习与无监督学习，分类...

Guakin_Huang 2019-04-25 17:57 评论0 收藏0
Learning Deep Learning（学习深度学习）

摘要：如果你对算法实战感兴趣，请快快关注我们吧。加入实战微信群，实战群，算法微信群，算法群。作者：chen_h微信号 & QQ：862251340微信公众号：coderpai简书地址：https://www.jianshu.com/p/e98... Learning Deep Learning（学习深度学习） There are lots of awesome reading lists...

newtrek 2019-07-30 15:16 评论0 收藏0
MongoDB 使用不同表结构存储时间序列数据的查询效率分析

摘要：每个对应时间序列的一行所以按照测试数据来说，就会插入个文档到里。同时嵌套存储还有助于在按条件过滤的情况下砍掉不需要递归查询的子文档数量。我们这里关注的是在同样配置的情况下，不同表结构对于查询时间的相对关系。数据结构介绍最完整的时间序列的逻辑数据模型如下： [timestamp],[d1],[d2]...[dn],[v1],[v2]...[vn] d1 ~ dn 是维度，比如...

LuDongWei 2019-06-26 16:51 评论0 收藏0