一种面向高维数据的密度峰值聚类模型

蔡旭芬，靳聪，胡飞，张勤

(中国传媒大学 信息工程学院，北京 100024)



一种面向高维数据的密度峰值聚类模型

蔡旭芬，靳聪，胡飞，张勤

(中国传媒大学 信息工程学院，北京 100024)

聚类是大数据时代对海量数据进行数据挖掘与分析的重要工具。本文基于密度峰值聚类算法提出了针对高维数据的聚类模型，以直接简单的形式实现六维度以上数据的任意形状聚类。该模型实现了自动预处理过程，以局部密度较大且距离其他局部密度较大点较远的点作为聚类中心，最后引入参数调整。实验结果表明，该模型不仅对低维数据聚类实用，在高维数据的聚类效果也非常显著。

高维；密度峰值；聚类中心；数据挖掘

1 引言

聚类是对物体或抽象对象的集合分成由类似的对象组成的多个类，在数据挖掘领域发挥重要作用，同时也获得了研究机构与学者的广泛关注。前人在聚类算法这一领域也做出了重要贡献。如传统的聚类算法中，K-means算法和K-medoids算法[1]原理容易理解，实现也方便快捷，但不足之处是对异常值较为敏感；层次聚类算法[2]和划分式聚类算法[3]聚类快，但仅适用于凸形的聚类簇；DBSCAN算法(Density-based Spatial Clustering of Applications with Noise)[6]和OPTICS算法(Ordering Points to identify the clustering structure)[7]这类基于密度聚类的算法恰恰解决了以上两类算法的缺陷。相比于通常用距离聚类中心的距离和来不断优化的算法[4][5]，基于密度的聚类算法采取一种更巧妙地方是：在整个样本空间点中，各目标类簇是由一群的稠密样本点组成的，而这些稠密样本点被低密度区域(噪声)分割，而算法的目的就是要过滤低密度区域，发现稠密样本点。DBSCAN算法将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类，但该算法对初始参数过于敏感。OPTICS算法克服了DBSCAN算法存在的问题得到了更好的结果，但该算法的问题在于实现很复杂，实践应用中操作性不强。文献[8]提出了密度峰值聚类(density peak cluster，DPC)算法巧妙地避免了以上问题，以一种更为直接简洁的方式完成了聚类。然而，该算法只在低维数据上有着优越的性能，但随着数据维数的增加，聚类效果急剧下降。因此，本文基于密度峰值聚类算法提出了针对高维数据的聚类模型，以直接简单的形式实现六维度以上数据的任意形状聚类。该模型实现了自动预处理过程，以局部密度较大且距离其他局部密度较大点较远的点作为聚类中心，最后引入参数调整。

2 密度峰值聚类

密度峰值聚类(DPC)算法本质上属于密度算法。其基本思想是假设要求每一类的中心由一些局部密度比较低的点包围，并且这些点距离其他局部密度高的点的距离较大。

2.1 密度聚类算法

假设有n个样本点{1，2，3，…，n}，构造距离矩阵D，

(1)

其中dij表示点i和点j的距离。然后，定义样本点i局部密度：

(2)

且

(3)

其中，dc是一个自定义阈值(thresh)，点i的局部密度即为所有距离点i的距离小于该阈值的点的个数。该阈值的选取，直接决定了局部密度的大小。

另外，定义关于点i的函数δ：

ii.否则δi=max{dij}

此时，δ即为所有局部密度比其大的点与该点的最小距离。聚类中心的选取基于以下一个简单的原则：聚类中心的局部密度较大，且距离其他聚类中心较远。计算出所有样本点的局部密度值ρ和δ之后，选取其中δ较大且ρ局部较大的点为聚类中心(cluster centers)。由算法的假设，可以知道，局部密度最大的点是一个中心点。在确定了聚类中心之后，其它样本点按照距离已判断点的点的集合从近到远依次判断该点的所属的类别；判断的准则为每个点的类别为该点邻域内最近的局部密度高于该点的点的所属的类别。

2.2 面向高维数据的密度聚类模型

本文提出的面向高维数据的密度聚类模型包括三个部分。首先是进行自动预处理选取初始聚类中心，实现方法为归一化ρ、δ，计算μ=ρ*δ，找出μ高于均值一个方差的异常点作为初始的聚类中心；然后进行聚类，最后进行参数调整，修正异常点。具体步骤如图1所示。

图1 密度聚类步骤

数据初始化后模型开始计算距离矩阵，确定相应的阈值thresh。然后再计算所有点的ρ、δ并对ρ、δ进行归一化，找出δ*ρ大于平均值一个标准差的点作为初始的聚类中心；再对聚类中心作近邻合并，标识分类；按照距离已分类点的远近，由近到远逐个标记分类；最后修正标注ρ较小，δ较大的异常点，合并相近的类。

通过所提出的模型推理本文还得到了局部密度最大的点必定满足δ局部最大这一结论，证明如下。

