基于改進的遺傳算法的特征選擇方法在冠心病檢測中的應用

李 勇， 秦彩杰

（三明學院信息工程學院，福建三明365004）

冠心病是由冠狀動脈器質(zhì)性狹窄或阻塞引起的心肌缺血缺氧或心肌壞死的心臟病[1].冠心病具有較高的發(fā)病率和致死率，并呈現(xiàn)年輕化趨勢，現(xiàn)已成為全球范圍內(nèi)威脅人類生命和健康的高危病種.因此早期的篩查診斷對于冠心病的有效治療非常關(guān)鍵[2].常用的冠心病臨床檢測方法包括心電圖檢測（常規(guī)心電圖、運動負荷心電圖、動態(tài)心電圖等），生化檢測，超聲檢測，多排的螺旋CT，冠脈造影等[3].其中冠脈造影是全球醫(yī)學界公認的診斷冠心病的“金標準”，但其檢測費用昂貴，是一種有創(chuàng)診斷技術(shù)，且具有副作用[4].而其他一些常用的冠心病診斷技術(shù)受到費用、技術(shù)條件以及主觀依賴檢查者的經(jīng)驗等方面的局限[5].近年來，越來越多的研究熱度集中在利用機器學習的方法探究與冠心病相關(guān)的危險因素，以及通過無創(chuàng)無損的方式進行冠心病的早期診斷篩查.

Patidar等[6]基于心率信號，采用最小二乘支持向量機檢測冠心病，算法取得了較好的分類性能.Sridhar等[7]從心電信號中提取特征，經(jīng)過離散小波變換和排序篩選后，輸入到機器學習分類模型中，實驗結(jié)果取得了較高的分類精度.Wiharto等[8]提出了采用C4.5決策樹模型結(jié)合臨床結(jié)果的冠心病分類方法.Liliana等[9]采用集成學習模型，通過SPECT圖像對冠心病進行分類，獲得了優(yōu)于單一分類器的實驗結(jié)果.Acharya等[10]提出了基于心電信號的卷積神經(jīng)網(wǎng)絡模型，實驗結(jié)果表明該算法有助于冠心病的早期診斷.

然而，無論是通過醫(yī)學的手段還是通過算法的方式挖掘出來的大量特征，對各種各樣的機器學習方法來說是一個嚴峻的挑戰(zhàn).因此特征選擇是機器學習過程中不容忽視的一個環(huán)節(jié).特征選擇算法可以有效地去除冗余特征和不相關(guān)特征，提高學習算法的泛化性能和運行效率，得到簡單和容易理解的學習模型，特征選擇本質(zhì)上是一個組合優(yōu)化問題.遺傳算法是模擬自然界生物進化過程的一種隨機搜索與優(yōu)化算法，已廣泛應用于自動控制、模式識別、工程設計、故障診斷、管理科學等領(lǐng)域[11].Joans等[12]提出了采用遺傳算法進行特征選擇，并結(jié)合隨機森林分類器的算法，所提出的算法在MRI上進行腦部腫瘤分類.結(jié)果顯示，該特征選擇方法有助于提高分類器的準確度.Zelenkov等[13]采用基于遺傳算法的集成模型進行破產(chǎn)預測.在集成過程中采用遺傳算法進行特征選擇，并采用遺傳算法確定每個分類器的權(quán)重.與很多已有的算法相比，該算法表現(xiàn)出了卓越的分類性能.Wang等[14]提出了利用自適應遺傳算法與本地搜索相結(jié)合的方法，解決多倉庫車輛路徑問題.該算法采用fitness-scaling技術(shù)，并能夠根據(jù)適應度值自適應調(diào)整遺傳算法.實驗結(jié)果表明，該算法在性能和計算時間上優(yōu)于傳統(tǒng)的優(yōu)化算法.Kumar等[15]提出了一種結(jié)合遺傳算法和支持向量機的DOS攻擊檢測方法，該方法應用在PMU2017數(shù)據(jù)集上，獲得了較高的檢測準確度和較低的錯誤預警率.Bolan~os等[16]采用非支配排序遺傳算法解決多個旅行商問題，該算法在真實實例上取得了不錯的實驗結(jié)果.

盡管遺傳算法在很多領(lǐng)域都存在成功的應用，但其自身仍然存在收斂速度慢、容易陷入局部最優(yōu)解等問題.因此本文提出一種基于改進的遺傳算法的特征選擇方法，并將其應用在冠心病的自動診斷中.

1 方法

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

Z-AlizadehSani數(shù)據(jù)集[17]包括303例病人，每例病人信息包括54個特征，包括病史，體格檢查指標、實驗室數(shù)據(jù)指標、ECG指標和超聲波心動圖指標.這些特征的離散化操作參照布朗的書[18]進行.

1.2 遺傳算法簡介

遺傳算法是一種求解問題的高效并行的全局搜索方法，其主要特點是群體搜索策略和群體中個體之間的信息交換，它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，自適應地控制搜索過程以求得最優(yōu)解或近似最優(yōu)解.遺傳算法所涉及的五大要素：參數(shù)編碼形式、初始群體的生成、適應度函數(shù)的設計、遺傳參數(shù)的設計（選擇算子、交叉算子、變異算子）和控制參數(shù)等[19，20].

