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

黃宇揚(yáng)，董明剛,2，敬 超,2

(1.桂林理工大學(xué) 信息科學(xué)與工程學(xué)院，桂林 541004； 2.廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室(桂林理工大學(xué))，桂林541004)(*通信作者電子郵箱d2015mg@qq.com)

0 引言

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

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

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

本文主要研究如何為KNN選擇最佳的實(shí)例集。研究?jī)?nèi)容及貢獻(xiàn)如下：

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

2)提出一種新的驗(yàn)證集選擇策略。選擇訓(xùn)練集中與測(cè)試集最鄰近的樣本組合成驗(yàn)證集，使遺傳算法計(jì)算的適應(yīng)度自適應(yīng)不同的測(cè)試集，提高了實(shí)例選擇的準(zhǔn)確度。

3)引進(jìn)一種新的遺傳算法目標(biāo)函數(shù)。將基于均方誤差的分類精度懲罰函數(shù)MSE(Mean Square Error)作為目標(biāo)函數(shù)能使遺傳算法準(zhǔn)確地找到最優(yōu)的訓(xùn)練樣本集，相比傳統(tǒng)目標(biāo)函數(shù)更為穩(wěn)定和有效。

1 PRKNN算法

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

(1)

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

2 GIS算法

2.1 基于決策樹(shù)與遺傳算法的二階段篩選機(jī)制

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

(2)

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

圖1 噪聲樣本子集的確定

本文將對(duì)Tnoise的樣本選擇問(wèn)題看作是一個(gè)遺傳優(yōu)化問(wèn)題，在Tnoise的基礎(chǔ)上生成不同的替代樣本子集，對(duì)這些子集進(jìn)行評(píng)價(jià)與對(duì)比，在進(jìn)化一定的代數(shù)后選出最優(yōu)的子集代替原來(lái)的Tnoise。

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

圖2 噪聲樣本子集編碼

圖3 遺傳算法的應(yīng)用

2.2 基于最近鄰規(guī)則的驗(yàn)證集選擇策略

傳統(tǒng)的驗(yàn)證集是從訓(xùn)練集中隨機(jī)選出與測(cè)試集等量的樣本組合而成[7]，用來(lái)輔助模型構(gòu)建。該驗(yàn)證集選擇方法存在以下問(wèn)題：

1)當(dāng)數(shù)據(jù)集較小時(shí)，從訓(xùn)練集中選出驗(yàn)證集會(huì)使訓(xùn)練集樣本的數(shù)量進(jìn)一步減少，對(duì)依賴訓(xùn)練集進(jìn)行分類的KNN算法的分類精度產(chǎn)生很大的影響。

2)使用隨機(jī)選取的驗(yàn)證集，由于它的隨機(jī)性，構(gòu)建出來(lái)的訓(xùn)練集會(huì)擬合于隨機(jī)的驗(yàn)證集導(dǎo)致分類效果不太穩(wěn)定。

針對(duì)以上不足，本文采用最近鄰規(guī)則復(fù)制訓(xùn)練集中與測(cè)試集最鄰近的樣本來(lái)組成驗(yàn)證集。具體算法流程如下：

算法1 最近鄰驗(yàn)證集選擇算法。

輸入 訓(xùn)練集為Tr，測(cè)試集為Te；

輸出 驗(yàn)證集為Vs。

fori=1:測(cè)試集樣本數(shù)量

forj=1：訓(xùn)練集樣本的數(shù)量

ifTrj最鄰近Tei

復(fù)制Trj到Vs

end if

end for

end for

該方法使驗(yàn)證集的特征更接近測(cè)試集。每一個(gè)測(cè)試集都會(huì)有一個(gè)與其對(duì)應(yīng)的驗(yàn)證集，算法能通過(guò)這些驗(yàn)證集，自適應(yīng)地構(gòu)造出更有效的訓(xùn)練集; 可以避免因選出驗(yàn)證集后使訓(xùn)練集縮減導(dǎo)致的KNN分類精度損失; 同時(shí)，KNN使用該訓(xùn)練集進(jìn)行分類，分類精度更高，分類效果更加穩(wěn)定。

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

選擇合適的遺傳算法目標(biāo)函數(shù)來(lái)計(jì)算適應(yīng)度是獲取最優(yōu)訓(xùn)練集的關(guān)鍵。傳統(tǒng)相關(guān)算法使用KNN的分類錯(cuò)誤率作為目標(biāo)函數(shù)并適當(dāng)?shù)卦黾討土P(Counting Estimator with Penalizing Term, CEPT)，如式(3)。驗(yàn)證集中的樣本數(shù)量為N，若其中第n個(gè)樣本Xn正確分類則h(Xn)=0，否則為1。

(3)

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

(4)

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

2.4 GIS算法流程

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

算法2 改進(jìn)的基于KNN的實(shí)例選擇算法。

