馬越 劉成忠

摘 ?要： 針對(duì)基因微陣列數(shù)據(jù)具有維數(shù)高、樣本小、冗余高的特點(diǎn)，為了提高基因分類算法的性能，提出一種基于灰狼優(yōu)化和支持向量機(jī)的分類算法。該算法使用主成分分析法進(jìn)行數(shù)據(jù)降維，選取15個(gè)相關(guān)系數(shù)最大的基因探針，利用改進(jìn)的灰狼優(yōu)化算法對(duì)支持向量機(jī)的獎(jiǎng)罰因子C與核寬度σ進(jìn)行參數(shù)尋優(yōu)，并在2組公開的癌癥微陣列數(shù)據(jù)上進(jìn)行試驗(yàn)。實(shí)驗(yàn)的準(zhǔn)確率分別為95.24%和 94.00%，通過與其它算法進(jìn)行性能對(duì)比，該算法具有高效、精準(zhǔn)的分類能力，對(duì)臨床醫(yī)學(xué)應(yīng)用有極為重要的參考意義。

關(guān)鍵詞： 基因微陣列;基因分類;主成分分析法;支持向量機(jī);灰狼優(yōu)化算法

中圖分類號(hào)： TP18 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.06.002

本文著錄格式：馬越，劉成忠. 一種改進(jìn)的基因微陣列數(shù)據(jù)分類算法[J]. 軟件，2020，41（06）：0711+31

【Abstract】： In order to improve the performance of classification algorithm， a classification algorithm based on Grey Wolf Optimizer （GWO） and Support Vector Machine （SVM） is proposed for the high dimension， small sample and high redundancy of gene microarray data. In this algorithm， Principal Component Analysis （PCA） was used to select 15 gene probes with the largest correlation coefficient. Then， the improved gray Wolf optimization algorithm was used to optimize the parameters of reward and punishment factor C and kernel width of SVM， and two groups of cancer microarray data were tested. The accuracy of the experimental results was 95.24% and 94.00%， respectively. Compared with other algorithms， this algorithm has the ability of efficient and accurate classification， which is of great reference significance for clinical medicine application.

【Key words】： Gene microarray; Genetic classification; Principal component analysis; Support vector machine; Grey wolf optimization algorithm

0 ?引言

各種癌癥及惡性腫瘤一直威脅著人類的生命健康，但是患病早期并不容易被查出，所以為各種疾病提供一種高效、準(zhǔn)確的診斷方法，可以讓患者及時(shí)接受治療，或許可以挽救患者生命。隨著基因微陣列技術(shù)的成熟，基因表達(dá)譜可以表示人類各個(gè)組織的正?；?，而且由于大量患者的貢獻(xiàn)，很多重大疾病的基因微陣列數(shù)據(jù)也已經(jīng)被共享，為基因分類與識(shí)別提供了大量的可靠數(shù)據(jù)。文獻(xiàn)[1-4]眾位支持向量機(jī)算法做了諸多研究，傅德勝[5]等人對(duì)PCA降維算法做了詳細(xì)介紹和研究。文獻(xiàn)[6-8]眾位研究人員對(duì)癌癥基因微陣列進(jìn)行了特征選擇，得到了低維可分的數(shù)據(jù)集。Chiaretti [9]等對(duì)白血病基因微陣列數(shù)據(jù)集的分類進(jìn)行了研究，并應(yīng)用到臨床治療和預(yù)測(cè)之中;Sun[10] 等在肺癌臨床治療中通過對(duì)肺癌微陣列數(shù)據(jù)特征分類從而做出預(yù)判;van t Veer LJ[11]等人對(duì)乳腺癌微陣列數(shù)據(jù)進(jìn)行了特征分類與預(yù)測(cè)。文獻(xiàn)[12-13]對(duì)灰狼算法進(jìn)行了詳細(xì)介紹。Xianhai Song[14]等人將灰狼優(yōu)化算法（Grey Wolf Op-timizer，GWO）與重力搜索算法（GSA）、遺傳算法（GA）、粒子群優(yōu)化算法（PSOGSA）和梯度算法做了相關(guān)比較，指出了灰狼優(yōu)化算法的魯棒性較強(qiáng)且收斂速度極快，所以適用于優(yōu)化支持向量機(jī)的獎(jiǎng)罰因子C與核寬度。蔡立軍[15]等人及葉明全[16]等人都使用蟻群算法對(duì)基因分類算法進(jìn)行優(yōu)化，準(zhǔn)確率接近90%。陶國(guó)嬌[17]提出了一種優(yōu)化群智能算法的方法，可以提高算法尋優(yōu)精度，趙乃剛[18]和曹盟盟[19]等人都對(duì)粒子群算法做了優(yōu)化和改進(jìn)，使得其優(yōu)化能力得到了進(jìn)一步提升。靳艷虹[20]做了基于粒子群算法的基因表達(dá)數(shù)據(jù)的研究，使用粒子群算法提升分類準(zhǔn)確率，但是粒子群算法的收斂速度明顯不如灰狼優(yōu)化算法。本文首先使用PCA降維算法對(duì)數(shù)據(jù)集進(jìn)行降維，然后使用基于改進(jìn)灰狼優(yōu)化算法的支持向量機(jī)做分類，提升支持向量機(jī)的分類效果。由于改進(jìn)的灰狼優(yōu)化算法相對(duì)于其他群智能算法，其收斂速度較快，所以在提高分類準(zhǔn)確率的同時(shí)算法時(shí)間復(fù)雜度問題也有所改善。

