丁 輝 胡 芬

(四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院，四川 成都 610066)(長(zhǎng)江職業(yè)學(xué)院公共課部，湖北 武漢 430074)

2013-09-10

丁輝(1983-)，男，碩士生，現(xiàn)主要從事算法設(shè)計(jì)方面的研究工作。

胡芬(1982-)，女，碩士，講師，現(xiàn)主要從事概率統(tǒng)計(jì)方面的教學(xué)與研究工作；E-mail:644107401@qq.com。

一種基于粒子群優(yōu)化的頂點(diǎn)著色聚類算法及其應(yīng)用

丁 輝 胡 芬

(四川師范大學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院，四川 成都 610066)(長(zhǎng)江職業(yè)學(xué)院公共課部，湖北 武漢 430074)

針對(duì)數(shù)據(jù)挖掘中的聚類問題，提出一種基于粒子群優(yōu)化的頂點(diǎn)著色聚類算法。根據(jù)修改粒子群算法中參數(shù)值，擴(kuò)展種群的搜索范圍，增強(qiáng)整個(gè)群體聚類效果，用頂點(diǎn)著色算法進(jìn)行進(jìn)一步聚類。將改進(jìn)的聚類算法應(yīng)用于識(shí)別阿爾茲海默病(Alzheimer’s disease)候選基因中，識(shí)別出了一些真實(shí)的候選基因(Somatostatin, GABRA1,MOG)。

粒子群優(yōu)化；頂點(diǎn)著色；聚類算法； 阿爾茲海默病

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是一種基于群體智能的具有全局尋優(yōu)能力的優(yōu)化工具，通過群體中粒子間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索，每代種群中的解具有“自我”學(xué)習(xí)提高和向“他人”學(xué)習(xí)的優(yōu)點(diǎn)，能夠得到較優(yōu)解[1-2]。PSO算法的基本屬性是：①基于一個(gè)隨機(jī)初始化種群；②通過反復(fù)迭代尋找最優(yōu)解；③基于當(dāng)、前代的信息更新。粒子群優(yōu)化算法具有并行處理特性，魯棒性好，粒子只通過內(nèi)部速度進(jìn)行更新，因此原理更簡(jiǎn)單、參數(shù)更少、實(shí)現(xiàn)更容易[3]。但是，在算法運(yùn)行過程中，粒子易陷入局部最優(yōu)，會(huì)出現(xiàn)早熟收斂現(xiàn)象。此外，PSO算法聚類技術(shù)必須要提前指定所要得到的聚類數(shù)目，而在很多實(shí)際情況下，最佳的聚類數(shù)目是預(yù)先未知的。

聚類算法是基因分析中主要技術(shù)之一。聚類在事先不規(guī)定分類規(guī)則的情況下，將基因表達(dá)數(shù)據(jù)按照其自身特征劃分為不同的類，它是一種無(wú)監(jiān)督的學(xué)習(xí)方法。聚類結(jié)果要求不同類間數(shù)據(jù)相似性越小越好，而類內(nèi)數(shù)據(jù)相似性越大越好。因此事先給出不同的分類規(guī)則，聚類效果和結(jié)果都會(huì)有一定影響。

應(yīng)用圖論的原理可以將基因聚類問題轉(zhuǎn)化為對(duì)圖的頂點(diǎn)著色問題。類內(nèi)的基因數(shù)據(jù)擁有同一種顏色，類間的基因數(shù)據(jù)擁有不同顏色[4]。因此，基因聚類問題轉(zhuǎn)化為圖論中的頂點(diǎn)著色問題，聚類基因類的個(gè)數(shù)就是頂點(diǎn)著色的最少顏色數(shù)。在聚類的過程中，可能出現(xiàn)一個(gè)基因?yàn)橐粋€(gè)類，這樣的基因稱為孤立點(diǎn)基因。

基于以上的介紹，筆者對(duì)PSO中的參數(shù)進(jìn)行改進(jìn)，優(yōu)化了粒子群算法，避免粒子過早陷入局部最優(yōu)，同時(shí)針對(duì)聚類數(shù)目情況，用圖論中的頂點(diǎn)著色原理可以有效地克服聚類的數(shù)目，同時(shí)用改進(jìn)的聚類算法作用于Alzheimer’s disease(AD)基因表達(dá)數(shù)據(jù)，從而識(shí)別出AD候選基因。

