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

丁 輝 胡 芬

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

2013-09-10

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

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

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

丁 輝 胡 芬

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

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

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

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

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

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

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

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

1.1基本粒子群算法

(1)

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

由式(1)組成的PSO算法成為標準粒子群優(yōu)化算法。另外可以通過給出粒子的速度和位置限定范圍來限制粒子的移動，以達到對算法較好控制:

(2)

1.2慣性因子的改進

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

(3)

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

1.3學(xué)習因子的改進

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

(4)

2 頂點著色算法

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

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

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

3 聚類算法設(shè)計

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

基于粒子群優(yōu)化算法的頂點著色算法是在使用一種距離作為相似性度量的基礎(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個類，Zm代表Gm中的元素個數(shù)，則類Gm的聚類中心Cm=(cm1,cm2,…,cmD)可以表示為：

(5)

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

(6)

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

(7)

3.2頂點著色操作

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

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

(8)

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

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

3.3聚類算法

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

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

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

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

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

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

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

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

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

4 算法試驗與分析

4.1數(shù)據(jù)來源

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

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

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

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

表2 識別候選基因表

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

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

4.3試驗結(jié)果

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

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

4.4算法分析

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

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

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

指標算法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ì)點與其質(zhì)心的相關(guān)性之和，數(shù)據(jù)越大，表示該算法中質(zhì)點間越集中，聚類效果優(yōu)。

5 結(jié) 語

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

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

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

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

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

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

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

[7] 曲福恒，崔廣才，李巖芳,等.模糊聚類算法及應(yīng)用[ ].北京: 國防工業(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

[編輯] 洪云飛