1 ?主成分分析法

主成分分析法（PCA）是數(shù)據(jù)降維中最常見的線性方法，PCA的目的是從樣本諸多屬性值中找到并保留相關(guān)系數(shù)最大的屬性值，從而達(dá)到降維效果。

將樣本點(diǎn)xi投影到新空間超平面上，并且使得樣本投影盡可能分開，此時(shí)就需要投影的方差最大化。

其主要步驟如下：

（1）計(jì)算樣本對(duì)應(yīng)的協(xié)方差矩陣 ，此時(shí)的協(xié)方差也可以看成相關(guān)系數(shù);

（2）對(duì)矩陣XXT進(jìn)行特征值分解;

（3）降序后取最大的D個(gè)特征值所對(duì)應(yīng)的特征向量，即相關(guān)系數(shù)最大的屬性對(duì)應(yīng)的特征向量;

（4）輸出D維投影矩陣即目標(biāo)矩陣可以用式（1）表示為：

2 ?支持向量機(jī)

經(jīng)過數(shù)據(jù)處理，使用支持向量機(jī)可以對(duì)所選的兩組數(shù)據(jù)集進(jìn)行分類處理。支持向量機(jī)（SVM）結(jié)合了VC維理論和最小化結(jié)構(gòu)風(fēng)險(xiǎn)，SVM分類的中主要依靠支持向量機(jī)，少數(shù)的支持向量決定了最后的結(jié)果，在剔除大量冗余樣本屬性的同時(shí)具有很好的魯棒性，增加或刪除非支持向量樣本對(duì)模型沒有影響，對(duì)于基因微陣列這種維度高，樣本少的數(shù)據(jù)分類極為適用。

其主要思想是將樣本通過核函數(shù)變換后從低維的不可分到高維的可分，找到一個(gè)超平面 將數(shù)據(jù)分成正樣本和負(fù)樣本兩類。最好的分類結(jié)果為距離超平面H最近的正、負(fù)樣本的距離最大，即目標(biāo)函數(shù)為式（2）：

支持向量機(jī)有兩個(gè)重要參數(shù) 和C。如果 太大，高斯分布會(huì)變成細(xì)長(zhǎng)型，只能作用于支持向量樣本附近，造成支持向量機(jī)獨(dú)立分類效果變差，而且容易發(fā)生過擬合。反之，如果 太小，高斯分布會(huì)變成矮寬型，此時(shí)曲線過于平滑，無法在訓(xùn)練集上取得較高的準(zhǔn)確率。系數(shù)C被稱為獎(jiǎng)罰系數(shù)，C的值越高，說明此時(shí)支持向量機(jī)接受誤差能力變差，容易發(fā)生過擬合，但C值太小又容易發(fā)生欠擬合現(xiàn)象，所以選取適合的系數(shù)C和 極其重要。

3 ?灰狼優(yōu)化算法及改進(jìn)