1 粒子群優(yōu)化算法

1.1基本粒子群算法

(1)

式中，ω為慣性因子;c1,c2為學(xué)習(xí)因子;r1,r2為[0,1]上的隨機(jī)數(shù);pij為第i個(gè)粒子中自身最好位置的第j維坐標(biāo);gj為全局最好位置的第j維坐標(biāo)。

由式(1)組成的PSO算法成為標(biāo)準(zhǔn)粒子群優(yōu)化算法。另外可以通過給出粒子的速度和位置限定范圍來(lái)限制粒子的移動(dòng)，以達(dá)到對(duì)算法較好控制:

(2)

1.2慣性因子的改進(jìn)

在算法的早期，通過提高慣性因子遞減速度，可以加強(qiáng)算法的全局收斂性，且得PSO的慣性權(quán)值為凹函數(shù)策略優(yōu)于線性函數(shù)策略，同時(shí)線性策略優(yōu)于凸函數(shù)策略，而在凹函數(shù)中遞減的指數(shù)函數(shù)性能最佳[5]。但是對(duì)于數(shù)據(jù)規(guī)模較大、維數(shù)較大的粒子群，如果搜索開始時(shí)過快降低慣性權(quán)值，使得在短時(shí)間內(nèi)進(jìn)入慣性權(quán)值比較小的狀態(tài)，這樣造成了局部搜索能力強(qiáng)而全局搜索能力弱的局面，容易早熟。因此筆者采用的慣性因子如下：

(3)

式中，t為迭代次數(shù)；T為總迭代次數(shù)。

1.3學(xué)習(xí)因子的改進(jìn)

學(xué)習(xí)因子c1表示粒子的個(gè)體認(rèn)知能力，學(xué)習(xí)因子c2表示粒子的社會(huì)認(rèn)知能力。因此在搜索的前期，c1取較大值而c2取較小值，目的是讓粒子多些向自己的最優(yōu)pbest學(xué)習(xí)，向全局最優(yōu)gbest學(xué)習(xí)少一些，這樣使得粒子的全局搜索能力增強(qiáng)；而在后期剛好相反，c1取較小值而c2取較大值，使粒子向全局最優(yōu)位置gbest的局部靠攏，局部搜索能力增強(qiáng)[6]。因此，筆者對(duì)c1,c2作如下調(diào)整：

(4)

2 頂點(diǎn)著色算法

給定圖G=(V,E)的一個(gè)k染色，用Vi表示在G中染以第i色的頂點(diǎn)集合(i=1,2,…,k)，則每個(gè)Vi都是G的獨(dú)立集。因此G的一個(gè)k染色對(duì)應(yīng)V(G)的一個(gè)劃分[V1,V2,…,Vk]，其中每個(gè)Vi是獨(dú)立集。反之，若V(G)有這樣一個(gè)劃分[V1,V2,…,Vk]，其中每個(gè)Vi均是獨(dú)立集(1≤i≤k)，則相應(yīng)地得到G的一個(gè)k染色，稱V(G)的這樣一個(gè)劃分為G的一個(gè)色劃分，每個(gè)Vi稱為色類(i=1,2,…,k)。因此G的色數(shù)χ(G)就是使這種劃分成為可能的最小自然數(shù)k。

如果一個(gè)圖G表示聚類效果圖時(shí)，通常利用圖的鄰接矩陣來(lái)描述它的結(jié)構(gòu)。下面給出如下定義：

設(shè)圖G的頂點(diǎn)集V(G)=(v1,v2,…,vn)，若vi與vj不同類時(shí)，則aij=1,反之若vi與vj同類時(shí)，則aij=0若則稱元素aij(i,j=1,2,…,n)構(gòu)成的n階矩陣為圖的鄰接矩陣(adjacent matrix)。特殊地，若鄰接矩陣中某一行元素只有一個(gè)0其他都為1時(shí)，則表示該行對(duì)應(yīng)的頂點(diǎn)與其他頂點(diǎn)都不屬于一類，即自己屬于一類，這樣的點(diǎn)稱之為孤立點(diǎn)。

3 聚類算法設(shè)計(jì)

3.1適應(yīng)度函數(shù)的選取

