杨照峰+时合生

摘 要： 针对模糊C?均值聚类算法容易陷入局部极值等缺陷，提出了基于改进QPSO的模糊C?均值聚类，算法利用QPSO的优点，并对量子门更新策略进行了改进。实验结果显示该算法提高了模糊聚类算法的聚类效果以及搜索能力，在全局寻优能力、跳出局部最优能力、收敛速度等方面具有优势。

关键词： 模糊C?均值聚类； 量子粒子群优化； 聚类分析； 量子门更新策略

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2014）07?0118?03

Fuzzy C?means clustering algorithm based on improved QPSO

YANG Zhao?feng1， SHI He?sheng2

（1. Software Engineering School， Pingdingshan University， Pingdingshan 467002， China；

2. Computer Science and Technical College， Pingdingshan University， Pingdingshan 467002， China）

Abstract： Since the fuzzy C?means clustering algorithm is easy to fall into local extremum， fuzzy C?means clustering algorithm based on the improved quantum particle swarm optimization （QPSO） is proposed. The local search ability and quantum gates update strategy were improved by making full use of the advantages of fast convergence of QPSO. The experimental results show that the algorithm improves the search ability and clustering effect of fuzzy clustering algorithm， and has superiority in the aspects of global optimization capability， jumping out of local optimum capacity and convergence rate.

Keywords： fuzzy C?means clustering； quantum particle swarm optimization； clustering analysis； quantum gates update strategy

0 引 言

模糊C?均值（Fuzzy C?Means，FCM）算法是目前众多的聚类算法中应用最广泛且较成功的[1?2]，1974年由Dunn提出该算法[3]。该算法虽然具有收敛速度快、局部搜索能力强等优点，但它对初始条件极为敏感。国内外很多相关研究人员对这个问题进行了深入的研究，如文献[4]提出基于GA的聚类方法，在一定程度上解决FCM的初值敏感性问题，但是由于遗传算法本身的缺陷，仍会出现未成熟收敛现象。

文献[5]利用免疫机制改进GA，并将C?均值算法与免疫GA有机结合，形成一种混合算法。文献[6]提出了基于PSO算法的改进模糊聚类算法（PSFC），该算法是一种实用的、速度更快、效率更高的改进聚类算法。本文提出了基于改进量子粒子群优化算法的模糊C?均值聚类，充分利用量子粒子群算法收敛速度快、局部搜索能力强的特点，并对量子门更新策略进行了改进。

1 模糊C?均值聚类概述

将数据集[X={x1，x2，…，xn}∈Rm]分为C类，[X]中任意样本[xk]对[i]类的隶属度为群[n]，分类结果用一个模糊隶属度矩阵[U={uik}∈Rm]表示，模糊C?均值聚类是通过最小化关于隶属度矩阵[U]和聚类中心[V]的目标函数[Jm（U，V）]来实现的。

如何为分类找到一个标准是一个非常关键的问题， 目前使用较多对于数据集[X]的划分实际上就是求有约束条件函数[W]的最小值（最小平方误差和）：

[W=min{W（U，P）}=mini=1c（xk∈Xi（dik）2）i-1cuik=1， 1≤k≤n]

式中[U]与[P]分别为数据集[X]的划分矩阵与聚类中心矩阵。

[（dik）2=（xk-pi）T（xk-pi）]

得到如下公式：

[uik=1j=1cdikdjk2] （1）

其中[dlk≠0，1≤l≤c。]

[uir=1，]且对[k≠r，][uik=0；][?i，r，]有[dir=0。]

[pi=k=1n（uik）2xkk=1n（ujk）2] （2）

2 量子粒子群优化算法简介

1995年美国研究人员J.Kennedy以及R.C.Eberhart受鸟群觅食行为的启发，提出了粒子群优化算法（Particle Swarm Optimization，PSO）[6]。粒子群优化算法自提出以来，已经取得了巨大的成功。目前，粒子群算法在如下领域得到了广泛的应用：故障诊断、模糊控制、生物医学、通信网络、分布式网络、电子与信息、组合优化、自动控制、规划设计、图像与视频、能源规划、神经网络、水文气象预测、机器人、军事安全、传感器网络、信号处理等。显然，由于粒子群优化简单容易扩展，能被不同的应用领域采用[7?8]。

2004年J.Sun等人提出了量子粒子群（Quantum?behaved Particle Swarm Optimization，QPSO）[7]，主要的改进是在标准的粒子群算法基础上引入量子行为，QPSO是以DELTA势阱为基础，认为粒子具有量子的行为，该算法的迭代公式如下[9?12]：

[mBest=1Mi=1MPi=1Mi=1MPi1，1Mi=1MPi2，…，1Mi=1MPiD] （3）

[Pd=（R1dPid+R2dPgd）（R1d+R2d）] （4）

[Xid（t+1）=Pd±β×mBestd（t）-Xid（t）×ln（1u）] （5）

