EM-KNN算法在復烤煙葉分類上的運用

張　慧，侯開虎，周　洲

（昆明理工大學，機電工程學院，云南 昆明　650000）

0　引言

K-近鄰（K-Nearest Neighbor，KNN）算法機器學習中解決分類問題的常用方法之一，KNN算法最早是由Cover和Hart在20世紀六十年代提出，在理論上算比較成熟的分類方法。KNN算法的分類原理是通過與分類對象最近的訓練樣本k來實現分類k一般選擇大于 3的任意數，樣本之間的空間距離一般采用 Euclidean 距離的計量方式，所要分類的對象以k個樣本為依據分類[1]。KNN算法省去了需要預先建立模型的步驟，與其他的機器學習算法相比具有簡單高效、不需要進行訓練等優點，在分類問題上被廣泛使用[2-5]。但傳統的KNN算法依然存在很多的不足：在計算時儲存參與計算的每一個樣本，耗費了極大的儲存空間[6]；KNN的計算原理決定了待分類樣本要與每一個樣本進行距離的計算，其計算量大；由于樣本的分配不均衡問題，可能造成分類結果失準[7]；需要通過計算不同的 k值的預測能力來選擇不同的k值，算法對不同k值的響應較靈敏，一般使用較小的k值，因此，在進行KNN算法前要確定一個確定k的值，多數情況下是由經驗選擇[8]。

為了解決KNN算法存在的問題，對KNN算法的優化一直是許多學者關注的問題，主要從兩個角度進行優化，原始KNN算法得出的k個最近樣本中是以少數服從多數的思想確定被分類樣本的類別，就會存在一些干擾樣本導致了分類的不精確，所以優化 KNN算法的第一個角度是對所給樣本進行剪枝，樊存佳等人[9]采用改進了的 K-Medoids聚類算法對分類中貢獻度低但影響分類結果的樣本進行裁剪，定義了度函數對測試文本的最近鄰文本進行有差別的處理，以此提高了KNN算法的計算速度和分類準確度，但這種方法有可能會過度裁剪；余鷹等人[10]通過引入變精度粗糙集模型，將訓練樣本劃分為核心數據塊和邊界數據塊，以此減小分類的干擾，增強 KNN算法的魯棒性，該算法更適用于球狀數據；耿麗娟等人[11]提出對樣本進行分層分類，最后一層的決策采用差分的方法，并用實例證明該方法在大數據分類下的有效性；嚴曉明等人[12]提出了類別平均距離的加權KNN算法，采用所屬類別的平均距離與待分類樣本和訓練樣本的距離差值比，大于設定的閾值，就將此樣本從原樣本中剔除。原始的KNN算法采用歐氏距離計算樣本的距離，忽略了樣本數據特征指標之間的相關性，歐氏距離的計算是基于所有的特征指標，然而在分類時實例也包含了與分類不相關的屬性，這時歐式距離分類就會變得不準確，第二個優化的角度就是針對樣本數據之間的距離進行優化，謝紅等[13]提出的基于卡方距離的KNN算法，并采用靈敏度對指標賦權，克服了歐式距離的不足；肖輝輝等[14]將歐氏距離測量改為基于特征指標相關距離，有效的度量了樣本之間的相似度；另外曾俊杰等在[15]提出基于馬氏距離、王幫軍等[16]提出基于改進協方差特征的 KNN算法，許杞剛等[17]采用多項式函數與歐氏距離相結合的方法進行距離度量。

本文是在上述研究的基礎之上，考慮到各種距離方法在 KNN算法的計算上沒有考慮過分類特征指標的權重問題，因此本文加入了特征指標的熵值法賦權對KNN算法進行改進，提出了EM-KNN算法，并且在基于python語言的Jupyter Notebook交互式 WEB端對復烤煙葉按化學成分的分類問題上運用 EM-KNN分類算法分析，并檢驗算法的合理性，突出改進的算法在提高復烤煙葉的分類精度上，優勝于傳統的KNN分類算法。

1　KNN算法

KNN算法的工作原理是：存在一個已經知道所屬分類的訓練樣本集，輸入待分類樣本，計算待分類樣本與訓練樣本集中每一個訓練樣本之間的距離，然后算法提取與待分類樣本最近鄰的k個樣本，一般只取最相近的前k個數據，一般2

