程明霞，郭玉翠

（北京郵電大學(xué) 理學(xué)院，北京 100876）

0 引言

目前對于醫(yī)學(xué)數(shù)據(jù)的處理和診斷預(yù)測方法大都利用數(shù)據(jù)挖掘技術(shù)定量和定性分析。然而實際問題中包含大量冗余特征，會導(dǎo)致機(jī)器學(xué)習(xí)存在兩種問題：對大型數(shù)據(jù)集進(jìn)行處理時，占用太多的資源而降低算法的處理速度；在特征總量明顯超過最優(yōu)值時，精準(zhǔn)度會降低[1]。另外，機(jī)器學(xué)習(xí)分類算法例如K-近鄰算法（K-Nearest Neighbor，KNN），隨機(jī)森林（Random Forest，RF），支持向量機(jī)（Support Vector Machine，SVM）等，在分類問題中都有不同的優(yōu)缺點。在機(jī)器學(xué)習(xí)算法中，沒有最好的算法，只有“更適合”解決當(dāng)前任務(wù)的算法，反復(fù)訓(xùn)練試錯才是選擇最佳算法的前提。從文獻(xiàn)[2]中可以看出，特征降維和超參數(shù)調(diào)優(yōu)可以明顯提升分類模型的預(yù)測準(zhǔn)確率。網(wǎng)格搜索法和梯度下降法是處理機(jī)器學(xué)習(xí)超參數(shù)優(yōu)化的兩種最常見的優(yōu)化方法[3]。通過為搜索的上限、下限和步長設(shè)置適當(dāng)?shù)闹?，網(wǎng)格搜索可以在一定間隔內(nèi)獲得最高的分類精度。然而，這種方法基于局部搜索，容易陷入局部最優(yōu)。而梯度下降算法對初始參數(shù)非常敏感。如果初始參數(shù)遠(yuǎn)離最優(yōu)解，則很容易收斂到局部最優(yōu)[4]。

元啟發(fā)式算法使用隨機(jī)算法與局部搜索算法相結(jié)合，一次運行就得到一組解，能夠耗費較少的時間和計算成本搜索到理想的解集，廣泛應(yīng)用于各類實際問題上[5]。文獻(xiàn)[6]提出一種改進(jìn)的二進(jìn)制粒子群優(yōu)化方法進(jìn)行特征選擇，結(jié)果有效降低了計算成本，提高了精度。Fei Ye[7]使用遺傳算法和粒子群優(yōu)化算法（或果蠅優(yōu)化算法）相結(jié)合的方法，并通過適應(yīng)度函數(shù)將它們與SVM分類器的分類準(zhǔn)確度聯(lián)系起來，實驗結(jié)果證明了改進(jìn)算法的明顯優(yōu)勢。Khan[8]等人提出了一種改進(jìn)的粒子群優(yōu)化的K-近鄰分類器，改進(jìn)的粒子群算法在特征選擇及分類精度上都有了明顯的提高。文獻(xiàn)[9]中提到，量子粒子群算法能夠極大降低粒子陷入早熟的概率，且相同條件下，比粒子群算法求參效率和穩(wěn)定性都高。

1 GA和QPSO混合算法

在機(jī)器學(xué)習(xí)分類算法的超參數(shù)和特征選擇的優(yōu)化問題上，大多數(shù)方法主要集中在使用單一算法來解決優(yōu)化問題。本文綜合考慮元啟發(fā)式算法的優(yōu)勢，利用遺傳算法在特征選擇上的效率和準(zhǔn)確性，以及量子粒子群算法在探索參數(shù)上的優(yōu)勢，提出了一種進(jìn)化的機(jī)器學(xué)習(xí)模型，采用基于遺傳算法（GA）和量子粒子群算法（QPSO）的混合進(jìn)化算法GA-QPSO，利用遺傳算法進(jìn)行特征子集的篩選，量子粒子群算法進(jìn)行超參數(shù)的優(yōu)化，兩種算法同時進(jìn)行，應(yīng)用在兩個目前比較流行的機(jī)器學(xué)習(xí)模型：隨機(jī)森林（RF）和K-近鄰算法（KNN）中，在四個UCI醫(yī)學(xué)數(shù)據(jù)集上進(jìn)行實驗驗證，并與單一算法結(jié)果進(jìn)行對比，算法流程圖如圖1所示。

