杜洪波，白阿珍，朱立軍

(1.沈陽(yáng)工業(yè)大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110870； 2.北方民族大學(xué) 信息與計(jì)算科學(xué)學(xué)院，寧夏 銀川 750021)

微陣列數(shù)據(jù)的顯著特點(diǎn)是樣本小、基因的維數(shù)大、高噪聲[1]，并且存在基因選擇難的問(wèn)題。為了解決此問(wèn)題,多種方法已經(jīng)被運(yùn)用來(lái)處理微陣列數(shù)據(jù)，譬如，聚類算法[2]、基因選擇方法[3]、分類算法[4]。

聚類算法是研究基因之間的相互關(guān)系的最基本的手段[1]。聚類能夠?qū)⒐δ芟嗨频幕蚓鄢梢活?，并且按照聚類的結(jié)果，預(yù)測(cè)未知的基因功能，尋找基因之間的調(diào)控關(guān)系和發(fā)現(xiàn)共同的模式[5]。由于基因芯片中含有大量的冗余的基因，對(duì)基因進(jìn)行分類之前非常有必要對(duì)其進(jìn)行去冗余工作，而基因選擇方法就是一種合適的選擇方法。

綜上討論，對(duì)基因微陣列運(yùn)用改進(jìn)的K-means融合PSO算法進(jìn)行基因選擇問(wèn)題的研究。首先，運(yùn)用過(guò)濾法Relief對(duì)基因進(jìn)行篩選；然后，利用改進(jìn)的K-means算法進(jìn)行分類，并利用PSO尋優(yōu)；最后，訓(xùn)練SVM，并評(píng)價(jià)獲得的最優(yōu)特征基因子集的質(zhì)量。提出的 “改進(jìn)的K-means算法融合微粒群優(yōu)化算法”簡(jiǎn)稱為“IK-PSO算法”。

1 相關(guān)算法

1.1 改進(jìn)的DPC算法

DPC是2014年由Alex Rodriguez和Alessandro Laio提出來(lái)的一種基于密度的新的聚類算法[6]。DPC算法的思想是：聚類中心往往是由一些局部密度較低的數(shù)據(jù)對(duì)象所包圍，并且與任何具有較高局部密度的其它的數(shù)據(jù)對(duì)象之間的距離都相對(duì)較大。

在DPC算法中，局部密度ρi和距離δi的計(jì)算依賴于截?cái)嗑嚯xdc，而DPC中的截?cái)嗑嚯xdc是通過(guò)人工設(shè)置的，屬于人工經(jīng)驗(yàn)的方法，雖然，截?cái)嗑嚯xdc的選擇具有魯棒性，但是，仍然缺少理論依據(jù)。因此，運(yùn)用文獻(xiàn)[7]中的選取截?cái)嗑嚯x的方法來(lái)對(duì)DPC進(jìn)行改進(jìn)。

對(duì)于數(shù)據(jù)對(duì)象i計(jì)算與其余各數(shù)據(jù)對(duì)象之間的賦權(quán)歐氏距離dij(i,j=1,2,…,n;i≠j)，從而得到向量li={di1,di2,…,din}，接著將li進(jìn)行升序排序進(jìn)而得到向量ci=sort(li)={ai1,ai2,…,ain}，再將ci中的兩兩相鄰的元素進(jìn)行做差運(yùn)算，并根據(jù)下列公式得到數(shù)據(jù)對(duì)象i的截?cái)嗑嚯xdci為

dci=aij|max(ai(j+1)-aij)

(1)

式中，max(ai(j+1)-aij)是向量ci中相鄰的兩個(gè)元素之差的最大值。

對(duì)于每一個(gè)數(shù)據(jù)對(duì)象i都有一個(gè)截?cái)嗑嚯xdci，因此，這些截?cái)嗑嚯x就可以構(gòu)成一個(gè)集合Dc={dc1,dc2,…,dcn}，而要選擇的最優(yōu)截?cái)嗑嚯xdc=min(Dc)。

這種改進(jìn)的方法為截?cái)嗑嚯xdc的選擇提供了依據(jù)，而且容易實(shí)現(xiàn)、算法簡(jiǎn)單。

1.2 K-means算法

K-means算法[8]是以K為參數(shù)，將數(shù)據(jù)集對(duì)象分成K個(gè)簇，使得簇內(nèi)的相似度盡可能較高，而簇間的相似度盡可能較低，其相似度是根據(jù)數(shù)據(jù)對(duì)象與一個(gè)簇中所有對(duì)象的平均值(即聚類中心)之間的距離來(lái)進(jìn)行度量的。

