基于K近邻的模糊密度峰值聚类算法研究

支 元，李 忠



基于K近邻的模糊密度峰值聚类算法研究

支 元，李 忠

（江苏联合职业技术学院常州刘国钧分院，江苏常州 213000）

基于密度的聚类算法（Density Peak Clustering，DPC）广泛使用在处理非球形数据集的聚类问题，算法使用较少的参数就能够实现数据集的处理。但该算法存在这样一些的不足：首先，全局变量的设定没有考虑数据的局部结构，特别是当不同类别的局部密度差别很大的情况下，容易忽略一些密度较小的类别，聚类效果不理想。其次，DPC提出了一种通过决策图来人工选取聚类中心点的方法，这也是DPC算法在人工智能数据分析的一个重大缺陷。为此，本文提出了基于K近邻的模糊密度峰值聚类算法，算法针对这两方面的不足进行了改进。最后本文使用人工数据集和UCI数据集进行了实验，实验结果表明本文所提出的算法，在不通过人工选取聚类中心的情况下，能够正确地找出类别个数，并且保持着较高的聚类精确度，验证了算法的有效性。

数据挖掘，聚类算法，密度峰值，K近邻

0 引言

聚类作为一种无监督的学习方法，被广泛应用到数据挖掘，模式识别，机器学习，图像处理等领域。其主要目的是将数据集中的样本划分为若干个通常是不相交的子集，每个子集代表一个类别，同一类别的数据点之间具有较高的相似性，不同类的的数据点之间相似性较低。目前，很多不同形式的聚类算法被提出，根据其使用方法的不同，聚类算法可以划分为如下几类：划分聚类算法[1-2]、层次聚类算法[3]、基于密度的聚类算法[4]、基于网格的聚类算法[5]以及基于模型的聚类算法[6]。每种聚类算法都其固有的优缺点和适用的数据集。

2014年Rodriguez A，Laio A在Science杂志上提出了一种新的聚类算法[7]，算法的核心思想在与对聚类中心的刻画上。作者认为每个类别的聚类中心应该具有两个特点：聚类中心本身的密度大，且被密度低的数据点包围；聚类中心与其他密度更大的数据点之间的距离相对更大。在这篇文章中我们称之为DPC（Density Peak Clustering）。在几个测试实验中，DPC可以较好的发现聚类中心，并且能够将其余点分配到其对应的类中。但是，DPC同样有一些不足。首先，对于截断距离选择的恰当与否直接影响到聚类的准确性，而的设置容易忽略数据的局部结构，对于类别密度差别比较大的聚类问题，容易忽略低密度的类别，效果不理想。其次，对于聚类中心点的选择上，DPC算法通过决策图来人为的选择聚类中心点，而人工选择聚类中心也是DPC算法在智能数据分析上的一个缺点。

为了克服这两方面的不足，我们提出了基于K近邻的模糊密度峰值聚类算法（KNN-FDPC）算法。首先，将高斯核函数与K近邻算法[8]相结合，对密度进行计算。其次，我们提出一种自适应的方法，先通过限定公式，筛选出满足条件的数据点，将其定义为局部聚类中心。在获得局部聚类中心后，我们将剩余点进行归类，然后再通过合并算法，对类别进行合并，最终得到聚类结果。整个算法过程省去人工选择聚类中心的过程，大大降低了算法的运行时间，并且在人工数据集和UCI数据集的实验结果表明，所提KNN-FDPC算法同样拥有较高的聚类精确度，从而验证了算法是有效可行的。

1 密度峰值聚类算法

不同于其它的密度聚类算法，Rodriguez A，Laio A提出的DPC算法[7]为聚类算法提供了一种新思路，这个算法将高于附近数据点的局部密度，且与更高局部密度的数据点距离相对较远的数据点定义为聚类中心。算法依据这两个特点，对数据集中的每一个数据点为其定义局部密度和所有局部密度大于的数据点中，与距离最小的数据点与之间距离。

（2）

（3）

DPC算法的具体流程如下：

方法：

1：计算距离矩阵；

4：生成决策图，人工选择聚类中心；

5：对非聚类中心的数据点进行归类；

6：输出每个样本的类别标签y；

2 K近邻算法

K近邻算法[8]是一种常用的监督学习方法，最早被用在分类算法中，KNN算法通过待分类样本点距离的多数投票结果进行分类。这种方法已经在分类、聚类和其它的领域展现出很强的技巧性，该算法的主要目的是：找出每个数据点距离最近的K个数据点。

假设我们从一个m维空间中获得一个由个数据点组成的数据集。我们使用欧式距离来计算点与点之间的距离，要想得到距离点最近的K个点，我们需要计算除数据点之外的所有数据点到的距离，选取距离最近的K个数据点，作为的K近邻数据点。

3 基于K近邻的模糊密度峰值聚类算法