灰狼優(yōu)化算法（GWO）最早是由澳大利亞的學(xué)者M(jìn)irjalili等人在2014年提出的?；依莾?yōu)化算法是在觀察灰狼在狩獵過程中進(jìn)行的一系列規(guī)律活動(dòng)而受到啟發(fā)，形成了一種新型的群智能優(yōu)化算法，該算法具有很強(qiáng)的收斂性，還具有參數(shù)少等特點(diǎn)，可以被應(yīng)用于圖像分類，參數(shù)優(yōu)化等領(lǐng)域.

GWO首先是種群等級(jí)劃分。計(jì)算種群每個(gè)個(gè)體的適應(yīng)度，并根據(jù)灰狼種群適應(yīng)度不同，由高到低將其分為 。如圖1所示。

狼是整個(gè)狼群的領(lǐng)導(dǎo)者，具有最高的適應(yīng)度，是距離最優(yōu)解最近的狼。其次是 狼，他們是僅次與頭狼的等級(jí)，他們負(fù)責(zé)協(xié)助頭狼領(lǐng)導(dǎo)狼群，同時(shí)也是頭狼的候選，最后是 狼，主要是平衡狼群內(nèi)務(wù)關(guān)系和協(xié)助前三種狼。

灰狼優(yōu)化算法把狩獵過程分成包圍，追捕及攻擊三個(gè)步驟，目標(biāo)為獲取獵物，即得到全局最優(yōu)解。算法實(shí)現(xiàn)如下：

圖3中直線，短虛線，長(zhǎng)虛線分別為粒子群算法，傳統(tǒng)灰狼優(yōu)化算法，改進(jìn)后灰狼優(yōu)化算法最優(yōu)適應(yīng)度（最優(yōu)解）變化曲線，顯然，不管從收斂速率還是收斂精度來看，傳統(tǒng)灰狼優(yōu)化算法和改進(jìn)后灰狼優(yōu)化算法都明顯優(yōu)于粒子群算法。在算法前期，改進(jìn)的灰狼優(yōu)化算法相對(duì)于傳統(tǒng)灰狼優(yōu)化算法有優(yōu)勢(shì)但不明顯，算法后期改進(jìn)后的灰狼算法在測(cè)試函數(shù)的測(cè)試下，無論從下降速率（收斂精度）還是從最優(yōu)適應(yīng)度（收斂精度）來看都具有明顯優(yōu)勢(shì)，所以此次對(duì)灰狼算法的優(yōu)化是極有意義的。

4 ?仿真實(shí)驗(yàn)

4.1 ?數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

本文使用的數(shù)據(jù)集I為多發(fā)性骨腫瘤樣本，包括173個(gè)樣本，通過Affymetrix U95Av2微陣列獲得122625個(gè)基因的表達(dá)譜。保存在美國(guó)生物技術(shù)信息中心（http：//www.ncbi.nlm.nih.gov/geo/）編號(hào)GSE755。使用的數(shù)據(jù)集Ⅱ?yàn)榉伟颖?，包?81個(gè)樣本，cRNA與人類U95A寡核苷酸探針陣列（Affymetrix， Santa Clara， CA）雜交，獲得12533個(gè)基因的表達(dá)譜?；蛭㈥嚵袛?shù)據(jù)可以在網(wǎng)址http：//www.chestsurg.org.中獲取。

4.2 ?實(shí)驗(yàn)結(jié)果分析

