基于流形距离的密度峰值快速搜索聚类算法

张嘉琪　张红云

摘要：针对2014年6月发表在Science上的基于密度峰和快速搜索的聚类算法容易忽略无密度极值的簇的缺陷，提出了一种基于流形距离的密度峰值快速搜索聚类算法。算法利用流形距离弥补了传统欧式距离对于复杂数据无法反应聚类的全局一致性（即位于同一个类中的样本点之间有较高的相似度）的缺陷，通过近邻点充分挖掘复杂数据的流形结构信息，使处于同一个流形中的样本点之间相似性较高，从而正确找到密度极值点作为聚类中心点，完成聚类。本文算法能够发现较复杂的流形结构，在公开数据集上能取得较好的实验结果。

關键词： 聚类；流形距离；密度极值；全局一致性；聚类中心

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）02-0179-04

Clustering by Fast Search and ?nd of Density Peaks Based on Manifold Distance

ZHANG Jia-qi1，2，ZHANG Hong-yun1，2

（1.Department of Computer Science and Technology， Tongji University， Shanghai 201804， China；2.Key Laboratory of Embedded Systems and Service Computing，Ministry of Education，Tongji University，Shanghai 201804， China）

Abstract：The clustering algorithm based on density peak and fast search， which was published on Science in June 2014， is easy to ignore the cluster which has no density extreme value.So We propose an algorithm based on manifold distance to solve this problem.Instead of Euclidean distance，the algorithm uses manifold distance to reflect the global consistency of samples，which means the samples in the same cluster have high similarity.We find manifold structure information of complex data by neighbor points ，so that samples in the same manifold have high similarity and the cluster center is easy to find. In this paper， we can find manifold structure of complex data， and obtain better results in the open data sets.

Key words：clustering；manifold distance；density peak； global consistency；clustering center

1 概述

聚类作为一种有效的数据分析手段，已成为模式识别，人工智能，数据挖掘等领域的研究热点。在聚类分析过程中，不需要任何先验知识或者是假设，因此聚类是一种无监督学习过程。聚类算法包括划分式聚类方法、层次聚类方法、基于密度的聚类方法和基于网格的聚类方法，以及基于模型的聚类算法.K-means[1]是应用范围最广的划分式聚类算法.然而，K-means算法的聚类结果依赖于初始类簇中心的选取，而且倾向于发现凸形状的簇，对噪声点和离群点敏感，且聚类个数K需要事先设定.针对K-means的缺陷，出现了K-modes[2]算法等诸多改进算法. DBSCAN[3]是一种比较典型的基于密度的聚类方法，要求聚类空间中的一定区域内所包含对象（点或其他空间对象）的数目不小于某一给定阈值。DBSCAN算法的显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类，与K-MEANS比较起来，不需要输入要划分的聚类个数。近邻传播聚类算法AP（affinity propagation）[4]将所有样本看作网络中的一个顶点，通过反复迭代交换近邻样本间的信息，寻找最优的类代表点样本集合，使所有样本与最近类代表点样本的相似度之和最大，发现数据集样本的类簇分布.AP算法具有简单、高效的优点，特别是在类别数目较多情况下，该算法具有非常好的聚类效果，但是该算法不能发现任意形状的簇. 基于层次的有CURE[5]、ROCK[6]、BIRCH[7]。层次的方法的缺陷在与错误的累积，它不能更正错误的决定。但是它能发现非凸的数据分布。

2014年6月Science发表了自动确定类簇数和类簇中心的新聚类算法CFSFDP （clustering by fast search and find of density peaks）[8]，该算法能快速发现任意形状数据集的密度峰值点（即类簇中心），并高效进行样本点分配和离群点剔除，适用于大规模数据的聚类分析.但是该算法容易忽略不存在密度极值点的簇，导致该类簇被划分到其他类中，造成错误的聚类结果。

鉴于此，本文提出一种采用流形距离的密度峰值快速搜索聚类算法，利用流形距离来保证同一个簇中的样本点相似性高，从而使每个簇中都存在密度极值，使算法能够准确发现簇中的聚类中心点，并完成聚类。

2 CFSFDP

