張　慧，侯開虎，周　洲

（昆明理工大學(xué)，機(jī)電工程學(xué)院，云南 昆明　650000）

0　引言

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

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

本文是在上述研究的基礎(chǔ)之上，考慮到各種距離方法在 KNN算法的計(jì)算上沒有考慮過(guò)分類特征指標(biāo)的權(quán)重問(wèn)題，因此本文加入了特征指標(biāo)的熵值法賦權(quán)對(duì)KNN算法進(jìn)行改進(jìn)，提出了EM-KNN算法，并且在基于python語(yǔ)言的Jupyter Notebook交互式 WEB端對(duì)復(fù)烤煙葉按化學(xué)成分的分類問(wèn)題上運(yùn)用 EM-KNN分類算法分析，并檢驗(yàn)算法的合理性，突出改進(jìn)的算法在提高復(fù)烤煙葉的分類精度上，優(yōu)勝于傳統(tǒng)的KNN分類算法。

1　KNN算法

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

1.1　距離度量

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

（1）Euclidean距離

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

（2）Manhattan距離

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

（3）Chebyshev距離

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

2　熵值法賦權(quán)的KNN算法

設(shè)有m個(gè)數(shù)據(jù)樣本，n個(gè)樣本特征指標(biāo)，有數(shù)據(jù)矩陣 M =( aij)m×n，信息論中，信息熵是系統(tǒng)無(wú)序程度的度量，信息是有序程度的度量，數(shù)值上二者互為相反數(shù)，樣本中的某一特質(zhì)指標(biāo)的信息熵越大，表明該指標(biāo)為決策所提供的信息量越小，相對(duì)應(yīng)的權(quán)重越小，相對(duì)地，某一指標(biāo)的信息熵越小，則該指標(biāo)提供的信息量越大，權(quán)重就越大[20]。

熵值法的計(jì)算步驟是：

2.1　熵值法

（1）第j項(xiàng)指標(biāo)下的第i個(gè)樣本數(shù)據(jù)占j指標(biāo)下總體樣本的比重tij

（2）計(jì)算第j項(xiàng)指標(biāo)的信息熵hj

（3）計(jì)算第j項(xiàng)指標(biāo)的熵值ej

熵值法賦權(quán)屬于客觀賦權(quán)方法的一種，有效的避免了主觀隨意性對(duì)指標(biāo)重要性的影響，所賦權(quán)值的大小是依據(jù)樣本數(shù)據(jù)的分散情況而來(lái)，有較強(qiáng)的理論依據(jù)，但也存在如果數(shù)據(jù)之間跨度太大，其賦權(quán)結(jié)果與指標(biāo)客觀反應(yīng)存在一定的差距，在本論文中的數(shù)據(jù)樣本波動(dòng)不大，不影響給樣本的特征指標(biāo)賦權(quán)，因此本文宜采用熵值法給樣本特征指標(biāo)賦權(quán)[21]。

2.2　改進(jìn)的KNN算法

基于傳統(tǒng)的 KNN分類算法的基礎(chǔ)上，考慮到傳統(tǒng)的 KNN算法忽略了各個(gè)特征指標(biāo)對(duì)分類結(jié)果的信息貢獻(xiàn)程度不同，在傳統(tǒng)的算法步驟中加入了熵值法給特征指標(biāo)賦權(quán)，使分類算法更精確。

改進(jìn)的KNN分類算法的步驟如下：

（1）創(chuàng)建樣本數(shù)據(jù)集，設(shè)數(shù)據(jù)集為S，Xi為訓(xùn)練樣本集，i∈ [1 ,…, m ]，數(shù)據(jù)集中包含 n個(gè)不同的分類類別，Yi為測(cè)試樣本，i∈ [1 ,…, t ]每一個(gè)訓(xùn)練樣本中包含m個(gè)特征指標(biāo)。用熵值法計(jì)算樣本數(shù)據(jù)的特征屬性權(quán)重，賦權(quán)過(guò)程按照公式（4）-（8）的方式進(jìn)行。

（2）給KNN算法中的k設(shè)定一個(gè)初值。

（3）用改進(jìn)的距離度量公式計(jì)算每個(gè)測(cè)試樣本和訓(xùn)練樣本的距離，如特征賦權(quán)的歐氏距離公式為：

（4）對(duì)計(jì)算出的距離進(jìn)行排序，選取距離待分類樣本最近的k個(gè)訓(xùn)練樣本。

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

（6）根據(jù)待分類樣本的分類結(jié)果，與實(shí)際的所屬類別對(duì)比，計(jì)算分類器的準(zhǔn)確率，計(jì)算準(zhǔn)確率的公式為：

式中：B為分類準(zhǔn)確的測(cè)試樣本數(shù)，C為測(cè)試樣本總數(shù)。

3　實(shí)例驗(yàn)證

