一種基于粒子群優化的頂點著色聚類算法及其應用

丁 輝 胡 芬

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

2013-09-10

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

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

一種基于粒子群優化的頂點著色聚類算法及其應用

丁 輝 胡 芬

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

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

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

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

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

應用圖論的原理可以將基因聚類問題轉化為對圖的頂點著色問題。類內的基因數據擁有同一種顏色，類間的基因數據擁有不同顏色[4]。因此，基因聚類問題轉化為圖論中的頂點著色問題，聚類基因類的個數就是頂點著色的最少顏色數。在聚類的過程中，可能出現一個基因為一個類，這樣的基因稱為孤立點基因。

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

1 粒子群優化算法

1.1基本粒子群算法

(1)

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

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

(2)

1.2慣性因子的改進

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

(3)

式中，t為迭代次數；T為總迭代次數。

1.3學習因子的改進

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

(4)

2 頂點著色算法

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

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

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

3 聚類算法設計

3.1適應度函數的選取

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

(5)

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

(6)

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

(7)

3.2頂點著色操作

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

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

(8)

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

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

3.3聚類算法

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

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

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

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

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

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

Step6產生一組gbest和聚類中心。

Step7P=P+1,轉Step2。

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

4 算法試驗與分析

4.1數據來源

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

4.2算法參數設置

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

表1 DNA microarray 數據組成結構

表2 識別候選基因表

表3 4種改進參數的聚類算法參數設置

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

4.3試驗結果

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

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

4.4算法分析

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

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

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

指標算法PSO+VCWPSO+VCCPSO+VCMPSO+VC類內歐式距離平均數倒數307.83301.63308.69403.37相關系數845.80839.16840.41853.62指數距離法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算術平均最小法1047.351046.201045.381052.09幾何平均最小法2094.952092.652091.002104.48

注：表中數據表示該算法中各質點與其質心的相關性之和，數據越大，表示該算法中質點間越集中，聚類效果優。

5 結 語

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

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

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

[3] 聞朝中，李智.粒子群算法在配電網絡無功補償優化中的應用[J].武漢工業學院學報, 2004,23(1): 18-21.

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

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

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

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

[編輯] 洪云飛