基于余弦相似性的自适应权重的改进FCM算法

胡建华　尹慧琳

摘 要： 模糊C-均值聚类算法（FCM）是一种经典的聚类算法，主要通过迭代更新隶属度和聚类中心来提高聚类的有效性。 FCM算法的性能主要通过类内紧性和类间分离性来评价，但其既依赖于初始聚类中心，也对噪声非常敏感。考虑到每个数据点和每个聚类中心对目标函数的不同重要性，本文提出了一种具有自适应权重的改进FCM聚类算法（Hybrid FCM）。主要贡献：将2个具有自适应指数p和q的自适应权向量ψ和φ引入FCM的目标函数，以体现不同数据点和聚类中心的重要性;为提高聚类性能，自适应指数p、q和模糊因子m采用粒子群优化算法（PSO）优化，新提出的聚类评价指标AWCVI作为PSO算法的适应度函数;迭代过程中利用余弦相似性对隶属度函数进行修正，提高算法的鲁棒性。实验表明，本文提出的算法能够有效地提高聚类效果。

关键词： 模糊C均值算法; 自适应权重; 余弦相似度; 粒子群算法

文章编号： 2095-2163（2021）07-0073-07中图分类号：TP181文献标志码： A

Improved FCM algorithm with adaptive weights based on cosine similarity

HU Jianhua， YIN Huilin

（College of Science， University of Shanghai for Science and Technology， Shanghai 200093， China）

【Abstract】As a classical clustering algorithm， fuzzy C-means clustering algorithm （FCM） improves the effectiveness of clustering by updating membership and clustering centers. The performance of FCM algorithm is mainly evaluated by intra cluster compactness and inter cluster separation. But FCM algorithm relies on the clustering centers and is very sensitive to noise. Considering the different importance of each data point and each cluster center， two adaptive weight vectors ψand φwith adaptive exponents p and q are introduced into the objective function of FCM， and an improved FCM clustering algorithm with adaptive weights is proposed; At the same time， the new clustering evaluation index  AWCVI is used to optimize the parameters p， q and the fuzzy factor m， which is determined by the particle swarm optimization algorithm （PSO）; The cosine similarity is used to modify the membership function in the iterative process to improve the robustness of the algorithm. Experimental results show that the proposed algorithm can effectively improve the clustering effect.

【Key words】Fuzzy C-means algorithm（FCM）; adaptive weight; cosine similarity; Particle Swarm Optimization

0 引 言

模糊C均值聚類算法是一种经典的聚类方法，由Dunn[1]在1973年提出，由于其简单、易实现而广泛应用于数据挖掘、模式识别、信号处理、图像分割等领域中[2-4]。然而，FCM算法依赖初始聚类中心、对噪声非常敏感、且容易陷入局部最优。因此，许多改进的FCM算法也相继提出以克服这些问题。一般FCM算法需要将样本对每个类满足归一化条件，这样会导致算法对非平衡数据集中噪声点和离群值异常敏感，文献[5]提出一种改进的模糊隶属度函数的FCM 聚类算法，能在聚类过程中不断对隶属度进行修正，从而消除噪声点，提高聚类的有效性;Zhou 等人 [6]结合了图像的空间信息和FCM 算法，提出了一种自适应空间信息模糊聚类算法用来提高图像分割的效果;文献[7]建立了一种基于特征的2型模糊聚类算法，将2型模糊集引入到聚类算法中，可以更灵活地处理由噪声环境引起的与隶属度概念相关的不确定性;将FCM算法与其他算法结合起来，能够解决FCM算法依赖初始值的问题，例如将FCM算法与粒子群算法结合在一起[8-9]，利用粒子群算法强大的全局寻优能力，能够使FCM算法取得相对更优的初始点，提升聚类效果;文献[10]将FCM算法与蚁群算法结合起来，克服FCM算法依赖初始值的缺点。考虑到噪声和样本分布不均衡，文献[11]中提出了一种具有自适应样本权重的FCM算法（AFCM-SP），通过对每个样本点赋予权重来区分不同的样本点对聚类结果的影响，并且用改进的粒子群算法（PSO-SP）对新引入的自适应参数进行优化，从而一定程度上降低了噪声点的影响。

