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

李 勇， 秦彩杰

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

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

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

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

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

1 方法

1.1 數據集

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

1.2 遺傳算法簡介

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

1.3 模擬退火

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

1.4 F-ScoreF-Score

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

1.5 算法的評價指標

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

1.6 本文算法

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

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

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

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

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

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

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

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

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

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

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

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

（1）根據特征的F-score的排序結果，構建等差數列，以此作為特征的初始分布權重引導種群初始化.

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

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

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

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

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

2 實驗結果

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

2.1 分類效果實驗

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

圖1 分類實驗結果圖

表1 分類實驗結果

2.2 特征維數約減效果比較

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

表2 特征維數約減結果

2.3 初始種群分布

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

圖2 初始種群分布實驗

2.4 類模擬退火算法效果

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

圖3 類模擬退火實驗結果

3 結論

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