1.1　距離度量

KNN算法中關鍵的就是計算待分類樣本與訓練樣本的距離，本文中所涉及到常用的距離度量方法有歐式距離、曼哈頓距離、閔可夫斯基距離[19]。設存在兩個 n維向量 X，Y，令 X=(X1,X2,…, Xn)，Y=(Y1,Y2,…, Yn)，各種距離度量公式如下所示：

（1）Euclidean距離

歐氏距離全稱為歐幾里得距離， X,Y的歐氏距離定義為：

（2）Manhattan距離

曼哈頓距離，又稱城市距離，X,Y的曼哈頓距離定義為：

（3）Chebyshev距離

切比雪夫距離，X,Y的切比雪夫距離定義為：

2　熵值法賦權的KNN算法

設有m個數據樣本，n個樣本特征指標，有數據矩陣 M =( aij)m×n，信息論中，信息熵是系統無序程度的度量，信息是有序程度的度量，數值上二者互為相反數，樣本中的某一特質指標的信息熵越大，表明該指標為決策所提供的信息量越小，相對應的權重越小，相對地，某一指標的信息熵越小，則該指標提供的信息量越大，權重就越大[20]。

熵值法的計算步驟是：

2.1　熵值法

（1）第j項指標下的第i個樣本數據占j指標下總體樣本的比重tij

（2）計算第j項指標的信息熵hj

（3）計算第j項指標的熵值ej

熵值法賦權屬于客觀賦權方法的一種，有效的避免了主觀隨意性對指標重要性的影響，所賦權值的大小是依據樣本數據的分散情況而來，有較強的理論依據，但也存在如果數據之間跨度太大，其賦權結果與指標客觀反應存在一定的差距，在本論文中的數據樣本波動不大，不影響給樣本的特征指標賦權，因此本文宜采用熵值法給樣本特征指標賦權[21]。

2.2　改進的KNN算法

基于傳統的 KNN分類算法的基礎上，考慮到傳統的 KNN算法忽略了各個特征指標對分類結果的信息貢獻程度不同，在傳統的算法步驟中加入了熵值法給特征指標賦權，使分類算法更精確。

改進的KNN分類算法的步驟如下：

（1）創建樣本數據集，設數據集為S，Xi為訓練樣本集，i∈ [1 ,…, m ]，數據集中包含 n個不同的分類類別，Yi為測試樣本，i∈ [1 ,…, t ]每一個訓練樣本中包含m個特征指標。用熵值法計算樣本數據的特征屬性權重，賦權過程按照公式（4）-（8）的方式進行。

（2）給KNN算法中的k設定一個初值。

（3）用改進的距離度量公式計算每個測試樣本和訓練樣本的距離，如特征賦權的歐氏距離公式為：

（4）對計算出的距離進行排序，選取距離待分類樣本最近的k個訓練樣本。

（5）按照所選擇的k個訓練樣本所屬的類別，以k個樣本中占比最大的樣本作為待分類樣本的類別。

（6）根據待分類樣本的分類結果，與實際的所屬類別對比，計算分類器的準確率，計算準確率的公式為：

式中：B為分類準確的測試樣本數，C為測試樣本總數。

3　實例驗證

本文通過數據驗證所改進的算法的準確性，在Jupyter Notebook交互式WEB端用python編寫KNN分類算法器，將數據集導入分類器中，選取不同的K值對數據進行驗證，整個驗證過程分為兩個部分，第一個部分采用原始的KNN算法對數據進行驗證，分別用歐氏距離、標準化歐氏距離、曼哈頓距離、切比雪夫距離對待分類樣本與訓練樣本的相似度進行度量，并計算出不同K值下分類的準確率。第二部分使用改進后的KNN算法，再分別對距離度量公式進行測試，將計算得到的不同K值下的準確率與第一個部分的結果進行比較，最后分析實驗結果。

3.1　實驗數據

本文采用的數據樣本是某煙葉復烤廠對復烤煙葉化學成分分析得到的數據，總的數據量是 749，分析的主要化學成分為尼古丁、總糖、還原糖、總氮、K、CL，也就是數據樣本的特征指標數為 6，一共分為5個類，部分實驗數據如表1所示，選擇數據總量的1/3作為測試樣本，其余的2/3作為訓練樣本。