基于粒子群優(yōu)化算法的頂點(diǎn)著色算法是在使用一種距離作為相似性度量的基礎(chǔ)上，將數(shù)據(jù)集合劃分為指定的M類，使得聚類劃分總體類間差異(Total Within-cluster Variation, TWCV)最小化[7]。設(shè){X1,X2,…,XN}為數(shù)據(jù)集合，xnd代表數(shù)據(jù)Xn的第d維屬性(n=1,2,…，N)。若用Gm代表第m個(gè)類，Zm代表Gm中的元素個(gè)數(shù)，則類Gm的聚類中心Cm=(cm1,cm2,…,cmD)可以表示為：

(5)

由此第m類的類間差異(Within-cluster Variation, WCV)可表示為：

(6)

式中,d(xnj,cmj)表示xnj到該點(diǎn)質(zhì)心cmj的一種距離。TWCV可表示為：

(7)

3.2頂點(diǎn)著色操作

根據(jù)鄰接矩陣定義，得到頂點(diǎn)隸屬關(guān)系。從頂點(diǎn)度數(shù)最小的頂點(diǎn)開始染色，找到不與其相鄰的頂點(diǎn)并選擇一個(gè)頂點(diǎn)進(jìn)行染色，再找不與這2個(gè)頂點(diǎn)相鄰的頂點(diǎn)集合中選擇一個(gè)染色，如此下去，將所有頂點(diǎn)染色為止，程序結(jié)束[4]。

設(shè){x1,x2,…,xN}為N個(gè)數(shù)據(jù)的集合，xnd代表數(shù)據(jù)xn的第d維屬性(n=1,2,…，N)，定義鄰接矩陣中的aij表示xi和xj的鄰接關(guān)系，且:

(8)

式中,dij為xi和xj之間的歐式距離;δ為給定的一個(gè)值。

aij=1表示xi和xj屬于不同的類，aij=0表示xi和xj屬于同一類。

3.3聚類算法

基于PSO的頂點(diǎn)著色聚類首先定義聚類劃分解的編碼規(guī)則，解群體在隨機(jī)初始化后隨著迭代過程中進(jìn)化，每一次進(jìn)化，在當(dāng)前代的粒子上進(jìn)行PSO更新操作和頂點(diǎn)著色操作，產(chǎn)生新一代粒子群體，進(jìn)化的過程一直持續(xù)到滿足事先定義的終止條件?；赑SO算法的頂點(diǎn)著色聚類算法流程如下:

Step1(粒子編碼) 在PSO聚類中，選擇對(duì)聚類中心進(jìn)行編碼，即每個(gè)粒子由M個(gè)聚類中心向量表示為Xi=(Ci1,Ci2,…,Cij,…,CiM)，其中Cij表示第i個(gè)粒子的第j個(gè)聚類中心向量。每一個(gè)粒子代表了對(duì)當(dāng)前數(shù)據(jù)的一種聚類劃分，粒子數(shù)目和類的數(shù)目根據(jù)聚類問題的復(fù)雜度適當(dāng)選取。

Step2(算法初始化) 在聚類的初始階段，隨機(jī)取出數(shù)據(jù)分配到M個(gè)類中，然后根據(jù)歐式距離得到每一類的數(shù)據(jù)，計(jì)算每一類的聚類中心，這樣就得到了PSO算法的一個(gè)初始粒子，反復(fù)N次計(jì)算，得到了N個(gè)粒子的初始粒子群。計(jì)算每個(gè)粒子的個(gè)體最好位置pbest，并且設(shè)置pbest為粒子的初始位置，將具有最小的TWCV的pbest定義為算法的初始全局最好位置gbest。令P=0。

Step3若達(dá)到收斂條件則執(zhí)行Step8，否則執(zhí)行Step4。

Step4(粒子更新操作) 根據(jù)粒子群優(yōu)化算法中采用式(3)、(4)給出的參數(shù)，由式(1)更新粒子速度和位置。

Step5(pbest和gbest的更新) PSO聚類的特點(diǎn)在于它的記憶性。整個(gè)粒子群的全局最好位置(gbest)和每個(gè)粒子的個(gè)體最好位置(pbest)在每次迭代后保存下來(lái)，用于下一次更新操作以指導(dǎo)新群體的產(chǎn)生。因此在PSO操作后和頂點(diǎn)著色操作后，每個(gè)粒子的pbest和整體gbest必須更新。

Step6產(chǎn)生一組gbest和聚類中心。

Step7P=P+1,轉(zhuǎn)Step2。