輸入 訓(xùn)練集為Tr，測(cè)試集為Te，最鄰近值為k，噪聲分部概率閾值為α；

輸出 分類正確率為Ac。

1)

復(fù)制訓(xùn)練集中與測(cè)試集最鄰近的樣本組成驗(yàn)證集；

2)

在訓(xùn)練集上進(jìn)行預(yù)分類，通過(guò)C4.5分類器將訓(xùn)練集劃分為幾個(gè)樣本子集：T1、T2、T3,…,并計(jì)算樣本子集的分類比率p1、p2、p3,…；

3)

fori=1:樣本子集的數(shù)量

4)

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

5)

根據(jù)Tnoise總的樣本數(shù)量N，初始化包含有10個(gè)N位二進(jìn)制向量個(gè)體的種群，其中1個(gè)二進(jìn)制向量每一位都為1，其余9個(gè)隨機(jī)產(chǎn)生；

6)

end for

7)

fori=1:30

8)

根據(jù)驗(yàn)證集計(jì)算種群中每一個(gè)個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值，并保存全局最優(yōu)值；

9)

使用輪盤(pán)賭法隨機(jī)選擇優(yōu)秀的個(gè)體交叉產(chǎn)生10個(gè)個(gè)體；

10)

將二進(jìn)制突變應(yīng)用到整個(gè)種群中；

11)

end for

12)

利用經(jīng)典的KNN算法基于全局最優(yōu)個(gè)體對(duì)應(yīng)的Tr對(duì)Te中的所有樣本進(jìn)行類別標(biāo)號(hào)；

13)

輸出標(biāo)號(hào)后的數(shù)據(jù)集Te

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

圖4 GIS算法流程

3 實(shí)驗(yàn)結(jié)構(gòu)

3.1 實(shí)驗(yàn)設(shè)置

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

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

表1 數(shù)據(jù)集信息

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

為了全面分析得到的實(shí)驗(yàn)結(jié)果，本文采用以下3種評(píng)價(jià)指標(biāo)：

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

2)AUC(Area Under Curve)。 AUC是接收者操作特征曲線ROC(Receiver Operating Characteristic)下方的面積[16]，是判斷二分類預(yù)測(cè)模型優(yōu)劣的標(biāo)準(zhǔn)(ROC曲線的橫坐標(biāo)是偽陽(yáng)率，縱坐標(biāo)是真陽(yáng)率)。為了計(jì)算AUC需要用到混淆矩陣來(lái)計(jì)算真陽(yáng)率(Sensitivity)、偽陽(yáng)率(Specificity)。

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

(5)

(6)

3)Kappa: Kappa系數(shù)從混淆矩陣中衍生出來(lái)的分類精度評(píng)價(jià)指標(biāo)[17]，代表被評(píng)價(jià)分類與完全隨機(jī)分類相比產(chǎn)生錯(cuò)誤減少的比例，它的計(jì)算公式如式(7)：

(7)

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

AUC作為二類數(shù)據(jù)集的評(píng)價(jià)指標(biāo)，Kappa系數(shù)作為多類數(shù)據(jù)集的評(píng)價(jià)指標(biāo)，分類精度同時(shí)作為二類、多類數(shù)據(jù)集的評(píng)價(jià)指標(biāo)。

4 實(shí)驗(yàn)結(jié)果分析

4.1 分類精度結(jié)果及分析

3.1節(jié)實(shí)驗(yàn)條件下，4個(gè)算法在數(shù)據(jù)集上的分類精度對(duì)比實(shí)驗(yàn)結(jié)果如表2(分類精度+標(biāo)準(zhǔn)差、每個(gè)數(shù)據(jù)集最優(yōu)分類精度為粗體)所示。由實(shí)驗(yàn)數(shù)據(jù)可得：

1)GIS在測(cè)試數(shù)據(jù)集上的平均分類精度及最優(yōu)分類精度占比(15/20)均高于其他三個(gè)對(duì)比算法。

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數(shù)據(jù)集、IFS-CoCo在Tic-tac-toe(Tic)、Vowel數(shù)據(jù)集的實(shí)驗(yàn)中相對(duì)于其他算法有較大的精度損失(低于KNN 5%以上)，導(dǎo)致平均精度較低，GIS比較穩(wěn)定且平均精度高于其他對(duì)比算法。

6)同為進(jìn)化實(shí)例選擇算法，相較于IFS-CoCo，GIS能在較小的迭代評(píng)估次數(shù)下獲得較優(yōu)且穩(wěn)定的分類精度。

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

表2 4種算法分類精度實(shí)驗(yàn)結(jié)果 %

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

表3 分類精度威爾科克森符號(hào)秩和檢驗(yàn)

綜合以上分析，GIS算法分類精度優(yōu)于其他三種對(duì)比算法。使用C4.5與遺傳算法相結(jié)合的二階段篩選機(jī)制，也優(yōu)于不進(jìn)行實(shí)例選擇、使用C4.5進(jìn)行實(shí)例選擇。