K-means的目標(biāo)函數(shù)為

(2)

式中，E是數(shù)據(jù)集中的所有數(shù)據(jù)對(duì)象的平方誤差總和；p是數(shù)據(jù)集中的數(shù)據(jù)對(duì)象；mi是類簇Ci的中心。

K-means算法描述如下：

輸入：包含n個(gè)對(duì)象的數(shù)據(jù)集和簇的數(shù)目K。

輸出：滿足目標(biāo)函數(shù)最小值的K個(gè)簇。

Step1：從n個(gè)數(shù)據(jù)對(duì)象中隨機(jī)地選擇K個(gè)對(duì)象作為初始聚類中心；

Step2：對(duì)剩余對(duì)象，根據(jù)它與聚類中心的距離，并根據(jù)最小距離原則將其指派到相應(yīng)的類簇中進(jìn)行劃分；

Step3：計(jì)算每個(gè)類簇的新的均值，即新的類簇中心；

Step4：回到Step2，循環(huán)，直到聚類中心不再發(fā)生變化。

1.3 基于改進(jìn)的DPC算法的K-means算法

針對(duì)K-means需要人為地確定聚類個(gè)數(shù)，隨機(jī)地選擇初始聚類中心進(jìn)行迭代從而導(dǎo)致不穩(wěn)定的聚類結(jié)果的缺陷，可以通過(guò)改進(jìn)的DPC來(lái)自動(dòng)確定聚類數(shù)目以及選取聚類中心作為K-means的初始聚類中心，接著運(yùn)用K-means算法進(jìn)行迭代。而在基于改進(jìn)的DPC算法的K-means算法中改進(jìn)的DPC是利用文獻(xiàn)[7]中介紹的方法來(lái)選擇最優(yōu)截?cái)嗑嚯xdc。此外，利用賦權(quán)歐氏距離[9]來(lái)更準(zhǔn)確地規(guī)范各對(duì)象的差異程度，從而更好地聚類。

改進(jìn)的K-means算法具體描述：

輸入：含有n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集合。

輸出：滿足目標(biāo)函數(shù)最小值的K個(gè)簇。

Step1：運(yùn)用熵值法來(lái)計(jì)算各個(gè)數(shù)據(jù)對(duì)象之間的賦權(quán)歐氏距離dij，并令dij=dji,i

Step2：確定截?cái)嗑嚯xdc；

Step3：根據(jù)確定的截?cái)嗑嚯xdc，并利用DPC算法中的方法計(jì)算每個(gè)數(shù)據(jù)對(duì)象i的ρi和δi；

Step4：根據(jù)γi=ρi×δi(i=1,2,…,n),γi的值越大，則i就越有可能是聚類的中心；

Step5：確定聚類中心cj(j=1,2,…,K)與K的值；

Step6：計(jì)算剩余每個(gè)數(shù)據(jù)對(duì)象與各類簇的中心的距離，并將每個(gè)數(shù)據(jù)對(duì)象分類給距其最近的類簇中，從而達(dá)到劃分的目的；

Step7：重新計(jì)算每個(gè)新簇的均值作為新的類簇中心；

Step8：計(jì)算目標(biāo)函數(shù)值；

Step9：直到目標(biāo)函數(shù)不再發(fā)生任何的變化，算法終止；否則，轉(zhuǎn)Step7。

1.4 PSO算法

PSO算法[10](微粒群優(yōu)化算法)的思想來(lái)源于對(duì)鳥(niǎo)群捕食行為的研究，它是模擬鳥(niǎo)集群飛行覓食的行為，鳥(niǎo)之間通過(guò)集體的協(xié)作從而使群體達(dá)到最優(yōu)目的。PSO隨機(jī)初始化粒子，并且粒子的速度根據(jù)它本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)進(jìn)行動(dòng)態(tài)的調(diào)整，而粒子的速度和位置按照以下的方程式進(jìn)行迭代：

vid=ωvid+c1r1(pid-xid)+c2r2(pgd-xgd)

(3)

xid=xid+vid

(4)

式中，ω是慣性權(quán)重值；c1,c2為正常數(shù)，稱為加速系數(shù)；r1,r2分別是[0,1]范圍內(nèi)變化的隨機(jī)常數(shù)。

2 IK-PSO算法