3.1 局部密度计算

针对DPC算法中的一些不足之处，我们提出了相应的解决办法。首先，在DPC算法中，对于截断距离选择的恰当与否直接影响到聚类的准确性，并且的设置具有全局性，数据的局部结构容易被忽略，对于局部差别比较大的聚类问题，效果不理想。在我们的工作中，我们使用核函数的方法来定义局部密度，并将KNN的思想运用到局部密度计算中，这在一定程度上体现了数据集的局部结构。

3.2 局部聚类中心获取与类别合并

为了克服DPC算法通过决策图人工选择聚类中心的局限性，本文中我们提出了一种方法，使得在没有人为干涉的情况下能够正确地获得聚类结果。我们先通过限定公式，获得满足条件的数据点，并将数据点定义为局部聚类中心，然后将剩余数据点进行分配得到局部聚类结束，最后通过提出的合并算法，对满足合并条件的类进行合并，得到全局聚类结果。

根据DPC提出的聚类中心两个特点：拥有高于附近点的局部密度，且与更高局部密度的点距离相对较远。我们设置限定公式，对聚类中心进行初步的选取。通过公式（5）（6），分别计算所有数据点局部密度的平均值和距离的标准方差。如果一个数据点的距离满足且局部密度满足则认为数据点为局部聚类中心。

（6）

通过约束条件获得的局部聚类中心同时拥有相对较大的局部密度和距离。在得到局部聚类中心后，我们使用DPC算法提出的归类方法，对其余点进行归类：对于所有数据点按局部密度大小降序排列，从局部密度大的数据点开始归类，如果一个数据点不是局部聚类中心，则该数据点的类别与比其局部密度高的所有数据点中距离最近的数据点类别相同。我们将对剩余点归类后的聚类结果，称为局部聚类。为了将满足合并条件的类进行合并，从而得到最终的全局聚类，我们在不增加其它变量的情况下提出了一个合并算法。

当一个类别中存在一个数据点，这个数据点K近邻的点中存在不属于该类别的点，则认为这样的数据点为边界点。

搜索每一个类别的边界点的K个近邻点，计算边界点与不同类点的平均局部密度，取所有平均局部密度的最大值，作为该类别到另外一点所在类别的边界密度。我们用表示类别A到类别B的边界密度，如果两个类相互间的边界密度与相同，则将两个类合并为一个类。

合并的过程我们采用一种策略：对于满足合并条件的类别，由密度小的局部聚类中心所在类别向密度大的局部聚类中心所在类别合并，合并的过程中，不断更新类与类的边界密度，通过这种合并策略，最终的合并结果会得到准确地得到全局聚类结果。

KNN-FDPC算法的具体流程如下：

输入：数据集X，k近邻参数K

1：计算距离矩阵；

3：自动获得满足限定公式的聚类中心；

4：将其余点分配到相应类别中；

5：计算类与类边界密度，并将局部聚类中心点按局部密度从小到大排序；

6：选取局部密度最小的局部中心所在类别，按局部密度从小到大的顺序，依次与其它类别进行边界密度比较：若满足合并条件，将局部密度小的局部聚类中心所在的类合并到密度大的局部聚类中心所在的类中。将局部密度最小的局部聚类中心删除。跳到步骤5；否则，结束算法；输出：每个样本的类别标签y。

4 实验结果与分析

本文使用聚类精确率[9]：

来评估算法对人工数据集和UCI数据集的聚类效果。

4.1 人工数据集实验

4.1.1 人工数据集

使用二维人工数据集来测试我们实验的性能，二维人工数据集的可视化，可以直观的看出我们所提算法的性能。在人工数据集实验部分，我们使用了4个常用的人工数据集，分别是：Spiral[10]、Flame[11]、Aggregation[12]、S1[13]。这4个数据集是测试聚类算法性能的常用数据集。数据集的大小，属性的个数，类的个数，如表1所示。

表1 人工数据集描述

Tab.1 Description of synthetic data set

4.1.2 人工数据集聚类结果及评价

首先使用Flame数据集，来简单、明确地说明整个KNN-FDPC算法的聚类过程，其次使用KNN- FDPC，DPC[7]，AP[14]，DBSCAN[4]，K-means[1]算法对上述4个数据集进行实验对比，其中由于K- means算法的精确度的高低对初始中心点的选取有关，因此我们选取20次运行结果的平均值作为最终的聚类精确度，对于K-means，DPC，AP与DBSCAN算法，我们都使用作者提供的原始代码进行实验，在参数的选择方面，我们都使用最优参数，以获得最优的聚类精确度。5种算法的对不同数据集的聚类精确度对比如表5所示，S1数据集聚类结果如图3所示。