1.3 模擬退火

遺傳算法中容易出現(xiàn)迭代前期快速收斂，而導致后期多樣性降低，進化變慢，從而陷入局部最優(yōu)解的困境.模擬退火算法局部搜索能力強，能有效彌補遺傳算法的缺陷.模擬退火算法是模擬晶體退火過程所得到的一種算法，它在搜索過程中具有概率突變的能力[21].它在退火過程中不但接收好的解，還可以以一定的概率來接受一個比當前解要差的解，從而有效地避免在搜索過程中陷入局部最優(yōu)解.

1.4 F-ScoreF-Score

是度量特征在不同類別間的區(qū)分度的一種指標，F(xiàn)-Score的值越大，代表該特征在不同類別之間的區(qū)分度越強[22].假設xk代表數(shù)據(jù)集中的樣本，k=1，2…，N.n+和n-為正類和負類樣本的數(shù)量，則數(shù)據(jù)集中第i個特征的F-Score由以下公式計算所得：

1.5 算法的評價指標

為了驗證算法的有效性，本文采用準確率，召回率和綜合評價指標F1-measure三個指標對算法進行評價.準確率和召回率是統(tǒng)計分類領(lǐng)域常用的一對度量指標，而F1-measure可以綜合考慮前面兩者.計算公式為：

1.6 本文算法

為了改進傳統(tǒng)遺傳算法早熟、多樣性退化、以及搜索效率不高等問題，本文提出了基于改進的遺傳算法的特征選擇方法（MGA）.相較于傳統(tǒng)的遺傳算法，MGA算法在種群初始化時，采用F-score的特征評價值引導種群的初始化，為遺傳算法搜索過程提供優(yōu)秀的搜索起始點.并且在遺傳操作過程中，當進化過程變慢時，采用類模擬退火的方式進行刺激，盡可能使算法跳出局部最優(yōu)解，避免算法早熟收斂.算法的具體步驟如下：

（1）編碼：二進制編碼方式簡單易行，因此文中采用二進制編碼形式對特征進行編碼，如下圖所示，每條染色體都是一個定長的二進制串.如果第i位為1，表示第i個特征處于被選中的狀態(tài)，為0表示沒有被選中.

（2）種群初始化：遺傳算法在大規(guī)模離散空間內(nèi)隨機搜索，其性能受到初始種群的影響.因此本文采用基于F-score的特征評價值引導種群的初始化，為遺傳算法提供優(yōu)秀的搜索起點.具體步驟為：

①利用公式1計算特征的F-score值并進行排序，排序越靠前表示該特征與類別的相關(guān)性越大.

②根據(jù)特征的排序結(jié)果，設定特征被選擇的概率.特征的F-Score值排在前面，那么在染色體中該特征被選擇的概率就會大一些，反之被選中的概率就會小一些.假設排序最靠前的特征被選中的概率為P0，排序最后的特征被選擇的概率為P1，在P0和P1之間形成等差數(shù)列即為其余特征被選擇的概率.文中P0，P1人為設定為0.8和0.4.

③根據(jù)步驟2設定好的特征被選擇的概率，生成n個染色體，即為初始種群.

（3）遺傳操作：進化過程是通過遺傳操作來完成的，最主要的遺傳操作包括選擇、交叉和變異，并且當進化過程變慢時，采用類模擬退火的方式進行刺激，盡可能使算法跳出局部最優(yōu)解.

①交叉操作：交叉操作是遺傳算法中產(chǎn)生新一代染色體的主要方法，通過預先設定的交叉概率隨機選擇兩個染色體交換部分基因，從而生成兩個新的染色體.文中采用單點交叉實現(xiàn)交叉操作.

②變異操作：變異操作可以使染色體的某些基因位按照較小的概率發(fā)生突變，決定了遺傳算法的局部隨機搜索能力，文中采用基本位變異操作.

③選擇操作：選擇操作的基礎是個體的適應度評價，適應度值高的染色體更有機會遺傳下一代，充分體現(xiàn)了優(yōu)勝劣汰的規(guī)則.文中對父代群體采用交叉變異操作，生成同樣規(guī)模的子代群體.然后父代群體和子代群體共同競爭，選擇出精英群體進行下一代進化.

④類模擬退火操作：當進化變慢時，例如連續(xù)5次最優(yōu)解值不變，文中采用類模擬退火的方式重新生成一組群體加入，增加種群的多樣性.實驗中采用類模擬退火方式加入的種群規(guī)模為初始群體規(guī)模的1/2，生成的群體中一半是在最優(yōu)解上增加擾動所得，另一半是隨機生成的種群.這一組種群按照一定的概率加入到當代群體中：適應度值大于最優(yōu)解的，必然要留在當代群體中，適應度值小于最優(yōu)解的但是大于當代群體適應度值平均值的也會加入到群體中，并淘汰群體中適應度值排在后面的劣勢基因，即：

本文提出的改進的遺傳算法具體的實現(xiàn)步驟如下：

