基于采樣壓縮的加速K-NN分類方法

王曉

(晉中學院信息技術與工程學院，山西晉中030619)

基于采樣壓縮的加速K-NN分類方法

王曉

(晉中學院信息技術與工程學院，山西晉中030619)

標準K-近鄰分類方法（K-Nearest Neighbor,K-NN）在進行樣本預測過程時，需要計算每一個待預測類別標記的樣本與所有已知標記樣本的距離，因此復雜度較高，無法處理含有大規模有標記樣本的分類問題。針對這個問題，本文提出一種基于采樣壓縮的加速K-NN分類方法（K-NN Method Based on Sampling Compress, KNN_S）。該方法將采樣思想引入到K-NN分類過程當中，即對于每一個新來的未知類別的待測樣本，不是計算其與所有帶類別標簽樣本的距離，而是通過采集一定數量的有標記樣本，計算這部分有標記樣本中距離待測樣本最近的近鄰樣本，來對待測樣本進行分類。實驗結果表明，本文提出的KNN_S方法能夠加速K-NN分類的過程。

K-NN分類；采樣；KNN_S算法；距離

K近鄰（K nearest neighbor,K-NN）分類方法[1-2]是一種最為常見的分類預測方法，其模型設計簡單，容易實現，且分類的可靠性往往較高，目前已經在多種領域中得到了成功應用[3-5]。然而，隨著現實應用問題中數據量的不斷增長，分類方法需要處理的數據規模越來越大，對于K-NN分類模型，當有類別標記的樣本規模非常大時，由于其在對新樣本類別的預測過程中需要計算新樣本到所有已標記樣本的距離，因此計算距離的耗時較多，無法有效處理大規模數據的分類問題[6-9]。

針對這個問題，本文提出一種基于采樣壓縮的加速K-NN分類方法。該方法將隨機采樣思想引入到K-NN分類過程當中，即對于一個待測樣本，不是計算其與所有樣本的距離，而是通過采集一定數量的有標記樣本來壓縮實際參與決策的帶標記樣本集，計算這部分帶標記樣本中距離待測樣本最近的k個近鄰樣本，然后對待測樣本按照少數服從多數的原則進行分類。由于計算距離的數目較少，因此分類的效率會相應提高。

1 標準K-近鄰分類方法

假設存在帶類別標記的樣本x1,x2,…,xn，且已知這些樣本對應的的類別標簽分別為y1,y2,…,yn，其中xi為p維空間中的樣本，其類別標簽yi∈{+1, -1}，待測試樣本為t1,t2,…,tm，近鄰參數為k。KNN方法對于任意一個待測試樣本tj，都需要計算該樣本與所有帶標記樣本xi的距離，p維空間中的距離計算如下：

根據上述距離公式，即可比較得到距離待測試樣本tj最近的k個帶標記樣本，然后根據該k個帶標記的近鄰樣本的類別標簽對待測樣本根據少數服從多數的原則進行打標簽。

在K-NN分類方法中，假設有標記樣本的規模為n，樣本維度為 p，則對于每一個待測樣本來說，預測其類別標簽的其復雜度可以寫成O(np)，整個算法執行的復雜度即為O(npm)，其中m為待測試樣本個數，然而在實際問題中，有標簽樣本集的規模往往較大（若該樣本集過小又缺乏代表性時，分類結果精度不高），此時算法的時間復雜度較高，無法在大規模數據集上執行。

2 基于采樣的加速K-NN算法

針對傳統K-NN分類方法無法處理大規模帶標簽數據的分類學習問題，本文提出了一種基于采樣壓縮的加速K-NN分類方法，該方法首先對帶標簽的樣本進行隨機抽樣，即得到一個抽樣集合{x1',x2',…,xn''}，假設抽樣的規模為n'且n'＜＜n，即抽樣樣本的規模要遠小于原始帶標簽樣本的規模，當一個待測樣本t進入時，首先計算待測樣本t與抽樣樣本集{x1',x2',???,xn''}中每一個抽樣樣本的距離，壓縮實際參與類別決策過程的帶標簽樣本數，并根據距離選擇最近的k個抽樣樣本集中的樣本，然后根據少數服從多數的原則對待測樣本來標記類別標簽。

