自適應(yīng)約束懲罰的粒子群聚類算法

張國英, 劉冠洲, 徐 寧, 周俊武

(1.中國礦業(yè)大學(xué)(北京) 計(jì)算機(jī)系 北京100083;2.北京礦冶研究總院 北京100044)

自適應(yīng)約束懲罰的粒子群聚類算法

張國英1, 劉冠洲1, 徐 寧2, 周俊武2

(1.中國礦業(yè)大學(xué)(北京) 計(jì)算機(jī)系 北京100083;2.北京礦冶研究總院 北京100044)

提出了基于懲罰約束問題的群體智能聚類算法PCSI,不必窮盡搜索樣本集,利用粒子群算法的優(yōu)化搜索機(jī)制在數(shù)據(jù)集中有指導(dǎo)地隨機(jī)搜索聚類中心向量,能夠以較小的計(jì)算代價(jià)確定樣本集的類別數(shù).有約束優(yōu)化過程的罰函數(shù)為兩部分之和:①目標(biāo)函數(shù),各樣本與其類別中心的均方誤差;②自適應(yīng)懲罰項(xiàng),即數(shù)據(jù)集的邊界作為粒子群移動的約束條件,對約束違反程度進(jìn)行懲罰.為降低不平衡數(shù)據(jù)集的影響,按照數(shù)據(jù)集的方差和模糊高斯函數(shù),將樣本到其類別中心的距離進(jìn)行模糊映射,歸一化到[0,1]區(qū)間.粒子群優(yōu)化方法免去了傳統(tǒng)方法的求導(dǎo)計(jì)算.聚類IRIS數(shù)據(jù)集和Reuters-21578文檔集以驗(yàn)證算法的有效性,對大規(guī)模數(shù)據(jù)聚類有明顯優(yōu)勢.

粒子群算法;智能優(yōu)化;自適應(yīng)罰函數(shù)

0 引言

群體智能優(yōu)化搜索算法在機(jī)器學(xué)習(xí)領(lǐng)域的作用日趨重要,粒子群算法作為其中的成員,能夠有助于確定無監(jiān)督聚類問題的類別數(shù)目.

聚類問題轉(zhuǎn)化為以各樣本與其類別中心的均方誤差為目標(biāo)函數(shù)的優(yōu)化問題,搜尋類別中心的過程即逐步降低均方誤差M SE并使其最小化,同時考慮類別范圍的約束.聚類過程可建模為非線性約束優(yōu)化問題,許多傳統(tǒng)算法(如梯度映射法、梯度下降法、懲罰函數(shù)法及障礙函數(shù)法等)能夠?qū)Ψ蔷€性約束優(yōu)化問題進(jìn)行求解,但單純使用這些方法或者效率低或者適用范圍受限.

計(jì)算智能家族的各種優(yōu)化搜索算法求解過程不依賴于目標(biāo)函數(shù)的解析性質(zhì),具有解的多樣性和計(jì)算的并行性等優(yōu)點(diǎn),能較好解決上述傳統(tǒng)算法易于陷入局部最優(yōu)的缺點(diǎn)[1],對優(yōu)化問題沒有求導(dǎo)的數(shù)學(xué)計(jì)算,可以處理任意形式的目標(biāo)函數(shù)和約束.用優(yōu)化搜索方法求解約束優(yōu)化問題時,首先把個體代入可行域,然后在可行域內(nèi)找到盡可能優(yōu)化的解.目前,懲罰函數(shù)法是最廣泛的約束問題處理方法.

罰函數(shù)通過調(diào)整罰因子實(shí)現(xiàn)目標(biāo)函數(shù)和約束之間的平衡,罰因子過小,對不可行解的懲罰不夠,導(dǎo)致過大的解空間;罰因子過大,使罰函數(shù)對應(yīng)的優(yōu)化曲面更加復(fù)雜,雖然有利于獲得可行解,但不利于獲得優(yōu)良解.本文用搜索過程中獲得的信息反饋指導(dǎo)罰因子的調(diào)整,并采用適應(yīng)性罰函數(shù)[2-3].遺傳算法和粒子群算法是基于生物進(jìn)化思想[4-5]的兩個典型的優(yōu)化搜索方法,將優(yōu)化搜索過程模擬成物種進(jìn)化過程.遺傳算法對復(fù)雜問題的編碼較困難,操作復(fù)雜、效率較低,對不同的優(yōu)化問題往往需要設(shè)計(jì)不同交叉或變異方式.Kennedy和Eberhart提出的粒子群優(yōu)化算法(particle swarm op timization)在許多優(yōu)化問題中的應(yīng)用更為成功[6].