因?yàn)槲㈥嚵芯哂懈呔S、小樣本的特點(diǎn)，如果僅使用PSO算法隨機(jī)地搜索最優(yōu)特征基因子集，無(wú)疑則會(huì)增加搜索的難度，從而降低搜索能力。因此，提出IK-PSO來(lái)對(duì)基因進(jìn)行選擇。首先，對(duì)于數(shù)據(jù)集未劃分成訓(xùn)練集和測(cè)試集的則利用bootstrap法將其劃分成訓(xùn)練集和測(cè)試集；接著，在訓(xùn)練集上運(yùn)用過(guò)濾法Relief對(duì)基因進(jìn)行初步篩選，選擇出對(duì)分類貢獻(xiàn)大的基因從而構(gòu)成備選基因子集；然后，利用改進(jìn)的K-means聚類算法將基因劃分成一定數(shù)量的簇，并運(yùn)用PSO對(duì)每一類簇進(jìn)行搜索選擇出相應(yīng)類簇中的最優(yōu)基因構(gòu)成最優(yōu)特征基因子集，在選擇基因時(shí)，只選擇最優(yōu)的基因可能會(huì)丟掉原本數(shù)據(jù)集中一些相對(duì)重要的基因，因此，除了要找出不同類簇中最優(yōu)的基因外，相應(yīng)的也要找到相對(duì)應(yīng)類簇中的次重要的基因，從而構(gòu)成最優(yōu)特征基因子集；最后，針對(duì)前面選擇的最優(yōu)特征基因子集來(lái)訓(xùn)練SVM，并利用其分類的性能來(lái)評(píng)價(jià)得到的最優(yōu)特征基因子集的質(zhì)量。

IK-PSO算法具體步驟如下：

Step1：利用bootstrap將微陣列數(shù)據(jù)劃分成訓(xùn)練集與測(cè)試集；

Step2：運(yùn)用過(guò)濾法Relief對(duì)基因進(jìn)行篩選，篩選出對(duì)分類貢獻(xiàn)相對(duì)較大的基因構(gòu)成備選基因子集；

Step3：在訓(xùn)練集中，對(duì)在Step2中篩選出的備選基因運(yùn)用改進(jìn)的K-means算法進(jìn)行聚類，從而，得到聚類數(shù)K和聚類分類；

Step4：對(duì)于Step3產(chǎn)生的類簇中未進(jìn)行PSO尋優(yōu)的一類簇將其看作粒子群，則粒子群的長(zhǎng)度由相應(yīng)簇中的基因決定；

Step5：將Step4中的粒子群進(jìn)行速度和位置的初始化；

Step6：計(jì)算每個(gè)粒子的適應(yīng)度；

Step7：根據(jù)適應(yīng)度更新pbest和gbest；

Step8：根據(jù)PSO更新每個(gè)粒子的位置、速度；

Step9：如果達(dá)到最大的迭代次數(shù)則算法終止，否則轉(zhuǎn)到Step5；

Step10：如果Step9后算法終止，從得到的結(jié)果中選擇最優(yōu)基因和次優(yōu)基因，并將其加入最優(yōu)特征基因子集O中；

Step11：若無(wú)類簇未進(jìn)行PSO尋優(yōu)，則算法終止，否則轉(zhuǎn)到Step4；

Step12：利用集合O訓(xùn)練分類器SVM，從而利用其分類的精確率來(lái)評(píng)價(jià)選擇的最優(yōu)特征基因的分類性能。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

利用典型的、公開(kāi)的小樣本，高維微陣列數(shù)據(jù)集結(jié)腸癌數(shù)據(jù)集(Colon)和結(jié)腸癌數(shù)據(jù)集(Leukemia)來(lái)進(jìn)行IK-PSO算法的測(cè)試。有關(guān)這兩個(gè)微陣列數(shù)據(jù)集的信息如表1所示。

表1 兩個(gè)微陣列數(shù)據(jù)集的相關(guān)信息

其中，Colon數(shù)據(jù)集最初是由Alon等分析的結(jié)腸癌數(shù)據(jù)集[11]，其包含了62個(gè)樣本的數(shù)據(jù)，22個(gè)正常的組織(positive)以及40個(gè)的腫瘤組織(negative)，并且，每個(gè)樣本的2 000個(gè)基因都是從其含有的6 500個(gè)基因中初選得來(lái)的。而Leukemia是由Golub等在1999年公布的急性白血病數(shù)據(jù)集[12]，此數(shù)據(jù)集總共包括72個(gè)樣本，而每個(gè)樣本均含有7 129個(gè)基因的數(shù)據(jù)表達(dá)。并且，其中25個(gè)為急性骨髓性白血病(Acute Myeloid Leukemia,AML)，47個(gè)為急性淋巴性白血病(Acute Lymphoblastic Leukemia,ALL)。在試驗(yàn)的過(guò)程中將這些樣本隨機(jī)地劃分成34個(gè)測(cè)試集和38個(gè)訓(xùn)練集。

