基于量子行為的粒子群優化算法分類規則獲取
2009-01-01 00:00:00劉韜殷鋒陳建英何蔚林
計算機應用研究 2009年2期
（1．西南民族大學 計算機科學與技術學院， 成都 610041；2．四川大學 計算機學院， 成都 610065）
摘 要：介紹了基本的粒子群算法，并針對基本的粒子群算法在收斂性能上的缺陷，提出將具有量子行為的粒子群優化算法應用于數據挖掘學科中的分類規則獲取。對加州大學厄文分校的若干數據集模式分類規則進行提取，與其他規則提取方法相比，證明該算法提高了分類規則的正確率以及全局尋優能力。
關鍵詞：粒子群；優化；量子行為；分類
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)02049604
Acquisition of classification rule based on
quantumbehaved particle swarm optimization
LIU Tao1，2，YIN Feng1，CHEN Jianying1，HE Yulin1
(1.School of Computer Science Technology， Southwest University of Nationality， Chengdu 610041， China;2.School of Computer Science， Sichuan University， Chengdu 610065， China)
Abstract:This paper introduced the basic particle swarm optimization(PSO)firstly．Forresolving the shortage of PSO onconvergence precise，presented quantumbehaved particle swarm optimization(QPSO).Presented a new algorithm of acquisition of classification rule based on QPSO，and extracted the classification rules of UCI data sets by this algorithm.The result indicates this algorithm achieves better classification accuracy and global optimum.
Key words:particle swarm；optimization；quantumbehaved；classification
分類是數據挖掘學科的一個重要研究領域，研究人員提出了許多分類規則的獲取算法，如利用決策樹歸納分類、貝葉斯分類、后向傳播分類、遺傳算法分類等。1995年，Kennedy等人[1]受鳥群覓食行為的啟發，提出了粒子群優化算法（PSO），它通過粒子追隨自身找到的最優解及整個粒子群的最優解來進行優化。與其他優化算法相比，其具有收斂速度快、簡單易實現，并且對目標函數要求較少等優點，于是有研究人員將PSO用于分類規則的獲取[2，3]，提高了分類規則獲取的速度。但是在經典的PSO 粒子群系統中，粒子的收斂是以軌道形式實現的，并且粒子的速度總是有限的，因此在搜索過程中粒子的搜索空間是一個有限的區域，不能覆蓋整個可行空間。一般的PSO 算法不能保證以概率1 搜索到全局最優解，這正是一般PSO 算法的最大缺陷。Sun等人[4]提出了QPSO（quantumbehaved particle swarm optimization）算法，它的全局搜索性能優于一般PSO算法。
本文基于量子行為的粒子群優化算法提出了一種新的分類規則獲取方法。該分類方法能保證粒子群的全局收斂，優于基于經典PSO算法的分類規則獲取方法。
1 基本粒子群算法（BPSO）
在PSO中，每個優化問題的解都是搜索空間中的一只鳥，稱之為粒子。所有的例子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定它們飛翔的方向和距離，然后粒子們就追隨當前的最優粒子在解空間中搜索。PSO 初始化為一群隨機粒子(隨機解)，并通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值p best；另一個極值是整個種群目前找到的最優解，這個極值是全局極值g best。另外，也可以不用整個種群而只用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。
1.1 PSO基本概念
定義1 粒子。類似于遺傳算法中的染色體，PSO中粒子為基本的組成單位，代表解空間的一個候選解。設解向量為d維變量，則當算法迭代次數為t時，第i個粒子Xi(t)可表示為 Xi(t)=[xi1(t)， xi2(t)，… ，xid(t)]。其中：xik(t)表示第i 個粒子在第k維解空間中的位置 ，即第i個候選解中的第k個待優化變量。
定義2 種群。粒子種群(population)由n個粒子組成，代表n個候選解。經過t次迭代產生的種群：pop(t)=[x1(t)，x2(t)，…，xi(t)，…，xn(t)]。其中：xi(t)為種群中的第i個粒子。
定義3 粒子速度。它表示粒子在單位迭代次數位置的變化即為代表解變量的粒子在d維空間的位移。Vi(t)=[vi1(t)，vi2(t)，…，vid(t)]。其中： vik(t)為第i個粒子在解空間第k維的速度。
定義4 慣性權重。粒子群優化算法的全局搜索特性通過隨機初始化的速度體現。慣性權重w用于控制前一次迭代產生的粒子速度對本次迭代速度的影響。粒子群優化算法的全局搜索特性通過隨機初始化的速度體現。慣性權重w∈[0，1]。Shi與Eberhart通過實驗證明，較大的慣性權重有利于粒子群進行全局搜索，而較小的慣性權重種群更傾向于局部搜索。在實際的優化問題求解過程中，慣性權重隨迭代次數線性遞減，w(t)=aw(t-1)，使粒子群在搜索的初始階段能夠以較大的概率在整個解空間進行搜索，并能夠快速收斂到最優解所在的局部區域，然后隨著慣性權重的遞減，粒子種群在該區域內實現局部微調。
定義5 適應度(fitness)函數。它由優化目標決定，用于評價粒子的搜索性能，指導粒子種群的搜索過程。算法迭代停止時適應度函數最優的解變量即為優化搜索的最優解。
定義6 個體極值(p best)。個體極值pi=(pi1，pi2，…，pid)是第i個粒子從搜索初始到當前迭代所對應的適應度最優的解變量。
定義7 全局極值(g best)。全局極值g=(g1，g2，…，gd)是整個粒子種群從搜索開始到當前迭代所對應的適應度最優的解變量。
PSO首先初始化為一群隨機粒子(隨機解)，然后通過迭代搜索最優解。在每一次迭代中，粒子通過個體極值與全局極值更新自身的速度和位置：
vij=wvij+c1r1(pij-xij)+c2r2(gj-xij)(1)
xij=xij+vij(2)
i=1，2，…，n; j=1，2，…，d-1
其中：r1，r2是均勻分布在(0，1)的隨機數；c1和c2是學習因子，通常c1=c2=2。
粒子就在解空間內不斷跟蹤個體極值與全局極值進行搜索，直至達到規定的最大迭代次數或達到最小的誤差標準為止。此外，為使粒子速度不至于過大，可設定速度上限Vmax，當某一維的速度超過這一設定速度時，就令這一維的速度為Vmax。
基本粒子群算法（BPSO）的具體流程如下：
a）初始化粒子群。
b)計算粒子群中每個粒子的適應度。
c)根據粒子的適應度更新個體極值和全局極值。
d)根據式(1)和（2）更新粒子群的速度和位置。
e)判斷是否達到最大迭代次數或滿足最小錯誤標準。如果沒有則轉步驟b)；否則循環結束。
1.2 PSO早熟現象的判定
研究發現:BPSO算法的前期側重于全局搜索，搜索可能的最優解，粒子向群體最優點移動，可能早熟(過早陷入局部極小)；粒子具有較大的運動速度，適合前期的全局搜索，在后期卻造成在群體最優點附近振蕩的粒子振幅過大，使解的收斂精度較低。
1.2.1 平均粒距
粒子群優化算法在運行過程中，整個種群追隨兩個極值運動。如果某個粒子發現當前最優位置，其他粒子將會迅速向其靠攏，種群的多樣性將會消失。若該位置為一局部最優點，粒子群就無法跳出這一局部最優點，從而無法展開對全局最優點的搜索。此時，算法陷入了局部最優，出現了所謂的早熟收斂現象。
文獻[5]指出平均粒距表達了種群各個體相互之間的分布離散程度，描述了種群的多樣性，進而判斷早熟現象。
設L為搜索空間對角最大長度；N為種群規模大小；D為解空間的維數；pid表示第i個粒子的第d維坐標值，d表示所有粒子第d維坐標值均值。平均粒距如下：
D(t)=1/(N×L)×Ni=1Nd=1(pid-pd)2（3）
由式(3)可知，平均粒距獨立于種群規模大小、解空間的維數以及每維搜索范圍。D(t)越小，表示種群越集中；D(t)越大，表示種群越分散。
1.2.2 適應度方差
隨著種群的不斷進化，個體之間的差異越來越小，而個體位置決定著個體的適應度大小。因此，根據種群中所有個體的適應度整體變化可以判斷種群的狀態。
設個體i的適應度為fi，當前種群的平均適應度為favg，σ2 為種群的適應度方差[6]，定義為
σ2=Ni=1[(fi-favg）/f]2（4）
其中：N為種群個體數目；f為歸一化定標因子，其作用是限制σ2的大小。f的取值采用如下公式：
f=max1≤i≤N|fi-favg|，max|fi-favg|＞1
1，其他（5）
式（4）表明，群體適應度方差反映的是種群中個體的聚集程度。σ2越小，則種群中個體的聚集程度越大；反之，則聚集程度越小。隨著迭代次數的增加，種群的個體適應度會越來越接近，因此σ2會越來越小。當σ2 種群的平均適應度方差從函數值方面反映粒子分布情況，而平均粒距從空間角度反映各個個體相互之間的分布離散程度。只采用平均適應度方差來描述種群的多樣性是不夠完善的，如當種群收斂于若干個分散的局部極小點時，而這幾個極小點又相差不大，則此時種群的適應度方差很小，平均粒距卻很大。因此，可以同時采用以上兩種策略對種群多樣性，即是否陷入停滯進行判斷。 2 量子粒子群算法（QPSO） 2.1 QPSO基本思想 在經典的PSO粒子群系統中，粒子的收斂是以軌道形式實現的，并且由于粒子的速度總是有限的，在搜索過程中粒子的搜索空間是一個有限的區域，不能覆蓋整個可行空間。一般的PSO算法不能保證以概率1搜索到全局最優解。而在量子空間中因為粒子滿足聚集態的性質，它可以在整個可行解空間中進行搜索，所以Sun等人[4，7]提出了QPSO算法，其全局搜索性能遠遠優于一般PSO算法。 在QPSO算法中，粒子的速度和位置信息都歸結于一個參數。為了保證算法的收斂性，每一個粒子必須收斂于各自的p點，p=(p1，p2，…，pd)，pd是該粒子在第d維的值。 pd=（φ1×pid+φ2×pgd）/(φ1+φ2)(6) 其中：φ1、φ2是介于0和1之間的隨機函數。 同時在粒子群中引入了一個中值最優位置來計算粒子的下一步迭代的變量，該值定義為所有粒子的局部極值的平均值。公式如下： m best=1/MMi=1Pi=(1/MMi=1pi1，…，1/MMi=1pid)（7） 其中：M是粒子群的個數；Pi是粒子i的全局極值。因此可以得到粒子的進化方程 x(t+1)=p±β×|m best-x(t)|×ln(1/u)(8) u=rand(0，1) 其中：β是系數創造力，調節它的值能控制算法的收斂速度。通常情況下，從1.0線性減小到0.5時，算法可以達到比較好的效果。 β=(1-0.5)×(MAXITER-t)/MAXITER+0.5(9) 其中：MAXITER是最大迭代次數；t是當前迭代次數。 式(6)~(9)為QPSO的算法方程。 QPSO的算法流程如下: 初始化種群每個粒子的位置向量x=(x1，x2，…，xd)，并把粒子群的歷史局部最優p賦初值，等于x for t=1 to MAXITER 利用式（9）計算β for i=1 to粒子數大小 if f(xi) pg=min(pi)(pg是全局最優) 利用式(7)計算m best for d=1 to 維數D φ1=rand(0，1)，φ2=rand(0，1) pd=(φ1×pid+φ2×pgd)/(φ1+φ2) u=rand(0，1) if rand(0，1)>0.5 xid=p-β*|m bestd-xid|*ln(1/u) else xid=p+β*|m bestd-xid|*ln(1/u) 直到終止條件滿足 2.2 QPSO算法的優點 量子粒子群算法能夠克服一般粒子群算法在收斂性能上的缺陷是由于其具有如下三點特性: a)量子系統是一個復雜的非線性系統并且符合狀態重疊原理，因此量子系統比一個線性系統具有更多的狀態。 b)量子系統是一個與典型隨機系統不同的不確定性系統，在這樣的一個系統中，一個粒子能夠以某一確定的概率出現在搜索空間中的任意一個位置，因為粒子沒有一個確定的軌跡。 c)在PSO算法中，粒子必須在一個有限的搜索范圍內以確保粒子群的聚集性，使算法收斂于一個最優點或局部最優點。在傳統的PSO算法中，有限的搜索范圍將粒子限制在了一個固定的區域；而在QPSO算法中，粒子能夠以某一確定的概率出現在整個可行的搜索空間中的任意一個位置，甚至是一個遠離p點的位置。這樣的一個位置可能比當前群體中的p best具有更好的適應值。 3 利用具有量子行為的粒子群算法實現分類 3.1 分類規則的表示 本文用一個粒子代表一條分類規則，規則通常描述成如下形式： if condition1 and condition2…and conditionk then class_x 本文研究連續型數值的屬性集問題，將規則描述成: if attribute1_min≤x1≤attribute1_max and attribute2_min≤x2≤attribute2_max and …… attributek_min≤xk≤attributek_max then class_x 粒子的每一維代表規則的一個分類變量。設有k個分類變量，x={x1，x2，…，xk}。其中粒子的每一維xi用上界和下界兩個變量表示： xi={attribute_i_min，attribute_i_max} 3.2 分類規則的適應度函數 分類規則的評估一般采用靈敏度(sensitivity)、特效度(specificity)和精度(precision)等指標。 給定兩類，可以使用術語正元組（感興趣的元組，如is_student=yes）和負元組(is_student=no)。真正（t_pos）是指用分類規則正確標記的正元組；而真負（t_neg）是分類規則正確標記的負元組；假正（f_pos）是錯誤標記的負元組（如is_student=no的元組，分類規則判定為is_student=yes）；類似地，假負(f_neg)是錯誤標記的正元組。靈敏度、特效度和精度分別定義為 sensitivity=t_pos/pos specificity=t_neg/neg precision=t_pos/(t_pos+f_pos) 其中：精度表示被分類標記為正樣本的數據實際是正樣本的百分比，常用于分類器中的規則匹配；靈敏度表示規則對正樣本的分類情況；特效度描述的是對負樣本的拒絕情況。分類規則r的適應度函數取分類規則的正確率： f(r)=accuracy=sensitivity×pos/(pos+neg)+specificity×neg/(pos+neg) （10） 3.3 規則提取算法 基于量子行為的粒子群算法某一個類別的分類規則的提取算法如下： a)用一個粒子代表一條分類規則，初始化一定數目的粒子，即在分類變量的有效區間內隨機初始化粒子分類變量的上下界變量，構成規則提取算法的初始候選解集，形成粒子群。 b)初始化每個粒子的歷史局部最優的p點，讓p等于粒子x的初始值:p=x。 c）利用前面所述的QPSO算法計算，分類規則r的適應度函數為f(r)（式(10)），注意兩個粒子（代表兩個分類規則）應取f(r)函數值較大的為優。并且當粒子的每一維xi的上界和下界兩個變量隨粒子飛行變化時，若任一個變量超過有效區間的邊界值，則將它設為邊界值。 d)全局最優的粒子pg即為所得最優解。 4 實驗與結果分析 實驗采用著名的鳶尾花（Iris）數據集，該數據集從加州大學厄文分校（UCI）的機器學習庫中得到。鳶尾花數據集包含150種鳶尾花的信息，每50種取自三個鳶尾花種之一：Setosa、Versicolour和Virginica。每個花的特征用下面五種屬性描述： a)萼片長度（cm）。 b)萼片寬度（cm）。 c)花瓣長度（cm）。 d)花瓣寬度（cm）。 e)類（Setosa， Versicolour， Virginica）。 它們的取值為[4.3，6.90]，[2.0，4.4]，[1.0，6.9]，[0.1，2.5]。根據以上信息構建QPSO分類算法，取粒子數為300，最大迭代次數為400，根據該算法提取的Iris數據集的分類規則如下： if 4.30≤x1≤6.90 and 2.02≤x2≤4.34 and 1.00≤x3≤2.44 and 0.10≤x4≤2.50 then class=Iris-Setosa if 4.68≤x1≤6.85 and 2.02≤x2≤3.55 and 1.72≤x3≤4.94 and 0.32≤x4≤1.67 then class=Iris-Versicolor if 4.80≤x1≤1≤6.90 and 2.00≤x2≤4.05 and 4.01≤x3≤6.90 and 1.62≤x4≤2.50 then class=Iris-Virginica 三條分類規則在Iris數據集上的正確率依次為99.3%、96.00%、86.67%， 而基本PSO算法分類規則的正確率依次為94.0%、96.67%、85.33%。實驗結果表明，QPSO算法提取的三條分類規則可以對Iris數據集中的所有實例進行成功分類，與基本PSO相比，正確率有所提高。 另外在UCI的機器學習數據倉庫中選擇三個數據集，主要針對取連續值特征的數據集，分別采用PSO和QPSO算法獲取分類規則，并采用10折交叉有效性（10-fold cross-validation）驗證方法進行分類規則的分類準確性估計。分類規則的平均正確率如表1所示。 表1 QPSO和PSO獲取分類規則的平均正確率比較 DataSetPSOQPSO Iris92.10±4.0594.00±3.86 Wine92.00±5.9093.30±5.39 Wdbc94.21±3.4096.33±2.98 Glass73.47±5.1378.10±6.67 從表1可以看出，基于量子行為的粒子群優化算法（QPSO）獲取的分類規則正確率優于一般PSO算法。 5 結束語 本文首先介紹了基本的粒子群算法，并針對基本粒子群算法在收斂性能上的缺陷，提出了具有量子行為的粒子群優化算法，將它應用于數據挖掘學科中的分類規則獲取算法。經實驗表明，它的收斂速度快，提高了正確率，是一種有效、可行的分類規則獲取算法。 參考文獻： ［1］ KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.1995:19421948. [2]段曉東，王存睿，王楠楠，等. 一種基于粒子群算法的分類器設計[J].計算機工程，2005，31（20）：107109. [3]高亮，高海兵，周馳，等．基于粒子群優化算法的模式分類規則獲取[J].華中科技大學學報：自然科學版，2004，32(11):2426. [4]SUN Jun，FENG Bin，XU Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proc of IEEE Conference on Evolutionary Computation.2004:325331. [5]KRIN T，VESTERSTROEM J S，RIGET J.Particle swarm optimization with spatial particle extension[C]//Proc ofIEEE Congress on Evolutionary Computation(CEC).Honolulu:IEEE，2002:14741479. [6]呂振肅，侯志容．自適應變異的粒子群優化算法[J].電子學報，2004，32(1):416420. [7]SUN Jun，XU Wenbo.A global search strategy of quantumbehaved particle swarm optimization[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems.2004:111116. [8]LIANG J J，QIN A K，SUGANTHAN P M，et al.Particle swarm optimization algorithms with novel learning strategies[C]//Proc of IEEE International Conference on Systems，Man and Cybernetics.[S.l.]:IEEE，2004：36593664.