1 群體智能聚類基礎(chǔ)

聚類的主要任務(wù)是找到聚類類數(shù)和各類別中心,K-means等硬聚類算法窮盡搜索整個訓(xùn)練集,反復(fù)計(jì)算各類別中心與所有樣本間的距離,不斷更新類別中心,使所有樣本與其類別中心的距離之和最小化.樣本個數(shù)越多或樣本的特征向量維數(shù)越高,計(jì)算復(fù)雜性就越高.

1.1 聚類的目標(biāo)函數(shù)

1)樣本集C均值(樣本數(shù)N)

2)樣本集C中第j類Cj(樣本數(shù)Nj)的類別中心

3)Cj的方差,反映第j類的分散度

4)均方誤差歸一化

σj即為類別j的均方誤差M SE,聚類的過程是使各類別及整個樣本集的均方誤差最小化.由于不同樣本集的分布差別很大,呈現(xiàn)出不同的密度或尺寸大小.若聚類過程降低均方誤差M SE的絕對值,則密度或尺寸較小的聚群被忽略,大的聚集會被分割.用模糊高斯函數(shù)將樣本與其類別中心的距離進(jìn)行歸一化處理,映射到[0,1]區(qū)間內(nèi).在保留聚類樣本集各類別的區(qū)分特征的條件下,將大小、緊密性不同的類別放在相同判別尺度下度量.

第j個聚類集Cj歸一化后的均方誤差為

假設(shè)類別數(shù)為J,訓(xùn)練集歸一化后均方誤差為

1.2 粒子群算法

粒子群優(yōu)化算法使用并行結(jié)構(gòu)策略[1,6],粒子種群在搜索空間快速移動,每個粒子代表優(yōu)化問題的一個候選解.算法隨機(jī)但有指導(dǎo)性地加強(qiáng)目標(biāo)函數(shù)在多維空間的搜索能力,具有最優(yōu)適應(yīng)度值的候選解是目標(biāo)函數(shù)的優(yōu)化解.PSO具有全局搜索和快速收斂的特點(diǎn),PSO種群中第i個粒子的第d維分量在t+1次迭代的移動速度由公式(6)決定,

粒子的移動速度由3部分構(gòu)成:記憶項(xiàng),各粒子前一次的速度;認(rèn)知項(xiàng),各粒子歷史過程到達(dá)的最優(yōu)位置;社會項(xiàng),整個種群到達(dá)的最優(yōu)位置.

粒子移動后的位置由公式(7)決定,即前一位置與移動速度之和

確定粒子種群的最優(yōu)位置Pg和粒子i的歷史最優(yōu)位置Pi是PSO優(yōu)化的關(guān)鍵.種群在搜索空間內(nèi)全局優(yōu)化Pg并指導(dǎo)搜索,直到達(dá)到迭代次數(shù)或滿足誤差閾值.

粒子群聚類以目標(biāo)函數(shù)(即樣本與其類別中心的均方誤差為適應(yīng)度函數(shù))決定其搜索方向.樣本集進(jìn)行映射后,每個類別分別在不同位置聚集,考慮聚集范圍的約束對類別中心的搜尋有明確的指導(dǎo)作用.粒子群以此為約束條件,對違反約束的移動進(jìn)行懲罰[7],迫使粒子群回歸恰當(dāng)范圍,同時粒子群的迭代次數(shù)作為懲罰因子,使聚類過程自適應(yīng)性地降低迭代次數(shù).

在D維歐式空間RD中,聚類方法依樣本的相似性自動將N個樣本分成J個聚類,并確定其類別的中心向量.集合{x1,x2,…,xNj}表示任一聚類Cj的樣本子集,聚類Cj的類別中心向量亦為D維,即zj=[zj1, zj2,…,zjD].PSO種群的任一粒子代表J個類別的中心向量,對于D維空間的樣本聚類,每個粒子的變元向量為J×D維,

2 罰函數(shù)及約束條件

2.1 適應(yīng)性懲罰函數(shù)

