基于EDA的加權(quán)KNN分類算法＊

謝雨寒，潘 峰,2

(1.貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院，貴州 貴陽 550025；2.貴州民族大學(xué)模式識別與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室)

0 引言

機(jī)器學(xué)習(xí)中的分類算法有K 近鄰（K-Nearest Neighbor，KNN）算法[1]、樸素貝葉斯、決策樹和支持向量機(jī)等[2]。分類算法通常假設(shè)訓(xùn)練樣本均勻分布在不同的類別中，而實(shí)際應(yīng)用中普遍是不平衡數(shù)據(jù)集，即存在部分類別對應(yīng)的樣本數(shù)量比另一部分類別少[3]。傳統(tǒng)分類器應(yīng)用于不平衡數(shù)據(jù)集分類時(shí)，會使得分類結(jié)果向多數(shù)類傾斜，出現(xiàn)多數(shù)類通常具有較高的準(zhǔn)確率，反之少數(shù)類普遍準(zhǔn)確率較低，從而導(dǎo)致分類整體性能下降[4]。盡管相較于樸素貝葉斯和支持向量機(jī)等，KNN 在處理不平衡數(shù)據(jù)集的分類問題上更具優(yōu)勢，但整體性能依然不好。

Songbo Tan 提出了基于權(quán)重的KNN 算法，為屬于多數(shù)類的近鄰樣本分配較小的權(quán)重，而少數(shù)類的近鄰樣本分配較大的權(quán)重[4]。郝秀蘭等提出了一種自適應(yīng)的加權(quán)KNN分類方法，定義樣本訓(xùn)練集臨界點(diǎn)這一概念，考慮了各類別樣本的具體數(shù)量，但是沒有進(jìn)一步考慮樣本的分布信息。而對于分類方法來說，分布信息是影響性能的重要因素[5]。王超學(xué)等在此基礎(chǔ)上提出一種加權(quán)KNN 算法GAK-KNN，定義了新的權(quán)重分配模型，根據(jù)不同類別間不平衡和不均勻的分布信息對各訓(xùn)練樣本分配相應(yīng)的權(quán)重，并運(yùn)用基于遺傳算法改進(jìn)的KNN算法對樣本進(jìn)行分類[6]。

遺傳算法通過選擇、交叉和變異等操作產(chǎn)生下一代，但交叉、變異算子不具備學(xué)習(xí)和識別樣本間連鎖關(guān)系的能力，在實(shí)際的選擇和重組過程中容易導(dǎo)致數(shù)據(jù)結(jié)構(gòu)塊被破壞，使得算法早熟或陷入局部最優(yōu)解。而分布估計(jì)算法（Estimation of Distribution Algorithm，EDA）[7]采用了完全不同的進(jìn)化模式，采用統(tǒng)計(jì)學(xué)習(xí)方式建立概率模型用于描述候選解的分布，再通過對概率模型進(jìn)行隨機(jī)采樣產(chǎn)生新種群，取代了遺傳算法傳統(tǒng)的交叉、變異過程，因此不容易導(dǎo)致局部收斂的問題。

本文提出一種基于EDA 改進(jìn)的加權(quán)KNN 算法，目的是克服遺傳算法的不足之處，同時(shí)，利用EDA 對整個(gè)群體在宏觀層面上構(gòu)建概率模型的特點(diǎn)，進(jìn)一步考慮到不平衡數(shù)據(jù)集的樣本各項(xiàng)特征的具體信息，改進(jìn)特征權(quán)重的分配方式，提高加權(quán)KNN算法分類的穩(wěn)定性和準(zhǔn)確率。

1 加權(quán)的KNN算法

1.1 基本KNN算法

KNN 算法的基本思想：對于給定的一個(gè)待分類的測試樣本，先搜索最接近該測試樣本的K個(gè)已知類別的訓(xùn)練樣本，即K個(gè)最近鄰；然后統(tǒng)計(jì)K個(gè)最近鄰，如果屬于某一類別的近鄰數(shù)量最多，則將這個(gè)測試樣本判定為該類。

新數(shù)據(jù)Y與某個(gè)訓(xùn)練樣本的相似度通常使用如下的歐氏距離公式計(jì)算：

其中，d(Y,Xi)表示Y與Xi的歐式距離為第i個(gè)訓(xùn)練樣本Xi的第l個(gè)特征屬性值。

1.2 權(quán)重的分配

