2024年3月15日发(作者：)

202157981

⦾

理论与研发

⦾

融合KNN优化的密度峰值和FCM聚类算法

兰红，黄敏

江西理工大学信息工程学院，江西赣州341000

摘要：针对模糊C均值（FuzzyC-Means，FCM）聚类算法对初始聚类中心和噪声敏感、对边界样本聚类不够准确且

易收敛于局部极小值等问题，提出了一种K邻近（KNN）优化的密度峰值（DPC）算法和FCM相结合的融合聚类算法

（KDPC-FCM）。算法利用样本的K近邻信息定义样本局部密度，快速准确搜索样本的密度峰值点样本作为初始类

簇中心，改善FCM聚类算法存在的不足，从而达到优化FCM聚类算法效果的目的。在多个UCI数据集、单个人造数

据集、多种基准数据集和Geolife项目中的6个较大规模数据集上的实验结果表明，改进后的新算法与传统FCM算

法、DSFCM算法对比，有着更好的抗噪性、聚类效果和更快的全局收敛速度，证明了新算法的可行性和有效性。

关键词：模糊C均值；聚类；密度峰值；K近邻；算法优化

文献标志码：A中图分类号：TP312doi：10.3778/.1002-8331.2005-0011

FusionofKNNOptimizedDensityPeaksandFCMClusteringAlgorithm

LANHong,HUANGMin

SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou,Jiangxi341000,China

Abstract：AimingattheproblemsthatFuzzyC-Means（FCM）clusteringalgorithmissensitivetotheinitialclustering

centerandnoise,isnotaccuratetoboundarysampleclusteringandiseasytoconvergetothelocalminimum,afusion

clusteringalgorithm（KDPC-FCM）combiningKNearestNeighbor（KNN）optimizedDensityPeaksClustering（DPC）

orithmusestheKNNinformationofthesampletodefinethelocaldensityofthe

sample,quicklyandaccuratelysearchesthesampleofthedensitypeakpointofthesampleastheinitialclustercenter,and

improvestheshortcomingsoftheFCMclusteringalgorithm,soastooptimizetheeffectoftheFCMclusteringalgorithm.

TheexperimentalresultsonmultipleUCIdatasets,asingleman-madedataset,multiplebenchmarkdatasets,and6

large-scaledatasetsintheGeolifeprojectshowthatcomparedwiththetraditionalFCMalgorithm,andDSFCMalgorithm,

theimprovednewalgorithmhasbetternoiseimmunity,clusteringeffectandfasterglobalconvergencespeed,which

provesthefeasibilityandeffectivenessofthenewalgorithm.

Keywords：FuzzyC-Means（FCM）;clustering;densitypeaks;KNearestNeighbor（KNN）;algorithmoptimization

聚类（clustering）就是将一个数据集分成多个簇

（cluster）或类，使得在同一类簇中的数据样本点之间具

有相对高的相似度，而不同类簇中的数据样本点差别较

大。根据聚类的结果可以从数据中发现规律和知识，探

索出藏在数据之后的规律和模式。聚类算法被普遍地

运用在数据科学分析和实际工程领域中

[1-4]

，经过许多国

内外研究人员的努力，产生了许多优秀的聚类算法，根

据研究方向和算法实现原理的不同，目前聚类算法可

划分为基于密度的方法、基于网格的方法、基于层次的

方法、基于模型的方法和基于划分式方法等五种主流

方法

[5]

。

模糊C均值（FuzzyC-Means，FCM）算法

[6]

是基于

划分式的聚类算法，此算法的基本思想是引入隶属度概

念来量化样本点从属于每个类簇的数值大小，由此进行

划分判断，使得划分到同一类簇的样本间相似度最大、

不同类簇的样本间相似度最小，已达到对数据集划分为

各类簇的目的，在模式识别、数据挖掘、数据分析、矢量

量化以及图像分割等领域应用比较广泛

[7-8]

。FCM算法

是C-Means算法的衍生改进算法，C-Means算法对数据

集划分属于硬性、具体的划分，但FCM算法对数据集的

基金项目：国家自然科学基金（61762046）；江西省教育厅科技重点项目（GJJ160599）；江西省自然科学基金（20161BAB212048）。

作者简介：兰红（1969—），女，博士，教授，硕士生导师，CCF会员，研究领域为图像处理、模式识别，E-mail：；

黄敏（1996—），男，硕士研究生，研究领域为图像处理、深度学习。

收稿日期：2020-05-05修回日期：2020-08-24文章编号：1002-8331（2021）09-0081-08

822021579

划分属于软（柔）性、模糊的划分。FCM算法没有考虑