表1　實驗數據部分示例Tab.1　Example of experimental data

3.2　對比分析

為了驗證改進 KNN分類算法的有效性，驗證過程中改變K值，分別用幾種常見的距離度量公式度量樣本之間的距離，驗證過程中，每一個距離公式測試了10次，為了比較三種距離公式在復烤煙依據化學成分分類的效果，取10次驗證的平均值，如表2所示。

從表2中可以看出，使用改進的基于三種距離度量方式 KNN分類算法在分類準確率上大致都得到了提高，在基于歐氏距離的KNN算法中效果最明顯，準確率提升幅度最大的是當K=3時的基于歐氏距離的 KNN算法，說明改進的 KNN算法在提升KNN分類精確度上有很好的效果。無論是原始的KNN算法還是改進后的KNN算法，使用切比雪夫距離公式度量的分類精確率遠遠小于其他兩種， 對于其他兩種距離度量，選擇K值為3或者5時，分類效果最佳。

為了更直觀的評價改進KNN算法的分類效果，分別繪制了K取不同值的分類準確率折線圖，由表2得出切比雪夫距離在此樣本中的分類準確率太低，因此在下面的分析中只對歐氏距離和曼哈頓距離作比較。當k=3時，實驗結果如圖1所示；當k=5時，實驗結果如圖2所示；當k=8時，實驗結果如圖3所示。

表2　不同距離公式、不同K值的測試精確率（%）Tab.2　Test accuracy of different distance formulas and different K values (%)

圖1　K值為3時結果準確率折線圖Fig.1 Curve of the accuracy of the results when the K value is 3

由圖1-圖3可以看出在復烤煙葉依據化學成分分類的數據樣本中，采用曼哈頓（Manhattan）距離公式的傳統 KNN分類算法分類準確率總體優于基于歐氏距離（Euclidean）的算法，通過加入熵值法特征向量賦權后，兩種距離公式算法的分類準確度都大大的提升了，歐氏距離KNN分類算法提高效果尤為顯著，圖1和圖2顯示出改進的Euclidean KNN算法在 10次的分類測試中準確率均高于傳統的算法。算法未改進之前，兩類度量距離算法在10次分類驗證中結果準確率起伏較大，改進后，其分類準確率不僅得到了提高，其數據的平穩度也得到了提高，當K=5或K=8時改進效果較明顯。

圖2　K值為5時結果準確率折線圖Fig.2 Curve of the accuracy of the results when the K value is 5

3.3　實驗結果

圖3　K值為8時結果準確率折線圖Fig.3　Curve of the accuracy of the results when the K value is 8

通過改進后的KNN算法與傳統的KNN算法對復烤煙葉依據化學成分的分類中看出，改進后的KNN算法在分類精度上得到了很大的提升。在KNN算法中，K值的選取對分類的效果有直接的影響，小的K值會導致為待分類樣本提供的信息太少而影響分類精度，由于KNN算法對待測樣本的分類實行“少數服從多數”的原則，所以太大的K值會導致決定權掌握在選取的訓練樣本中的“多數”手中，也會出現不合理的分類，從圖1-圖3中可以看出，當K=3時，分類準確度失衡幅度最大，當K=8時次之，當K=5時，改進后的KNN算法的分類準確率起伏不大，較為平穩。由此可以得出，在對復烤煙葉依據化學成分的分類中，使用改進的基于歐氏距離的KNN算法中，當選取K=5，其分類效果最佳。

4　結論

在KNN分類算法中，傳統的KNN算法采用歐氏距離對樣本之間的距離進行度量，由于數據樣本的不同，每一個樣本的特征指標在決定所屬類別時提供的信息往往是不一樣的，分類結果往往與實際相差甚遠，因此本文提出一種基于熵值法對特征指標賦予權重的KNN分類算法（ME-KNN），通過分類準確度衡量分類效果，并在復烤煙葉依據化學成分的分類數據樣本中進行分類算法的測試，結果顯示ME-KNN算法分類效果得到了很大的提升，通過對三種分類距離公式的測試，在本文采用的數據樣本中基于歐式距離的ME-KNN算法分類效果最佳。