采用云量子PSO的属性约简方法

常红伟，夏克文 ，2，白建川 ，2，牛文佳 ，武盼盼

1.河北工业大学 电子信息工程学院，天津 300401

2.河北省大数据计算重点实验室，天津 300401

粗糙集（RS）理论是一种有效分析和处理不准确、不完整信息的数学工具。其中，属性约简是粗糙集理论的核心内容之一，是在保持原有判断能力不改变的条件下，剔除其中不相关或不重要的属性，然后探索最优的属性组合，从而降低知识的复杂度，减小系统规模，进而发现隐含的知识，挖掘出潜在的规律[1-2]。属性约简的计算问题是一个NP-hard问题[3]。针对该问题，不少学者提出了很多高效的启发式搜索算法，其中，有很多关于粒子群优化算法（PSO）与属性约简相结合的方法。在文献[4]中，提出了一种基于GA-PSO的粗糙集约简方法，对不满足适应度条件的粒子进行交叉变异，加强局部收敛能力同时保持了全局搜索能力；在文献[5]中，提出一种粗糙集和遗传粒子群算法相结合的方法进行属性约简，在数据量大、属性维度高的问题上，具有高效的处理能力；在文献[6]中，提出一种基于PSO算法的属性约简方法，应用于有监督的特征选择中，同时利用标准医疗数据集进行实验，验证了所提方法增强现有的特征技术的效率；在文献[7]中，提出一种量子粒子群算法和蝙蝠算法相混合的方法，避免早熟的同时改变量子粒子群中的因子，并将其应用于求解模具车间调度问题。

而在粒子群优化算法中，种群根据自身所处的位置选择不同搜索方式存在模糊性、不确定性，不能准确地找到全局搜索和局部搜索的平衡点，进而容易造成局部最优和早熟等问题[8]。为此，Sun等人提出了量子粒子群优化算法（QPSO），使粒子能够出现在可行区域的任意位置，扩大了搜索区间，与标准PSO相比，寻优性能有所增强[9]。尽管如此，依然存在陷入局部最优的可能。而云模型[10]是由中国工程院院士李德毅等人提出的一种描述定性与定量之间的不确定关系模型，其特征可以通过期望值、熵值和超熵值来表示，构造不同的算法来生成云滴及确定度，进而为不确定的、模糊的定性定量关系提供搜索方法依据。

为此，本文拟引入云模型到量子粒子群算法中，提出了一种结合云模型改进的量子粒子群算法，同时利用属性依赖度构造属性约简数学模型，然后使用改进的算法求解该数学模型，并对UCI数据库中的4个典型数据集进行仿真对比与分析。

1 改进量子粒子群算法

1.1 量子PSO概述

量子粒子群优化算法（QPSO）是在2004年Sun等人研究了Clcrc教授的关于PSO粒子收敛行为的研究成果后提出的一种新颖智能算法模型。该模型基于δ势阱建立的，因此粒子具有量子的行为。由于处于量子束缚态的粒子能够以特定的几率出现在量子空间中任意位置，同时满足聚集态的性质，进而能够搜索整个区间，因此QPSO算法的全局搜索能力强于PSO优化算法。由于量子空间中的粒子无法同时确定速度和位置，因此粒子的状态只能通过波函数来表示，同时利用求解Schrodinger方程获得空间中粒子在某点显现的概率密度函数。为了得到粒子的位置，将量子状态塌缩到经典状态，进一步利用逆变换方法获得粒子的位置公式：

在文献[11]中L被定义为：

粒子的位置计算公式表示如下：

其中，μ,rand表示[0，1]之间的随机数；β表示收缩扩张因子；M表示种群的个数；D表示粒子的维度；Pi表示第i个粒子的Pbest；X(t)表示前一时刻粒子的位置。

而收缩扩张因子β对传统的量子PSO算法收敛性有很大的影响。如果选取不当，就会陷入局部最优和早熟。下面将对算法提出改进。

1.2 算法改进

本文将云模型与量子粒子群算法结合，形成云量子粒子群算法（CQPSO），为了平衡收缩扩张因子对QPSO算法收敛性的影响，改进的算法利用黄金分割理论，把粒子分成3个子群，根据不同粒子群的搜索状态调整收缩扩张因子β的值，调整策略如下：

