改進(jìn)GA-SVM在冠狀動(dòng)脈疾病診斷中的應(yīng)用

盧春紅， 顧曉峰

(江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室， 無錫 214122)

冠狀動(dòng)脈疾病(CAD)包含與心臟及心血管系統(tǒng)相關(guān)的一系列疾病，是當(dāng)前世界各國引發(fā)死亡的主要原因之一。據(jù)統(tǒng)計(jì)，西方國家死亡人數(shù)中有30%可歸因于該疾病。CAD的誘發(fā)與環(huán)境、生活習(xí)慣、身體狀況、基因等內(nèi)外因素有關(guān)，不僅治療費(fèi)用昂貴，而且診斷困難，特別是在沒有癥狀顯現(xiàn)的情況下，醫(yī)師僅憑自身專業(yè)知識(shí)及經(jīng)驗(yàn)很難作出正確及時(shí)的診療決策。

隨著計(jì)算機(jī)輔助智能診斷技術(shù)在醫(yī)療領(lǐng)域的應(yīng)用越來越廣泛，研究人員開發(fā)了一些機(jī)器學(xué)習(xí)算法來幫助診斷CAD。例如，Tsipouras等[1]提出了基于模糊規(guī)則的四階段決策系統(tǒng)來診斷CAD，得到了65%的分類精度；Setiwan等[2]提出了一種模糊決策支持系統(tǒng)，可獲得比醫(yī)師單獨(dú)診斷更好的CAD預(yù)測(cè)率。另外，一些基于人工智能的診斷系統(tǒng)也被廣泛用于診斷各種復(fù)雜疾病[3-5]。支持向量機(jī)(SVM)作為一種非常有效的統(tǒng)計(jì)學(xué)習(xí)方法[6]，近年來受到了醫(yī)療界的廣泛關(guān)注[7, 8]。然而，高維的CAD數(shù)據(jù)集增加了計(jì)算復(fù)雜度及過度擬合的風(fēng)險(xiǎn)[9]，同時(shí)SVM的參數(shù)也影響SVM的分類精度。因此，去除高維數(shù)據(jù)集中的不相關(guān)特征以及同步優(yōu)化SVM參數(shù)成為此類智能診斷系統(tǒng)中的一個(gè)重要步驟。

遺傳算法(GA)基于達(dá)爾文自然選擇理論，屬于使用最廣泛的優(yōu)化工具之一。不像其他的啟發(fā)式搜索算法易于局部收斂，GA可在復(fù)雜的搜索空間大概率地找到全局最優(yōu)解，而且對(duì)初始化條件不敏感，GA可應(yīng)用于醫(yī)療決策系統(tǒng)[10-11]。然而，GA不能很好的調(diào)整可行解空間的范圍，而且容易產(chǎn)生過早收斂現(xiàn)象[12]。

本文提出了基于改進(jìn)GA-SVM的CAD診斷方法，自動(dòng)優(yōu)化SVM參數(shù)，同步?jīng)Q策最優(yōu)特征子集，最終改善了醫(yī)療診斷的分類精度。該算法提出新的分組多基因交叉技術(shù)，將杰出染色體分成3個(gè)基因小組，每個(gè)小組保存了更好的基因信息。不像傳統(tǒng)的GA通過交換1對(duì)父輩染色體信息進(jìn)行交叉操作，分組多基因交叉技術(shù)產(chǎn)生攜帶更多基因信息的染色體。最后將改進(jìn)GA-SVM算法與前饋BP神經(jīng)網(wǎng)絡(luò)(BPNN)和Takagi-Sugeno型自適應(yīng)模糊推理系統(tǒng)(ANFIS)進(jìn)行了比較，進(jìn)一步驗(yàn)證了該算法的有效性。

1 支持向量機(jī)

SVM是Vapnik等人在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上提出的一種學(xué)習(xí)方法[6]，擁有強(qiáng)大的泛化能力。設(shè)有N個(gè)訓(xùn)練樣本，每個(gè)輸入樣本的類標(biāo)為yi，則訓(xùn)練集可表示為：{xi,yi},i= 1…N,x∈Rd(d是維數(shù))，yi∈ {-1, 1}。

對(duì)于線性可分的數(shù)據(jù)，存在一個(gè)超平面來分割兩類數(shù)據(jù)。超平面可描述為：

x·w-b=0

(1)

為使該平面能正確分類所有樣本，并具備一定的分類間隔，需滿足下面的約束：