經(jīng)過數(shù)據(jù)預(yù)處理后，將數(shù)據(jù)分為訓(xùn)練集和測(cè)試集，數(shù)據(jù)集I（多發(fā)性骨腫瘤數(shù)據(jù)集）的訓(xùn)練集為131個(gè)樣本，包括103例正常，28例多發(fā)性骨腫瘤患者，測(cè)試集42個(gè)樣本，包括34例正常，8例多發(fā)性骨腫瘤患者。數(shù)據(jù)集Ⅱ（肺癌數(shù)據(jù)集）的訓(xùn)練集為131例肺癌患者，109例正?；蚪M，22例肺癌患者，測(cè)試集50個(gè)樣本，包括41例正常基因組，9例肺癌患者。使用SVM對(duì)其進(jìn)行分類，選用3折交叉驗(yàn)證（3-fold cross-validation），將訓(xùn)練集隨機(jī)分成3份，3次訓(xùn)練中每次選用2份做訓(xùn)練集，另外1份做測(cè)試集，并使用參數(shù)優(yōu)化算法對(duì)SVM參數(shù)σ和C進(jìn)行優(yōu)化，參數(shù)優(yōu)化算法有很多，其中最簡(jiǎn)單是網(wǎng)格搜索法（Grid Search），奉國(guó)和[22]介紹了使用網(wǎng)格搜索法在尋找支持向量機(jī)局部最優(yōu)參數(shù)σ和C時(shí)，具有節(jié)約時(shí)間開銷等優(yōu)點(diǎn)。使用粒子群優(yōu)化算法，傳統(tǒng)灰狼優(yōu)化算法和改進(jìn)的灰狼優(yōu)化算法也可以搜索最佳系數(shù)σ和C，在訓(xùn)練支持向量機(jī)的過程中，計(jì)算3次分類準(zhǔn)確率的平均值作為適應(yīng)度。經(jīng)過200次迭代，得到以下結(jié)果見表2。

由上表可知，通過網(wǎng)格搜索和其他3種群智能優(yōu)化算法都可以對(duì)支持向量機(jī)的參數(shù)進(jìn)行優(yōu)化，但是灰狼算法隨機(jī)概率搜索算法，而網(wǎng)格搜索法是一種指定范圍的窮舉搜索法，所以在準(zhǔn)確率方面3種群智能優(yōu)化算法是優(yōu)于網(wǎng)格搜索法的。群智能算法的時(shí)間復(fù)雜度高于網(wǎng)格搜索，但是相較與粒子群算法和傳統(tǒng)灰狼算法，改進(jìn)后的灰狼優(yōu)化在時(shí)間復(fù)雜度方面有了穩(wěn)定改善，且在第二組數(shù)據(jù)中，準(zhǔn)確率也有了提升。與其他文獻(xiàn)對(duì)比見表3。

由表3可知，通過對(duì)灰狼優(yōu)化算法的收斂因子和邊界進(jìn)行優(yōu)化，本次實(shí)驗(yàn)的準(zhǔn)確率高于游偉[23]提出的SVM-RFE-SFS和高振斌[24]提出的LS-SVM。所以結(jié)合準(zhǔn)確率和時(shí)間復(fù)雜度來看，本次實(shí)驗(yàn)所提出的算法對(duì)基因微陣列數(shù)據(jù)更好的分類能力。

5 ?結(jié)束語(yǔ)

本文提出了一種基于改進(jìn)灰狼優(yōu)化的支持向量機(jī)，使用該方法對(duì)PCA降維后的多基因微陣列數(shù)據(jù)進(jìn)行分類，并使用獨(dú)立測(cè)試方法獲得分類準(zhǔn)確率。通過與使用網(wǎng)格搜索優(yōu)化，粒子群優(yōu)化，傳統(tǒng)GWO優(yōu)化的SVM及其他文獻(xiàn)提出的算法進(jìn)行性能對(duì)比，可以得出該算法準(zhǔn)確率（95.24%和94.00%）高于 ? 其它算法，而且相較于粒子群優(yōu)化算法和灰狼優(yōu)化 ?算法，本文提出的灰狼優(yōu)化算法在時(shí)間復(fù)雜度方面 ?有了明顯改善，對(duì)臨床醫(yī)學(xué)應(yīng)用有極為重要的參考 ?意義。

此次研究對(duì)灰狼優(yōu)化算法的改進(jìn)還存在一些不足，可以結(jié)合各個(gè)狼群的適應(yīng)度，對(duì)狼的位置更新公式進(jìn)行加權(quán)，或許可以再次提高算法的效率，今后可以對(duì)此方向進(jìn)行深入研究。

參考文獻(xiàn)

[1] 陳海紅. 多核SVM文本分類研究[J]. 軟件， 2015， 36（5）： 7-10.

[2] 孫鵬， 馮翔. 一種基于集成學(xué)習(xí)的健壯性半監(jiān)督 SVM [J]. 軟件， 2018， 39（11）： 182-186.

