面向K最近鄰分類的遺傳實例選擇算法

黃宇揚，董明剛,2，敬 超,2

(1.桂林理工大學 信息科學與工程學院，桂林 541004； 2.廣西嵌入式技術與智能系統重點實驗室(桂林理工大學)，桂林541004)(*通信作者電子郵箱d2015mg@qq.com)

0 引言

K最近鄰(K-Nearest Neighbors,KNN)分類算法是一種典型的非參數惰性學習方法[1]，因其簡單和有效使它被廣泛用于分類問題[2-3]。它通過分析已知類的訓練樣本來預測新樣本的類，因此訓練集中的樣本很大程度地影響了KNN的分類精度和分類效率。目前KNN分類方法存在的主要問題如下：1)訓練集太大或數據的維數較高時，其計算的代價較高[4-5];2)訓練集存在大量噪聲樣本時，會嚴重影響分類精度[6-8]。

實例選擇算法可以有效緩解以上問題，通過對訓練集樣本的選擇，在原訓練集中尋找訓練效果較好的代表樣本集, 它通過縮減訓練集來提高分類效率，同時通過刪除噪聲樣本來提高分類精度, 因此實例選擇受到關注。文獻[5]通過“最鄰近鏈”方法刪除訓練樣本密集區中對分類決策影響不大的訓練樣本來減少訓練集樣本的數量; 文獻[8]在處理二分類問題時，通過使用決策樹對訓練集進行預分類來確定噪聲樣本。

此外，進化算法[9]也是一種有效的實例選擇方法[10-14]: 文獻[10]將實例選擇問題看作是一個遺傳優化問題，在原有訓練集的基礎上生成不同的訓練集組合，選擇最優的訓練集組合來代替原始的訓練集; 文獻[11]將遺傳算法運用到實例選擇中，并與非進化實例選擇方法進行對比, 相較之下，它有著更高的分類精度; 文獻[12]采用協同進化的方式，同時對樣本和樣本的特征進行選擇，獲得訓練效果最佳的訓練集及樣本特征; 文獻[13]同時優化樣本權重和特征權重，根據最優的權重進行訓練; 文獻[14]將遺傳算法與模糊粗糙集理論相結合，進行特征選擇以提高KNN的分類精度。上述方法取得了不錯的效果，但還存在以下問題：1)存在誤刪的風險，從而造成分類精度的降低；2)算法效率偏低。

本文主要研究如何為KNN選擇最佳的實例集。研究內容及貢獻如下：

1)提出基于決策樹和遺傳算法的二階段篩選機制。先使用決策樹確定噪聲樣本存在的范圍，再使用遺傳算法在該范圍內精確刪除噪聲樣本。該篩選機制能進一步提高分類精度，并縮小在訓練集中進行實例選擇的范圍, 相較于對整個訓練集進行實例選擇的算法[7,12-13]有著較高的效率。

2)提出一種新的驗證集選擇策略。選擇訓練集中與測試集最鄰近的樣本組合成驗證集，使遺傳算法計算的適應度自適應不同的測試集，提高了實例選擇的準確度。

3)引進一種新的遺傳算法目標函數。將基于均方誤差的分類精度懲罰函數MSE(Mean Square Error)作為目標函數能使遺傳算法準確地找到最優的訓練樣本集，相比傳統目標函數更為穩定和有效。

1 PRKNN算法

文獻[8]提出了一種基于KNN的二分類實例選擇方法(PRe-classification basedKNN, PRKNN), 在處理較大的數據集時，既提高了分類效率，又提高了分類精度。首先通過訓練集構建決策樹分類器，訓練集中的每個樣本都被劃分到決策樹的子葉節點中，經過決策樹的分類后，訓練集被分為幾個不同的樣本子集; 然后根據分類比率p(p是該樣本子集正類樣本的數量和總樣本數量的比值)和閾值α(α<0.5)來判斷這幾個樣本子集哪些是噪聲樣本大量存在的子集。如果該樣本子集分類比率p≥α且≤1-α,則該樣本子集確定為噪聲樣本大量存在的子集，這些樣本子集將會被刪除出訓練集。ω=1表示將該樣本子集留在訓練集，ω=0表示將該樣本子集刪除，刪減法則遵循式(1)：

(1)