CFSFDP是2014年发表在Science杂志上的一种聚类算法，因为它的思想简洁优美，提出之后就受到了广泛的关注。该算法的核心思想在于对聚类中心的确定上，作者认为聚类中心同时具有以下两点特征：

1.本身的密度大，周围点的密度比他小

2.与其他密度更大的点的距离相对更大

因此为每个样本点都引入两个属性：局部密度[ρi]和距离[δi]，由公式（1）（2）计算获得。

[ρi=j∈IS＼{i}e-（dijdc）2] （1）

[δi=minj∈IiS{dij}，IiS不為空maxj∈IS{dij}，IiS为空] （2）

[IS]表示所有样本点的下标序号，[IiS]表示所有密度大于点i的样本点的下标序号。[dc]表示邻域大小，根据所有点与点的欧式距离小于[dc]的占总样本数的k%来确定，k为我们需要输入的参数。[dij]表示两个样本点的欧式距离。如公式（1），（2）所示，对于局部密度[ρi]，该算法用高斯核来进行密度的计算，用点i到比点i密度高的所有点的最短距离表示[δi]。

如图1所示，图1（a）是样本集，样本集的序号按照密度的大小降序排列，图1（b）为以两个属性为横纵坐标的决策图，显然点1和点10为聚类中心。对于剩下的点，点的类别标签与高于当前点密度的最近的点的标签一致。从而对所有点的类别进行了指定。而且该算法利用临界密度很好的过滤掉噪音点。

该算法仅需要输入确定邻域的参数k，且时间复杂度较K-means低，能识别部分复杂分布的样本点，在人脸识别上也取得了较好的实验结果。但是该算法的有效性建立在一个隐性的假设，即数据集中属于同一个类的数据点的密度分布有且仅有一个极值。倘若数据分布不含有这一特征，相对稀疏的类的聚类中心则容易被淹没，例如圆环型数据集，CFSFDP就会得到错误的结果[9]。

3 基于流形距离的相似性度量方法

在复杂数据聚类问题，由于数据的分布通常具有不可预期的复杂结构，导致了传统的基于欧氏距离相似性度量的聚类算法无法反映聚类的全局一致性（即位于同一流形上的数据点具有较高的相似性）.从图2所示的例子中可以看出，在用欧式距离衡量样本点之间的相似性时候，样本点A与样本点C的相似性要比样本点A与样本点B的相似性更大.因此A与C划分到同一类的概率是要大于A与B划分到同一类的概率的。但是，显而易见，A与B是属于同一个流形，也就是说A与B是属于同一类的，用欧氏距离作为相似性度量根本无法反映图中所示数据的全局一致性.因此，对于现实世界中复杂的聚类问题，简单地采用欧氏距离作为相似性度量会严重影响聚类算法的性能。

流行距离又叫做测地距离（Geodesic distance），Isomap[10]降维算法为了在低维空间下保留数据在高维空间的相似性，引入了测地距离的概念。测地距离的基本思想是：当两点非常接近（k近邻点）时，测地距离等于欧式距离，而当两点相对较远的时候，测地距离则根据近邻点之间测地距离的累加实现，是一种迭代的距离度量方法[10]。例如图2的聚类问题，若采用测地距离作为相似性度量的方法，A可以通过若干个k近邻点迭代的计算与B之间的相似度，而与C的相似度为无穷小的，这种相似性度量方法比直接采用欧氏距离更加合理。

测地距离的计算过程如下[10]：

1.定义邻域大小n，根据邻域大小构造测地距离

2.每个样本与自己的n近邻点的距离为欧氏距离，与其余点的距离为无穷大。即：

[dG（xi，xj）=dE（xi，xj），若xi，xj为近邻∞，若xi，xj不为近邻] （3）

3.使用其他点为媒介，计算每个样本与其他所有点的距离：

[dG（xi，xj）=mindG（xi，xj），dG（xi，xt）+dG（xt，xj）] （4）

4 基于流形距离的密度峰值快速搜索聚类算法

流形距离能放大类间差异，使同一个流形上的样本点能有更大的概率被划分到同一类上，同时也保证了同一个流形上的样本点有更高的相似性，也就是说流形上存在密度极值点。为了能使CFSFDP聚类算法能够发现在欧式空间下容易被忽略的聚类中心，本文在原有CFSFDP聚类思想的基础上，提出了一种基于流形距离的密度峰值快速搜索聚类算法，具体步骤如下：