但是由于样本的最终聚类结果也受到了聚类中心的影响，本文通过对样本与中心同时赋予权重的方法来提高算法聚类效果，基于自适应权重，还提出了新的聚类评价指标对聚类结果进行评价，同时，聚类过程中的隶属度函数可能会因为随机的初始值而降低聚类效果，所以对迭代过程中的隶属度进行余弦修正增强算法的鲁棒性，实验表明这一想法的确能够有效提高算法的性能。考虑到每个数据点和每个聚类中心对目标函数的不同重要性，本文提出了一种具有自适应权重的改进FCM聚类算法（Hybrid FCM）。在新算法中，2个具有自适应指数p和q的自适应权向量ψ和φ引入FCM的目标函数，以区分不同数据点和聚类中心在迭代过程中的不同重要性;为提高聚类性能，自适应指数p、q和模糊因子m采用粒子群优化算法（PSO）优化;相应地，新提出一种带权重的聚类评价指标AWCVI用来刻画类内紧致度和类间分离性，并作为PSO算法的适应度函数;为了提高算法的鲁棒性，迭代过程中利用余弦相似性对隶属度函数进行修正。通过在5个数据集上与另外3种算法对比的实验表明，本文提出的算法能够有效地提高聚类效果。

1 相关工作

1.1 经典FCM算法

模糊C-均值聚类算法（FCM）是一种经典的聚类算法，主要通过迭代更新隶属度和聚类中心来提高聚类的有效性。从模型上看，FCM算法是用于求解最小化问题，以C均值函数作为目标函数：

其中，xi表示第i个样本;令U=（μji）c×n表示模糊隶属度矩阵，μji表示第i个样本属于第j类的隶属度，满足约束条件：

研究中，V={v1，v2，…，vc}是所有聚类中心的集合，ci为第i个聚类中心;m为模糊因子，一般取值为2。FCM的隶属度函数和聚类中心的更新迭代公式为：

1.2 余弦相似性

余弦相似性，也叫余弦距离，是用向量空间中2个向量夹角的余弦值作为衡量2个个体之间的差异的大小度量。设M和N为2个样本向量，其计算公式为：

其中，分子为M，N的向量内积，分母为向量M，N的模的乘积。余弦值取值范围为[-1，1]，越接近1，就说明2个向量越相似。余弦值注重从方向上区分样本的差异，而对绝对的数值不敏感，可修正数据度量标准不统一等问题

。在数据挖掘领域，余弦相似性常用来衡量聚类的类内凝聚程度。

1.3 粒子群优化算法

粒子群优化（PSO）算法因为其具有搜索速度快、效率高、算法简单等优点，成为近年来广泛使用的优化算法之一[12-15]，其传统模型为：

其中，Vi（t）表示在搜索空间内第i个粒子在t时刻的速度;Xi（t）表示在t时刻的位移;ω是惯性权重;c1，c2是加速系数，分别称为认知加速系数和社会加速系数，本文设置ω=0.729，c1=c2=1.49。在寻优过程中，Pi和Pg分别代表第i个粒子的个体最佳位置与全局最佳位置。

2混合自适应加权FCM算法

2.1 混合自适应加权FCM模型

FCM是一种快速有效的聚类算法，但在噪声和样本分布不均衡的情况下，算法聚类结果不理想。文献[11]考虑到每个样本的重要性，提出了具有样本自适应权重的FCM算法（AFCM-SP） ，一定程度上减少了噪声干扰，提高算法性能。但在聚类过程中，聚类中心也起着非常重要的作用。观察式（1），可以发现经典FCM算法的目标函数可以写成：

将Di=∑cj=1μmji‖xi-vj‖2看成数据点xi对目标函数Jc的贡献，则式（8）表明每个数据点对于目标函数具有相同的重要性，显然这是不合实际情况的。本文同时考虑到不同样本和聚类中心对目标函数的不同影响程度，提出混合自适应加权FCM算法（Hybrid FCM），其目标函数如下：