將約束優(yōu)化問題轉(zhuǎn)化為等價(jià)的無約束優(yōu)化問題,罰函數(shù)法是最常用的約束處理技術(shù),將目標(biāo)函數(shù)和約束綜合為一個罰函數(shù),典型的罰函數(shù)[2]為

其中,f(x)為優(yōu)化問題的目標(biāo)函數(shù),Gi(x)和Hj(x)分別為不等式約束和等式約束函數(shù),ri和sj為相應(yīng)的罰因子,Gi(x)和Hj(x)普通形式為:

對于不可行解,違反約束的程度越強(qiáng),相應(yīng)的Gi(x)和Hj(x)函數(shù)值就越大,則罰函數(shù)φ(x)的值就越大.罰因子過小,對不可行解的懲罰不夠,獲得的解可能為不可行解;罰因子過大,會使罰函數(shù)對應(yīng)的優(yōu)化曲面復(fù)雜化,雖然有利于獲得可行解,但不利于獲得優(yōu)良解.合理設(shè)置罰因子是利用罰函數(shù)法求解約束優(yōu)化問題的關(guān)鍵.

把迭代搜索過程中獲得的信息反饋指導(dǎo)罰因子的調(diào)整[3],包括可行解和不可行解的信息,采用通用性更強(qiáng)的適應(yīng)性罰函數(shù)降低約束優(yōu)化的迭代次數(shù),提高解的精度.適應(yīng)性懲罰函數(shù)定義為

λ(t)在迭代過程隨迭代次數(shù)t更新的方式為[3]

其中,β1>1,β2<1,case1表示迭代至第t代時找到的最好個體均為可行解,由罰因子過大導(dǎo)致,可適當(dāng)減小罰因子來降低對不可行解的懲罰壓力;case2表示迭代至第t代時找到的最好個體均為不可行解,表示罰因子過小,需適當(dāng)增大罰因子來增強(qiáng)對不可行解的懲罰;case3表示迭代至第t代時找到的最好個體包括不可行解和可行解,表示罰因子基本合適,可保持.

2.2 群體智能聚類的罰函數(shù)

粒子群聚類的目標(biāo)函數(shù)為粒子種群中所有粒子位置與其類別中心的均方誤差值,聚類過程使均方誤差最小化,

其中,M為粒子種群的粒子數(shù),J為樣本集合聚類的類別數(shù)目,xij表示種群第i個粒子的第j個類別中心分量.每個粒子位置到其類別中心的距離應(yīng)小于粒子位置與樣本集均值的距離,否則表示粒子的移動離開了訓(xùn)練樣本集.優(yōu)化解Z使均方誤差最小,并代表搜索到的所有類別中心的向量集合.

約束條件沒有等式約束條件,僅表示為不等式約束函數(shù)

其中,xi表示種群的第i個粒子,約束粒子群聚類的適應(yīng)度函數(shù)除考慮粒子與其類別中心的均方誤差外,需對粒子移動違反約束的情況進(jìn)行懲罰,適應(yīng)度函數(shù)表述為均方誤差函數(shù)與懲罰函數(shù)之和,采用適應(yīng)性懲罰函數(shù)[3]

3 自適應(yīng)約束懲罰的群體智能聚類算法

基于約束懲罰的群體智能聚類算法(PCSI)可以自動確定樣本集的聚類個數(shù),并對違反約束的情況進(jìn)行自適應(yīng)懲罰調(diào)整,如果找到的最好個體均為可行解,表示罰因子已足夠大,如果找到的最好個體均為不可行解,表示罰因子非常小.PCSI算法步驟如下[7]:

1)初始化種群中M個粒子的位置和速度.每個粒子代表的聚類數(shù)隨機(jī)產(chǎn)生且互不相同,每個粒子的變元維度也各不相同,為類別數(shù)×維數(shù)D,初始速度向量在小范圍內(nèi)隨機(jī)產(chǎn)生;

2)根據(jù)適應(yīng)度函數(shù)式(16)對粒子進(jìn)行評價(jià),適應(yīng)度函數(shù)為均方誤差目標(biāo)函數(shù)與自適應(yīng)罰函數(shù)之和;

3)每個粒子在迭代的過程中獲得的自身歷史最小適應(yīng)度值的位置為其局部優(yōu)化指導(dǎo)Pi;

4)種群粒子取得最小適應(yīng)度值的位置為全局優(yōu)化指導(dǎo)Pg;

