黃光華， 殷 鋒， 馮九林

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

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

1 KNN 算法及其缺陷分析

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

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

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

KNN算法的步驟如下：

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

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

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

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

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

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

2.1 改進(jìn)分析

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

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

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

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

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

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

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

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

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

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

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

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

那么參考函數(shù)：

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

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

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

2.2 WCKNN 算法流程：

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

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

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

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

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

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

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

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

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

2.3 WCKNN 算法的偽代碼描述

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

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

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

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

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

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

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

3.2 實驗結(jié)果分析

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

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

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

4 結(jié)束語

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