yi(w·xi-b)≥1

(2)

最大化分類間隔，構(gòu)造最優(yōu)超平面，求解下面的約束問題：

(3)

對(duì)于線性不可分的數(shù)據(jù)，在式(3)中增加一個(gè)松弛變量ξi≥0,目標(biāo)函數(shù)變?yōu)椋?/p>

s.t.yi(w·xi-b)≥1-ξi

(4)

其中C為懲罰因子，用來平衡錯(cuò)分樣本數(shù)和最大分類間隔。

引入Lagrange乘子αi> 0，該二次規(guī)劃問題轉(zhuǎn)化為對(duì)偶問題：

(5)

根據(jù)求得的Lagrange乘子，可得到?jīng)Q策函數(shù)：

(6)

對(duì)于線性不可分的數(shù)據(jù)，通過核函數(shù)將低維空間的數(shù)據(jù)變換到高維特征空間，使之成為線性可分，然后在新的空間尋找最優(yōu)超平面。點(diǎn)積xi·xj可由非線性核函數(shù)替換。本文使用分類能力強(qiáng)的徑向基核函數(shù)(RBF)作為映射函數(shù)[13]，k(xi,xj)=exp(-β‖xi-xj‖)，β>0。

盡管在機(jī)器學(xué)習(xí)中，SVM算法可以達(dá)到優(yōu)異的分類性能，但是它的最終結(jié)果同時(shí)受到最優(yōu)特征子集以及SVM 參數(shù)(C,β)的影響。

2 遺傳算法

GA是基于達(dá)爾文進(jìn)化理論來模擬自然選擇和生物遺傳的一種隨機(jī)優(yōu)化技術(shù)，包含適應(yīng)度函數(shù)，選擇、交叉和變異操作[12]，可用來解決很多傳統(tǒng)的梯度優(yōu)化方法難以解決的問題(如非線性的、離散的、隨機(jī)的目標(biāo)求解問題等)。GA把問題的解表示成“染色體”或個(gè)體，即通常用二進(jìn)制編碼0或1來表示的編碼串。

隨機(jī)產(chǎn)生初始種群中的染色體，也即假設(shè)解集，置于后代的遺傳進(jìn)化中。根據(jù)計(jì)算的每個(gè)染色體的適應(yīng)度，選擇優(yōu)秀的父輩染色體遺傳到下一代種群中。根據(jù)精英策略，一些頂級(jí)排行的優(yōu)秀染色體可以直接復(fù)制，成為下一代種群中的染色體；而剩下的優(yōu)秀染色體經(jīng)過交叉、變異操作后，遺傳到下一代。對(duì)新一代種群重新評(píng)價(jià)選擇、交叉和變異操作，不斷循環(huán)，使種群中優(yōu)秀染色體的適應(yīng)度值不斷提高，則迭代過程收斂，進(jìn)化過程結(jié)束。最后一代的染色體解碼，即為給定問題的最優(yōu)解。

3 方法

3.1 提出的算法

提出的算法利用GA在遺傳進(jìn)化過程中，自動(dòng)地決策特征子集和同步優(yōu)化SVM的參數(shù)(懲罰因子C和核參數(shù)β),其流程如圖1所示。主要步驟如圖1。

1)算法首先初始化初始種群。如圖2所示，每個(gè)染色體分為3個(gè)基因小組(S1, S2, S3)，每個(gè)小組由一段基因組成，分別是：懲罰因子、核參數(shù)和特征子集。

圖1 提出算法的流程圖

圖2 染色體描述

2)對(duì)種群中的所有染色體進(jìn)行解碼。二進(jìn)制的懲罰因子和核參數(shù)轉(zhuǎn)換為十進(jìn)制，去除數(shù)據(jù)集中未被選中的特征。

3)第(2)步中獲得的參數(shù)作為SVM輸入，使用訓(xùn)練集構(gòu)建SVM模型。

4)計(jì)算測(cè)試集的適應(yīng)度函數(shù)值。算法提出的適應(yīng)度函數(shù)不僅體現(xiàn)了SVM的泛化能力，而且通過第二項(xiàng)來懲罰GA所選擇的特征數(shù)。

(7)

