采用云量子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.