（1）设粒子群的个数为n，在第k次迭代中xi的适应度为 fi(k)，同时根据适应度的大小，对种群进行从小到大的排序，则粒子群的黄金适应度为：

优于 fgold(k)的粒子群个数为n1，则其黄金适应度为：

次于 fgold(k)的粒子群个数为n2，则其黄金适应度为：

本文根据粒子适应度的不同来确定不同的收缩因子，进而将粒子群划分为3个子群。

（2）如果当前粒子的适应度 fi(k)优于 fgold1(k)，表明该部分粒子接近最优值，不需要再进行全局搜索，应加快局部收敛速度，所以收敛因子β取0.4。

（3）若粒子适应度 fi(k)优于 fgold2(k)而次于 fgold1(k)，采用云模型对其改进：先设定粒子的数学期望值为EX=fbest(k),b1=b2=2，粒子的熵为：En=(fgold1(k)-fbest(k))/b1，设粒子的超熵与熵的关系值为He=En/b2,则在此区间内的粒子β的取值为：

式（10）中 En′=normrnd(En,He)。

（4）若粒子适应度 fi(k)次于 fgold2(k)，则该部分粒子适应度较差，表明距离群体的最优解较远，应扩大全局收敛能力，所以收敛因子β取0.9。

1.3 测试函数仿真对比

为了验证新算法的有效性，本文采用4个标准测试函数[12]进行仿真对比。

（1）Sphere经典函数是单峰函数，数学表示如下：

该函数在x=[0,0,…,0]处有全局最小值0。仿真寻优迭代曲线如图1所示。

图1 Sphere函数寻优迭代曲线

由图1可知，在相同的初始值和初始速度条件下，CQPSO下降速度最快，同时CQPSO算法到达最大迭代次数200次后达到无限接近全局最优[0,0,…,0]处，比QPSO算法迭代寻优结果精确7个数量级,同时比PSO算法迭代寻优结果精确16个数量级。

（2）Schwefel经典函数也是一个单峰函数，数学表示如下：

该函数在x=[0,0,…,0]处有全局最小值0。仿真寻优迭代曲线如图2所示。

图2 Schwefel函数寻优迭代曲线

由图2可知，CQPSO算法和QPSO算法到达最大迭代次数50次后，取得的最小值无限接近于全局最优[0,0,…,0]处，比PSO算法迭代结果精确1个数量级。

（3）Rastrigin经典函数是多峰函数，数学表示如下：

该函数在x=[0,0,…,0]处有全局最小值0。仿真寻优迭代曲线如图3所示。

图3 Rastrigin函数寻优迭代曲线

由图3可知，在相同的初始值和初始速度条件下，CQPSO下降速度最快，CQPSO算法迭代170次时达到全局最优[0,0,…,0]处，传统QPSO算法迭代173次达全局最优，传统PSO算法迭代185次达全局最优。

（4）Ackley函数为连续、旋转、不可分离的多峰函数。主要通过一个余弦波形来调整指数函数，维数可调。它的拓扑结构的特征是：外部区域几乎平坦（由于主导函数是指数函数），中间出现一个孔或者峰（由于余弦波形的调整），从而变得不平滑。此多峰函数具有大量局部优点，但是全局最优值在[0,0,…,0]处。数学表示如下：

该函数在x=[0,0,…,0]处有全局最小值0。仿真寻优迭代曲线如图4所示。

图4 Schwefel函数寻优迭代曲线

由图4可知，CQPSO算法到达最大迭代次数100次后达到无限接近全局最优[0,0,…,0]处，比QPSO算法迭代寻优结果精确2个数量级，同时比PSO算法迭代寻优结果精确4个数量级。

由于仿真函数的最小值均为0，所以仿真结果的最小值与误差相等。上述测试函数仿真结果即误差如表1所示。

表1 测试函数仿真结果对比表

通过上述经典函数仿真测试，提出的CQPSO算法可行。下面将进一步应用此改进的算法进行属性约简。

2 基于CQPSO算法的粗糙集属性约简

2.1 属性约简描述