為了更加確切地描述樣本間的相似度，需要進(jìn)一步考慮各屬性之間內(nèi)在的性質(zhì)和聯(lián)系，并對其重要性進(jìn)行區(qū)分。因此根據(jù)每個(gè)屬性的重要程度賦予一個(gè)相應(yīng)的權(quán)重，引入權(quán)重值wl(l=1,2,…,n)，將加權(quán)的歐氏距離表示為[8]：

加權(quán)歐氏距離能更準(zhǔn)確地反映出各屬性對于樣本的不同作用，使分類算法獲得更好的結(jié)果。但如何選取合適的權(quán)重涉及數(shù)據(jù)的實(shí)際意義，需要對各屬性的具體效果有深入的了解，而在實(shí)際的操作中難以達(dá)到這一要求。

因此，在沒有先驗(yàn)知識的前提下，將與樣本對應(yīng)的多種的權(quán)重wl取值情況視為求解內(nèi)容，通過EDA多次迭代獲得最優(yōu)的權(quán)重向量，使加權(quán)KNN算法分類效果達(dá)到最佳。

2 EDA-KNN算法

EDA 的基本思想是從當(dāng)前種群中選取部分優(yōu)勢群體，并利用這些優(yōu)勢群體估計(jì)和學(xué)習(xí)種群的分布，建立概率模型，然后對該概率模型隨機(jī)采樣，產(chǎn)生新一代種群，如此操作，逐次迭代，逐漸逼近最優(yōu)解。

對于加權(quán)的KNN算法，其實(shí)際分類效果關(guān)鍵取決于選取的權(quán)重，而EDA 具備構(gòu)建概率模型這一特點(diǎn)，使其能夠宏觀地描述樣本特征的分布信息。EDAKNN 算法的目的是將不同的權(quán)重取值作為不同個(gè)體的編碼構(gòu)建種群，更加準(zhǔn)確地針對測試樣本分配各項(xiàng)特征的權(quán)重值，并通過多次迭代獲得分類準(zhǔn)確率最高的個(gè)體，提高分類算法的性能。

2.1 矩陣結(jié)構(gòu)種群

本文的EDA 采用了二維關(guān)系構(gòu)建矩陣結(jié)構(gòu)的種群，即運(yùn)用了二維數(shù)組，數(shù)組中每個(gè)元素對應(yīng)種群中一個(gè)個(gè)體，代表一個(gè)可能解。這樣的二維關(guān)系，使得種群可以被視為由多個(gè)一維子種群組成，便于將各個(gè)子種群進(jìn)行獨(dú)立的查找最優(yōu)構(gòu)成優(yōu)勢子群，無需排序操作。文獻(xiàn)[9]采用將各行最優(yōu)置于主對角線，本文將各行最優(yōu)置于第一列，如圖1 到圖2 所示，灰度標(biāo)識行中最優(yōu)個(gè)體。

圖1 矩陣結(jié)構(gòu)種群

圖2 首列最優(yōu)的矩陣結(jié)構(gòu)種群

2.2 適應(yīng)度評價(jià)

權(quán)重的取值范圍為[0,1]，權(quán)重值為0 則表示對應(yīng)的屬性不影響分類結(jié)果，權(quán)重值越大則表示對應(yīng)的屬性越重要。本文采用十進(jìn)制編碼的EDA，種群個(gè)體表示為a(i,j),其基因?yàn)閘=1,2,…,n，相應(yīng)的公式⑴的權(quán)重值l=1,2,…,n，以此將權(quán)重值劃分為10 個(gè)等級0.0,1.0/9,2.0/9,…,9.0/9。

運(yùn)用加入權(quán)重{w1,w2,…,wn}的KNN 算法執(zhí)行對訓(xùn)練樣本集X的分類，并將分類準(zhǔn)確率fi,j(w)作為個(gè)體a(i,j)的適應(yīng)度，適應(yīng)度越高的個(gè)體越占優(yōu)。

2.3 算法步驟

Step1初始化矩陣結(jié)構(gòu)種群A(t)(t=0)，由H×(H+1)的個(gè)體構(gòu)成，以a(i,j)表示種群第i行第j列的個(gè)體，i=0,1,…,H?1;j=0,1,…,H；

Step2分別將個(gè)體a(i,j) 對應(yīng)的權(quán)重值w={w1,w2,…,wn}用于對訓(xùn)練樣本集X進(jìn)行分類，獲得每個(gè)個(gè)體的適應(yīng)度fi,j(w)，i=0,1,…,H?1;j=0,1,…,H；

Step3以A0,A1,…,AH?1表示由每一行全部個(gè)體組成的規(guī)模為H+1 的子種群，依次尋找子種群Ai中最優(yōu)個(gè)體a(i,jbest)(0 ≤jbest≤H+1)，并將其賦給對應(yīng)的每行第一個(gè)個(gè)體a(i,0)，i=0,1,…,H?1；