盡管PRKNN方法在提高KNN的分類效率和分類精度上取得了不錯的效果; 但是在處理部分數據集時，由于刪除掉的樣本子集里包含有大量的非噪聲樣本，會嚴重地影響分類精度，甚至低于傳統的KNN算法。為此本文采用其預分類的思想，提出了改進的遺傳實例選擇(Genetic Instance Selection，GIS)算法。 首先使用決策樹初步確定噪聲樣本大量存在的范圍；再使用遺傳算法在該范圍內精確定位并刪除噪聲樣本。該方法相較于當前進化實例選擇算法在分類精度和分類效率上均有一定程度的提升。

2 GIS算法

2.1 基于決策樹與遺傳算法的二階段篩選機制

正如第1章所述，PRKNN算法將訓練集進行預分類，把訓練集分成幾個樣本子集；然后根據式(1)將一些樣本子集從訓練集中刪除，但是這些樣本子集中大概率包含非噪聲樣本，從而導致分類精度降低。本文算法不將這些樣本子集完全刪除，而將其中的樣本加入噪聲樣本集Tnoise，其余樣本作為非噪聲樣本保留在訓練集中；隨后使用遺傳算法在Tnoise中精確刪除噪聲樣本；最后，Tnoise剩余的樣本與原來留下的樣本組成訓練集。為了使預分類思想能在多類問題中應用，本文算法將重新將p定義為主類占比，代表子集中最大同類樣本數量和總樣本數量的比值，同時α的范圍變為α>0.5。若該樣本子集p小于或等于α則該樣本子集為噪聲樣本子集, 否則為非噪聲樣本子集，樣本子集的確定遵循式(2)：

(2)

如圖1的例子，假設設定α的值為0.8。決策樹將訓練集分成A、B、C、D四個樣本子集。子集A、D的p為0.88和1，均大于0.8，是非噪聲樣本子集，所以里面的樣本將保留在訓練集中; 子集B、C的p為0.56和0.5，為噪聲樣本子集，里面的樣本將加入Tnoise，使用遺傳算法進行進一步篩選，決定樣本是否留在訓練集中。

圖1 噪聲樣本子集的確定

本文將對Tnoise的樣本選擇問題看作是一個遺傳優化問題，在Tnoise的基礎上生成不同的替代樣本子集，對這些子集進行評價與對比，在進化一定的代數后選出最優的子集代替原來的Tnoise。

如圖2所示，Tnoise的樣本用N位的二進制向量b表示，N為所有Tnoise中包含的樣本總量。每一位代表Tnoise里的每一個樣本。如果b的第n位b[n]=1,則其代表的相應樣本為非噪聲樣本，將保留在訓練集中；反之將從訓練集中刪除。比特流b由給定目標函數的最小化來決定。如圖3所示，本文將使用遺傳算法獲取最優的比特流b。

圖2 噪聲樣本子集編碼

圖3 遺傳算法的應用

2.2 基于最近鄰規則的驗證集選擇策略

傳統的驗證集是從訓練集中隨機選出與測試集等量的樣本組合而成[7]，用來輔助模型構建。該驗證集選擇方法存在以下問題：

1)當數據集較小時，從訓練集中選出驗證集會使訓練集樣本的數量進一步減少，對依賴訓練集進行分類的KNN算法的分類精度產生很大的影響。

2)使用隨機選取的驗證集，由于它的隨機性，構建出來的訓練集會擬合于隨機的驗證集導致分類效果不太穩定。

針對以上不足，本文采用最近鄰規則復制訓練集中與測試集最鄰近的樣本來組成驗證集。具體算法流程如下：

算法1 最近鄰驗證集選擇算法。

輸入 訓練集為Tr，測試集為Te；

輸出 驗證集為Vs。

fori=1:測試集樣本數量

forj=1：訓練集樣本的數量

ifTrj最鄰近Tei

復制Trj到Vs

end if

end for

end for

該方法使驗證集的特征更接近測試集。每一個測試集都會有一個與其對應的驗證集，算法能通過這些驗證集，自適應地構造出更有效的訓練集; 可以避免因選出驗證集后使訓練集縮減導致的KNN分類精度損失; 同時，KNN使用該訓練集進行分類，分類精度更高，分類效果更加穩定。

2.3 基于均方誤差的分類精度懲罰函數

選擇合適的遺傳算法目標函數來計算適應度是獲取最優訓練集的關鍵。傳統相關算法使用KNN的分類錯誤率作為目標函數并適當地增加懲罰(Counting Estimator with Penalizing Term, CEPT)，如式(3)。驗證集中的樣本數量為N，若其中第n個樣本Xn正確分類則h(Xn)=0，否則為1。

(3)

文獻[7]在CEPT的基礎上提出了更為有效和穩定的基于均方誤差的分類精度懲罰函數MSE，如式(4)：

(4)