我们先利用Flame数据集来详细说明我们所提算法的整个聚类过程。Flame数据集如图1(a)所示，我们设置参数K=9，生成的决策图如图1(b)所示。从数据集中第一个数据点开始，寻找满足限制条件的数据点，并依次定义为：类别1，类别2，类别3……。所有数据点中，满足局部聚类中心限制条件的数据点个数为4，如图1(c)所示，不同的颜色对应不同的类别。将这4个点定义为局部聚类中心，4个局部聚类中心的局部密度从小到大排序依次为：类别2，类别3，类别1，类别4。在找到聚类中心后，我们将剩余数据点进行归类，局部聚类结果如图1(d)所示。

由合并算法，我们先计算出4个类相互间的边界密度，如表2所示。其中第a行，第b个数据代表从类别a到类别b的边界密度，用表示。我们先选取类别2依次与类别3，类别1，类别4进行边界密度的比较，如表2所示，类别2与类别3满足合并条件=，所以我们将类别为2的所有数据点合并到类别3中，如图1(e)所示，然后删除局部聚类中心2，并更新表2为表3。合并后剩余三个局部聚类中心，如图1(f)所示。3个局部聚类中心的局部密度从小到大排序依次为：类别3，类别1，类别4。同样的方法，我们先选取类别3依次与类别1，类别4进行边界密度的比较，如表3所示，类别3与类别1满足合并条件=，所以我们将类别为3的所有数据点合并到类别1中去，如图1(g)所示，然后删除局部聚类中心3，并更新表3为表4。合并后剩余三个聚类中心如图1(h)所示。2个局部聚类中心的局部密度从小到大排序依次为：类别1，类别4。比较类别1与类别4的边界密度，因为类别，所以终止合并过程。所以最终获得的全局聚类结果如图1(g)所示。

图1 Flame数据集聚类过程。(a) Flame数据集。(b) KNN-FDPC算法生成决策图。(c) KNN-FDPC算法获得的局部聚类中心。(d)局部聚类结果(e)类别2合并到类别3后的聚类结果(f)类别2合并到类别3后的决策图及局部聚类中心。(g)类别3合并到类别1后的聚类结果(h)类别3合并到类别1后的决策图及局部聚类中心。

表2 4个类别相互间的边界密度

Tab.2 Mutual boundary density of four categories

表3 2合并到类别3后的边界密度

Tab.3 Mutual boundary density of three categories

表4 3和并到类别1后的边界密度

Tab.4 Mutual boundary density of two categories

Aggregation数据集包含了7个不易察觉的类，图2(a)中彩色点表示满足约束条件的13个局部聚类中心。图2(b)表示剩余数据点归类后的，未合并的KNN-FDPC算法的局部聚类结果。图2(c)表示KNN-FDPC算法最终的全局聚类结果。图2(d)表示合并后剩余的局部聚类中心，也是最终的聚类中心。合并后局部聚类中心从13个减少到7个，恰好对应Aggregation数据集中的7个类。结果显示，KNN-FDPC数据集准确的将Aggregation数据集分为了7个类。

图2 Aggregation数据集聚类合并过程。(a) KNN-FDPC算法获得的局部聚类中心。(b)未合并的KNN-FDPC算法聚类结果。(c) KNN-FDPC算法聚类结果。(d)合并后剩余的局部聚类中心。

表5 人工数据集实验结果

Tab.5 Experimental results of synthetic data set

图3 S1数据集聚类结果

分析实验结果，与K-means算法不同，KNN- FDPC，DPC和DBSCAN算法对各种复杂形状的数据集有着较好的聚类效果，而K-means算法只能对球状分布的数据进行聚类所以聚类的精确度都相对较低。与DPC算法相比较，虽然KNN-FDPC是一种自适应获取局部聚类中心，并通过合并算法将局部聚类合并为全局聚类，省去了手动选取聚类中心的步骤，但是KNN-FDPC算法同样能够准确的确定聚类中心，确保聚类结果拥有相仿的精确度。

4.2 UCI数据集实验

4.2.1 UCI数据集

为了验证算法在真实世界数据集的有效性，我们在UCI公共数据集上取出3个数据集进行了实验。

从UCI中取出的数据集分别为Iris、Seeds和Wine，其中数据集Iris的属性总数为4，有3个类别，各类别的样本数为50:50:50；数据集Seeds属性总数为7，有3个类别，各类别的样本数为70:70: 70；数据集Wine属性总数为13个，有三个类别，各类别的样本数为59:70:47。

表6 UCI数据集描述

在实验之前，我们使用min-max规则化，对实验数据进行一次预处理，公式如下：

4.2.2 UCI数据集聚类结果及评价

如表7所示，KNN-FDPC算法可以自动获得了每个数据集的聚类中心，而不需要手动地通过决策图来选择聚类中心。这是KNN-FDPC算法的最明显的优势。在精确率方面，KNN-FDPC算法相比较DPC算法，有相似或更好的精确率，说明KNN-FDP算法，在省去人工选择聚类中心的步骤的同时，同样可以保持着较高的精确率。

