一種交叉驗(yàn)證和距離加權(quán)方法改進(jìn)的KNN 算法研究

黃光華， 殷 鋒， 馮九林

(西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 四川 成都 610041)

大數(shù)據(jù)時(shí)代，互聯(lián)網(wǎng)數(shù)據(jù)的爆發(fā)式增長導(dǎo)致數(shù)據(jù)出現(xiàn)了密度高，維度復(fù)雜等一系列數(shù)據(jù)問題，如何有效的對(duì)這些數(shù)據(jù)進(jìn)行歸類存儲(chǔ)已經(jīng)成為信息檢索、數(shù)據(jù)庫管理、數(shù)據(jù)挖掘和數(shù)據(jù)分析等領(lǐng)域亟待解決的關(guān)鍵問題之一.在眾多的分類算法中，KNN算法以適用于樣本容量較大的類域自動(dòng)分類著稱，對(duì)于新時(shí)代背景下涌現(xiàn)出的海量數(shù)據(jù)處理難的問題，KNN算法的上佳表現(xiàn)確實(shí)為業(yè)界稱道.

1 KNN 算法及其缺陷分析

K-最臨近(K -NearestNeighbor)算法[4]是著名的數(shù)據(jù)挖掘分類算法.核心思想是在向量空間模型中進(jìn)行決策歸類分析，將一個(gè)待分類對(duì)象視作一個(gè)n維向量，將其放入一個(gè)特征空間中，這個(gè)特征空間由m個(gè)已經(jīng)訓(xùn)練好的特征向量構(gòu)成，這m個(gè)特征向量屬于多個(gè)不同的類別集ε∈ (1，2，3…，η)，設(shè)該待分類對(duì)象和向量空間中的m個(gè)特征向量的距離為D=(D1，D2，D3，…Dm) ，給定一個(gè)基準(zhǔn)k，從D中按照從小到大的順序選出k個(gè)值，查看這k個(gè)值分別屬于哪一類數(shù)據(jù)，該待分類對(duì)象最后將被分類至類別出現(xiàn)次數(shù)最多的類中.

在KNN 算法中，歐式距離是被較頻繁使用到的距離度量方法.使用這個(gè)距離，歐氏空間成為度量空間.對(duì)于兩個(gè)n維向量x和y，兩者的歐式距離定義為：

其中， (xi，yi) 為數(shù)據(jù)點(diǎn)i的坐標(biāo)值，D 值為數(shù)據(jù)點(diǎn)i與j之間的距離.

KNN算法的步驟如下：

①輸入一個(gè)待分類數(shù)據(jù)對(duì)象x，計(jì)算它與訓(xùn)練集T中的每個(gè)樣本數(shù)據(jù)對(duì)象的距離，并設(shè)置基準(zhǔn)值k.

②尋找出待分類對(duì)象x與訓(xùn)練集T中的樣本數(shù)據(jù)對(duì)象距離最近的k個(gè)樣本數(shù)據(jù)對(duì)象.

③對(duì)②中尋找到的k個(gè)樣本數(shù)據(jù)對(duì)象在類型集合ε中進(jìn)行類型匹配，找出包含最多個(gè)數(shù)的類.

④將待分?jǐn)?shù)據(jù)x劃分到(3)中包含次數(shù)最多的類中，結(jié)束此次匹配.

KNN算法在大樣本的情況下對(duì)試驗(yàn)樣本有較強(qiáng)的一致性結(jié)果. 但是KNN需要一個(gè)較大的樣本空間來對(duì)數(shù)據(jù)進(jìn)行測(cè)試，算法每一次對(duì)測(cè)試數(shù)據(jù)的分類都是在樣本全局的基礎(chǔ)上進(jìn)行的，這就對(duì)較大的物理內(nèi)存空間產(chǎn)生了必然性要求(用以存放數(shù)據(jù))；且KNN算法在訓(xùn)練數(shù)據(jù)集不平衡時(shí)，即數(shù)據(jù)集中的某一個(gè)類所擁有的數(shù)據(jù)占整個(gè)數(shù)據(jù)集中的數(shù)據(jù)量比例較大時(shí)，在搜索k個(gè)鄰居時(shí)，得到的結(jié)果將偏重于擁有數(shù)據(jù)較多的類，這種情況下所得的預(yù)測(cè)結(jié)果偏差相對(duì)較高.

2 交叉驗(yàn)證和距離加權(quán)方法改進(jìn)KNN算法-WCKNN(Weighted cross -validation KNN)

2.1 改進(jìn)分析