粗糙集理论是一种有效分析和处理不准确、不完整信息的有效工具[13]。属性约简的目的是在保持原有判断能力不改变的条件下，保证属性约简个数最少。粗糙集和属性约简相关基本知识如下：

定义1设 P⊆Q,Y∈U,[x]p={y∈U|x ind(P)y},集合Y的下边界（正域）定义为：PY=posp(Y)={x∈U|[x]p∈Y}。

定义2设一个知识库K=(U,R),R表示一个等价关系P,Q∈R，依赖性γp(Q)=card(posp(Q))/card(U)，其中card(X)表示集合X中所包含元素的个数。

定义3条件属性C中所有不可缺少的属性的集合。

定理1若R⊆P,γp(Q)=γR(Q)，则称R是P的一个相对约简。

由定理1可知，约简前后划分Q的依赖性是不变的。

2.2 粒子编码与适应值函数

（1）粒子编码

对于PSO中的粒子编码问题，通过一定的转换，先将属性转成能够直接处理的粒子形式。假设信息系统的属性集为Q={q1,q2,…,qn}，通过编码将其转化成由0，1组合而成的二进制串P={a1,a2,…,an}。ak=0表示属性qk没有被选中，ak=1表示属性qk被选中，其中k∈[1,2,…,n]。

（2）适应度函数

适应值函数是智能优化计算中最核心的部分，可以将一个粒子的适应值对应于该粒子与最优目标粒子的相关性。如果适应值函数选取不当，无法找到属性约简的最优解。而目标解为保证与最初条件属性集有同样依赖度且条件属性最少的子集。这个目标解包括最小的条件属性个数和最大的依赖度，同时其还是一个多目标求解问题。因此，需要先将其转换成单目标求解问题。

根据上述分析，建立粒子适应值函数如下：

其中，card(x)表示粒子x中被选中的条件属性集的个数，m表示原始条件属性集的个数，γC′(D)表示当前粒子条件属性子集的依赖度，γC(D)是原始条件属性全集的依赖性。

为了保证所得结果是一个最小属性约简，在粒子群进化过程中可以动态调整k1、k2，使搜索路径朝着最优目标的方向发展。建立自适应函数[14]如下：

2.3 属性约简算法步骤

根据上述分析，基于CQPSO算法的粗糙集属性约简具体算法流程如下：

步骤1计算各个属性的依赖度，求出条件属性的核Core(C)；如果 γCore(C)(D)=γC(D)，那么 Core(C)即为最小属性约简，输出结果结束；否则转步骤2。

步骤2设置相关的参数，并随机初始化粒子种群。

步骤3根据公式（15）和（16）计算所有粒子的适应值，并初始化Pbest,Gbest。

步骤4根据云模型，对粒子进行分类，得到相应的收缩因子β。

步骤5根据公式（1）～（6）更新粒子位置，并计算每个粒子的适应值。

步骤6更新Pbest和Gbest。

步骤7若终止条件满足，则输出结果结束；否则转步骤4。

算法流程图如图5所示。

3 仿真结果与分析

本文仿真实验环境为Matlab R2010a，运行环境基于Windows7操作系统平台，内存2.00 GB，处理器为Intel®CoreTMi3-2350M CPU@2.30 GHz，并通过对 UCI数据库中的4个标准数据集仿真分析对比，数据集如表2所示。

实验中分别采用PSO约简算法、QPSO约简算法以及提出的云量子粒子群（CQPSO）约简算法进行实验并分析对比，并分别取独立运行10次的平均结果作为属性约简的计算结果，如表3所示。

图5 CQPSO算法实现流程图

表2 实验数据集

表3 属性约简计算结果

由表3可知，对于4个实验数据而言，不论从时间方面还是属性约简个数，CQPSO算法约简的结果更为理想。特别是Sponse数据集，约简个数有很大程度的提高；在对Zoo数据集属性约简的过程中，时间有很大缩减。

此外，本文进一步比较提出的CQPSO算法、PSO算法及QPSO算法在收敛速度和寻优能力方面的差异性，并详细描述在进化过程中三种算法对应的适应值变化。图6、图7分别为Sponge和Soybean_large在优化进程中适应值随迭代次数变化的曲线。

图6 Sponge寻优迭代曲线