KNN_S分類算法的具體執行過程如下。

初始化：假設帶類別標簽的訓練樣本集為x1,x2,???,xn，其對應的類別標簽為 y1,y2,???,yn，其中 xi為p維空間中的樣本，其類別標簽yi∈{+1,-1}，測試樣本為t1,t2,???,tm，測試樣本對應的真實類別標簽為y1,y2,???,ym，近鄰分類參數設置為k，抽樣參數設置為s，s∈(0,1]。

Step1：對帶有類別標簽的樣本集x1,x2,???,xn進行隨機抽樣，假設得到的抽樣樣本集結果為{x1',x2',???xn''}，對應的類別標簽為{y1',y2',???,yn''}，既有如下的抽樣本規模關系：

Step2：計算每個待測樣本tj到壓縮后的帶標簽抽樣樣本xi'的距離，計算方法類似于式（1），即：

Step3：選擇距離最近的k個壓縮后的樣本集中的帶標簽樣本，并根據這k個近鄰的標簽以少數服從多數的原則對待測試樣本tj進行打預測類別標簽；

Step4：對于每一個待測樣本，都循環執行Step2-Step3的過程，直到所有待測樣本的預測類別標簽y1',y2',???,ym'都得到時為止；

Step5：根據待測樣本得到的預測類別標簽y1',y2',???,ym'與其真實的類別標簽 y1,y2,???,ym進行對比，得到分類器性能的好壞；

Step 6：算法結束。

假設KNN_S分類方法中，有標記樣本的規模為n，抽樣壓縮之后的樣本規模為n'，則對于每一個待測樣本來說，其預測標簽過程的復雜度變為O(n'p)，當然，抽樣壓縮之后的帶標簽樣本集只是原始樣本集的一個盡可能優秀的表示，但根據其得到的分類結果肯定無法與原始分類結果一致，而只能是一種近似的逼近。在實際問題中，可以根據用戶的任務需求來設置抽樣參數s，若用戶任務對分類精度要求較高，則應該設置較大的抽樣參數值，即有較小的抽樣壓縮比例，當然此時效率的提升不明顯，當用戶任務對分類效率的要求較高時，可以設置較小的抽樣參數值，以有效壓縮實際參與類別決策的有標記樣本的數量，提高預測過程的學習效率。

3 實驗結果及分析

為驗證本文所提出的ISVM_S學習方法的性能，本文在構造的正態分布數據集和3個典型的UCI數據集上進行了測試。人工構造的正態分布數據集中，正類和負類分別以（+1，+1）和（-1，-1）為中心，以（1 0，0 1）為協方差矩陣來構造，其中正類和負類的比例分別為500:500。測試集與訓練集構造方法一致，人工構造的訓練集分布如圖1所示。

圖1 人工構造的正態分布數據集

實驗中采用的標準UCI分類數據集如表1所示。

表1 實驗數據集

由于影響KNN_S算法性能的參數主要為樣本壓縮參數s，因此本文測試了在不同的樣本壓縮參數s下的實驗結果。本文將實驗結果與標準的K-NN進行了比較，實驗中近鄰參數取5，人工數據集的實驗結果見表2。表中第一行數值為樣本壓縮參數，由于人工構造的正態分布數據集規模較小，因此抽樣壓縮參數分別取10%、20%、30%、40%和50%。

表2 人造數據集上的測試精度

從實驗結果可以看出，對于不同壓縮比的人造正態分布數據集，本文提出的KNN_S方法與傳統K-NN相比，在多數壓縮比參數下，其方法的精度都與K-NN接近（特別地，當參數取30%、40%和50%時），測試精度與K-NN均相同，這是由于人造的正態分布數據集本身樣本分布簡單，容易區分兩類樣本，當然，壓縮比降低到10%之后，精度與KNN相比，還是存在4%的差距。但從算法的運行效率上看，在5個不同的抽樣壓縮參數下，算法的效率都有了明顯的提高，提高值達到了100%到800%，特別指出的是，當樣本壓縮參數取30%時，算法所需要的類別預測時間僅為原來的36%，但測試精度與標準K-NN一致。