输入：高斯核参数[σ]，CFSFDP算法邻域参数k，样本点

输出：聚类结果

第一步：近邻个数可取3到6个[1]，计算第3节的流行距离，用高斯核计算点与点之间的相似度，获得样本点的相似度矩阵[A∈Rn×n]，对角线上的元素Aii = 0。

[Aij=e-dG（xi，xj）22σ2] （5）

第二步：按照公式（1）（2）计算每个样本点的密度和距离属性。

第三步：将每个点绘制到以密度为横坐标，距离为纵坐标的坐标轴上，根据第2节CFSFDP的步骤选取聚类中心。

第四步：对于剩下的点，点的类别标签与高于当前点密度的最近的点的标签一致。

5 实验结果及分析

5.1 有效性实验

为了验证算法的有效性，采用公开数据集Jain，Pathbased，Spiral和人工数据集同心圆对算法进行检验。在相似性计算时，近邻个数n根据文献[12]取3，高斯核参数[σ]根据经验取5，CFSFDP算法邻域参数k取20。

如图3所示，本文算法对于复杂分布的流形结构都能取得正确的聚类结果。这是因为流形距离根据结构信息使同一个流形中的样本点相似性更加真实。每个簇中都存在密度极值点，便于CFSFDP算法发现该簇中的聚类中心点，弥补了在欧氏距离下容易忽略某些聚类中心的缺陷。

5.2 对比性实验

对比CFSFDP聚类算法，同样利用四种数据集进行对比性实验。实验需要使用的参数与5.1节一致。

（a） 3 circle

（b）pathbased

（c） spiral

（d）jain

图4 CFSFDP算法实验结果

如图4所示，CFSFDP较难在此类分部复杂的数据集上取得正确的聚类结果。这是因为在用欧式距离衡量相似性的时候，该算法还是倾向于发现球状的簇，导致某些密度小的类簇聚类中心被忽略，造成错误的聚类结果。

6 结论

本文将流形距离和CFSFDP算法相结合，提出一种能处理复杂分布数据的聚类算法，并通过对聚类效果进行分析，得到了若干有指导意义的结论。与现有典型的聚类算法相比，本文提出的算法能准确找到聚类中心，稳定的取得较好的聚类效果，且时间复杂度与原算法一致，为聚类问题的研究提供了新的思路。但是本文算法会随着设置的邻域个数变大，会出现过连通的问题，也就是不同类之间的点也存在最短路径，如何确定邻域个数，是一个值得深入研究的课题。

参考文献：

[1]吴夙慧，成颖，郑彦宁，等. K-means算法研究综述[J]. 现代图书情报技术， 2011（5）：28-35.

[2]梁吉业，白亮，曹付元. 基于新的距离度量的K-Modes聚类算法[J].计算机研究与发展，2010（10）：1749-1755

[3]冯少荣，肖文俊. DBSCAN聚类算法的研究与改进[J].中国矿业大学学报，2008（1）：105-111。

[4]Local and global approaches of affinity propagation clustering for large scale data[J]. Journal of Zhejiang University（Science A：An International Applied Physics & Engineering Journal），2008（10）：1373-1381.

[5]馮兴杰，黄亚楼. 增量式CURE聚类算法研究[J]. 小型微型计算机系统，2004（10）：1847-1849.

[6]赵雪，陈龙飞.基于MapReduce的ROCK聚类算法[J].河北科技师范学院学报， 2014，28（1）：26-32.

[7]蒋盛益，李霞.一种改进的BIRCH聚类算法[J].计算机应用，2009，29（1）：293- 296.

[8]Alex Rodriguez，Alessandro Laio.Clustering by fast search and find of density peaks.Science 344，1492（2014）.

[9]张文开.基于密度的层次聚类算法研究[D].中国科学技术大学，2015.

[10]Tenenbaum J B，Silva V，Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290（12）：2319-2323.

[11]陶新民，宋少宇，曹盼东，等.一种基于流形距离核的谱聚类算法[J].信息与控制，2012，41（3）：307-313.

[12]Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）：395-416.