其约束条件为：

其中， μij∈[0，1]; ψ=（ψ1，ψ2，…，ψn）为样本权重向量;  φ=（φ1，φ2，…，φc）为中心权重向量; ψi>0，φj>0。为了最小化Gh，引入了拉格朗日函数：

对任意的i，j，对L计算与μji，ψi，φj，vj相关的偏导数，并使其分别等于0，结合约束条件（10）∏nl=1，l≠iψl=1ψi，∏cl=1，l≠jφl=1φj，得到使目标函数（9）达到最小的充要条件：

将式（11）、式（14）与式（3）、式（4）对比，Hybrid FCM的隶属度和中心都因为自适应随权向量ψ、φ的引进做了相应的调整， 这有利于克服FCM算法对初始聚类中心的依赖和减低噪声的干扰。为了降低算法陷入局部最优的可能性，隶属度函数进一步用余弦相似度作为矫正因子来修正，计算公式为[16]：

同时，Hybrid FCM中，自适应参数p，q和m一样是个超参数，用来控制函数的凸性和模糊度，恰当的取值对聚类结果起着至关重要的作用。

2.2 基于自适应权重的聚类有效性指标

聚类有效性指标（AWCVI）是用来衡量聚类效果的评价函数，XB指标[13]是最广泛使用的聚类有效性指标之一，具体公式为：

CVIXB值越小，则表示具有良好的类内紧凑性和类间的分离性，说明聚类结果越好。此外，类间的最小距离反映了类间分离的尺度，而类内的平均距离体现了集群内的紧凑性尺度。本文结合新引入的自适应权重，提出新的聚類有效性指标AWCVI如下：

作为比值函数，AWCVI的值越小，表示聚类效果越好。

2.3 混合自适应加权FCM算法的流程

Hybrid FCM算法分为2部分。首先，为了更好的聚类效果，新引入的自适应参数p，q和模糊因子m通过经典的PSO算法优化，基于自适应权重的聚类有效性指标AWCVI作为PSO算法的适应度函数。其次，以式（9）为最小化的目标函数，通过有限次的迭代，得到最终的聚类结果。算法流程如下：

（1）在三维搜索空间内初始化粒子种群Xi=（pi，qi，mi）， i=1，2，…，N，初始化隶属度矩阵U，样本权重向量ψ，中心权重向量φ，通过式（10）计算初始聚类中心V，设置收敛阈值eps。

（2）初始化粒子的速度和位移。

（3）根据式（11）～式 （15）迭代更新U，ψ，φ，V。

（4）根据式（19）计算每个粒子的适应度AWCVI（Xi（t）），得到t时刻的Pi， Pg。

（5）根据式（6）、式（7）更新粒子的速度和位移。

（6）当达到最大迭代次数时或者当∣AWCVI（Pg（k））-AWCVI（Pg（k-1））∣

同时，研究又给出基于余弦相似性的自适应权重的改进FCM算法流程如下：

（7）初始化U，ψ， φ， 通过式（14）计算聚类中心V。

（8）根据式（11）～（14）迭代更新U， ψ，φ，V。

（9）通过式（15）对更新后的U进行余弦修正。

（10）利用式（9）计算目标函数Gh。

（11）当算法收敛时或达到最大迭代次数时，进行（5）;否则，回到（2）。

（12）得到最终聚类结果。

在此基础上，研发得到的算法伪代码如下。

算法1 基于自适应权重的聚类有效性指标AWCVI的PSO算法

输入：Xi=（mi， pi， qi）

输出：最优的m， p， q

初始化粒子群X=X（m， p， q）， 隶属度函数U， 权重向量ψ，φ， 并且计算初始聚类中心V

初始化Pi， Pg，设置最大迭代次数Itermax， 收敛域eps

function FISTNESS FUNCTION=AWCVI（X）

for k=1：itermax do