3.2 實(shí)驗(yàn)結(jié)果

IK-PSO在數(shù)據(jù)Colon、Leukemia上的分類精確率如表2所示。

表2 IK-PSO的分類精確率

3.3 與F+SVMRFE、F+SVMDEA等算法的比較

為了說(shuō)明IK-PSO的適用性，將IK-PSO與F+SVMRFE、F+SVMDEA等算法進(jìn)行了比較，所選擇的基本都是以Filter為基礎(chǔ)，進(jìn)行基因預(yù)選的算法。比較結(jié)果如表3、圖1所示。

表3 算法精確率的比較結(jié)果

圖1 不同數(shù)據(jù)集不同算法的分類準(zhǔn)確率對(duì)比

根據(jù)表3，可以看出在Colon中，IK-PSO除了相對(duì)于最大相關(guān)最小冗余算法的精確率稍有所提高外，而相對(duì)于其余的幾種算法的分類精確率顯著提高，而在Leukemia上，IK-PSO的分類精確率相較于R+PSO、最大相關(guān)最小冗余外，而相對(duì)于其余的三種算法均有所提高。綜上所述，提出的IK-PSO算法能夠有效地選擇出數(shù)據(jù)集的最優(yōu)特征基因子集，進(jìn)而獲得較高的分類精確率。

4 結(jié) 語(yǔ)

為了解決高維、小樣本的基因數(shù)據(jù)集的基因選擇困難的問(wèn)題，提出IK-PSO來(lái)對(duì)基因進(jìn)行選擇，其結(jié)合了篩選、聚類以及PSO尋優(yōu)的性能，并在兩個(gè)經(jīng)典的癌癥數(shù)據(jù)集上進(jìn)行了驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，將本算法應(yīng)用到基因微陣列的基因選擇中能夠選擇出有效的基因子集進(jìn)而提高分類的精確率。

[1] 楊善秀,韓 飛,關(guān) 健.基于聚類和微粒群優(yōu)化的基因選擇新方法[J].計(jì)算機(jī)應(yīng)用,2013,05:1285-1288.

[2] VARMA S,SIMON R.Iterative class discovery and feature selection using minimal spanning trees[J].BMC Bioinformatics,2004,5:126.

[3] YAO F Z,COQUERY J,CAO K A L.Independent principal component analysis for biologically meaningful dimension reduction of large biological data sets [J].BMC Bioinformatics,2012,13(1):1-15.

[4] 于化龍,顧國(guó)昌,劉海波,等.基于相關(guān)性分析的微陣列數(shù)據(jù)集成分類研究[J].計(jì)算機(jī)研究與發(fā)展,2010,02:328-335.

[5] RANA S,JASOLA S,KUMAR R.A hybrid sequential approach for data clustering using K-means and particle swarm optimization algorithm[J].International Journal of Engineering,Science and Technology,2010,2(6)：167-176.

[6] RODRIGUEZ A，LAIO A.Rodriguez ， A.Laio.Clustering by fast search and find of density peaks[J].Science,2014,344(6191)：1492-1496.

[7] 雙翼帆,顧幸生.基于改進(jìn)的快速搜索聚類算法和高斯過(guò)程回歸的催化重整脫氯前氫氣純度多模型建模方法[J].化工報(bào),2016,03:765-772.

[8] 陳磊磊.不同距離測(cè)度的K-Means文本聚類研究[J].軟件,2015,36(01):56-61.

[9] 盛 華,張桂珠.一種融合K-means和快速密度峰值搜索算法的聚類方法[J].計(jì)算機(jī)應(yīng)用與軟件,2016,10:260-264，269.

[10]杜洪波,董文娟.Relief-PSO混合算法在基因微陣列特征選擇中的應(yīng)用[J].沈陽(yáng)工程學(xué)院學(xué)報(bào)：自然科學(xué)版,2016,12(03):267-271.

[11]ALON U,BARKAI N,NOTTERMAN D A,et al.Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays[J].Proceedings of the National Academy of Sciences USA,1999,96(12):6745-6750.

[12]GOLUB T R,SLONIM D K,TAMAYO P,et al.Molecular classification of cancer：Class discovery and class prediction by gene expression monitoring[J].Science,1999,286 (5439):531-536.