在數(shù)據(jù)集有限的情況下使用k折交叉驗(yàn)證[5-6]，將原始數(shù)據(jù)集均分成C組，每一次將其中的C-1 組數(shù)據(jù)作為訓(xùn)練集，以用于建立模型，剩下的1 組數(shù)據(jù)做為驗(yàn)證集，這樣會(huì)同時(shí)通過訓(xùn)練得到C個(gè)模型，通過平均k次驗(yàn)證的結(jié)果，最終得到一個(gè)單一評(píng)測(cè)結(jié)果作為該模型真實(shí)分類率，k折交叉驗(yàn)證充分利用了數(shù)據(jù)集對(duì)算法效果進(jìn)行測(cè)試. 如果這C個(gè)模型的均值(即真實(shí)分類率)效果良好的話，那么在一定程度上這個(gè)模型就有了一定的泛化能力.

我們首先應(yīng)該明確一點(diǎn)，當(dāng)給定了k值以后，在使用傳統(tǒng)的KNN算法得到的排序數(shù)組必定有一個(gè)或多個(gè)分類，這些分類即是和待分類對(duì)象最接近的已分類對(duì)象.無論返回的結(jié)果是否正確，在一般情況下，使用傳統(tǒng)KNN算法得到的排序數(shù)組中會(huì)存在正確的結(jié)果.

其次，對(duì)于KNN算法或者改進(jìn)的KNN算法而言，訓(xùn)練集和測(cè)試集的數(shù)據(jù)是透明的，無論我們對(duì)算法做出何種改變，測(cè)試集都只是用來驗(yàn)證算法最終的普適度.即：用測(cè)試集去測(cè)試我們改進(jìn)的正確性，當(dāng)測(cè)試集對(duì)于改進(jìn)算法表現(xiàn)出比較好的普適度時(shí)，就可以利用這種改進(jìn)去測(cè)試一個(gè)新的樣本，對(duì)未知的樣本進(jìn)行分類.

我們已經(jīng)知道，在傳統(tǒng)的KNN算法測(cè)試中，何種類別出現(xiàn)的多，那么就把當(dāng)前的測(cè)試樣本劃分為哪一類.所以顯然的，我們可以將本次實(shí)驗(yàn)中某類出現(xiàn)的次數(shù)li和當(dāng)前選取的k值之比作為分類結(jié)果為某類的概率pi，即：

那么在傳統(tǒng)的KNN算法實(shí)驗(yàn)中，對(duì)于某個(gè)測(cè)試樣本，若某兩種類別出現(xiàn)次數(shù)差距較小，即概率之差：

非常小，那么使用傳統(tǒng)KNN算法得到的結(jié)果對(duì)于該待測(cè)樣本來說就可能具備了模糊性. 相反的，若使用傳統(tǒng)KNN算法得到的可能出現(xiàn)類別的個(gè)數(shù)是唯一的，那么對(duì)于該待測(cè)樣本而言，傳統(tǒng)的KNN算法能夠良好的預(yù)測(cè)此次結(jié)果.

所以，若我們?cè)谀炒螠y(cè)試中，用傳統(tǒng)的KNN算法得到的分類概率是多分布的，即在KNN算法求得的排序數(shù)組中出現(xiàn)了多個(gè)可能分類，且出現(xiàn)概率最大的兩個(gè)類別的概率之差g非常小，理論上，我們就將其他出現(xiàn)概率小的類別近似視為不可能類別，將該兩類出現(xiàn)概率最大的類別視為極大可能類別.

于是，在上述k折交叉驗(yàn)證理論和分類概率pi的基礎(chǔ)上提出WCKNN算法，算法的主要思想為在某兩類分類出現(xiàn)概率之差非常接近時(shí)增加距離加權(quán)驗(yàn)證，根據(jù)類別加權(quán)距離之和的平均作為評(píng)斷分類結(jié)果的標(biāo)準(zhǔn)若傳統(tǒng)的KNN算法得到的類別數(shù)是唯一的，則不進(jìn)行加權(quán).

首先我們需要確定距離加權(quán)驗(yàn)證的次數(shù)，傳統(tǒng)的KNN算法是根據(jù)待測(cè)點(diǎn)和k個(gè)最鄰近點(diǎn)的距離比較來確定待測(cè)點(diǎn)的分類，因此對(duì)改進(jìn)的KNN算法而言，我們不希望因?yàn)閗值的變動(dòng)而造成加權(quán)驗(yàn)證次數(shù)的變動(dòng).我們發(fā)現(xiàn)對(duì)于函數(shù)：

當(dāng)x的取值大于0 時(shí)，其值恒為1，所以無論k值根據(jù)經(jīng)驗(yàn)取多少時(shí)，都不會(huì)影響加權(quán)次數(shù)，由此我們確定距離加權(quán)驗(yàn)證的次數(shù)為1 次.