4.2 AUC和Kappa結(jié)果及分析

在3.1節(jié)實(shí)驗(yàn)條件下，4個(gè)算法的AUC(二類數(shù)據(jù)集)、Kappa(多類數(shù)據(jù)集)對(duì)比實(shí)驗(yàn)結(jié)果(AUC或Kappa +標(biāo)準(zhǔn)差、每個(gè)數(shù)據(jù)集最優(yōu)AUC或Kappa為粗體)如表4所示。

表4 4種算法AUC或Kappa實(shí)驗(yàn)結(jié)果 %

GIS算法與其他三個(gè)對(duì)比算法在AUC或Kappa上的威爾克森秩和檢驗(yàn)結(jié)果如表5所示。

表5 AUC和Kappa威爾科克森符號(hào)秩和檢驗(yàn)

由表5實(shí)驗(yàn)數(shù)據(jù)得：

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

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在數(shù)據(jù)集Tic、Saheart、Titanic、Haberman有較大的AUC損失(低于KNN5%以上)。IFS-CoCo在數(shù)據(jù)集Tic、Pima、Spectfhear、Banana、Vowel有較大的AUC和Kappa損失。

由表4實(shí)驗(yàn)數(shù)據(jù)得：每一組對(duì)比實(shí)驗(yàn)，P-value均小于常規(guī)的顯著水平，可以證明GIS在AUC和Kappa上優(yōu)于其他對(duì)比算法。

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

5 討論

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

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

在3.1節(jié)實(shí)驗(yàn)條件下，對(duì)遺傳算法策略驗(yàn)證的實(shí)驗(yàn)結(jié)果如表6(分類精度+標(biāo)準(zhǔn)差、最優(yōu)分類精度為粗體)和圖5所示，由實(shí)驗(yàn)數(shù)據(jù)可知：

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

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

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

圖5 遺傳算法策略驗(yàn)證

NVS+MSE策略與其他策略在分類精度上的威爾克森秩和檢驗(yàn)結(jié)果如表7所示，其中MSE vs CEPT測(cè)試是在屏蔽掉NVS的對(duì)比測(cè)試即RVS+MSE vs RVS+CEPT，同樣的NVS vs RVS屏蔽了MSE。由實(shí)驗(yàn)數(shù)據(jù)可知：

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

2)在NVS vs RVS實(shí)驗(yàn)中，R+與R-的差值為117，且P-value小于常規(guī)顯著水平，說(shuō)明NVS相對(duì)于RVS對(duì)分類精度有較顯著的提升。

3)NVS+MSE策略對(duì)比其他的策略，P-value均遠(yuǎn)小于常規(guī)顯著水平。

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

5.2 算法時(shí)間復(fù)雜度討論

面向KNN的進(jìn)化訓(xùn)練集選擇算法主要的時(shí)間消耗來(lái)源于每次進(jìn)化迭代過(guò)程中對(duì)適應(yīng)度的計(jì)算。IFS-CoCo采用協(xié)同進(jìn)化的方式同時(shí)進(jìn)行實(shí)例選擇(Instance Selection, IS)、特征選擇(Feature Selection, FS)及實(shí)例和特征選擇(Instance and Feature Selection, IFS)。每次迭代需要計(jì)算三個(gè)適應(yīng)度(IS、FS、IFS分別的適應(yīng)度)。 它不引進(jìn)驗(yàn)證集，直接使用原始的訓(xùn)練集進(jìn)行訓(xùn)練，所以每次計(jì)算適應(yīng)度的時(shí)間復(fù)雜度為

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

雖然GIS的時(shí)間復(fù)雜度高于PRKNN，但由第4章的實(shí)驗(yàn)結(jié)果可知GIS在分類精度、AUC和Kappa及分類效果的穩(wěn)定性上遠(yuǎn)優(yōu)于PRKNN。

6 結(jié)語(yǔ)

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

表6 5種遺傳算法策略的分類精度實(shí)驗(yàn)結(jié)果 %

表7 遺傳算法策略威爾克森秩和檢驗(yàn)

經(jīng)驗(yàn)證GIS 綜合性能優(yōu)于傳統(tǒng)KNN、PRKNN、IFS-CoCo等算法，NSV+MSE也優(yōu)于傳統(tǒng)的遺傳實(shí)例選擇策略。

GIS未來(lái)的研究方向如下：1)GIS算法的兩個(gè)關(guān)鍵參數(shù)k和α均需要手動(dòng)設(shè)置，可以將它們改成自適應(yīng)的形式以提高算法的智能性；2)在對(duì)噪聲區(qū)進(jìn)行實(shí)例選擇時(shí)，可以不局限于樣本的選擇，可以擴(kuò)展到特征選擇。樣本選擇與特征選擇相結(jié)合或許能進(jìn)一步提升分類精度；3)使用新的遺傳算法代替原始的遺傳算法進(jìn)實(shí)例選擇。