其中：w為權(quán)重系數(shù)(0

(8)

其中：N為總的測(cè)試集中的總樣本數(shù)，Nc為正確分類的測(cè)試樣本數(shù)。

5)選擇t個(gè)頂級(jí)排行的優(yōu)秀染色體作為杰出染色體群。該杰出染色體群生成r個(gè)分組多基因交叉染色體，如圖3所示，每個(gè)杰出基因小組通過輪盤選擇策略生成各自的基因小組。假設(shè)杰出基因小組的適應(yīng)度與它們對(duì)應(yīng)的染色體的適應(yīng)度相等。由于促進(jìn)了可行解中的高質(zhì)量的信息交換，該算法更有效地增強(qiáng)了搜索解空間的能力。適應(yīng)度越高的染色體，它相應(yīng)的基因小組被遺傳的概率越大。分組多基因交叉染色體形成新的可行解集合。再重新評(píng)價(jià)適應(yīng)度及選擇操作，產(chǎn)生杰出父輩池。

圖3 分組多基因交叉技術(shù)

6)第(5)步中選出最杰出的染色體作為精英，不需要經(jīng)過交叉與變異操作，直接復(fù)制到下一代中。

7)杰出父輩池中的染色體與普通父輩池中的染色體進(jìn)行配對(duì)，經(jīng)過交叉(如圖4所示)和變異，產(chǎn)生新生代的個(gè)體。

圖4 交叉算子

8)重復(fù)步驟(2)～(7)直到產(chǎn)生最大的代數(shù)。最后一代中具有最佳適應(yīng)度值的染色體被選為最優(yōu)解。

3.2 數(shù)據(jù)集

CAD的早期診療非常重要，研發(fā)CAD自動(dòng)診斷系統(tǒng)可幫助醫(yī)師準(zhǔn)確預(yù)診，使患者得到及時(shí)治療。本文中的數(shù)據(jù)集來自于UCI機(jī)器學(xué)習(xí)倉[13]中的Cleveland數(shù)據(jù)集，包含14個(gè)特征屬性：Chest pain type (Cp)，Age，Sex，Resting blood pressure (Restbps)，Serum cholesterol in mg/dl (Chol)，F(xiàn)asting blood sugar (Fbs)，Resting electrocardiographc results (Restescg)，maximum heart rate achieved (Thalach)，Exercise induced angina (Exang)，ST depression induced by exercise relative to rest (Oldpeak)，slope of the peak exercise ST segment (Slope), number of major vessels colored by fluoroscopy (Ca)，Thalium (Thal)及diagnosis of heart disease。本文主要使用前13個(gè)特征，其屬性用特征ID描述(ID分別為1～13)，其數(shù)值用一個(gè)0～4的整數(shù)表征，0代表正常無疾病，數(shù)值1～4依次表示疾病的嚴(yán)重程度。在Cleveland數(shù)據(jù)集中去除6個(gè)缺失的樣本值，剩下的297個(gè)樣本記錄中，54%屬于正常的樣本狀態(tài)，余下46%屬于有病理的樣本狀態(tài)。

3.3 實(shí)驗(yàn)參數(shù)設(shè)置

基于SVM的Cleveland數(shù)據(jù)分類在MATLAB上進(jìn)行，隨機(jī)地將數(shù)據(jù)集中的正常樣本和疾病樣本分別以1∶1的比例分入訓(xùn)練和測(cè)試集中，組合成新的訓(xùn)練和測(cè)試集。SVM的分類表現(xiàn)很大程度上取決于合適的參量C和β， 圖2中的基因小組S1和S2對(duì)應(yīng)懲罰因子和核函數(shù)的范圍分別為{2-8, 28}, {2-4, 24}，將它們編碼為二進(jìn)制串。基因小組S3自動(dòng)的設(shè)置為數(shù)據(jù)集的13個(gè)特征的二進(jìn)制編碼串，具有1值的基因說明S3選中了對(duì)應(yīng)的特征。改進(jìn)的GA的參數(shù)設(shè)置如表1中所述。

表1 改進(jìn)GA參數(shù)

4 仿真結(jié)果分析與討論

改進(jìn)GA可以去除不相關(guān)的特征，保存與CAD狀態(tài)最相關(guān)的特征，增強(qiáng)SVM的分類性能。受交叉算子的影響，改進(jìn)GA的空間搜索能力加強(qiáng)。同時(shí)，變異算子引進(jìn)了搜索的隨機(jī)行為，可發(fā)現(xiàn)新的搜索空間，并防止GA過早收斂。圖5顯示了目標(biāo)問題求解過程中，改進(jìn)GA的適應(yīng)度函數(shù)值隨代數(shù)增加而不斷變化?？梢钥闯?，種群中的個(gè)體朝著近似最優(yōu)解的方向進(jìn)化，新生代的染色體含有比父輩更好的基因，而且收斂速度比傳統(tǒng)的GA更快，在第35代的時(shí)候收斂。