式中：[mBest]为平均最优位置；[M]为粒子的数目；[D]为粒子的维数；[Pi（Pi1，Pi2，…，Pid）]为第[i]个粒子的个体最优位置；[Xi（Xi1，Xi2，…，Xid）]为第[i]个粒子的位置；[Pg]为全局最优位置；[u、][R1d、][R2d]是介于（0，1）之间的随机数， [β]称为收缩扩张系数。

3 基于量子粒子群优化算法的模糊C?均值

聚类算法

3.1 量子粒子编码

量子粒子群优化算法是采用量子染色体对问题进行描述的，量子染色体具体形式描述如下：

[qtj=αtj1βtj1αtj2βtj2……αtjmβtjm] （6）

式中：[m]表示量子比特的个数，[j=1，2，…，n。] 在这种编码方式中，一条染色体能够同时表达多个态的叠加，而传统的编码方式只能表示一个具体的状态，所以QPSO比其他传统进化算法更容易保持种群的多样性。

QPSO中的每个微粒的位置代表一个聚类中心的集合[Ui=（zi1，zi2，…，zik），]其中[zik（1≤k≤K）]为一个聚类中心，[K]为聚类数，如果数据集有[m]个属性，那么[zik]为[m]维。故粒子由[zik]顺序连接而成，其长度为[K×m。]

3.2 量子门更新

量子门的构造是算法的关键所在。目前在QPSO中主要采用的是量子旋转门：

[U（Δθi）=cos（Δθi）-sin（Δθi）sin（Δθi）cos（Δθi）] （7）

更新过程如下：

[α′iβ′i=U（Δθi）αiβi]

旋转量子门示意图如图1所示。

图1 旋转量子门示意图

一般方法是通过查询表得到角度的设置。为了防止算法陷入早熟收敛，本文提出一种[R&Nε]门旋转策略。[R&Nε]门由旋转门和[Nε]门构成。非门（Not?gate）是经典的量子门，它的作用是交换量子比特位的参数。[Nε]门即是经改进的带概率[ε]的非门，它的转换矩阵如下所示：

[Nε：0110]with probability [ε；]

[Nε：1001]with probability [1-ε；] where [0<ε?1。]

在[R&Nε]门的作用下，量子比特Q?bit更新公式如下：

[α，β=R&Nεα，β，Δθ] （8）

where for [α，β=RΔθα，β′] and [ε=rand（）]

（1） if [ε?ε] then [α，β′=β，α′]

（2） if [ε>ε] then [α，β′=α，β′。]

3.3 算法流程

改进QPSO算法流程如图2所示。

4 实验结果与分析

实验以UCI中的3个实际数据集作为聚类对象，分别用PSO算法与FCM结合以及本文算法对数据对象进行聚类分析。各算法的聚类中心数为其类别数。评价指标如下：

[E=nN×100%] （9）

式中：[N]表示总对象数；[n]表示错误分类的对象数。实验结果见表1。

图2 改进QPSO算法流程

表1 实验结果

[数据集＼&算法＼&平均值＼&最小值＼&最大值＼& E /%＼&Iris＼& PSO?FCM＼&7.115 8＼&6.835 6＼& 10.890 8＼&17.7＼&本文方法＼&6.821 1＼&6.003 2＼&6.935 8＼&15.4＼&＼&Soybean?small＼&PSO?FCM＼&266.971 1＼&250.956 7＼&277.114 3＼&25.8＼&本文方法＼&220.352 8＼&212.124 5＼&244.902 1＼&17.9＼&＼&Labor?neg＼&PSO?FCM＼&141.444 7＼&132.009 1＼&144.998 0＼&22.6＼&本文方法＼&135.224 5＼&132.346 7＼&136.999 0＼&16.3＼&]

对于UCI中的3个实际数据集，本文算法聚类指标[E]均比PSO?FCM要小，聚类正确率尤其是对于Soybean?small样本得到了较大的提高， 本文算法的代价函数最大值远小于PSO?FCM，且平均值比PSO?FCM要小，这充分体现了本文改进算法的全局寻优能力强于PSO?FCM。

5 结 论

提出了基于改进OPSO的模糊C?均值聚类，充分利用量子粒子群算法收敛速度快、局部搜索能力强的优点的特点，并对量子门更新策略进行了改进。实验结果显示该算法提高了模糊聚类算法的聚类效果以及搜索能力，在全局寻优能力、跳出局部最优能力、收敛速度等方面具有优势。

参考文献

[1] ZHU L， CHUNG F L， WANG S T. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（3）： 578?591.