Step8(頂點(diǎn)著色聚類)P組選取最佳聚類效果的粒子及其聚類中心點(diǎn)，給出每個(gè)類的分類閾值，由其對(duì)應(yīng)的類中的數(shù)據(jù)距離建立鄰接矩陣，根據(jù)頂點(diǎn)著色聚類算法，得到算法結(jié)果(筆者給出的分類閾值是該類間各頂點(diǎn)間距離平均值的3.5倍)。

4 算法試驗(yàn)與分析

4.1數(shù)據(jù)來(lái)源

數(shù)據(jù)是Alzheimer’s Disease(AD)基因數(shù)據(jù)，其來(lái)源于美國(guó)國(guó)家生物信息網(wǎng)[8]，該數(shù)據(jù)包含22283個(gè)基因，從正常、輕度、中度和重度4種狀態(tài)下獲取，為了進(jìn)行基因表達(dá)數(shù)據(jù)進(jìn)行運(yùn)算，把所有的原始數(shù)據(jù)表示為矩陣的形式(如表 1)。表 1包含了22283行9列，每一行表示一個(gè)基因在9種不同的樣本中獲得的數(shù)據(jù)，每一列表示一個(gè)樣本的22283個(gè)基因表達(dá)值，表 1的基因表達(dá)矩陣記為Mctrl。同樣地可以得到輕度、中度和重度狀態(tài)下的基因表達(dá)矩陣，分別記為Mincip、Mmoder和Msevere，這3個(gè)矩陣的行數(shù)均為22283，列數(shù)分別為7,8,7。

4.2算法參數(shù)設(shè)置

聚類實(shí)驗(yàn)中各聚類算法的參數(shù)設(shè)置如下：慣性因子最大值和最小值分別為2和0.5，速度最大值和最小值分別為0.5和-0.5，粒子群個(gè)數(shù)10組，每個(gè)粒子群由18個(gè)粒子組成，聚類中心點(diǎn)為75個(gè)，迭代次數(shù)100次。

表1 DNA microarray 數(shù)據(jù)組成結(jié)構(gòu)

表2 識(shí)別候選基因表

表3 4種改進(jìn)參數(shù)的聚類算法參數(shù)設(shè)置

注：PSO+VC、WPSO+VC、CPSO+VC、MPSO+VC為4種改進(jìn)參數(shù)的頂點(diǎn)(VC)聚類算法。

4.3試驗(yàn)結(jié)果

聚類算法的試驗(yàn)環(huán)境為MATLAB 2010b， Intel Core 2 Quad Q8300 2.5GHz 4.00GB。識(shí)別AD候選基因的標(biāo)準(zhǔn)如下：當(dāng)一個(gè)基因在正常狀態(tài)下與其他基因聚為一類，但在其他3種生病狀態(tài)與任何基因都不能聚為一類，這個(gè)基因成了孤立的；此外4種狀態(tài)AD樣本數(shù)據(jù)的采集是相互獨(dú)立，因此孤立基因的出現(xiàn)只與疾病本身有關(guān)，而與外在條件無(wú)關(guān)，這樣的孤立基因作為識(shí)別AD患者的候選基因。

利用基于粒子群優(yōu)化的頂點(diǎn)著色聚類算法識(shí)別出了28個(gè)AD候選基因(表2)，其中SST和MOG證實(shí)與AD有關(guān)[9-10]；GABRA1作為突觸成員之一，是調(diào)節(jié)G蛋白信號(hào)進(jìn)行編碼的基因，減少的GABRA1阻礙了AD腦的神經(jīng)功能[9],其他某些基因可能潛在和AD有關(guān)的通路(不在筆者討論范圍內(nèi))。

4.4算法分析

選取表 1中前1000行數(shù)據(jù)，給出了4個(gè)參數(shù)更改(表3)的基于粒子群的頂點(diǎn)著色聚類效果比較。針對(duì)參數(shù)改進(jìn)的4種算法，為了可比性，其他設(shè)置一致：給定10個(gè)相同的初始聚類中心點(diǎn)，產(chǎn)生18個(gè)種群，迭代次數(shù)50。