图7 Soybean_large寻优迭代曲线

图6和图7的寻优曲线图都表明了迭代次数与适应值两者之间的关系：适应度越高，最小属性约简效果越佳。且与PSO和QPSO约简算法相比，CQPSO约简算法具有更好的收敛速度和寻优能力。

最后，本文还采用QPSO-SVM[15]进行识别，对比3种算法属性约简后识别的准确率，结果如表4所示。

表4 属性约简后识别准确率结果比较 %

表4中，本文提出的算法准确率相比其他两种算法较高，尤其是对数据集Vote识别准确率高达95.47%。

4 结束语

本文针对属性约简中传统粒子群优化算法的收敛速度慢、早熟等问题，提出一种改进的云量子粒子群优化算法，并应用于粗糙集属性约简中，得到如下结论：

通过将云模型与量子粒子群算法结合，提出云量子粒子群算法（CQPSO），并利用黄金分割理论，划分粒子种群来确定不同粒子群的搜索方式。在对经典函数的测试对比中，提出的CQPSO收敛速度快，寻优精度高，算法性能可靠。

在进一步利用CQPSO算法对UCI数据集进行属性约简过程中，提出的CQPSO算法首先对核心适应值进行仿真优化，再利用属性约简后的结果进行识别分析。结果表明，CQPSO算法识别准确率高。

：

[1]Jia X，Shang L，Zhou B，et al.Generalized attribute reduct in rough set theory[J].Knowledge-Based Systems，2016，91（1）：204-218.

[2]Song J，Tsang E C C，Chen D，et al.Minimal decision cost reduct in fuzzy decision-theoretic rough set model[J].Knowledge-Based Systems，2017,13（3）：1-9.

[3]Hu Q，Zhang L，Zhou Y，et al.Large-scale multi-modality attribute reduction with multi-kernel fuzzy rough sets[J].IEEE Transactions on Fuzzy Systems，2017.

[4]Dai S P，Liu S J，Zheng S F.A GA-PSO based attribute reduction algorithm for rough set[J].Computer Engineering&Science，2015，37（2）：397-401.

[5]Konar P，Sil J，Chattopadhyay P.Knowledge extraction using data mining for multi-class fault diagnosis of induction motor[J].Neurocomputing，2015，166：14-25.

[6]Inbarani H H，Azar A T，Jothi G.Supervised hybrid feature selection based on PSO and rough sets for medical diagnosis[J].Computer Methods&Programs in Biomedicine，2014，113（1）.

[7]周恺，王艳，纪志成.混合量子粒子群算法求解模具车间调度问题[J].系统仿真学报，2016，28（6）：1247-1254.

[8]Yao B，Yu B，Hu P，et al.An improved particle swarm optimization forcarton heterogeneousvehicle routing problem with a collection depot[J].Annals of Operations Research，2016，242（2）：1-18.

[9]Sun J，Wu X，Palade V，et al.Convergence analysis and improvements of quantum-behaved particle swarm optimization[J].Information Sciences，2012，193（15）：81-103.

[10]Liu L.Routing of logistics distribution vehicles using cloud adaptive mean particle swarm optimization[J].International Journal of Simulation—Systems，Science&Techno，2016，15（17）.

[11]Berndt D J，Watkins A.Investigating the performance of genetic algorithm-based software test case generation[C]//High Assurance Systems Engineering，2004.

[12]丁进良，杨翠娥，陈立鹏，等.基于参考点预测的动态多目标优化算法[J].自动化学报，2017，43（2）：313-320.

[13]Pawlak Z.Theoretical aspect of reasoning about data[M]//Rough sets：theoretical aspects of reasoning about data.[S.l.]：Kluwer Academic Publishers，1991.

[14]Antón J C Á，Nieto P J G，Gonzalo E G，et al.A new predictive model for the state-of-charge of a high-power lithium-ion cell based on a PSO-optimized multivariate adaptive regression spline approach[J].IEEE Transactions on Vehicular Technology，2016，65（6）：4197-4208.

[15]Guo X，Peng C，Zhang S，et al.A novel feature extraction approach using window function capturing and QPSOSVM for enhancing electronic nose performance[J].Sensors，2015，15（7）：15198-15217.