[2] BAMI M， CAPPELLINI V， MECOCCI A. Comments on “a possibilistic approach to clustering” [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（3）： 393?396.

[3] 高新波，谢维信.模糊C均值聚类算法中参数m的优选[J].模式识别与人工智能，2000，13（1）：7?11.

[4] 欧阳，成卫，韩逢庆.基于遗传算法的模糊C?均值聚类算法[J].重庆大学学报：自然科学版，2004，27（8）：89?92.

[5] 孙洋，罗可.基于免疫遗传算法的模糊C?均值聚类[J].计算机工程与应用，2009，45（3）：152?153.

[6] 薛丽萍，尹俊勋，纪震.基于粒子群优化?模糊聚类的说话人识别[J].深圳大学学报：理工版，2008，25（2）：178?183.

[7] 关庆，邓赵红，王士同.改进的模糊C?均值聚类算法[J].计算机工程与应用，2011，47（10）：27?28.

[8] 刘兵，夏士雄，周勇，等.基于样本加权的可能性模糊聚类算法[J].电子学报，2012，40（2）：371?375.

[9] 武小红，周建江.可能性模糊C?均值聚类新算法[J].电子学报，2008，36（10）：1996?2000.

[10] 李盼池，张巧翠，杨雨.一种基于相位编码的自适应量子粒子群算法[J].计算机工程与应用，2011，47（23）：57?60.

[11] 向毅，钟育彬.自适应阶段变异量子粒子群优化算法研究[J].计算机应用研究，2012，29（6）：2035?2039.

[12] 李栋.量子衍生多目标进化算法及其应用研究[D].长沙：湖南大学，2008.

[13] 皋军，王士同.具有特征排序功能的鲁棒性模糊聚类方法[J].自动化学报，2009，35（2）：145?153.

参考文献

[1] ZHU L， CHUNG F L， WANG S T. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（3）： 578?591.

[2] BAMI M， CAPPELLINI V， MECOCCI A. Comments on “a possibilistic approach to clustering” [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（3）： 393?396.

[3] 高新波，谢维信.模糊C均值聚类算法中参数m的优选[J].模式识别与人工智能，2000，13（1）：7?11.

[4] 欧阳，成卫，韩逢庆.基于遗传算法的模糊C?均值聚类算法[J].重庆大学学报：自然科学版，2004，27（8）：89?92.

[5] 孙洋，罗可.基于免疫遗传算法的模糊C?均值聚类[J].计算机工程与应用，2009，45（3）：152?153.

[6] 薛丽萍，尹俊勋，纪震.基于粒子群优化?模糊聚类的说话人识别[J].深圳大学学报：理工版，2008，25（2）：178?183.

[7] 关庆，邓赵红，王士同.改进的模糊C?均值聚类算法[J].计算机工程与应用，2011，47（10）：27?28.

[8] 刘兵，夏士雄，周勇，等.基于样本加权的可能性模糊聚类算法[J].电子学报，2012，40（2）：371?375.

[9] 武小红，周建江.可能性模糊C?均值聚类新算法[J].电子学报，2008，36（10）：1996?2000.

[10] 李盼池，张巧翠，杨雨.一种基于相位编码的自适应量子粒子群算法[J].计算机工程与应用，2011，47（23）：57?60.

[11] 向毅，钟育彬.自适应阶段变异量子粒子群优化算法研究[J].计算机应用研究，2012，29（6）：2035?2039.

[12] 李栋.量子衍生多目标进化算法及其应用研究[D].长沙：湖南大学，2008.

[13] 皋军，王士同.具有特征排序功能的鲁棒性模糊聚类方法[J].自动化学报，2009，35（2）：145?153.

参考文献

[1] ZHU L， CHUNG F L， WANG S T. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（3）： 578?591.

[2] BAMI M， CAPPELLINI V， MECOCCI A. Comments on “a possibilistic approach to clustering” [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（3）： 393?396.

[3] 高新波，谢维信.模糊C均值聚类算法中参数m的优选[J].模式识别与人工智能，2000，13（1）：7?11.

[4] 欧阳，成卫，韩逢庆.基于遗传算法的模糊C?均值聚类算法[J].重庆大学学报：自然科学版，2004，27（8）：89?92.

[5] 孙洋，罗可.基于免疫遗传算法的模糊C?均值聚类[J].计算机工程与应用，2009，45（3）：152?153.

[6] 薛丽萍，尹俊勋，纪震.基于粒子群优化?模糊聚类的说话人识别[J].深圳大学学报：理工版，2008，25（2）：178?183.

[7] 关庆，邓赵红，王士同.改进的模糊C?均值聚类算法[J].计算机工程与应用，2011，47（10）：27?28.

[8] 刘兵，夏士雄，周勇，等.基于样本加权的可能性模糊聚类算法[J].电子学报，2012，40（2）：371?375.

[9] 武小红，周建江.可能性模糊C?均值聚类新算法[J].电子学报，2008，36（10）：1996?2000.

[10] 李盼池，张巧翠，杨雨.一种基于相位编码的自适应量子粒子群算法[J].计算机工程与应用，2011，47（23）：57?60.

[11] 向毅，钟育彬.自适应阶段变异量子粒子群优化算法研究[J].计算机应用研究，2012，29（6）：2035?2039.

[12] 李栋.量子衍生多目标进化算法及其应用研究[D].长沙：湖南大学，2008.

[13] 皋军，王士同.具有特征排序功能的鲁棒性模糊聚类方法[J].自动化学报，2009，35（2）：145?153.