5)根據(jù)式(6)和式(7)進(jìn)行粒子速度和位置的更新;

6)重復(fù)步驟2)～5),粒子群在兩次迭代中的適應(yīng)度值之差小于閾值,則具有最小適應(yīng)度值的粒子所代表的聚類數(shù)為訓(xùn)練樣本集的類別數(shù);

7)隨機(jī)產(chǎn)生M個粒子的初始種群,每個粒子的向量維度為:類別數(shù)(步驟6)確定)×維數(shù)D,其中第一個粒子的初始位置為步驟6)具有最小適應(yīng)度值的粒子位置,初始速度向量在小范圍內(nèi)隨機(jī)產(chǎn)生.

8)重復(fù)步驟2)～5),粒子群在兩次迭代中的適應(yīng)度值之差小于閾值,輸出全局優(yōu)化指導(dǎo)Pg及其適應(yīng)度值.Pg代表的類數(shù)目為聚類數(shù)目,向量Pg代表各類別的中心位置.

4 實(shí)驗(yàn)及分析

以Reuters-21578文本數(shù)據(jù)集的Top10子集和IRIS數(shù)據(jù)集進(jìn)行聚類實(shí)驗(yàn),驗(yàn)證約束懲罰的群體智能聚類算法的有效性,進(jìn)行了約束懲罰聚類和無約束群體智能聚類的對照實(shí)驗(yàn).

IRIS數(shù)據(jù)集分為3個類別,共150個樣本,Top10數(shù)據(jù)集包含earn,Acq,Money-fx,Grain,Crude, Trade,interest,w heat,ship和corn共10個類別.PCSI聚類算法主要解決聚類類別數(shù)和搜索出各類別的中心向量這兩個主要問題,式(16)為粒子群優(yōu)化的目標(biāo)函數(shù),采用自適應(yīng)罰函數(shù),迭代過程嚴(yán)格限制粒子的移動范圍在訓(xùn)練樣本集合內(nèi)各類別的內(nèi)部,對移動出可行域的運(yùn)動進(jìn)行懲罰.

PCSI算法分兩步進(jìn)行:首先搜索樣本集的類別數(shù);然后搜索類別中心向量.PCSI算法的參數(shù)設(shè)置為[8]:最大迭代次數(shù)tmax=150;搜索樣本集類別數(shù)時,粒子種群數(shù)目M=5;搜索類別中心向量時,粒子種群數(shù)目M =10;學(xué)習(xí)因子c1=c2=0.5,自適應(yīng)性罰因子的系數(shù)β1=5且β2=0.2.

粒子群初始迭代時在全局范圍較大速度尋優(yōu),在后續(xù)迭代過程降低移動速度,能夠在最優(yōu)值的鄰域內(nèi)逐步逼近最優(yōu)解,因?yàn)檩^大的移動速度在優(yōu)化解鄰域容易震蕩.

4.1 聚類實(shí)驗(yàn)結(jié)果

對基于約束懲罰的群體智能聚類算法進(jìn)行聚類實(shí)驗(yàn)測試,確定數(shù)據(jù)集的聚類個數(shù)時,種群的粒子數(shù)M設(shè)置為5.對于IRIS數(shù)據(jù)集,5個粒子分別代表樣本集類別數(shù)2,3,4,5,6;對于Top10數(shù)據(jù)集,5個粒子分別代表樣本集類別數(shù)6,8,10,12,14.采用自適應(yīng)罰函數(shù)聚類,表1和表2分別為5個種群粒子對IRIS數(shù)據(jù)集和Top10數(shù)據(jù)集聚類的實(shí)驗(yàn)結(jié)果,即每個粒子在聚類結(jié)束時的適應(yīng)度值和迭代次數(shù).

表1 PCSI算法對IRIS數(shù)據(jù)集聚類的實(shí)驗(yàn)結(jié)果Tab.1 Experimental results of PCSIclassifying IRIS

表2 PCSI算法對Top10數(shù)據(jù)集聚類的實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of PCSIclassifying Top10

表1中第2個粒子代表樣本集有3個類別,種群中獲得了最小的適應(yīng)度值,且迭代時收斂最快.Top10數(shù)據(jù)集聚類收斂較慢,表2僅取115次迭代的實(shí)驗(yàn)結(jié)果作為對比,第3個粒子代表樣本集有10個類別,在迭代過程中適應(yīng)度值一直低于其他粒子.IRIS數(shù)據(jù)集和Top10數(shù)據(jù)集的聚類結(jié)果均符合數(shù)據(jù)集的分布.