在確定了距離加權(quán)的次數(shù)之后，我們便可以開始考慮如何分配我們的權(quán)值了. 傳統(tǒng)的KNN算法以距離為核心，根據(jù)k值選取訓(xùn)練集中前k個(gè)離測(cè)試點(diǎn)最近的點(diǎn).我們以加權(quán)的思想再深究之，便可以對(duì)KNN算法從另外一個(gè)角度有一個(gè)新的理解.即：

距離越小，權(quán)值越大.距離越大，權(quán)值越小.

那么參考函數(shù)：

f(x) 在整個(gè)實(shí)數(shù)集中的函數(shù)值恒大于0，其對(duì)稱軸為x=u，我們將u取為1.a決定了函數(shù)的定點(diǎn)高度，我們將之取為k，σ為方差，我們將之取為1，這樣f(x) 就是一個(gè)正態(tài)分布了.對(duì)于指定的k我們就可以產(chǎn)生一一與之對(duì)應(yīng)的權(quán)值了.

因?yàn)槲覀儗⒛硟煞N出現(xiàn)次數(shù)最多的類別視為極大可能類別，所以在進(jìn)行加權(quán)計(jì)算時(shí)，為了簡化運(yùn)算量，只需要將權(quán)值與極大可能類別中的元素一一相乘，這樣就得到了我們需要的加權(quán)距離. 但是這時(shí)候若我們直接對(duì)新的加權(quán)距離進(jìn)行重新排序，那么結(jié)果仍然不會(huì)有任何改變，這是因?yàn)槲覀儾]有改變某種類別出現(xiàn)的次數(shù)，同時(shí)根據(jù)距離越小，權(quán)值越大的理念，即使讓傳統(tǒng)的KNN算法得到的排序數(shù)組組內(nèi)序列發(fā)生變化，若仍然以類別出現(xiàn)次數(shù)之和來作為分類評(píng)判標(biāo)準(zhǔn)，則是徒費(fèi)力氣.

那么，同樣根據(jù)傳統(tǒng)KNN算法的思想，既然傳統(tǒng)的KNN算法是以類別出現(xiàn)的次數(shù)之和來進(jìn)行分類，我們簡單的稱這種思想為歸一化思想.那么在本次加權(quán)改進(jìn)中，我們可以延續(xù)這種歸一化的思想，將加權(quán)后屬于相同類別下的加權(quán)距離進(jìn)行歸一化，再對(duì)極大可能類的每一類的距離總和分別求平均，那么依據(jù)距離越小，權(quán)值越大的思想，實(shí)驗(yàn)的結(jié)果就應(yīng)該就是加權(quán)距離之和平均更大的那一類.

2.2 WCKNN 算法流程：

步驟1：將原始訓(xùn)練集劃均分為c- 1 個(gè)子訓(xùn)練集，余下的一個(gè)子集作為驗(yàn)證集，從驗(yàn)證集中取出數(shù)據(jù)對(duì)象xi，xi∈x= {x1，x2，x3…xn}

步驟2：根據(jù)傳統(tǒng)的KNN算法，得到本次分類的原始距離排序數(shù)組.

步驟3：根據(jù)經(jīng)驗(yàn)值k 和函數(shù)：

確定加權(quán)次數(shù)，使得加權(quán)次數(shù)不會(huì)受k值的影響.

步驟4：計(jì)算類別出現(xiàn)概率，若有多個(gè)類別出現(xiàn)，選取出現(xiàn)概率之差最小的兩個(gè)類別，根據(jù)高斯函數(shù)：

取定權(quán)值，一一相乘后得到新的加權(quán)距離.

步驟5：對(duì)同屬一類的加權(quán)距離進(jìn)行求和，加權(quán)距離總和與出現(xiàn)次數(shù)之比，即加權(quán)平均距離更大的類別即為本次改進(jìn)實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果.

步驟6：實(shí)驗(yàn)采用的是5 -折交叉法，所以重復(fù)步驟1 到步驟6 共計(jì)5 次，注意在步驟1 中確保每次的驗(yàn)證集不相同，最后統(tǒng)計(jì)5 個(gè)模型下的分類正確率，得到分類正確率的均值作為WCKNN算法的最終分類正確率，以驗(yàn)證WCKNN的正確性.

步驟7：不斷改變k 值，重復(fù)步驟1 -6，得到不同k 值下的WCKNN的正確率，為最后的實(shí)驗(yàn)對(duì)比打下數(shù)據(jù)基礎(chǔ).

2.3 WCKNN 算法的偽代碼描述

現(xiàn)根據(jù)改進(jìn)分析及算法流程給出改進(jìn)WCKNN算法的相關(guān)偽代碼. 其中k是近鄰數(shù)量，testdata是測(cè)試集，traindata是訓(xùn)練集，cls是實(shí)驗(yàn)數(shù)據(jù)的所屬類別.

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

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