圖 1中表示了1000個(gè)基因表達(dá)水平的4種聚類效果圖，每個(gè)子圖都包含了1000行9列的顏色子塊，相鄰兩行間的顏色子塊不同反映了2個(gè)基因表達(dá)水平差異性。差異性越小，表示聚類效果越佳。圖1(d)的差異性最小，相鄰行間的顏色整體性較強(qiáng)。為了刻畫聚類效果，根據(jù)文獻(xiàn)[7]給出的幾種計(jì)算質(zhì)點(diǎn)與質(zhì)心的相關(guān)性函數(shù)，計(jì)算了以上4種聚類效果的適應(yīng)度值(表4)。分析表 4中數(shù)據(jù)可知，改進(jìn)的聚類算法適應(yīng)度各個(gè)指標(biāo)均優(yōu)于其他3種聚類算法，說(shuō)明改進(jìn)后的聚類算法在對(duì)聚類效果有一定改進(jìn)。

圖1 4種改進(jìn)參數(shù)的聚類算法treeview效果圖

指標(biāo)算法PSO+VCWPSO+VCCPSO+VCMPSO+VC類內(nèi)歐式距離平均數(shù)倒數(shù)307.83301.63308.69403.37相關(guān)系數(shù)845.80839.16840.41853.62指數(shù)距離法872.87868.88870.36873.62直接距離歐式距離923.06920.66920.83927.50c=0.3契比雪夫距離973.44972.26971.09978.82海明距離725.13718.87723.32726.91最大最小法1036.031034.731034.081040.57算術(shù)平均最小法1047.351046.201045.381052.09幾何平均最小法2094.952092.652091.002104.48

注：表中數(shù)據(jù)表示該算法中各質(zhì)點(diǎn)與其質(zhì)心的相關(guān)性之和，數(shù)據(jù)越大，表示該算法中質(zhì)點(diǎn)間越集中，聚類效果優(yōu)。

5 結(jié) 語(yǔ)

提出了一種基于粒子群優(yōu)化的頂點(diǎn)著色聚類算法，在標(biāo)準(zhǔn)粒子群的基礎(chǔ)上，根據(jù)3個(gè)參數(shù)選取對(duì)聚類效果的影響，修改了這3個(gè)的參數(shù)值，并且利用該算法識(shí)別出阿爾茲海默病(AD)候選基因。試驗(yàn)結(jié)果表明，該算法提高了聚類效果，以及識(shí)別出的某些候選基因具有一定的合理性。但筆者的研究是直接給出了頂點(diǎn)著色聚類的閾值，沒有分析閾值的改變而影響聚類效果和試驗(yàn)結(jié)果，今后將繼續(xù)研究閾值的最佳選取，以提高聚類效果。

[1]紀(jì)震，廖惠連，吳青華.粒子群算法及應(yīng)用[M].北京: 科學(xué)出版社,2009.

[2] 高尚，楊靜宇.群智能算法及其應(yīng)用[M].北京: 中國(guó)水利水電出版社,2006.

[3] 聞朝中，李智.粒子群算法在配電網(wǎng)絡(luò)無(wú)功補(bǔ)償優(yōu)化中的應(yīng)用[J].武漢工業(yè)學(xué)院學(xué)報(bào), 2004,23(1): 18-21.

[4] 王海英，黃強(qiáng)，李傳濤,等.圖論算法及其MATLAB實(shí)現(xiàn)[M].北京: 北京航空航天大學(xué)出版社, 2010.

[5] 陳貴敏，賈建援，韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究[J].西安交通大學(xué)學(xué)報(bào), 2006,40(1): 53-56.

[6] 徐生兵，夏文杰，代安定.一種改進(jìn)學(xué)習(xí)因子的粒子群算法[J].信息安全, 2012,(7):17-19.

[7] 曲福恒，崔廣才，李巖芳,等.模糊聚類算法及應(yīng)用[ ].北京: 國(guó)防工業(yè)出版社, 2011.

[8] NCBI, A D gene expression level.2007.URL: http://www.ncbi.nlm.nih.gov/geoprofiles/.

[9] Burgos-Ramos E,et al.Somatostatin and Alzheimer’s disease[J].Molecular and cellular endocrinology, 2008,286(1): 104-111.

[10]Frenkel D,et al.Nasal vaccination with a proteosome-based adjuvant and glatiramer acetate clears β-amyloid in a mouse model of Alzheimer disease[J].Journal of Clinical Investigation, 2005,115(9): 2423-2433.

TP311.1

A

1673-1409(2013)31-0061-05

[編輯] 洪云飛