圖1 混合算法流程設(shè)計

1.1 適應(yīng)度函數(shù)f的計算

充分考慮到降低特征數(shù)量以及提高分類準(zhǔn)確度這兩個目標(biāo)，本文粒子更新迭代采用的適應(yīng)度函數(shù)設(shè)計如公式（1），在迭代的過程中，適應(yīng)度值越大越優(yōu)。其中S是選擇的特征個數(shù)，N是原始特征的總數(shù)，A是十折交叉驗證分類準(zhǔn)確率的均值。

1.2 算法步驟

（1）數(shù)據(jù)預(yù)處理。使用的數(shù)據(jù)集都是來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的數(shù)據(jù)集[10]。K-近鄰算法是基于距離度量進(jìn)行模型預(yù)測和分類的，由于距離對特征之間不同取值范圍非常敏感，所以按照公式（2）對數(shù)據(jù)做歸一化處理，其中max和min分別為x所在特征列樣本數(shù)據(jù)的最大值和最小值。另外對于缺失的數(shù)據(jù)，本文選擇均值插補(bǔ)法處理，以該屬性所有存在值的平均值來插補(bǔ)缺失的值。

（2）種群的初始化。首先，GA層種群中每個粒子初始化為隨機(jī)的二進(jìn)制字符串，字符串的位數(shù)等于樣本的特征個數(shù)，每條字符串即代表一個特征子集的選擇結(jié)果，字符串中編碼為“1”即此序號位置的特征被選中，“0”表示未選中。QPSO層初始化粒子設(shè)置為在參數(shù)最大值與最小值范圍內(nèi)的隨機(jī)值。

（3）混合算法粒子個體的組成。

如圖2所示：N代表原始特征總數(shù)，M代表分類模型待優(yōu)化參數(shù)的個數(shù)。所提出混合算法的個體由兩個不同的子個體組成，一個是在GA層中用于表示所選的新特征子集的個體，另一個是用于表示機(jī)器學(xué)習(xí)算法（RF/KNN）超參數(shù)值的個體。

圖2 混合模型個體組成示意

（4）適應(yīng)度的計算。結(jié)合混合模型的個體組成，計算每個個體的適應(yīng)度值，GA和QPSO層分別傳遞出特征子集和參數(shù)信息，在訓(xùn)練計算層，機(jī)器學(xué)習(xí)分類算法（RF或者KNN），通過十折交叉驗證訓(xùn)練數(shù)據(jù)10次，最后得出準(zhǔn)確率以及各個評價指標(biāo)的平均值，通過公式（1）計算總體適應(yīng)度值。種群的更新需要適應(yīng)度值的指引，中間層將適應(yīng)度值傳回GA和QPSO層進(jìn)行種群的更新迭代。

（5）GA層和QPSO層優(yōu)化。GA的優(yōu)化包括種群的復(fù)制，選擇（用輪盤賭選擇方法），交叉（單點交叉）和變異操作；QPSO層根據(jù)個體歷史最優(yōu)、平均歷史最優(yōu)和全局最優(yōu)更新粒子位置。

（6）迭代終止條件。系統(tǒng)達(dá)到最大迭代次數(shù)，算法迭代終止，記錄此時的最優(yōu)參數(shù)和最優(yōu)特征子集；否則重復(fù)步驟（4）和（5）。

2 數(shù)據(jù)實驗與分析

2.1 實驗及參數(shù)設(shè)置

為了將提出的混合算法的分類性能與單一算法進(jìn)行比較，使用Python3語言分別進(jìn)行了GA-RF、QPSORF、GA-QPSO-RF、GA-KNN、QPSO-KNN、GAQPSO-KNN共6種實驗，對比GA和QPSO單獨優(yōu)化以及混合起來后的優(yōu)化性能。