[3] 陳東. 癌癥基因微陣列分類方法的研究[D]. 長(zhǎng)沙： 湖南大學(xué)， 2012.

[4] 蘇志同， 周文龍. 基于SVM 的心律失常的研究和分析[J]. 軟件， 2015， 36（9）： 98-100.

[5] 傅德勝， 經(jīng)正俊. 基于PCA-LDA 和KNN-SMO 的數(shù)據(jù)碎片分類識(shí)別算法[J]. 軟件， 2015， 36（7）： 21-25.

[6] YU L， LIU H. Feature selection for high-dimensional data： a fast correlation-based filter solution[M]// feature selection for high-dimensional data. Springer Publishing Company， Incorporated， 2003： 207.

[7] LIU Y. Wavelet feature extraction for high-dimensional microarray data[J]. Neurocomputing， 2009， 72（4-6）： 985-990.

[8] 吳辰文， 王偉. 一種結(jié)合隨機(jī)森林和鄰域粗糙集的特征選擇方法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2017， 38（06）： 1358-1362.

[9] Chiaretti， S. Gene expression profile of adult T-cell acute lymphocytic leukemia identifies distinct subsets of patients with different response to therapy and survival[J]. Blood， 2004， 103（7）： 2771-2778.

[10] SUN Z， Yang. Gene expression profiling on lung cancer outcome prediction： Present clinical value and future premise[J]. Cancer Epidemiology Biomarkers & Prevention， 15（11）： 2063-2068.

[11] van 't Veer Laura J， Dai Hongyue， van de Vijver Marc J， et al.?Gene expression profiling predicts clinical outcome of breast cancer[J]. Nature， 2002， 415（6871）.

[12] Mirjalili， Seyedali， Mirjalili， et al. Grey Wolf Optimizer[J]. Advances in Engineering Software， 69： 46-61.

[13] 張悅， 孫惠香， 魏政磊. 具有自適應(yīng)調(diào)整策略的混沌灰狼優(yōu)化算法[J]. 計(jì)算機(jī)科學(xué)， 2017， 44（S2）： 119-122+159.

[14] SONG X， TANG L， ZHAO S， et al. Grey Wolf Optimizer for parameter estimation in surface waves[J]. Soil Dynamics and Earthquake Engineering， 2015， 75： 147-157.

[15] 蔡立軍， 蔣林波， 易葉青. 基于蟻群優(yōu)化算法的基因選擇[J]. 計(jì)算機(jī)應(yīng)用研究， 2008（09）： 2754-2757.

[16] 葉明全， 高凌云， 萬春圓. 基于人工蜂群和SVM的基因表達(dá)數(shù)據(jù)分類[J]. 山東大學(xué)學(xué)報(bào)（工學(xué)版）， 2018， 48（03）： 10-16.

[17] 陶國(guó)嬌， 李智. 帶認(rèn)知因子的交叉鴿群算法[J]. 四川大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 55（02）： 295-300.

[18] 趙乃剛. 慣性權(quán)重動(dòng)態(tài)調(diào)整的混沌粒子群算法[J]. 軟件， 2016， 37（3）： 01-03.

[19] 曹盟盟， 姚文斌. 基于改進(jìn)粒子群算法的虛擬機(jī)放置算法[J]. 軟件， 2015， 36（12）： 89-92

[20] 靳艷虹. 基于PSO的基因表達(dá)數(shù)據(jù)聚類研究[D]長(zhǎng)沙： 中南大學(xué)， 2013.

[21] 林星， 馮斌， 孫俊. 基于邊界變異的量子粒子群優(yōu)化算法[J]. 計(jì)算機(jī)工程， 2008（12）： 187-188+191.

[22] 奉國(guó)和. SVM分類核函數(shù)及參數(shù)選擇比較[J]. 計(jì)算機(jī)工程與應(yīng)用， 2011， 47（03）： 123-124+128.

[23] 游偉， 李樹濤， 譚明奎. 基于SVM-RFE-SFS的基因選擇方法[J]. 中國(guó)生物醫(yī)學(xué)工程學(xué)報(bào)， 2010， 29（01）： 93-99.

[24] 高振斌. 基于最小二乘支持向量機(jī)微陣列基因特征分類[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2019， 36（08）： 288-292.