本文通過(guò)數(shù)據(jù)驗(yàn)證所改進(jìn)的算法的準(zhǔn)確性，在Jupyter Notebook交互式WEB端用python編寫KNN分類算法器，將數(shù)據(jù)集導(dǎo)入分類器中，選取不同的K值對(duì)數(shù)據(jù)進(jìn)行驗(yàn)證，整個(gè)驗(yàn)證過(guò)程分為兩個(gè)部分，第一個(gè)部分采用原始的KNN算法對(duì)數(shù)據(jù)進(jìn)行驗(yàn)證，分別用歐氏距離、標(biāo)準(zhǔn)化歐氏距離、曼哈頓距離、切比雪夫距離對(duì)待分類樣本與訓(xùn)練樣本的相似度進(jìn)行度量，并計(jì)算出不同K值下分類的準(zhǔn)確率。第二部分使用改進(jìn)后的KNN算法，再分別對(duì)距離度量公式進(jìn)行測(cè)試，將計(jì)算得到的不同K值下的準(zhǔn)確率與第一個(gè)部分的結(jié)果進(jìn)行比較，最后分析實(shí)驗(yàn)結(jié)果。

3.1　實(shí)驗(yàn)數(shù)據(jù)

本文采用的數(shù)據(jù)樣本是某煙葉復(fù)烤廠對(duì)復(fù)烤煙葉化學(xué)成分分析得到的數(shù)據(jù)，總的數(shù)據(jù)量是 749，分析的主要化學(xué)成分為尼古丁、總糖、還原糖、總氮、K、CL，也就是數(shù)據(jù)樣本的特征指標(biāo)數(shù)為 6，一共分為5個(gè)類，部分實(shí)驗(yàn)數(shù)據(jù)如表1所示，選擇數(shù)據(jù)總量的1/3作為測(cè)試樣本，其余的2/3作為訓(xùn)練樣本。

表1　實(shí)驗(yàn)數(shù)據(jù)部分示例Tab.1　Example of experimental data

3.2　對(duì)比分析

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

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

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

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

圖1　K值為3時(shí)結(jié)果準(zhǔn)確率折線圖Fig.1 Curve of the accuracy of the results when the K value is 3

由圖1-圖3可以看出在復(fù)烤煙葉依據(jù)化學(xué)成分分類的數(shù)據(jù)樣本中，采用曼哈頓（Manhattan）距離公式的傳統(tǒng) KNN分類算法分類準(zhǔn)確率總體優(yōu)于基于歐氏距離（Euclidean）的算法，通過(guò)加入熵值法特征向量賦權(quán)后，兩種距離公式算法的分類準(zhǔn)確度都大大的提升了，歐氏距離KNN分類算法提高效果尤為顯著，圖1和圖2顯示出改進(jìn)的Euclidean KNN算法在 10次的分類測(cè)試中準(zhǔn)確率均高于傳統(tǒng)的算法。算法未改進(jìn)之前，兩類度量距離算法在10次分類驗(yàn)證中結(jié)果準(zhǔn)確率起伏較大，改進(jìn)后，其分類準(zhǔn)確率不僅得到了提高，其數(shù)據(jù)的平穩(wěn)度也得到了提高，當(dāng)K=5或K=8時(shí)改進(jìn)效果較明顯。

圖2　K值為5時(shí)結(jié)果準(zhǔn)確率折線圖Fig.2 Curve of the accuracy of the results when the K value is 5

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

圖3　K值為8時(shí)結(jié)果準(zhǔn)確率折線圖Fig.3　Curve of the accuracy of the results when the K value is 8

通過(guò)改進(jìn)后的KNN算法與傳統(tǒng)的KNN算法對(duì)復(fù)烤煙葉依據(jù)化學(xué)成分的分類中看出，改進(jìn)后的KNN算法在分類精度上得到了很大的提升。在KNN算法中，K值的選取對(duì)分類的效果有直接的影響，小的K值會(huì)導(dǎo)致為待分類樣本提供的信息太少而影響分類精度，由于KNN算法對(duì)待測(cè)樣本的分類實(shí)行“少數(shù)服從多數(shù)”的原則，所以太大的K值會(huì)導(dǎo)致決定權(quán)掌握在選取的訓(xùn)練樣本中的“多數(shù)”手中，也會(huì)出現(xiàn)不合理的分類，從圖1-圖3中可以看出，當(dāng)K=3時(shí)，分類準(zhǔn)確度失衡幅度最大，當(dāng)K=8時(shí)次之，當(dāng)K=5時(shí)，改進(jìn)后的KNN算法的分類準(zhǔn)確率起伏不大，較為平穩(wěn)。由此可以得出，在對(duì)復(fù)烤煙葉依據(jù)化學(xué)成分的分類中，使用改進(jìn)的基于歐氏距離的KNN算法中，當(dāng)選取K=5，其分類效果最佳。

4　結(jié)論

在KNN分類算法中，傳統(tǒng)的KNN算法采用歐氏距離對(duì)樣本之間的距離進(jìn)行度量，由于數(shù)據(jù)樣本的不同，每一個(gè)樣本的特征指標(biāo)在決定所屬類別時(shí)提供的信息往往是不一樣的，分類結(jié)果往往與實(shí)際相差甚遠(yuǎn)，因此本文提出一種基于熵值法對(duì)特征指標(biāo)賦予權(quán)重的KNN分類算法（ME-KNN），通過(guò)分類準(zhǔn)確度衡量分類效果，并在復(fù)烤煙葉依據(jù)化學(xué)成分的分類數(shù)據(jù)樣本中進(jìn)行分類算法的測(cè)試，結(jié)果顯示ME-KNN算法分類效果得到了很大的提升，通過(guò)對(duì)三種分類距離公式的測(cè)試，在本文采用的數(shù)據(jù)樣本中基于歐式距離的ME-KNN算法分類效果最佳。