遺傳算法中粒子的維度與數(shù)據(jù)集的原始特征總數(shù)一致，量子粒子群算法的粒子維度與待優(yōu)化的超參數(shù)個數(shù)一致，即RF算法中是2（森林中樹的棵樹和最大深度），KNN算法中是1（k值）。遺傳算法的交叉和變異概率依據(jù)文獻(xiàn)[7]設(shè)置。量子粒子群算法的控制系數(shù)根據(jù)文獻(xiàn)[11]的結(jié)論，選擇取值范圍在［0.6，0.8］之內(nèi)線性減小的策略；根據(jù)大多數(shù)文獻(xiàn)的取值設(shè)置和經(jīng)驗，我們選擇RF和KNN參數(shù)的搜索范圍如表1所示，n代表總體樣本個數(shù)。

表1 算法參數(shù)設(shè)置

2.2 實驗分析

使用UCI數(shù)據(jù)庫的四個醫(yī)學(xué)數(shù)據(jù)集進(jìn)行實驗，具體描述如表2。

表2 數(shù)據(jù)集的描述

（1）帕金森病數(shù)據(jù)集（PDD）的實驗。四種方法的實驗每種運行10次取最后的平均值填入表中。

PDD數(shù)據(jù)集包含48個良性樣本和147個惡性樣本。對于RF和KNN分類器，分別記錄未優(yōu)化的、GA或QPSO單獨優(yōu)化的、混合優(yōu)化的實驗結(jié)果，如表3和表4所示，在PDD數(shù)據(jù)集上進(jìn)行10次十折交叉驗證實驗，在平均準(zhǔn)確率A，精準(zhǔn)率P，召回率R，F(xiàn)1分?jǐn)?shù)和所選特征數(shù)量平均值S，RF算法參數(shù)中搜索到的最優(yōu)棵樹和最大深度，或KNN參數(shù)搜索到的最優(yōu)K值的詳細(xì)結(jié)果。

表3 實驗結(jié)果（PDD數(shù)據(jù)集-RF）

表4 實驗結(jié)果（PDD數(shù)據(jù)集-KNN）

從表3和4中可以明顯看到GA-QPSO混合算法的優(yōu)勢，其中GA-QPSO混合算法和GA、QPSO單獨優(yōu)化方法相比，將RF分類器的平均分類精度分別提高了2.72%和3.61%左右，將KNN分類器分別提高了1.30%和0.79%左右；在特征篩選的個數(shù)方面，GA-QPSO混合算法在KNN上得到了最低值，減小了模型的復(fù)雜度。在RF上雖然不是最低，但也和最低值相差不大；在參數(shù)搜索方面，GA-QPSO混合算法減少了隨機(jī)森林樹的棵樹和最大深度，減小了模型復(fù)雜度，同時，搜索到的最優(yōu)K值要更合理和準(zhǔn)確（QPSO算法十次搜索到的K的平均值為1，說明其極易陷入過擬合）。

圖3、圖4和圖5對比了未優(yōu)化的、GA或QPSO單獨優(yōu)化的、混合優(yōu)化的十折交叉驗證每一折的準(zhǔn)確率結(jié)果及十次的標(biāo)準(zhǔn)差變化。可以看出，混合算法的分類準(zhǔn)確率幾乎始終在所有方法之上，且十折的標(biāo)準(zhǔn)差處于所有方法中的較低水平，波動很低，表明所提出的混合算法可以獲得穩(wěn)定的更優(yōu)結(jié)果。基于這些結(jié)果，可以認(rèn)為GA-QPSO混合算法在PDD數(shù)據(jù)集上可以為RF和KNN分類器實現(xiàn)更好的分類性能。

圖3 十折交叉驗證分類準(zhǔn)確率變化-RF

圖4 十折交叉驗證分類準(zhǔn)確率變化-KNN

圖5 不同算法的十折交叉驗證分類準(zhǔn)確率標(biāo)準(zhǔn)差的變化（左-RF，右-KNN）