Step4在選出的優(yōu)勢個(gè)體構(gòu)成的種群{a(0,0),a(1,0),…,a(H?1,0)}中尋找最優(yōu)個(gè)體abest，若滿足停止條件，則輸出；

Step5根據(jù)優(yōu)勢種群{a(0,0),a(1,0),…a(H?1,0)}中各項(xiàng)值的分布，獲得概率矩陣P(t)=(pvu(t))n×10,v∈{0,1,...,9},u表示基因位，基于概率矩陣采樣獲得新一代種群A(t+1)，返回Step2。

3 實(shí)驗(yàn)仿真與分析

3.1 實(shí)驗(yàn)環(huán)境

本文程序運(yùn)用Java 語言進(jìn)行編寫，未使用任何第三方軟件包。工作計(jì)算環(huán)境為多核CPU 臺式電腦，其中硬件為：Intel(R) Core(TM) i5-9400F CPU，16.0 GB RAM；軟件為Windows 11（64 bit）+OpenJDK-17，使用IntelliJ IDEA 2022.3集成開發(fā)環(huán)境運(yùn)行。

3.2 測試數(shù)據(jù)集

本文選擇三組UCI 數(shù)據(jù)集檢驗(yàn)EDA-KNN 算法的分類效果，各數(shù)據(jù)集的樣本屬性、類別數(shù)量分布如表1所示。

表1 數(shù)據(jù)集樣本分布信息

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

本文將EDA-KNN 算法、KNN 算法和運(yùn)用矩陣遺傳算法改進(jìn)的GA-KNN 算法[10]用于三個(gè)數(shù)據(jù)集分類結(jié)果比較。GA-KNN 采用二進(jìn)制編碼，即權(quán)重的取值為{0,1}，將各屬性僅判定為對于分類有影響（權(quán)重值為1）和無影響（權(quán)重值為0）。為了降低不平衡數(shù)據(jù)的影響，設(shè)定k=1。設(shè)數(shù)據(jù)集樣本數(shù)為m，訓(xùn)練集X的樣本數(shù)為n，相應(yīng)測試集Y的樣本數(shù)為m-n。每次隨機(jī)從數(shù)據(jù)集中隨機(jī)劃分選擇訓(xùn)練集和測試集，分別運(yùn)用EDA-KNN、GA-KNN 和KNN 算法，對測試樣本進(jìn)行分類，獲得樣本分類的準(zhǔn)確率作為運(yùn)行結(jié)果。

從圖3、圖5 和圖7 可以看出，使用EDA 優(yōu)化的加權(quán)KNN 算法分類比普通KNN 算法分類準(zhǔn)確率提高顯著，同時(shí)EDA-KNN 也比GA-KNN 有所提高；從圖4、圖6 和圖8 可以得出，EDA-KNN 比GA-KNN 在迭代中能夠較快獲得最優(yōu)權(quán)重向量。

圖3 Sonar分類結(jié)果

圖4 Sonar分類收斂性

圖5 Cleveland分類結(jié)果

圖6 Cleveland分類收斂性

圖7 Winequality分類結(jié)果

圖8 Winequality分類收斂性

由此可見，EDA-KNN 執(zhí)行數(shù)據(jù)分類的性能遠(yuǎn)優(yōu)于基本KNN，并且在處理不平衡數(shù)據(jù)集時(shí)，分類的穩(wěn)定性和準(zhǔn)確率都比GA-KNN更具優(yōu)勢。

4 結(jié)束語

提出一種采用矩陣結(jié)構(gòu)種群的EDA，運(yùn)用十進(jìn)制編碼對加權(quán)KNN 的權(quán)重進(jìn)行分級優(yōu)化，構(gòu)成EDAKNN 算法。通過EDA 算法學(xué)習(xí)的特征權(quán)重向量構(gòu)成加權(quán)KNN 算法，提高分類性能，比GA-KNN 算法的收斂速度更快，對于不平衡數(shù)據(jù)集的分類更加穩(wěn)定，不容易過早收斂。后續(xù)將考慮運(yùn)用基于連續(xù)型概率模型的分布估計(jì)算法進(jìn)一步優(yōu)化權(quán)重的分配，使權(quán)重值更加精確，以此提升算法性能；本文主要是針對較小維度和數(shù)據(jù)量不大的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，下一步工作是構(gòu)建并行KNN 分類器，提高對大數(shù)據(jù)集特征權(quán)重的評估響應(yīng)速度，使之具有更實(shí)際和廣泛的應(yīng)用。