到样本点的邻域关系和局部信息，容易导致算法对噪声

敏感。此外，FCM算法在初始聚类中心的选取原则上

是随机选取，若初始聚类中心选择不理想甚至选择了噪

声点作为聚类中心，将导致算法收敛于局部极值点或得

到错误的聚类结果。面对以上问题，许多科研专家使用

不同的方法来改进FCM算法。文献[9-10]采用改良模

糊加权指数的计算方法，聚类效果良好；文献[11-12]通

过改变数据加权的策略来优化迭代过程从而提高聚类

的效果；文献[13-14]从初始中心点的选择出发，使用各

种方法优化初始中心点的选择来避免选中噪声点，提高

聚类的准确性；文献[15-16]是根据数据集的空间分布

信息，改变目标函数从而得到新的隶属度计算方法；文

献[17-18]则是通过把密度峰值算法与FCM算法相结合

的方法来优化FCM算法，达到了较好的效果。

文献[9-16]这些改进方法都是根据模糊C均值算法

某个方面的不足朝特定的方向优化改良FCM算法，聚

类效果在一定程度上得到了提升和改善，但是未综合考

虑到数据样本中的样本数据和噪声数据点的空间分布

信息对聚类效果的影响。文献[17-18]主要是利用样本

的局部密度信息，使用密度峰值算法来优化初始中心的

选择，从而使得改进后的算法在抗噪性和全局收敛能力

上超过其他算法，但是在使用密度峰值算法时保留了需

要主观选择的截断距离

d

C

，影响了聚类效果，尤其在数

据集样本规模较小时影响较大。因此，本文提出了一种

融合KNN优化的密度峰值和FCM聚类的改进算法，使

用KNN来代替截断距离

d

C

，既解决了需要主观选择截

断距离的问题又使得在样本密度度量方面有了统一的

密度度量准则，进一步提升了FCM算法的性能。

1KNN优化的DPC算法

1.1算法基本思想

快速搜索和查找样本密度峰值的聚类算法

[19]

（clus-

teringbyfastsearchandfindofdensitypeaks，DPC

算法）可以快速地找到任意形态、规模数据集样本的密

度峰值即类簇中心点，在大规模聚类处理分析方面表现

出色，其基本思想是，在理想情况下，类簇中心周围的样

本点的局部密度要小于类簇中心的局部密度，且不同类

簇中心间应有较远的距离。根据这两个特点，设计了两

个变量，一个是样本

i

的局部密度

ρ

i

；另一个是样本

i

到距离它最近且局部密度比它大的样本

i

的距离

δ

i

，它

们的定义如公式

(

（1）和（2）所示：

ρ

i

=

∑

χd

ij

-d

c

（1）

i≠j

)

δ

i

=min

j:ρ

j

>ρ

i

(d

ij

)

（2）

式（1）中

d

n

2

ij

=

∑

|

x

i

-x

j

|

表示的是数据样本点

i

到样

i=1

本点

j

之间的欧式距离；

d

c

被称为截断距离，

χ(x)=

