基于EDA的加權KNN分類算法＊

謝雨寒，潘 峰,2

(1.貴州民族大學數據科學與信息工程學院，貴州 貴陽 550025；2.貴州民族大學模式識別與智能系統重點實驗室)

0 引言

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

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

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

本文提出一種基于EDA 改進的加權KNN 算法，目的是克服遺傳算法的不足之處，同時，利用EDA 對整個群體在宏觀層面上構建概率模型的特點，進一步考慮到不平衡數據集的樣本各項特征的具體信息，改進特征權重的分配方式，提高加權KNN算法分類的穩定性和準確率。

1 加權的KNN算法

1.1 基本KNN算法

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

新數據Y與某個訓練樣本的相似度通常使用如下的歐氏距離公式計算：

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

1.2 權重的分配

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

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

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

2 EDA-KNN算法

EDA 的基本思想是從當前種群中選取部分優勢群體，并利用這些優勢群體估計和學習種群的分布，建立概率模型，然后對該概率模型隨機采樣，產生新一代種群，如此操作，逐次迭代，逐漸逼近最優解。

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

2.1 矩陣結構種群

本文的EDA 采用了二維關系構建矩陣結構的種群，即運用了二維數組，數組中每個元素對應種群中一個個體，代表一個可能解。這樣的二維關系，使得種群可以被視為由多個一維子種群組成，便于將各個子種群進行獨立的查找最優構成優勢子群，無需排序操作。文獻[9]采用將各行最優置于主對角線，本文將各行最優置于第一列，如圖1 到圖2 所示，灰度標識行中最優個體。

圖1 矩陣結構種群

圖2 首列最優的矩陣結構種群

2.2 適應度評價

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

運用加入權重{w1,w2,…,wn}的KNN 算法執行對訓練樣本集X的分類，并將分類準確率fi,j(w)作為個體a(i,j)的適應度，適應度越高的個體越占優。

2.3 算法步驟

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

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

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

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

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

3 實驗仿真與分析

3.1 實驗環境

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

3.2 測試數據集

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

表1 數據集樣本分布信息

3.3 實驗結果

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

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

圖3 Sonar分類結果

圖4 Sonar分類收斂性

圖5 Cleveland分類結果

圖6 Cleveland分類收斂性

圖7 Winequality分類結果

圖8 Winequality分類收斂性

由此可見，EDA-KNN 執行數據分類的性能遠優于基本KNN，并且在處理不平衡數據集時，分類的穩定性和準確率都比GA-KNN更具優勢。

4 結束語

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