命题 设r为邻域的阈值。对于任意k∈{k，dik

故δk<δi，证毕。

事实上，由该命题的证明过程我们可以发现，局部密度最大的点的δ大于所有非局部密度最大点的δ。故而δ已经足够能够反映出该聚类中心的选取方法，故而聚类中心的选取只需要考虑δ即可。

本文选取了文献[8]提供的聚类数据库使用该模型对二维数据进行测试结果如图2所示。其中阈值按照所提出的条件选取：所有点的平均近邻数量为总个数的1%到2%之间。图2(a)的数字分别表示二维点局部密度从大到小的顺序，图2(b)为所有点的density-delta图，横轴表示局部密度，纵轴表示δ。在图2(b)中，点1和点10同时有较高的δ，又有局部较高的密度，故选为聚类中心点。对于未赋值的点2，距离点2最近的密度高于该点的点为点1，故点2的类别标记为与1点相同。

(a) (b)图2 二维数据集聚类

定义边界区域包含属于该类但是距离其他类的点的距离小于阈值的点。令一类边界区域的局部密度最大的点的局部密度为ρb，该类中所有局部密度大于ρb的点被认为可靠性的点，其余的点被认为是异常点，也就是噪音。

3 实验结果与分析

本文提供了数据获取方法和数据集，阐述了实验搭建环境及实验设置，并展示了实验结果与分析。

3.1 实验搭建

本文实验环境是在一台linux操作系统台式机电脑基于Matlab平台实现的。系统配置为6核Intel Xeon Processor X4860，CPU 2.26 GHz 64 GB内存。本文的实验中，还利用了爬虫技术在真实网络环境中爬取了大量的基于web的消费者月消费水平数据，对本文提出的模型进行测试。该数据包含多个维度的数据信息，通过该模型对各个维度信息的分析可以很好地指导实际应用中如对广告精准投放、客户定向推荐等。

3.2 实验结果

本文实验根据不同归一化处理方法进行数据的DPC聚类，其中作z-score归一化处理可以将数据转换成正态分布的数据。当对数据只作z-score归一化处理时效果不好；只作数据线性归一化处理效果不好；先作线性归一化再做z-score处理效果也不好；作对数处理，效果得到改善。在对数据进行逐步分析，其中出现了一类点，该类中有相当的点局部密度远高于其他的局部密度，这导致了其δ尽管小于其他点，μ依然较大，使得部分聚类中心的μ不在均值的一个标准差之上。实验扩大聚类中心的寻找范围，调整减小初始聚类中心选择条件中的下限限定，聚类可以得到明显的变化。但是在对源数据作相关实验时候，对权重作小幅度调整的时候对聚类结果并无影响。也就是说在部分数据中均值加一个标准差已经足够选取到合适的中心点。图3为六维数据局部密度图。而且该模型对于处理非凸包类型的数据聚类效果显著。聚类效果如图4所示。

图3 六维数据局部密度-δ图

(a)三维数据集聚类 (b)六维数据集聚类

(c)七维数据集聚类 (d)七维以上数据集聚类图4 数据集各维数聚类效果

4 结论

本模型在对各种高维数据非规则图形聚类的处理效果良好，但是要注意该算法的前提：每一类的中心由一些局部密度比较低的点包围，并且这些点距离其他局部密度高的点的距离较大。该模型还存在的问题是对于不同类别数量级差别较大的聚类效果不够理想，有待进一步研究与改进。

[1]Luncien M，Cam L，Neyman J.Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability[J].University of California，1967.

[2]Johnson S C.Hierarchical clustering schemes[J].Psychometrika，1967，32(3)：241-254.

[3]Hand D J，Mannila H，Smyth P.Principles of data mining[M].MIT press，2001.

[4]Frey B J，Dueck D.Clustering by passing messages between data points[J].Science，2007，315(5814)：972-976.

[5]Höppner F.Fuzzy cluster analysis：methods for classification，data analysis and image recognition[J].John Wiley & Sons，1999.

[6]Ester M，Kriegel H P，Sander J，Xu X.Density-based spatial clustering of applications with noise[J].In Int Conf Knowledge Discovery and Data Mining，Vol 240，1996.

[7]Ankerst M，Breunig M M，Kriegel H P，Sander J.OPTICS：ordering points to identify the clustering structure[J].In ACM Sigmod Record，28(2)：49-60，1999.

[8]Rodriguez A，Laio A.Clustering by fast search and find of density peaks[J].Science，2014，344(6191)：1492-1496.

[9]Fu L，Medico E.FLAME，a novel fuzzy clustering method for the analysis of DNA microarray data[J].BMC bioinformatics，2007，8(1)：3.

[10]Zahn C T.Graph-theoretical methods for detecting and describing gestalt clusters[J].Computers，IEEE Transactions on，1971，100(1)：68-86.

[11]Chang H，Yeung D Y.Robust path-based spectral clustering[J].Pattern Recognition，2008，41(1)：191-203.

(责任编辑：宋金宝)

A High Dimension Data Based Density Peak Cluster Model

CAI Xu-fen，JIN Cong，HU Fei，ZHANG Qin

(Information Engineering School，Communication University of China，Beijing 100024，China)

Clustering is an important tool for data mining and analysis for massive data in big data era.This paper proposes a clustering model in terms of high dimension data based on density peak cluster algorithm and realizes clustering data above six dimension with arbitrary shape simply and directly.This model achieves automatically pre-process and takes local points with larger density and far away from other local points as the clustering center followed by introducing the fine-tuning.Experimental results suggest that our model not only work for low dimension data，but also achieving promising performance for high dimension data.

high dimension；density peak；clustering center；data mining

2016-03-04

蔡旭芬(1989-)，女(汉族)，湖北咸宁人，中国传媒大学媒介音视频教育部重点实验室博士研究生， E-mail：xufen.cai.whu@gmail.com.

TM153

A

1673-4793(2016)05-0029-05