{

1,x≤0

0,x>0

，局部密度

ρ

i

的含义是其他数据样本点到第

i

个数据样本点之间的欧氏距离小于截断距离的个数。式

（2）中

δ

i

表示数据样本点

i

与局部密度更高的数据样本

点之间的距离，当

i

是局部密度最大点时，

δ

i

=max

j

(d

ij

)

。

根据式（1）可知，截断距离

d

c

可以影响局部密度

ρ

i

的

值，文献[19]中指出当样本数据集规模较小时，

d

c

对DPC

算法聚类结果影响较大，反之则较小。为了减少

d

c

对聚类

效果的影响，当样本数据集规模较小时DPC算法采用高

斯核

[20]

来计算样本局部密度

ρ

i

，其公式如式（3）所示：

∑

exp

æ

ç

æ

d

2

ρ

ij

ö

ö

i

=

（3）

i≠j

ç

-

ç

è

è

d

c

÷

÷

ø

÷

ø

由公式（1）~（3）可知，当数据样本点

i

的局部密度

ρ

i

最大时，它的

δ

i

距离将远大于其他样本点的

δ

i

距离，

δ

i

距离异常大的点往往是该数据样本集的类簇中心，其

样本点的局部密度也相对较大，因此，DPC算法是用构

造样本点的局部密度

ρ

i

和样本距离

δ

i

值二维决策图的

方法来选择数据集样本的类簇中心（

ρ

i

和

δ

i

值都较大

时对应的点）。但是当每个类簇数据集规模都较小时，

样本的稀疏性会导致类簇中心点模糊，要找到其密度峰

值点是十分困难的

[19]

，这时将采用综合变量

γ

i

构成的曲

线决策图来寻找密度峰值点

[19]

，其公式如式（4）所示：

γ

i

=ρ

i

×δ

i

（4）

γ

i

值越大则为密度峰值点的可能性越大，对

γ

i

排

序再从中选择最大的若干个点作为密度峰值点，其余的

样本点分配到与其最近的密度峰值点形成类簇。为了

避免样本噪声点的影响，DPC算法给每个类簇定义了边

界区域：由属于该类簇但与其他类簇数据样本点的距离

小于截断距离

d

c

的数据样本点构成

[21]

。设置一个阈值

ρ

b

：每个类簇边界区域数据样本点总数值

[17]

。每个类簇

中的数据样本点的局部密度大于

ρ

b

值则视为核，反之

则视为噪声样本点，由此得到最终的聚类结果。

1.2算法局限性分析

（1）根据数据集样本规模的大小不同，采用了两种

不同度量样本局部密度的方法，但是没有一个客观科学

的标准来判定数据集规模的大小，导致聚类结果受样本

局部密度度量方法的影响。

（2）当数据集相对复杂时，不同类簇的密度会有较

大的差异，使用欧氏距离进行密度度量，取不同的截断

距离将会导致完全不同的聚类结果，容易出错，并且截

断距离是人为设定，没有一个明确的标准和规范。

（3）DPC聚类算法在样本聚类时具有连错效应，即

若有一个样本分类错误，其他样本接着分类错误，将导

致千差万别的聚类结果。

2KDPC和FCM的融合算法

2.1DPC算法的改进KDPC

本文引入了样本的

K

近邻信息来对DPC算法进行

改进优化（KDPC），为了统一DPC聚类算法中两种计算

样本局部密度的方法准则，提出了一种新的不受

d

c

影

响的样本局部密度计算方法，该方法适用于不同规模的

数据集。

使用样本点的

K

邻近信息来计算样本的局部密度

ρ

i

值，其定义如式（5）所示：

ρ

i

=d

j∈

∑

exp

KNN(i)

(

-

ij

)

（5）

当样本点的

K

邻近距离越大时，其

ρ

i

值就越小，否

则反之。与式（1）和式（3）相比较，参与式（5）的计算范

围要小很多，原本需要样本点与数据集其他所有样本点

之间的距离参与密度计算，现在只要样本点与之相邻的

K

个样本点之间的距离参与密度计算即可，更加能够反

映出样本点的局部密度信息。

为了减少噪声样本的干扰，在计算数据样本点的局

部密度之前，要将噪声样本剔除，为了识别出噪声样本，

本文对其有如下定义：若样本点的KNN距离大于数据

集中所有样本点的平均KNN距离，则该样本点被认定

为噪声样本点。样本点的KNN距离

K

d

(i)

计算如式（6）

所示，数据集中所有样本点的平均KNN距离

M

计算如

式（7）所示，噪声样本点的识别函数

N

如式（8）所示。

K

d

(i)=max

j∈K

(

i

)

{d

ij

}

（6）

M=

1

∑

N

N

K

d

(i)

（7）

i=1

N={x|K

d

(

x

)

>M}

（8）

上式中

K

(

i

)

为数据样本点

i

的

K

邻近点集合，

N

表示

数据集中总样本数。

KDPC算法首先运用式（6）~（8）识别标记噪声样

本，减少噪声对整体算法的影响，其次用引入

K

邻近信

息的式（5）来代替式（1）和（3）计算出数据集中每个样本

点的局部密度值，接着用式（2）计算出每个样本点的

δ

i

值，最后使用式（4）来选取数据集中的若干密度峰值即

聚类中心点。KDPC算法避免了DPC算法需要主观判

断数据集规模、人工设定截断距离

d

c

等问题，从而更加

精准地找到数据集的密度峰值点。

2.2FCM聚类算法

FCM聚类算法将数据集样本点之间的相似程度定

义为隶属度，假设数据集为

X={x

1

,x

2

,…,x

n

}

，被划分

为

i

类，聚类中心点为

c

i

，则数据集中任意样本点

j

与

某个类中心点

c

i

的隶属度为

u

ij

，其目标函数（9）和约束

条件（10）如下所示：

J=

∑

c

∑

n

u

m

j=1

ij



x

j

-c

i=1

i



2

（9）

2021579

83

∑

c

u

ij

=1,j=1,2,…,n

（10）

i=1

式中，

m

为隶属度

u

ij

的指数权重因子，

n

为数据集样本

总数。采用拉格朗日乘数法及其他数学运算方法，当目

标函数最小时，解出

u

ij

的值为式（11）所示，

c

i

的值为式

（12）所示。

u

ij

=

1

∑

c

æ

ç



2

（11）

x

j

-c

i

m-1

k=1

ç

è





ö

x

j

-c

k



÷

÷

ø

c

n

u

m

i

=

∑

ij

x

j=1

∑

n

u

m

j

（12）

j=1

ij

FCM算法的步骤为：先随机初始化一个满足约束

条件（10）的

u

ij

值，然后根据式（12）计算出

c

i

的值，其次

将得到的

c

i

作为输入，根据式（11）计算出新的

u

ij

值，此

时根据式（9）计算出目标函数

J

值。再次根据式（12）、

（11）和（9）迭代计算出

c

i

、

u

ij

和

J

的值，如此循环迭代

计算，当

J

达到最小值时停止计算，输出

c

i

和

u

ij

的值，

完成聚类。

2.3算法思想

算法总体可分为两部分，（1）KDPC部分：运用

KDPC算法思想计算出数据集中所有样本点的

γ

i

值，根

据

γ

i

值大小进行排序（从大到小排序），假设数据集可

分为

c

类，则选取

γ

i

值排序后的前

c

个样本点作为该数

据集的聚类中心点；（2）FCM部分：运用第（1）部分获得

的聚类中心，计算出对应的隶属度

u

ij

，开始循环迭代计

算，满足终止条件完成聚类，获得更加精准的聚类结果。

2.4算法步骤

KDPC-FCM算法步骤如下：

KDPC部分：运用改进的密度峰值算法初始化数据

集的聚类中心，具体步骤如算法1所示。

算法1KDPC部分算法步骤

输入：样本数据集

X

，类别数

c

。

输出：初始化聚类中心集

c

i

(0)

。

处理过程：

步骤1数据预处理：对数据进行归一化处理。

步骤2根据式（6）~（8）对数据集中的噪声样本进行识别

并标记，去除噪声样本点。

步骤

3计算数据集中非噪声样本间的欧式距离，根据

式（5）计算出非噪声样本点的局部密度

ρ

i

值。

步骤4根据步骤3中获得的

ρ

i

值，运用式（2）计算出非

噪声样本点的

δ

i

值。

步骤5根据式（4）计算出非噪声样本点的

γ

i

值，由该值

大小将非噪声样本点进行从大到小排序。

步骤6在排序后的非噪声样本点中选取前

c

个样本点，

得到该数据集的初始化聚类中心集

c

i

(0)

。

842021579

(0)

FCM部分：根据KDPC部分得到的聚类中心集

c

i

，

使用FCM算法进行循环迭代计算，获取聚类结果。具

体步骤如算法2所示。

算法2FCM部分算法步骤

输入：样本数据集

X

，初始化聚类中心集

c

i

，指数权重

因子

m

（一般选取

m=2

效果最佳）。

输出：聚类中心集

c

i

，隶属度矩阵

u

ij

。

处理过程：

步骤1初始化迭代次数

t

，令

t=0

。

步骤2根据初始化聚类中心集

c

i

，由式（11）计算出隶

属度矩阵

u

ij

。

步骤3根据

c

i

、

u

ij

，由式(9)计算出目标函数

J

值。

步骤4根据隶属度矩阵

u

ij

，由式(12)计算出新的聚类

中心集

c

i

(t+1)

(t)

(t)(t)(t)

(t)

(t)

(0)

集

c

i

值和隶属度矩阵

u

ij

，由此划分数据集，得到聚类结果。

2.5算法具体流程

KDPC-FCM算法的总体流程如图1所示，首先对数

据进行归一化预处理，减少后续运算量，运用自定义的

噪声识别函数

N

将数据集中的噪声样本标记剔除，然

后利用式（5）计算出每个非噪声样本点的局部密度

ρ

i

，

接着使用式（2）和（4）分别计算出非噪声样本点的

δ

i

值

和

γ

i

值，根据

γ

i

值的大小排序得到数据集的初始化聚

类中心点集合

c

i

，到此KDPC部分结束；开始FCM部

分：初始化指数权重因子令

m=2

，根据KDPC部分得到

的

c

i

开始循环迭代计算聚类中心集

c

i

的值和隶属度

矩阵

u

ij

的值，当目标函数稳定不变时终止迭代，根据最

终得到的

c

i

和

u

ij

划分数据集输出最后的聚类结果。

(0)

(0)

。

(t+1)

步骤5根据聚类中心集

c

i

度矩阵

u

ij

J

(t+1)

(t+1)

，由式(11)计算出新的隶属

3实验分析

。

(t+1)

步骤6根据

c

i

值。

、

u

ij

(t+1)

，由式（9）计算出新的目标函数

步骤7判断

J

-J

(t)(t+1)

>0

是否成立，若是，则

t=t+1

并

转到步骤4继续执行；否则，终止运算。

步骤8完成上述7步，多次迭代后得到最终的聚类中心

开始

为了验证本文KDPC-FCM算法的有效性，在加利

福尼亚大学尔湾分校（UniversityofCalifornia，Irvine，

简称UCIrvine或UCI）的机器学习数据库上的多个真

实数据集和人造数据集上进行实验，对比算法有FCM

聚类算法，以及文献[18]提出的DSFCM聚类算法。采

用Python进行仿真实验，各数据集的情况如表1所示。

结束

数据预处理

计算

K

d

(i)=max

j∈(i)

{d

ij

}

KDPC部分

计算

M=

1

∑

K

d

(i)

N

i=1

计算

N={x|K

d

(x)>M}

计算

J

n

得最终的

c

i

和

u

ij

否

FCM部分

J

-J

(t)(t+1)

>0

是

(t+1)

m

=

∑∑

u

ij

i=1i=1

cn

(t+1)

||x

j

-c

i

(i+1)

2

||

令

t=t+1

样本是否

为噪声点

是

计算

u

(t+1)

i

||x

j

-c

t

||

m

2

=1

∑

()

-1

||x-c||

jk

k=1

c

(t+1)

否

计算

ρ

i

=

j∈KNN(i)

∑

exp(-d

ij

)

计算

c

标

记

剔

除

噪

声

点

(t+1)

i

=

∑

j=1

n

u

ij

n

j=1

m(t)

m

ij

∑

u

x

j

计算

δ

i

=min

j:ρ

j

>ρ

i

(d

ij

)

计算

J

=

∑∑

u

ij

||x

j

-c

i

||

2

(t)

m(t)

(t)

i=1j=1

cn

计算

γ

i

=ρ

i

×δ

i

并排序

||x

j

-c

t

||

m

2

计算

u

ij

(t)=1

∑

()

-1

||x-c||

jk

k=1

c

(t)

得到初始化聚类中心

c

i

(0)

初始化迭代次数

t

，令

t=0

图1KDPC-FCM算法总体流程图

表1

数据集

Iris

C5

Wine

类别数

3

5

3

2021579

85

各数据集的情况

属性数

4

2

13

样本数

150

300

178

样本分布

50、50、50

5、20、200

59、71、48

基础，验证了KDPC算法的有效性。

3.2抗噪性对比分析

C5数据集是本文人造数据集，由样本分布在5个半

径都为0.2的圆上以及周围的随机噪声样本组成，其中5

个圆是圆心点分别为（1，2），（2，2），（0，2），（1，3），（1，

1）。样本的分布特征为每个圆上均匀分布20个样本

点，分布在5个圆周围的200个随机噪声样本点满足在5

个圆之外，中心点位于（1，2）、宽为5高为4的矩形之内，

并且服从均匀分布。具体分布情况如图2（a）所示。使

用C5数据集对FCM算法、DSFCM算法和本文提出的

KDPC-FCM算法进行抗噪性对比试验。三种算法分别

在该数据集上运行100次，观察记录其聚类结果。实验

结果如下：FCM算法在100次聚类过程中，有23次实验

聚类结果不理想，其中一次的聚类结果如图2（b）所示；

DSFCM算法和本文KDPC-FCM算法在100次实验中都

取得了不错的聚类结果，图2（c）和图2（d）分别为两种

聚类算法的某一次聚类结果。

图2（a）中的每个黑色点代表着C5数据集中的每

个数据样本。图2（b）~（d）中的不同彩色点代表不同的

类簇，即相同的颜色为一类，黑色样本点为识别出的噪

声样本点，其中分类错误样本点被红色矩形框标注。图

2（b）中有29个样本点被标注红色矩形框，图2（c）和图

2（d）分别有11个和5个样本点被标注。

实验结果分析：FCM算法不仅将数据集外围的许

多噪声样本进行了分类，其内部类簇数据样本点也存在

着分类错误的情况，这是由于FCM算法初始化隶属度

矩阵

u

ij

是随机的，这导致了得到的初始化聚类中心也

是随机的，一旦初始化聚类中心点选择不当，将导致聚

类结果出现大量的错误分类；DSFCM算法将一小部分

其中，Iris和Wine数据集都是UCI上的真实数据

集，C5数据集是人造数据集。Iris数据集是鸢尾花样本

分类数据集，包含4个属性分别是：萼片长度、萼片宽

度、花瓣长度和花瓣宽度；分为3类：Setosa、Versicolour

和Virginica，每个类别都有50个样本，共150个样本；C5

数据集是个二维数据集，包含形状类似5个圆的样本

点，即5个类簇，每个类簇又由20个样本点组成，并且在

这5个类簇周围有200个随机噪声点样本。Wine数据

集是葡萄酒分类数据集，由组成葡萄糖的13种物质含

量作为其属性，分为3类：Class1、Class2和Class3，分别

包含59、71和48个样本。

3.1初始化聚类中心对比分析

为了验证DPC的改进算法KDPC算法的有效性，运

用KDPC算法对Iris数据集进行初始化聚类中心的选

取，并与Iris数据集的实际中心作对比，如表2所示。

表2初始化聚类中心对比

Iris真实聚类中心

（5.003.421.460.24）

（5.932.774.261.32）

（6.582.975.552.02）

KDPC算法初始化Iris聚类中心结果

（5.01063.42081.46050.2480）

（5.92072.67034.35851.3211）

（6.59152.96895.66372.0452）

从表2可以看出，KDPC算法初始化Iris数据集聚类

中心结果与Iris数据集的真实聚类中心非常近似，误差

在百分数级别，这证明了KDPC算法能够优化初始聚类

中心的求取结果，为后续FCM算法聚类打下了较好的

（a）C5数据集（b）FCM聚类结果

（c）DSFCM聚类结果

图2

（d）KDPC-FCM聚类结果

C5数据集上各算法聚类结果图

862021579

表3Wine数据集上各聚类算法三种聚类评价指标值对比

RI

FCM

85.27

59.37

67.58

70.74

DSFCM

87.92

65.98

61.68

71.86

KDPC-FCM

93.61

73.64

63.91

77.05

FCM

81.42

68.37

52.89

67.56

93.24

75.89

61.48

76.87

Jaccard

DSFCM

83.74

70.15

56.38

70.09

KDPC-FCM

89.97

73.27

61.76

75.00

KDPC-FCM

%

葡萄酒

类别

Class1

Class2

Class3

均值

FCM

82.54

70.76

53.45

68.92

F-measure

DSFCM

88.65

68.77

58.96

72.13

靠近C5最大的圆型类簇噪声样本进行了错误分类，总

体聚类效果良好，这是由于DSFCM算法采用了结合密

度峰值和样本空间信息的方式来优化初始化聚类中心

的选择，因此取得了较好的实验结果；KDPC-FCM算法

仅将逼近圆样本的5个噪声样本误识别属于样本类簇，

聚类效果较好，这是由于KDPC-FCM算法在初始化聚

类中心时，先对噪声进行了定义和识别，降低了噪声样

本对聚类结果的影响。

从上述实验结果及分析可以得出结论：FCM算法

对噪声敏感，DSFCM算法和KDPC-FCM算法都具有良

好的抗噪性，并且KDPC-FCM算法要略优于DSFCM

算法。

3.3聚类效果及鲁棒性对比分析

为了验证三种算法的聚类效果及鲁棒性，本文采用

UCI数据库中的Wine数据集进行仿真对比实验，该数

据集同Iris数据集一样，是聚类算法实验中常用的数据

集。采用F-measure指标、兰德指数（RandIndex，RI）和

Jaccard系数来评价三种算法在Wine数据集上的聚类效

果，三项检测指标数越大证明聚类效果越好。

F-measure指标计算公式为：

F-measure=

(

β

2

+1

)

PR

β

2

P+R

（13）

P=

|

T∩F

|

|

F

|

（14）

R=

|

T∩F

|

|

T

|

（15）

式中，

β

为参数变量，本文使用

β=1

进行计算，

P

是精

准率，

R

是召回率，F-measure的取值范围为[0，1]。

T

表示数据集的真实分布，

F

表示算法聚类结果分布，

P

和

R

的取值范围均为[0，1]。

兰德指数及Jaccard系统计算公式为：

RI=

TP+

TP

TN

+

+

TN

FP+FN

（16）

Jaccard=

|

T∩F

|

|

T∪F

|

（17）

式中，

TP

表示同一类的样本被分到同一类簇的对数；

TN

表示不同类的样本被分到不同类簇的对数；

FP

表

示不同类的样本被分到同一类簇的对数；

FN

表示同一

类的样本被分到不同类簇的对数。RI和Jaccard的取值

范围也都为[0，1]。

使用FCM算法、DSFCM算法以及本文KDPC-FCM

算法分别对Wine数据集进行聚类，使用上述三项聚类

结果检测指标分别对三种算法的聚类结果进行检测

运算，其检测的结果如表3所示。从表中可以看出：在

F-measure指标下，FCM算法在Class2类别处的值要略

高于DSFCM算法，其他类别均是KDPC-FCM>DSFCM>

FCM；在RI指数下，FCM算法在Class3类别处的值要高

于DSFCM和KDPC-FCM算法，其他类别均是KDPC-

FCM>DSFCM>FCM；在Jaccard系数下，三类别均是

KDPC-FCM>DSFCM>FCM。综合来看，在Wine数据集

下总体各指标值均是KDPC-FCM>DSFCM>FCM，表明

本文KDPC-FCM在Wine数据集下聚类效果方面要优

于DSFCM和FCM算法。

为了检验三种算法的鲁棒性能，本文采用的方法

是：将三种算法在Wine数据集上各进行50次运算实验，

然后计算出每个算法在上述三种聚类评价指标的标准

差，标准差越小，证明算法的波动性越小，稳定性和鲁棒

性越强。经过实验的结果并运算得出各算法的标准差，

三种对比算法在三种不同聚类评价指标上的标准差结

果如表4所示。

表4各算法在各评价指标的标准差对比

算法

F-measureRIJaccard

FCM0.12570.10240.0985

DSFCM0.10470.08910.0497

KDPC-FCM0.08760.07130.0415

从表4的结果可以看出KDPC-FCM算法的标准差

在三种评价指标上均要小于其他两种算法，为了进一步

验证KDPC-FCM算法的聚类效果和鲁棒性，分别使用

三种对比算法在表5所示的6个基准数据集上进行聚类

实验。

表5各基准数据集

数据集类别数噪声样本数

Flame2

有

240

Blobs3

无

1500

Compound6

有

399

Aggregation7

无

788

R1515

无

600

D3131

有

3100

经过实验，在以上六种基准数据集上的聚类效果如

图3所示。

FCMDSFCMKDPC-FCM

2021579

87

（a）Flame

（b）Blobs

（c）Compound

（d）Aggregation

（e）R15

（f）D31

图3各算法在六种基准数据集上聚类效果对比图

图3中的不同彩色点代表不同的类簇，即相同彩色

点为同一类簇，其中灰色点为识别出的噪声样本点。根

据图3可以看出，在Aggregation、R15及D31三种基准

数据集上DSFCM算法和KDPC-FCM算法的聚类效果

差不多，而FCM算法聚类效果较以上两种算法效果较

差；在Flame、Blobs及Compound三种基准数据集上，

DSFCM算法要比FCM算法效果稍好一点，而KDPC-FCM

算法的聚类效果最好。

综合在Wine数据集和六种基准数据集上的实验对

比分析，可以得出初步结论：在三种对比算法中，FCM

算法的聚类效果和鲁棒性较差，DSFCM算法次之，本文

KDPC-FCM算法聚类效果和鲁棒性较强。

规模的数据集上分别进行实验，用于实验的数据集如表

6所示。

表6

数据集

User000

User002

User018

User000-002

User000-030

User000-050

性能对比实验数据集

类别数

未知

未知

未知

未知

未知

未知

维度

3

3

3

3

3

3

样本数

176182

248217

47279

528382

7649862

11113351

User等6个的数据集来自微软亚洲研究院的Geolife

项目

[22]

。该项目数据集包含182个用户在超过五年（2007

年4月至2012年8月）时间里的户外活动。该数据集的

GPS轨迹由一系列带有时间戳的点表示，每个点包含纬

3.4性能对比分析

为了对本文提出的算法进行性能对比分析，在不同

882021579

度、经度和高度信息。User000表示为使用了编号为000的

用户所有活动数据，User000-002表示使用编号从000至

002的三个用户的所有活动数据，其他数据集依次类推。

采用Geolife项目数据集测试数据规模对性能的影

响实验，即表6中的6个User数据集，分别使用FCM、

DSFCM以及本文KDPC-FCM算法在这6个数据集上进

行聚类，并记录在每个数据集上运行的时间，得到如表7

所示的实验结果。

表7规模性能实验结果

s

数据集

FCMDSFCMKDPC-FCM

User01822.821.410.135

User000282.928.830.987

User002425.6816.721.098

User.5740.695.194

User000-030

—

200.7640.575

User000-050

—

460.6758.146

由于本文主要是针对FCM算法进行对比分析，因

此表7中KDPC-FCM的实验结果并未加上KDPC运行

的时间。

从表7可以看出，随着数据集的样本数的规模增

加，三种算法的时间也随之增加，且KDPC-FCM算法的

聚类速度明显要快于其他两种算法，且随着数据集的样

本数量达到百万级别时，FCM算法的聚类时间将非常

漫长，本文由于时间限制，用“

—

”表示其时间暂时无法计

算，而DSFCM和KDPC-FCM算法在数据达到千万级别

时，速度仍比较快，且KDPC-FCM算法保持在1min内。

4总结

本文针对FCM算法对噪声点敏感、容易局部收敛

等问题，提出了融合KNN优化的密度峰值和FCM聚类

算法KDPC-FCM，该算法先将噪声样本识别去除后，在

使用引入的样本的

K

近邻信息来计算样本的局部密度，

对DPC算法进行了改进，使得初始化中心点更加接近真

实数据中心点，从而使得FCM算法可以更加精准快速地

得到较好的聚类结果。为了验证算法的有效性，本文在

UCI中的多个数据集、一个人工数据集、多个基准数据集

以及微软亚洲研究院的Geolife项目数据集上进行实验，

并与传统FCM算法和DSFCM算法进行了对比分析，得

出结论：KDPC-FCM算法能够有效提高聚类的抗噪性、

准确性和全局收敛能力，达到了较好的聚类效果。

参考文献：

[1]卢俊杰，黄金泉，鲁峰.似然K均值聚类用于涡扇发动机

气路故障诊断[J].计算机工程与应用，2020，56（9）：136-141.

[2]王杰，陈志刚，刘加玲，等.基于聚类的云隐私行为挖掘技

术[J].计算机工程与应用，2020，56（5）：80-84.

[3]王燕，亓祥惠，段亚西.基于马尔科夫随机场的改进

FCM图像分割算法[J].计算机工程与应用，2020，56（4）：

197-201.

[4]杨琳，翟瑞芳，阳旭，等.结合超体素和区域增长的植物器

官点云分割[J].计算机工程与应用，2019，55（16）：197-203.

[5]伍育红.聚类算法综述[J].计算机科学，2015，42（S1）：

491-499.

[6]nrecognitionwithfuzzyobjective

functionalgorithms[J].AdvancedApplicationsinPattern

Recognition，1981，22：203-239.

[7]齐淼，张化祥.改进的模糊C-均值聚类算法研究[J].计算机

工程与应用，2009，45（20）：133-135.

[8]尹宝勇，刘慧，刘建生.基于改进FCM和径向基函数插值

的图像修复[J].江西理工大学学报，2014，35（3）：73-78.

[9]肖满生，肖哲，文志强，等.模糊C均值聚类区间型模糊化

参数模型[J].系统工程与电子技术，2015，37（4）：868-873.

[10]周开乐，杨善林，王晓佳，等.基于自适应模糊度参数选择

改进FCM算法的负荷分类[J].系统工程理论与实践，

2014（5）：1283-1289.

[11]RICHARDJH，y-weightedfuzzyC-

meansclustering[J].IEEETransactionsonFuzzySystems，

2009，17（1）：243-252.

[12]周世波，徐维祥，柴田.基于数据加权策略的模糊C均

值聚类算法[J].系统工程与电子技术，2012，36（11）：

2314-2319.

[13]WUZ，WUZ，ovedFCMalgorithm

withadaptiveweightsbasedonSA-PSO[J].Neural

ComputingandApplications，2017，28（12）：3113-3118.

[14]KHALILIAMA，BEZDEKJ，POPESCUM，etal.

ImprovementstotherelationalfuzzyC-meansclustering

algorithm[J].PatternRecognition，2014，47（12）：3920-3930.

[15]肖满生，肖哲，文志诚，等.一种空间相关性与隶属度平滑

的FCM改进算法[J].电子与信息学报，2017（5）：1123-1129.

[16]LIUY，CHENHP，SHENXJ，orrection

FCMalgorithmwithconditionalspatialinformationfor

imagesegmentation[J].KSIITransactionsonInternet

andInformationSystems，2018，12（9）：4336-4354.

[17]任新维，张桂珠.融合密度峰值和模糊C-均值聚类算

法[J].传感器与微系统，2018，37（3）：145-147.

[18]周世波，徐维祥，徐良坤.融合密度峰值和空间邻域信

息的FCM聚类算法[J].仪器仪表学报，2019，40（4）：

137-144.

[19]RODRI´GUEZA，ringbyfastsearchand

findofdensitypeaks[J].Science，2014，344：1492-1496.

[20]ift，modeseeking，andclustering[J].

IEEETransactionsonPatternAnalysisandMachine

Intelligence，1995，17：790-799.

[21]谢娟英，高红超，谢维信.K近邻优化的密度峰值快速

搜索聚类算法[J].中国科学（信息科学），2016，46（2）：

258-280.

[22]ZHENGY，ZHANGL，XIEX，interesting

locationsandtravelsequencesfromGPStrajectories[C]//

InternationalConferenceonWorldWideWeb，2009：

791-800.