為了驗(yàn)證算法的準(zhǔn)確性，我們采用WCKNN算法進(jìn)行手寫體數(shù)字的識(shí)別[2].在實(shí)驗(yàn)中不斷改變每個(gè)測(cè)試數(shù)據(jù)的鄰居數(shù)量k，驗(yàn)證不同k值下改進(jìn)算法的正確率.

手寫體數(shù)字的原始總體樣本為10 000 個(gè)手寫體數(shù)字，經(jīng)過5 -折交叉法建立5 個(gè)模型后，得到實(shí)驗(yàn)數(shù)據(jù)，并去除異常數(shù)據(jù)(如距離為0，表示本次測(cè)試樣本和訓(xùn)練集里的樣本重合，不應(yīng)當(dāng)納入實(shí)驗(yàn)結(jié)果考慮范圍)后，使用WCKNN算法不斷對(duì)k值進(jìn)行改變，由于篇幅有限，只給出表1 和表2 的實(shí)驗(yàn)數(shù)據(jù)，表中描述的是兩種算法的正確率，num是K折交叉驗(yàn)證中每折的數(shù)據(jù)量，也即每次測(cè)試集的數(shù)據(jù)量.

表1 實(shí)驗(yàn)數(shù)據(jù)(跨度為1)Table 1 Experimental data (span is 1)

表2 實(shí)驗(yàn)數(shù)據(jù)(跨度為5)Table 2 Experimental data (span is 5)

由表1 和2 可知，對(duì)于本次實(shí)驗(yàn)采用的對(duì)手寫體數(shù)字進(jìn)行識(shí)別的實(shí)驗(yàn)而言，WCKNN算法的最佳k值為6，對(duì)于不同的k值，WCKNN算法都基本上保證了識(shí)別的正確率比傳統(tǒng)的KNN算法高.

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

為了方便比較 WCKNN 算法和 KNN 算法的關(guān)系，將實(shí)驗(yàn)數(shù)據(jù)繪制成圖1.

圖1 算法分類正確率對(duì)比圖Fig.1 Algorithm correct rate comparison chart

從圖1 可以看到，使用WCKNN算法在不同的k值下的得到的分類準(zhǔn)確率，較直接使用傳統(tǒng)KNN算法得到的分類準(zhǔn)確性要高，所以使用WCKNN算法一定程度上可以增加我們分類的準(zhǔn)確性，且在手寫數(shù)字識(shí)別實(shí)驗(yàn)中，分類效果峰值差距達(dá)到了1%左右，此也驗(yàn)證了2.1 改進(jìn)分析的正確性，進(jìn)而驗(yàn)證了改進(jìn)算法的正確性.從實(shí)驗(yàn)結(jié)果(表2)可知，當(dāng)k值較大時(shí)，傳統(tǒng)的KNN算法收斂的速率較大，而改進(jìn)的WCKNN算法的收斂速度則更加緩慢一些，由此可知，改進(jìn)的KNN算法分類結(jié)果更加穩(wěn)定，更加適合用于數(shù)據(jù)分類.

4 結(jié)束語

KNN 算法每一次都是在樣本全局的基礎(chǔ)上去進(jìn)行歸類計(jì)算，這在很大程度上消耗了空間，增大了算法空間復(fù)雜度，本文通過交叉驗(yàn)證的形式，通過建立不同的模型，相比于傳統(tǒng)的KNN 算法，降低了空間復(fù)雜度.且傳統(tǒng)KNN 算法在樣本分類不平衡時(shí)，預(yù)測(cè)偏差相對(duì)偏高，本文通過對(duì)距離機(jī)制方面的研究和改進(jìn)，通過激活函數(shù)進(jìn)行加權(quán)，通過實(shí)驗(yàn)結(jié)果分析可知，在樣本分類不平衡時(shí)，WCKNN 算法的預(yù)測(cè)偏差要低于傳統(tǒng)的KNN 算法，分類更具有代表性，達(dá)到了預(yù)想的效果.但是改進(jìn)的WCKNN算法仍具有進(jìn)一步的提高空間，首先是沒有解決出現(xiàn)概率之差的閾值的自動(dòng)選取，目前的策略是人為的進(jìn)行選取閾值，這是一大缺陷，其次WCKNN算法并沒有根本上解決傳統(tǒng)KNN算法的k值的選取較多的依賴于經(jīng)驗(yàn)的問題，只是能根據(jù)不斷的實(shí)驗(yàn)確定最佳k值而不能自適應(yīng)k值，而k值的選取也會(huì)在一定程序上對(duì)分類的正確性有所影響，這些將會(huì)是在今后的試驗(yàn)中值得去研究和改進(jìn)的方向.