圖5 兩種方法的適應(yīng)度函數(shù)變化過程

由于GA的尋優(yōu)空間非常復(fù)雜，算法每次運(yùn)行不一定找到相同的最優(yōu)特征子集；或者，所選的多個(gè)特征子集都可得到SVM的最佳分類精度。因此，判斷哪些特征有助于評(píng)價(jià)樣本的狀態(tài)很重要。在不同樣本上運(yùn)行100次改進(jìn)GA，每個(gè)特征被選擇的次數(shù)如圖6所示，水平線為y=70. 其中7個(gè)特征被選擇的概率至少為0.7，使用GA尋找到含有這7個(gè)特征的子集分類時(shí)，SVM達(dá)到最佳分類效果。最佳特征子集包含特征Cp，Age，Exang，Oldpeak，Slope，Ca，Thal。改進(jìn)GA不僅將Cleveland數(shù)據(jù)集的特征數(shù)從13減至7，優(yōu)化了SVM參數(shù)，因而增強(qiáng)了SVM的分類性能。

圖6 運(yùn)行改進(jìn)GA100次過程中每個(gè)特征被選中的次數(shù)

表2列出了SVM對(duì)應(yīng)的分類率。應(yīng)用完整的特征集時(shí)，訓(xùn)練集中的正常和疾病樣本分類率分別為86.4%和84.3%，測(cè)試集中的正常和疾病樣本分類率分別為83.7%和82.1%。應(yīng)用GA優(yōu)化的特征子集時(shí)，訓(xùn)練集中的正常和疾病樣本分類率分別提高了1.2%和1.6%，測(cè)試集中的正常和疾病樣本分類率分別提高了2.1%、1.2%。然而，利用改進(jìn)的GA獲得優(yōu)化后的特征集，其分類結(jié)果最佳，測(cè)試集中的正常和疾病樣本分類率分別達(dá)到87.2%和85.4%。可見，與采用特征全集及傳統(tǒng)的GA優(yōu)化得到的結(jié)果相比，基于改進(jìn)GA優(yōu)化的特征子集可得到更好的分類率。如果醫(yī)師將健康人誤診為CAD患者，這種錯(cuò)誤的決策由于不會(huì)置人于危險(xiǎn)狀態(tài)下，是可容忍的。反之，如果將CAD患者誤診健康人群，可能導(dǎo)致延誤治療甚至引發(fā)死亡，必須盡可能避免這種情況。

表2 SVM對(duì)應(yīng)的分類率(%)

表3 改進(jìn)GA-SVM與其他3種方法的分類結(jié)果比較(%)

將本文提出的方法與傳統(tǒng)的GA-SVM、BPNN及ANFIS 3種方法進(jìn)行比較。BPNN是人工神經(jīng)網(wǎng)絡(luò)(ANN)中常用的分類器[14-15]。經(jīng)過測(cè)試后，單神經(jīng)網(wǎng)絡(luò)中包含2個(gè)隱含層的結(jié)構(gòu)是最好的分類器。第1個(gè)隱含層中含有5個(gè)神經(jīng)元，第2個(gè)隱含層中含有3個(gè)神經(jīng)元。隱含層使用Sigmoid函數(shù)，輸出層應(yīng)用線性變換函數(shù)。整個(gè)神經(jīng)網(wǎng)絡(luò)應(yīng)用Levenberg Marquardt (LM)算法。ANFIS是神經(jīng)網(wǎng)絡(luò)與模糊理論結(jié)合的產(chǎn)物[16]，該算法應(yīng)用減聚類，聚類半徑為0.7。后兩種分類器也利用MATLAB來仿真，使用相同的訓(xùn)練和測(cè)試集并應(yīng)用了全特征集。幾種方法的分類結(jié)果列于表3。測(cè)試結(jié)果表明，BPNN和ANFIS分類器在正常樣本上可分別獲得82.9%和84.2%的正確分類率，在CAD疾病樣本上則為80.5%和82.5%，而本文提出的方法具有優(yōu)于這兩種分類器的表現(xiàn)，同時(shí)也比傳統(tǒng)的GA-SVM分類結(jié)果好。這表明基于改進(jìn)GA特征選擇的SVM診斷是一種有效的CAD診斷評(píng)估方法。