其中:N表示驗證集中樣本的數量；C表示樣本集的總類別；k表示k鄰近值，kn[i]/k表示驗證集中第n個樣本被預測為第i類的概率；cn為該樣本的真實類別。

2.4 GIS算法流程

算法的整體流程主要包含三大步驟：第一步，使用決策樹確定噪聲樣本大量存在的范圍即Tnoise；第二步，使用遺傳算法從該范圍中刪除噪聲樣本；第三步，使用KNN進行分類。具體算法流程如下：

算法2 改進的基于KNN的實例選擇算法。

輸入 訓練集為Tr，測試集為Te，最鄰近值為k，噪聲分部概率閾值為α；

輸出 分類正確率為Ac。

1)

復制訓練集中與測試集最鄰近的樣本組成驗證集；

2)

在訓練集上進行預分類，通過C4.5分類器將訓練集劃分為幾個樣本子集：T1、T2、T3,…,并計算樣本子集的分類比率p1、p2、p3,…；

3)

fori=1:樣本子集的數量

4)

Ti的主類占比小于等于α則將該子集的樣本加入Tnoise，否則不做處理；

5)

根據Tnoise總的樣本數量N，初始化包含有10個N位二進制向量個體的種群，其中1個二進制向量每一位都為1，其余9個隨機產生；

6)

end for

7)

fori=1:30

8)

根據驗證集計算種群中每一個個體對應的目標函數值，并保存全局最優值；

9)

使用輪盤賭法隨機選擇優秀的個體交叉產生10個個體；

10)

將二進制突變應用到整個種群中；

11)

end for

12)

利用經典的KNN算法基于全局最優個體對應的Tr對Te中的所有樣本進行類別標號；

13)

輸出標號后的數據集Te

其中，步驟1)驗證集與測試集越相似，遺傳算法得出的最優訓練集越接近于測試集的最優訓練集，最后對測試集進行KNN分類時分類的精度越高。步驟4)參數α的值設置太小，所確定的噪聲區范圍會偏大,使GIS算法在較小迭代次數和種群條件下得到的分類效果也偏低；參數α的值設置太大，會使噪聲區太小或沒有噪聲區，導致GIS失去效果，相當于KNN。建議將α設置在0.1～0.3。步驟5)使初始化的初代種群有一個個體是每一位都為1的二進制向量。將其作為初代個體之一，可以保證在C4.5決策樹分類器誤將非噪聲樣本子集劃分為噪聲樣本子集時，將保留原始的訓練集作為最優訓練集的備選個體之一。算法整體結構和流程如圖4所示。

圖4 GIS算法流程

3 實驗結構

3.1 實驗設置

為了驗證算法的有效性，本文通過Keel編程實現算法，并在Win10系統下的Keel軟件進行實驗。對本文算法GIS、基于協同進化的實例特征選擇算法(Instance and Feature Selection based on Cooperative Coevolution, IFS-CoCo)[12]、PRKNN算法[8]、經典KNN算法[1]這四個算法進行對比。實驗數據來源于Keel平臺標準的數據集庫，大部分在UCI上有對應的數據集，數據集信息如表1所示。為了更好地驗證GIS的可靠性和穩定性，數據集樣本數量小于1 000的數據集使用3折交叉驗證，大于1 000的使用5折交叉驗證，實驗10次取平均。四個算法k=7；GIS、PRKNNα=0.2；GIS、IFS-CoCo初始化10個個體，遺傳迭代30次；四個算法其余參數按原算法默認值設置。

PRKNN只是二分類算法，本文通過重新定義p的方法將其擴展到多類(詳見2.1節)，不影響其處理二類問題的效果。

表1 數據集信息

3.2 評價標準

為了全面分析得到的實驗結果，本文采用以下3種評價指標：

1)分類精度。分類精度是測試樣本被正確分類的數量和測試樣本總數量的比值，是衡量一個分類器分類效果的重要指標[15]。

2)AUC(Area Under Curve)。 AUC是接收者操作特征曲線ROC(Receiver Operating Characteristic)下方的面積[16]，是判斷二分類預測模型優劣的標準(ROC曲線的橫坐標是偽陽率，縱坐標是真陽率)。為了計算AUC需要用到混淆矩陣來計算真陽率(Sensitivity)、偽陽率(Specificity)。

在混淆矩陣中，真陽性(TP)是正確分類的正類樣本的數量；偽陽性(FP)是錯誤分類正類樣本的數量；真陰性(TN)是正確分類的負類樣本的數量；偽陰性(FN)是錯誤分類的負樣本的數量。根據混淆矩陣，真陽率(Sensitivity)、偽陽率(Specificity)的計算公式如式(5)、式(6)：