for i=1：N＼＼＼＼ N为种群数量

if AWCVI（Xi（k））

Pi（k）=Xi（k）

end if

[JP4]Vi（t+1）=ωVi（t）+c1r1（Pi（t）-Xi（t））+c2r2（Pg（t）-Xi（t））

Xi（t+1）=Xi（t）+Vi（t+1）

i=i+1

end for ＼＼＼＼ 更新粒子的速度与位置

Pg=arg min AWCVI（Pi（k））

if ∣AWCVI（Pg（k））-AWCVI（Pg（k-1））∣

return Pg=（m， p， q） ＼＼＼＼ 全局最优粒子

else

k：=k+1

end if

end for

Return Pg =（m， p， q）

end function

算法2 混合自适应加权FCM算法

输入： Pg=（m， p， q）＼＼＼＼ 由算法1可以得到全局最优的m， p ，q值

输出： 聚类结果

初始化 隶属度函数U， 权重向量ψ，φ， 并且计算初始聚类中心V， 聚类数目c， 设置最大运算次数Itermax， 收敛阈值eps

function OBJECT FUNCTION=Gh （U，ψ，φ， V）

for k=1：Itermax do

for  i=1：n＼＼＼＼ n为数据的数量

for  j=1：c

计算μji，ψi，φj，vj

＼＼＼＼更新隶属度， 权重向量和聚类中心

uk+1ji=12ukji+12xi·vj‖xi‖‖vj‖

＼＼＼＼ 对隶属度进行余弦修正

end for

end for

if |Gh （k）-Gh （k-1）|

return Gh （k） ＼＼＼＼ 算法收敛时的目标函数值

else

k：=k+1

end if

end for

Return 隶属度函数U，权重向量ψ， φ， 聚类中心V， 与目标函数值Gh

end function

3 仿真实验与结果分析

为了验证提出算法的聚类性能，本文对5个数据集进行仿真实验，人工数据集Twomoons用来验证算法的鲁棒性，数据集信息包括数据的数量、特征、类别，见表1;同时采用FCM算法[1]，AFCM-SP[11]算法与SFCM算法[16]作为对比算法。实验之初，随机分配[0，1]之间的值给uji，ψi和φj设置为1;在聚类过程的最大迭代次数为200，收敛阈值eps为10-5;在优化参数p，q，m的PSO中，搜索空间为3维，种群粒子数为20，最大迭代次数设置为20。在5个数据集中由PSO算法得到的最优p，q，m值列在表中，详见表2。

对于前四个数据集，本文从Xie Beni指标（CVIXB）、聚类准确率（Accuracy）、标准互信息（NMI）三个方面对4种算法进行对比实验。CVIXB值越小、Accuracy和NMI值越大说明聚类效果越好。实验结果见表3～表6。从表3～表6中可以看出，本文提出的改进算法Hybrid FCM在IRIS上的各个指标都优于其它3种算法，在SONAR中，Hybrid FCM和AFCM-SP算法有相同的准确率，但是CVIXB和NMI值都优于AFCM-SP;在SPIRAL中，经典的FCM有着较好的CVIXB值，但是准确率和NMI值还是Hybrid FCM更为优异;在SYM上，Hybrid FCM准确率略低于SFCM算法，但CVIXB和NMI值都排在第一位。對于人工数据集Twomoons，本文添加3个评价指标，即：召回率（Recall）、 精确率（Precision）和F1值，结果见表7。Hybrid FCM在Accuracy、NMI、Recall、F1值在4个方面都有优势;Twomoons数据集经过4种算法聚类后的数据分布如图1所示，可以发现在类边界部分，改进的算法有着更好的效果。图2给出4种算法在不同数据集上的收敛曲线以证明算法良好的收敛性。综上所述，本文提出的Hybrid FCM算法在5个数据集上都体现出较为优异的性能，能有效提高聚类效果。

4 结束语