（1）根據(jù)特征的F-score的排序結(jié)果，構(gòu)建等差數(shù)列，以此作為特征的初始分布權(quán)重引導種群初始化.

（2）根據(jù)適應度函數(shù)，計算父代群體的適應度值.

（3）對父代群體進行選擇、交叉和變異操作，生成同樣種群大小的子代群體，并計算子代群體的適應度值.

（4）對父代中n個染色體和子代中的n個染色體的適應度值進行統(tǒng)一排序，排序最靠前的n個染色體形成新一代群體.

（5）進化過程變慢時，采用類模擬退火的方式生成新的一組群體加入，增加種群多樣性，擺脫局部最優(yōu)解的困境.

（6）重復步驟2，3，4，直到滿足終止條件.

2 實驗結(jié)果

文中基于GA的特征選擇方法參數(shù)設置：初始種群40，迭代次數(shù)100，交叉概率0.8，變異算子0.01，類模擬退火產(chǎn)生的種群規(guī)模20，以支持向量機的分類結(jié)果作為遺傳算法的適應度函數(shù).

2.1 分類效果實驗

支持向量機基于最大間隔分離原理，在最小化模型復雜度和訓練誤差的前提下最小化結(jié)構(gòu)風險，在人工智能醫(yī)學領(lǐng)域被廣泛使用.為了驗證算法的效果，將文中所提出的算法與SVM算法，傳統(tǒng)的遺傳算法，以及基于F-Score與序列前向搜索策略的算法相比較.實驗中采用十折交叉驗證來驗證算法的性能.由于遺傳算法是一種隨機搜索策略，所以將十折交叉驗證重復十次，用十次交叉驗證的結(jié)果來增加算法的置信度.分類實驗結(jié)果圖如圖1所示，具體的數(shù)值結(jié)果如表1所示.可以看出，文中所提出的MGA算法準確率、召回率以及F1-Measure指標分別為93.36 0.88%、96.64 1.05%、94.90 0.94%.該算法在準確率、召回率以及F1-Measure指標上優(yōu)于其他三種算法，說明MGA算法對于冠心病的自動分類效果較好.相對于傳統(tǒng)的GA來說，MGA算法的標準差更小，說明算法的穩(wěn)定性更好.

圖1 分類實驗結(jié)果圖

表1 分類實驗結(jié)果

2.2 特征維數(shù)約減效果比較

幾種對比方法在特征維數(shù)約減方面的表現(xiàn)如表2所示，幾種方法都對特征維數(shù)約減做出了貢獻，基于F-Score+SFS方法的特征約減效果最好.但是序列前向搜索算法的局限性在于特征一旦加入無法剔除，沒有充分考慮特征之間的關(guān)聯(lián)，有時候會得到局部最優(yōu)解.傳統(tǒng)的遺傳算法和文中所提出的MGA也明顯減少了特征維數(shù).這對于降低模型復雜度，減少過擬合風險存在很大的幫助.

表2 特征維數(shù)約減結(jié)果

2.3 初始種群分布

文中所提出的算法，采用基于特征加權(quán)的概率分布進行種群初始化操作.采用特征的F-Score評價值為先驗知識，指導種群的初始化，使得遺傳算法有較好的搜索起始點.文中記錄了20次算法執(zhí)行過程的起始點與傳統(tǒng)的遺傳算法起始點的對比，對比結(jié)果如下圖2所示.相對于傳統(tǒng)的遺傳算法，基于先驗知識生成的初始種群中的最優(yōu)解的分布更集中.這說明了采用基于先驗知識對特征加權(quán)指導種群初始化，遺傳算法的搜索起始點更高，使得后續(xù)算法在一個初步優(yōu)化了的子集中搜索.

圖2 初始種群分布實驗

2.4 類模擬退火算法效果

針對遺傳算法后期多樣性變差，進化速度變慢，容易陷入局部最優(yōu)解的問題，文中采用類模擬退火的方法進行刺激.以隨機選擇的一次算法的運行時間為例，下圖3描畫了一次算法運行的過程中迭代次數(shù)與算法F1-Mesure的對應曲線圖.算法經(jīng)過52次收斂到最優(yōu)解，其中星號點表示在執(zhí)行類模擬退火方法時產(chǎn)生的優(yōu)于當代最優(yōu)解的解.可以看出類模擬退火能夠在算法陷入局部最優(yōu)解時進行刺激，增加種群多樣性，使算法盡可能趨于全局最優(yōu)解.

圖3 類模擬退火實驗結(jié)果

3 結(jié)論

文中采用了多種舉措改進遺傳算法的局限性，并采用基于改進的遺傳算法進行特征選擇，結(jié)合支持向量機進行冠心病分類.實驗結(jié)果表明該方法很好地改善了遺傳算法的多樣性，有效地解決了傳統(tǒng)遺傳算法的早熟收斂局限性.并且該算法能夠有效地降低特征維數(shù)，并能夠進一步提高算法的分類效果.該方法可以輔助臨床醫(yī)生進行冠心病的早期篩查，為患者的有效治療爭取時間.