在真實的UCI數據集上的實驗結果如表3所示。由于UCI數據集規模較大，因此抽樣壓縮參數分別取5%、10%、15%、20%和25%。

表3 UCI數據集上的實驗結果

從表3在標準的UCI數據集上進行測試的結果可以看出，在Banana數據集上，在所有抽樣壓縮參數下得到的分類精度均與K-NN一致，而分類時間卻提高了100～120s左右；同理，在Diabetis數據集上，KNN_S方法也得到了與K-NN基本一致的分類結果，且在預測效率方面有明顯的提高。這說明雖然二者均為真實的數據集，數據分布可能較為復雜，但由于帶標簽數據的規模較大，因此抽樣壓縮基本上不會影響類別預測的結果。但在數據集German上，與標準K-NN分類方法相比，雖然在預測效率上有了明顯提高，但預測精度卻存在明顯下降，特別地，當抽樣壓縮參數取5%時，測試精度降低了11.8%，這可能是由于該數據集為高維數據集，因此抽樣結果對于距離分布敏感，因此抽樣壓縮得到的帶標記樣本與原始整體帶標記樣本分布存在較大差異，導致分類預測結果不好。

4 結語

基于采樣壓縮的加速K-NN分類方法，將采樣思想引入到K-NN分類過程當中，對每個待測樣本，通過采集一定數量的有標記樣本，計算這部分有標記樣本中距離待測樣本最近的近鄰樣本，減少了計算距離的個數，提高了分類的效率。

[1]LIU Z G,PAN Q,Dezert J.A new belief-based K-nearest neighbor classification method[J].Pattern Recognition,2013,48(3):834-844.

[2]MITCHELL H B,SCHAEFER P A.A“soft”K-nearest neighbor voting scheme[J].International Journal of Intelligent Systems,2001 (16):459-468.

[3]彭凱，汪偉，楊煜普.基于余弦距離度量學習的偽K近鄰文本分類算法[J].計算機工程與設計，2013,34(6):2200-2203,2211.

[4]楊帆，林琛，周綺鳳,等.基于隨機森林的潛在k近鄰算法及其在基因表達數據分類中的應用[J].系統工程理論與實踐，2012,32(4):815-825.

[5]郭玉堂.基于互K近鄰圖的自動圖像標注與快速求解算法[J].計算機科學，2011,38(2):277-280.

[6]LIU Z G,PAN Q,DEZERT J.A new belief-based K-nearest neighbor classification method[J].Pattern Recognition,2013,48(3): 834-844.

[7]劉應東，?；菝?基于K-均值聚類的小樣本集KNN分類算法[J].計算機應用與軟件,2011,28(5):112-113.

[8]NICOLAS G P,DOMINGO O B.Boosting k-nearest neighbor classifier by means of input space projection[J].Expert Systems with Applications,2009,36(7):10570-10582.

[9]HART P E.The condensed nearest neighbor rule[J].IEEE Transactions on Information Theory,1968,14(3):515-516.

Speeding K-NN Classification Method Based on Sampling Compress

WANG Xiao
(School of Information Technology&Engineering,Jinzhong University,Jinzhong Shanxi,030619)

This paper presents a K-Nearest Neighbor(KNN)method based on sampling compress,called KNN_S,in order to solve the problem that the low training efficiency and cannot solving the large scale problems of normal K-NN because it need compute the distance between the sample to be tested and the labeled samples in the new sample classification prediction process.By introducing the sampling idea into the K-NN classification process,when the new sample to be tested is produced,this method is not computing all the distances between all the labeled samples and the new sample,but it executed by computing the distances between the new coming sample and the compressed samples by sampling process to classify the prediction sample.The experiment results demonstrate that the proposed KNN_S method can speed the K-NN classification process.

K-NN classification;sampling;KNN_S algorithm;distance

TP18

A

〔責任編輯 高海〕

1674-0874(2017)04-0017-04

2016-11-15

王曉（1980-），男，山西汾陽人，碩士，講師，研究方向：人工智能與數據挖掘。