针对传统FCM算法依赖于初始聚类中心、对噪声敏感、容易陷入局部最优等缺点，本文提出一种基于余弦相似性的自适应权重的改进FCM算法。首先，新算法考虑了样本与聚类中心联合起来对目标函数的影响程度，引入了样本与聚类中心权重和相应的自适应因子，使得原问题解空间的维数更大，最优解的精度提高;其次，提出了一种基于权重的聚类有效性指标作为PSO算法的适应度函数去优化模糊因子m与自适应因子p， q;最后，对隶属度函数进行余弦相似性修正，大大增强了算法的鲁棒性。实验结果表明本文改进的算法能有效提高算法的聚类性能。

参考文献

[1]DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J]. Journal of Cybernetics， 1973，3（3）： 32-57.

[2]夏邢， 薛涛， 李婷. 基于Spark的模糊C均值算法改进[J]. 西安工程大学学报， 2019， 33（1）：100-105.

[3]徐晓东，吕干云，鲁涛， 等. 基于智能电表数据与模糊C均值算法的台区识别[J]. 南京工程学院学报（自然科学版），2020，18（4）：1-7.

[4]高立扬， 牛衍亮， 张小平. 基于模糊C均值聚类推理模型的高铁土建工程造价智能估算[J]. 石家庄铁道大学学报（社会科学版）， 2020， 14（2）：36-43.

[5]XIAO Mansheng， WEN Zhicheng， ZHANG Juwu， et al. An FCM clustering algorithm with improved membership function[J]. Control and Decision， 2015，30（12）：2270-2274.

[6]ZHOU Wengang， SUN Ting， ZHU Hai. Image segmentation algorithm based on FCM optimized by adaptive spatial information[J]. Application Research of Computers， 2015，32（7）：2205-2208.

[7]YANG Xiyang， YU Fusheng， PEDRYCZ W. Typical characteristics-based type-2 fuzzy C-Means algorithm[EB/OL]. [2020]. https：//10.1109 /TFUZZ.2020.2969907.

[8]HESAM I， AJITH A. Fuzzy C-means and fuzzy swarm for fuzzy clustering problem[J]. Expert Systems with Applications，2011，38（3）：1835-1838.

[9]文傳军， 詹永照. 粒子群高斯诱导核模糊C均值聚类算法[J]. 科学技术与工程， 2018， 18（8）：78-84.

[10]鲁明， 王彬， 刘东儒，等. 基于蚁群优化模糊C均值聚类算法的疲劳驾驶研究[J]. 湖北汽车工业学院学报， 2019， 33（2）：23-28.

[11]WU Ziheng， WU Zhongcheng， ZHANG Jun. An improved FCM algorithm with adaptive weights based on SA-PSO[J]. Neural Computing and Applications， 2017，28： 3113-3118.

[12]XIE X L， BENI G. A validity measure for fuzzy clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1991， 13（8）：841-847.

[13]刘军梅. 新型混沌粒子群混合优化算法[J].软件导刊，2017，16（2）：59-62.

[14]徐超， 单志勇， 徐好好. 具有动态学习能力的分层进化粒子群优化算法[J]. 软件导刊， 2021， 20（1）：128-131.

[15]LIU Weibo， WANG Zidong， LIU Xiaohui， et al. A novel particle swarm optimization approach for patient clustering from emergency departments[J]. IEEE Transactions on Evolutionary Computation，2019，23（4）： 632-644.

[16]LI Minxuan. An improved FCM clustering algorithm based on cosine similarity[C]// ACM International Conference Proceeding Series. Hong Kong，China：ACM，2019： 103-109.

[17]LANCICHINETTI A ， FORTUNATO S ， KERTéSZ J. Detecting the overlapping and hierarchical community structure of complex networks[J]. New Journal of Physics， 2009， 11（3）：033015.

基金项目： 国家自然科学基金（61873169）。

作者简介： 胡建华（1978-），女，博士，讲师，主要研究方向：人工智能、李代数; 尹慧琳（1996-），女，硕士研究生，主要研究方向：人工智能、李代数。

通讯作者： 胡建华Email： hjh_2021@usst.edu.cn

收稿日期： 2021-04-23