4.2 約束與無約束聚類實(shí)驗(yàn)

確定聚類個數(shù)后,繼續(xù)搜索類別的中心向量.設(shè)置種群的粒子數(shù)為10,并與無約束粒子群聚類算法CPSO進(jìn)行對照實(shí)驗(yàn),具體見圖1,圖2.

PCSI聚類IRIS數(shù)據(jù)集時迭代到42代時收斂,其適應(yīng)度值為0.64.而CPSO在迭代到50代時基本收斂,適應(yīng)度值為0.74.PCSI的聚類時間是CPSO的84%,適應(yīng)度值下降10.9%.

PCSI聚類Top10數(shù)據(jù)集時,迭代過程其適應(yīng)度值一直低于CPSO,迭代到50代時PCSI算法基本收斂,適應(yīng)度值為1.621.而CPSO的適應(yīng)度值為2.491,適應(yīng)度值下降56.2%.約束懲罰的群體智能聚類算法比無約束智能聚類算法的聚類效率有明顯提高.

[1] Kennedy J,Eberhart R C.Particle swarm op timization[C]//Proceedings of 1995 IEEE International Conference Neural Networks.Perth,1995:1942-1948.

[2] 王凌,何鍥,金以慧.智能約束處理技術(shù)綜述[J].化工自動化及儀表,2008,35(1):1-7.

[3] Wang Y,Cai Z X,Guo GQ.M ulti-objectiveop timization and hybrid evolutionary algo rithm to solve constrained optimization p roblem s[J].IEEE Trans on System s,Man and Cybernetics,Part B:Cybernetics,2007,37(3):560-575.

[4] Montes EM,Coello C A C.A simp le multimembered evolution strategy to solve constrained op timization p roblems[J]. IEEE Transon Evolutionary Computation(S10892778X),2005,9(1):1-17.

[5] Bandyopadhyay S,Maulik U.Genetic clustering fo r automatic evolution of clusters and app lication to image classification [J].Pattern Recognition,2002,35:1197-1208.

[6] Om ran M,Engelbrecht A,Salman A.Particle swarm op timization method for image clustering[J].Journal of Pattern Recognition and A rtificial Intelligence,2005,19(3):297-322.

[7] Zhang Guoying,Liu Yalu,Sha Yun,et al.A new cluster algo rithm based on constrained particle swarm op timization [J].Journal of Computational Information System s,2008,4(3):1037-1040.

[8] Shi Y,Eberhart R C.Parameter selection in particle swarm op timization[C]//Evolutionary Programming V II:Proceedings of 7th Annual Conference on Evolutionary Programming.New York,1998:591-600.

Particle Swarm Clustering Algorithm Based on Adapative Constrained Penalty

ZHANG Guo-ying1, L IU Guan-zhou1, XU Ning2, ZHOU Jun-w u2
(1.Department of Com puter,China university of M ine Technology(Beijing),Beijing 100083,China; 2.Beijing General Research Institute of M ine and M etallurgy,Beijing 100044,China)

A clustering algorithm based on punishing constraint of swarm intelligence(PCSI)is p roposed.Directed by the natureof PSO,PCSIcould random ly search the centersof clustersand obtain the number of clustersw ith fewer computation cost.Penalty function consistsof two components:the first one is the objective function,mean square error(M SE)between every samp le and its cluster center,and the second one is adap tive penalty function,the boundary of data set could be used to constrain particle movement,and the circum stance of violating constraints is punished by corresponding constraint function w ith differential coefficient.In order to decrease the effect of unbalanced data set,the distance of samp le to its cluster center is normalized into space[0,1]by the variation of data set and fuzzy Gaussian function.PCSIisevaluated by clustering IRIS data set and Reuters-21578 text set,and the clustering perfo rmance of PCSIis superio r to non-constrained algo rithm in large size data set.

PSO algorithm;constraint op timization;adap tive penalty function

TP 301.6

A

1671-6841(2010)02-0047-06

2009-11-17

張國英(1968-),女,副教授,博士,主要從事人工智能研究,E-mail:zhangguoying1101@163.com.