表7 UCI数据集实验结果

Tab.7 Experimental results of UCI data set

5 总结与展望

本文设计了一种基于K近邻的模糊密度峰值聚类算法。算法将高斯核函数与K近邻算法相结合，对局部密度进行计算，可以有效的克服截取距离对密度影响的问题。其次，采用自适应的方法，对聚类中心进行初步选取，获得局部聚类中心，并将剩余非局部聚类中心数据点归类后，使用提出的合并算法对类别进行合并，获得准确的聚类结果。相较于DPC算法，所提算法在不添加任何参数的情况下，能够自动地发现聚类中心，并且很好的解决了由于截取距离设置的全局性，使得数据的局部结构被忽略的问题。KNN-FDPC算法在几个人工数据集和UCI数据集上进行了实验，实验过程中KNN- FDPC算法准确的寻找到了聚类中心，并取得了很好的聚类精确度。但是，本文的研究工作还有待进一步深入和发展，比如如何对高维数据进行更稳定的合并。

[1] 基于机器视觉的动态多点手势识别方法[J]. 李文生, 解梅, 邓春健. 计算机工程与设计. 2012(05).

[2] 贾俊芳, 王秀义, 郑建新. 基于模糊集的兴趣发现新方法[J]. 软件, 2016, 37(3): 04-08.

[3] LI Yugang. Research on The Generation of Current in A Test Basin for Deepwater Engineering[J]. The Journal of New Industrialization, 2014, 4(8): 9-14.

[4] 孟晨宇, 史渊, 王佳伟, 等. Windows内核级防护系统[J]. 软件, 2016, 37(3): 16-20

[5] 基于向量内积不等式的分布式k均值聚类算法[J]. 倪巍伟, 陆介平, 孙志挥. 计算机研究与发展. 2005(09).

[6] 基于MapReduce的分布式近邻传播聚类算法[J]. 鲁伟明, 杜晨阳, 魏宝刚, 沈春辉, 叶振超. 计算机研究与发展. 2012(08).

[7] ZHANG Chong, WANG Yankai. Orbit and Attitude Coupled Collaborative Control for Spacecraft Formation[J]. The Journal of New Industrialization, 2014, 4(8): 30-36.

[8] 基于K-means聚类的数字半色调算法[J]. 何自芬, 詹肇麟, 张印辉. 计算机应用研究. 2013(01).

[9] Ding S F, Jia H J, Shi Z Z. Spectral clustering algorithm based on adaptive Nyström sampling for big data analysis[J]. J Softw, 2014, 25(9): 2037-2049.

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

[11] 邻域形态空间与检测算法[J]. 张凤斌, 席亮, 王大伟, 岳新. 控制与决策. 2011(10).

[12] WU Jin, SHANG Xiao, ZHANG Jinhuan. Design of GSM module in Target positioning monitor[J]. The Journal of New Industrialization, 2014, 4(8): 37-43.

[13] 夏新凯, 陈冬火. 基于KeY 的程序分析和验证[J]. 软件, 2016, 37(3): 74-78

[14] Frey B J, Dueck D. Clustering by passing messages between data points[J]. science, 2007, 315(5814): 972-976.

Fuzzy Density Peaks Clustering Algorithm Based on K-nearest Neighbors

ZHI Yuan, LI Zhong

(Jiangsu Union Technical Institute Changzhou Liu Guojun Branch, Changzhou 213000, China)

A novel clustering algorithm based on density (DPC) has been proposed recently, this algorithm can deal with non-spherical cluster and does not require too many parameters. But the algorithm has some defects. First the local structure of data has not been taken into account when it calculates the local density. It does not perform well when clusters have different densities. Secondly, this algorithm utilizes decision graph to manually select cluster centers. Manual selection of cluster centers is a big limitation of DPC in intelligent data analysis. In this paper, we propose an improved method. It has been improved for the deficiencies in these two aspects. We use synthetic data set and UCI data set to make the experiments. Experimental results show that our algorithms can correctly identify the number of categories without manually selecting cluster center and maintain a high clustering accuracy, which verifies that the proposed algorithm are effective and feasible.

Data mining; Clustering; Density peaks; K nearest neighbor

TP301.6

A

10.3969/j.issn.1003-6970.2017.04.015

2016年度江苏省教育科学“十三五”重点资助规划课题（项目编号：B-a/2016/03/06）

支元(1982-)，男，讲师，主要研究方向：数据挖掘、智能控制。

支元，江苏省常州市戚墅堰富民路296号信息(物联网)工程系。

本文著录格式：支元，李忠. 基于K近邻的模糊密度峰值聚类算法研究[J]. 软件，2017，38（4）：85-90