5 結(jié)論

提出了一種基于改進(jìn)GA-SVM的CAD疾病診斷方法。該算法的主要貢獻(xiàn)在于自動(dòng)決策最優(yōu)的特征子集并同步優(yōu)化SVM參數(shù)，增加了SVM的分類精度。改進(jìn)的GA應(yīng)用新的分組多基因交叉技術(shù)，促進(jìn)了頂級(jí)排行的優(yōu)秀染色體的基因交換。與BPNN及ANFIS兩種算法相比，提出的算法具有更好的表現(xiàn)。

參考文獻(xiàn)：

[1]Tsipouras M G, Exarchos T P, Fotiadis D I, et al. Automated diagnosis of coronary artery disease based on data mining and fuzzy modeling [C]. IEEE Trans on Information Technology in Biomedicine, 2008, 12 (4): 447-458.

[2]Setiawan N A, Venkatachalam P A, Hani A M. Diagnosis of coronary artery disease using artificial intelligence based decision support system [C]. Proceedings of the International Conference on Man-Machine Systems, BatuFerringhi, Penang, 2009.

[3]Anooj P K. Clinical decision support system: risk level prediction of heart disease using weighted fuzzy rules [J]. Journal of King Saud University Computer and Information Sciences, 2012, 24(8): 27-40.

[4]Ahmad F A, Isa A M, Hussain Z, et al. Intelligent medical disease diagnosis using improved hybrid genetic algorithm multilayer perceptron network [J]. Journal of Medical Systems, 2013, 37(2): 1-8.

[5]Mokeddem S, Atmani B, Mokeddem M. Supervised feature selection for diagnosis of coronary artery disease based on genetic algorithm [C]. Proceedings of International Conference on Computer Science & Information Technology, 2013: 41-51.

[6]Vapnik V N. Statistical learning theory [M]. New York: Wiley, 1989.

[7]Abibullaev B, An J. Decision support algorithm for diagnosis of AD/HD using electroencephalograms [J]. Journal of Medical Systems, 2012, 36(2): 2675-2688.

[8]黃瑞梅，杜守洪，陳子怡，等. 基于支持向量機(jī)的癲癇腦電信號(hào)模式識(shí)別研究[J]. 生物醫(yī)學(xué)工程學(xué)雜志，2013, 30(5)：919-924.

[9]Zcift A, Guelten A. Gentic algorithm wrapped Bayesian network feature selection applied to differential diagnosis of erythemato-squmous diseases [J]. Digital Signal Processing, 2013, 23(1): 230-237.

[10]Kocer S, Canal M R. Classifying epilepsy diseases using artificial neural networks and genetic algorithm [J]. Journal of Medical Systems, 2011, 35(4): 489-498.

[11]Elveren E, Yumusak N. Tuberculosis disease diagnosis using artificial neural network trained with genetic algorithm [J]. Journal of Medical Systems, 2011, 35(7): 329-332.

[12]張 梅，胡躍明，汪 濤，等. 基于改進(jìn)遺傳神經(jīng)網(wǎng)絡(luò)的優(yōu)化預(yù)測(cè)方法及其在腹膜透析中的應(yīng)用[J]. 生物醫(yī)學(xué)工程學(xué)雜志，2009, 26(6): 1186-1190.

[13]Keerthi S S, Lin C J. Asymptotic behaviors of support vector machines with Gaussian kernel [J]. Neural Computation, 2003, 15(7): 1667-1689.

[14]王多點(diǎn)，邱國慶，戴婷婷，等. 基于改進(jìn)BP神經(jīng)網(wǎng)絡(luò)的圍巖自穩(wěn)能力評(píng)估模型[J]. 計(jì)算機(jī)應(yīng)用， 2012, 32(4): 1056-1059.

[15]董傳亮，史仲平. 基于自聯(lián)想神經(jīng)網(wǎng)絡(luò)的谷氨酸發(fā)酵故障診斷[J]. 生物學(xué)雜志，2009, 26(3): 33-37.

[16]韓寶如，邢益良，劉瑤利. 基于Takagi-Sugeno型自適應(yīng)模糊神經(jīng)網(wǎng)絡(luò)的模擬電路故障診斷[J]. 電子質(zhì)量, 2013, 3(5): 31-35.