李 勇， 秦彩杰

（三明學(xué)院信息工程學(xué)院，福建三明365004）

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

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

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

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

1 方法

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

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

1.2 遺傳算法簡介

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

1.3 模擬退火

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

1.4 F-ScoreF-Score

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

1.5 算法的評價指標(biāo)

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

1.6 本文算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 分類效果實(shí)驗(yàn)

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

圖1 分類實(shí)驗(yàn)結(jié)果圖

表1 分類實(shí)驗(yàn)結(jié)果

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

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

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

2.3 初始種群分布

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

圖2 初始種群分布實(shí)驗(yàn)

2.4 類模擬退火算法效果

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

圖3 類模擬退火實(shí)驗(yàn)結(jié)果

3 結(jié)論

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