(5)

(6)

3)Kappa: Kappa系數從混淆矩陣中衍生出來的分類精度評價指標[17]，代表被評價分類與完全隨機分類相比產生錯誤減少的比例，它的計算公式如式(7)：

(7)

其中：r是它的行數，xii是i行i列(主對角線)上的值，xi+和x+i分別是第i行和第i列的和，N為測試集的樣本數量。

AUC作為二類數據集的評價指標，Kappa系數作為多類數據集的評價指標，分類精度同時作為二類、多類數據集的評價指標。

4 實驗結果分析

4.1 分類精度結果及分析

3.1節實驗條件下，4個算法在數據集上的分類精度對比實驗結果如表2(分類精度+標準差、每個數據集最優分類精度為粗體)所示。由實驗數據可得：

1)GIS在測試數據集上的平均分類精度及最優分類精度占比(15/20)均高于其他三個對比算法。

2)GIS相較于PRKNN在分類精度上平均提高3.56%，提高范圍為0.07%～26.9%。

3)GIS相較于IFS-CoCo在分類精度上平均提高1.52%，提高范圍為0.03%～11.8%。

4)GIS相較于KNN在分類精度上平均提高1.66%，提高范圍為0.2%～12.64%。

5)PRKNN在Titanic、Bupa數據集、IFS-CoCo在Tic-tac-toe(Tic)、Vowel數據集的實驗中相對于其他算法有較大的精度損失(低于KNN 5%以上)，導致平均精度較低，GIS比較穩定且平均精度高于其他對比算法。

6)同為進化實例選擇算法，相較于IFS-CoCo，GIS能在較小的迭代評估次數下獲得較優且穩定的分類精度。

7)在具體實例選擇步驟分類結果的對比中，使用C4.5決策樹進行實例選擇時(PRKNN)，平均分類精度最低(72.25%)，當不進行實例選擇時(KNN)平均分類精度為74.15%，當使用C4.5與遺傳算法結合的二階段篩選機制進行實例選擇時(GIS)平均分類精度最高(75.81%)，最優分類精度占比最高(15/20)。

表2 4種算法分類精度實驗結果 %

GIS與其他三個對比算法在分類精度上威爾克森秩和檢驗[18]結果如表3所示，不論與哪個算法相比,GIS的R+的值均遠大于R-的值。P-value均遠小于常規的顯著水平(0.05)，可以證明GIS在這組實驗上的分類精度遠優于其他對比算法。

表3 分類精度威爾科克森符號秩和檢驗

綜合以上分析，GIS算法分類精度優于其他三種對比算法。使用C4.5與遺傳算法相結合的二階段篩選機制，也優于不進行實例選擇、使用C4.5進行實例選擇。

4.2 AUC和Kappa結果及分析

在3.1節實驗條件下，4個算法的AUC(二類數據集)、Kappa(多類數據集)對比實驗結果(AUC或Kappa +標準差、每個數據集最優AUC或Kappa為粗體)如表4所示。

表4 4種算法AUC或Kappa實驗結果 %

GIS算法與其他三個對比算法在AUC或Kappa上的威爾克森秩和檢驗結果如表5所示。

表5 AUC和Kappa威爾科克森符號秩和檢驗

由表5實驗數據得：

1)GIS算法的AUC和Kappa均值及最優AUC和Kappa占比(13/20)均優于其他對比算法。

2)GIS相較于PRKNN在AUC和Kappa上平均提高3.79%，提高范圍為0.25%～18.32%。

3)GIS相較于IF-CoCo在AUC和Kappa上平均提高3.89%，提高范圍1.27%～23.29%。

4)GIS相較于KNN在AUC和Kappa上平均提高1.06%，提高范圍0.04%～12.82%。

5)PRKNN在數據集Tic、Saheart、Titanic、Haberman有較大的AUC損失(低于KNN5%以上)。IFS-CoCo在數據集Tic、Pima、Spectfhear、Banana、Vowel有較大的AUC和Kappa損失。

由表4實驗數據得：每一組對比實驗，P-value均小于常規的顯著水平，可以證明GIS在AUC和Kappa上優于其他對比算法。

如果不能精確地刪除訓練集中的噪聲樣本，會對依靠訓練集進行分類的分類算法產生嚴重的影響，即使能提高分類精度，也可能造成AUC和Kappa的損失。GIS有效降低了誤刪率，提高了AUC和Kappa和穩定性。

5 討論

5.1 遺傳算法策略有效性討論