為了評估算法的搜索尋優(yōu)能力，圖6和圖7展示了在100次迭代中，記錄的PDD數(shù)據(jù)集上運行的第五折的三種方法的最佳適應(yīng)度曲線。圖中結(jié)果表明GA-QPSO混合算法總能夠在迭代中快速找到最優(yōu)解且算法穩(wěn)定收斂，同時具有良好的全局搜索能力和局部搜索能力，且適應(yīng)度值一直處于較高水平，也表明了混合算法的優(yōu)勢（注：QPSO算法單獨優(yōu)化中沒有加入特征選擇過程，并且極易陷入過擬合）。

圖6 三種方法適應(yīng)度迭代對比-RF

圖7 三種方法適應(yīng)度迭代對比-KNN

（2）其他數(shù)據(jù)集的實驗。利用同樣的方法，本文計算了其他數(shù)據(jù)集的實驗結(jié)果。在皮膚病和肥胖估計這兩個多分類數(shù)據(jù)集上，輸出Kappa系數(shù)來評價多分類結(jié)果的好壞。

表5展示了混合算法優(yōu)化在其他數(shù)據(jù)集上的實驗結(jié)果，表中僅僅展示了在混合算法優(yōu)化下，RF和KNN中最好的結(jié)果。如乳腺癌數(shù)據(jù)集上，混合算法優(yōu)化KNN模型的分類準(zhǔn)確率達(dá)到了97.73%，比在RF上高0.18%，所以表中只記錄了“乳腺癌-KNN”，最終選出了13個最優(yōu)特征（原始特征是30個），參數(shù)K的最優(yōu)值是15。同樣，在各個數(shù)據(jù)集的實驗結(jié)果中，混合算法始終在各個指標(biāo)上有明顯的優(yōu)勢。實驗中發(fā)現(xiàn)，RF在多分類數(shù)據(jù)集上的準(zhǔn)確率以及Kappa系數(shù)明顯高于KNN，且明顯高于單獨算法的優(yōu)化結(jié)果。

表5 其他數(shù)據(jù)集實驗結(jié)果

3 結(jié)語

綜合所有實驗結(jié)果，可以得出結(jié)論：將GA-QPSO混合算法用在二分類或者多分類數(shù)據(jù)集上可以為RF或者KNN分類器實現(xiàn)更好的分類性能。其中，對于二分類問題，混合算法在很大程度上提升了分類準(zhǔn)確率、精準(zhǔn)率、召回率以及F1的值，精準(zhǔn)率P表示的是預(yù)測為患病的樣本中真正患病的比例，召回率R表示的是真正患病的樣本中被預(yù)測正確的比例。在醫(yī)學(xué)疾病診斷問題中，我們希望的是在保證精準(zhǔn)率的條件下，努力提升召回率，實驗結(jié)果中可以看出，混合算法的優(yōu)化結(jié)果符合我們的預(yù)期，有利于早期及時精準(zhǔn)治療方案的實施，并且預(yù)測準(zhǔn)確率高，預(yù)測更穩(wěn)定。另外，對于多分類問題，RF的結(jié)果普遍比KNN的好，因此在處理此類問題上可以偏向使用RF模型。

本文通過將元啟發(fā)式算法與機(jī)器學(xué)習(xí)算法相結(jié)合，對傳統(tǒng)的數(shù)據(jù)分類模型進(jìn)行特征選擇與超參數(shù)搜索兩方面的同步優(yōu)化，利用遺傳算法和粒子群算法不同方面的優(yōu)點，將這兩種算法結(jié)合起來同時進(jìn)行。實驗結(jié)果證明了混合算法GA-QPSO的明顯優(yōu)勢。

在未來的研究中，我們會將混合算法與更多不同的分類器結(jié)合，共同對比它們的優(yōu)缺點，以更好地解決醫(yī)學(xué)診斷問題；另外，雖然我們主要在醫(yī)學(xué)數(shù)據(jù)集上驗證了提出的算法，但是它同樣也適用于更廣泛的分類問題，這也是下一階段的研究內(nèi)容之一；最后，我們會探索其他的元啟發(fā)式算法與機(jī)器學(xué)習(xí)分類算法的結(jié)合，并與本文實驗結(jié)果作對比，探索對分類效果優(yōu)化更好的算法。