為了更好地驗證最近鄰驗證集選擇(Nearest Verification set Selection, NVS)策略和遺傳算法適應度計算策略MSE的有效性，本文將采用不同的驗證集選擇策略包括NVS、隨機驗證集選擇(Random Verification set Selection, RVS)策略與不同的適應度計算策略包括CEPT、MSE兩兩組合進行配對實驗。

在3.1節實驗條件下，對遺傳算法策略驗證的實驗結果如表6(分類精度+標準差、最優分類精度為粗體)和圖5所示，由實驗數據可知：

1)NVS+MSE的遺傳組合策略在測試數據集的平均分類精度及最優分類精度占比(16/20)均優于其他三種對比策略。

2)NVS的驗證集選擇策略相對于RVS策略對分類精度平均提高1.11%(CEPT)、1.96%(MSE)，有著較大的提升。

3)MSE+NVS相對于CEPT+NVS的策略組合對平均分類精度有1%的提升。

圖5 遺傳算法策略驗證

NVS+MSE策略與其他策略在分類精度上的威爾克森秩和檢驗結果如表7所示，其中MSE vs CEPT測試是在屏蔽掉NVS的對比測試即RVS+MSE vs RVS+CEPT，同樣的NVS vs RVS屏蔽了MSE。由實驗數據可知：

1)在MSE vs CEPT實驗中，R+與R-的差值為51，P-value也偏大，說明在此次實驗中MSE相對于CEPT對分類精度提升不明顯。

2)在NVS vs RVS實驗中，R+與R-的差值為117，且P-value小于常規顯著水平，說明NVS相對于RVS對分類精度有較顯著的提升。

3)NVS+MSE策略對比其他的策略，P-value均遠小于常規顯著水平。

綜合以上分析，GIS在使用NVS+MSE的遺傳算法策略進行實例選擇時。能提高實例選擇的精確度，準確刪除噪聲樣本，提高GIS的分類精度。在該組合策略中NSV起主要作用，與MSE結合能得到最好的效果。

5.2 算法時間復雜度討論

面向KNN的進化訓練集選擇算法主要的時間消耗來源于每次進化迭代過程中對適應度的計算。IFS-CoCo采用協同進化的方式同時進行實例選擇(Instance Selection, IS)、特征選擇(Feature Selection, FS)及實例和特征選擇(Instance and Feature Selection, IFS)。每次迭代需要計算三個適應度(IS、FS、IFS分別的適應度)。 它不引進驗證集，直接使用原始的訓練集進行訓練，所以每次計算適應度的時間復雜度為

3O(N·S)，N為訓練集中樣本的數量，S為從訓練集中選擇樣本的數量。GIS引進驗證集，只進行IS，時間復雜度為O(M·S)，M為驗證集樣本的數量(M≤N)。IFS-CoCo是基于整個訓練集進行全局尋優，GIS使用C4.5進行噪聲范圍定位后再進行準確的局部尋優，所以GIS在遺傳算法的時間復雜度上小于IFS-CoCo。綜合以上分析GIS在時間復雜度上小于IFS-CoCo。

雖然GIS的時間復雜度高于PRKNN，但由第4章的實驗結果可知GIS在分類精度、AUC和Kappa及分類效果的穩定性上遠優于PRKNN。

6 結語

本文提出了一種新的面向KNN的遺傳實例選擇算法GIS來提高KNN的分類精度。先通過C4.5決策樹確定噪聲樣本大量存在的范圍；再使用遺傳算法在這個范圍內精確地刪除噪聲樣本，進一步提升了分類精度。相對于當前進化實例選擇算法效率更高，效果更好。本文還提出一種新的遺傳實例選擇策略NSV+MSE，遺傳算法使用該策略進行實例選擇時，能針對不同的測試集選擇出更適合它們的訓練集，從而有效提升遺傳算法進行實例選擇的準確度。

表6 5種遺傳算法策略的分類精度實驗結果 %

表7 遺傳算法策略威爾克森秩和檢驗

經驗證GIS 綜合性能優于傳統KNN、PRKNN、IFS-CoCo等算法，NSV+MSE也優于傳統的遺傳實例選擇策略。

GIS未來的研究方向如下：1)GIS算法的兩個關鍵參數k和α均需要手動設置，可以將它們改成自適應的形式以提高算法的智能性；2)在對噪聲區進行實例選擇時，可以不局限于樣本的選擇，可以擴展到特征選擇。樣本選擇與特征選擇相結合或許能進一步提升分類精度；3)使用新的遺傳算法代替原始的遺傳算法進實例選擇。