沈莉莉，劉 叢，蔣林華，鄔春學

(上海理工大學 光電信息與計算機工程學院，上海 200093)

?

一種自動檢測K近鄰值算法

沈莉莉，劉 叢，蔣林華，鄔春學

(上海理工大學 光電信息與計算機工程學院，上海 200093)

由于傳統的KNN算法需要針對不同的數據集選擇不同的k值的缺陷，提出了兩種自適應近鄰值的檢測算法。該算法以傳統的KNN算法為基礎，使用多個K值對數據進行多次分類，而后對多次分類結果進行統計，根據統計值來決定樣本點的類歸屬。方法一為統計多次分類中每個類別所包含的近鄰數目，將近鄰數目最多的類作為樣本點的歸屬類；方法二為統計多次分類中的歸屬類數目，將數目最多的作為樣本點的歸屬類，兩種方法可以避免每次設置K值的弊端。從實驗結果可以看出，提出的算法得到的數據更加穩(wěn)定，更具有代表性。

KNN算法；分類；自適應

隨著網絡技術與數據存儲技術的發(fā)展，每天都有大量的數據不斷涌現，給數據存儲和分析領域帶來了挑戰(zhàn)，設計強有力的數據分析工具是當今面臨的主要問題。K近鄰算法是一種比較簡單的分類算法，其已在數據分析中得到了廣泛應用。該算法的主要思想為對某一待分類樣本X，在訓練集中找出K個與其最相近的樣本，分析這些樣本的分類情況，對分類樣本X分類。大量的研究者致力于KNN算法的研究，由于KNN需要多次尋找周圍最近的K個鄰居點，這會導致計算量巨大。所以如何降低算法的時間復雜度是研究熱點之一。樊東輝提出了基于聚類的KNN算法，改進[1]IKNN算法，該算法首先使用DBSCAN聚類算法對樣本進行聚類，再使用KNN算法找到n個最近鄰樣本對測試樣本進行分類。張順提出用于多標記學習的K近鄰改進算法WML-KNN算法，對樣本進行均勻抽樣，降低算法的時間復雜度，根據鄰近樣本類別標記信息計算測試樣本的最大后驗概率，最后得到測試樣本的類別標記。滕敏的K-最近鄰分類算法應用研究[3],對近鄰算法中K的取值對算法的影響，測試出不同的K值在分類算法中的誤差率，實驗得出當K值約為n/k時，具有較低的誤差率，分類效果較好。KNN算法使用預先設定好的K值進行分類，但在傳統的K最近鄰算法中并不能已知哪個K值是最佳的分類結果，所以要對選取的K值進行判斷，否則選取的K值可能與真實數據有較大的偏差。另一方面，K值的選擇也是研究熱點之一，楊柳提出一種自適應的大間隔近鄰分類算法[4]，在LMNN算法提出了自適應K值的ALMNN算法，該算法克服了K值全局固定的缺點，減少了K值對分類結果的影響。王增民提出基于熵權的K最臨近算法改進[5]，該算法克服了維度災難問題，對樣本進行屬性約簡。焦淑紅提出KNNY算法采用KNN和SVM融合的方法，降低識別率低的問題[6]。王邦軍提出了改進協方差特征的KNN分類算法[7]，不使用歐氏距離。鄧箴提出用模擬退火算法改進的KNN算法[8]，加快KNN的分類速度。劉應東劃分K最近鄰圖來改進KNN算法[9]。張著英提出一種高效的KNN算法[10]，對屬性約簡。鄧振云提出基于局部相關性的KNN分類算法[11]，解決固定值選取問題。本文提出一種新的改進算法，無需直接確定K的值也達到了最佳分類的效果，解決了選取不同K值對實驗結果不同的問題，達到了實驗結果的自適應。

1 K最近鄰算法

K近鄰算法(K-Nearest Neighbor,KNN)[12]，即尋找測試數據點周圍最近的K個數據點，可以簡單地認為是K個最近的鄰居。當K=1時，就是尋找最近的鄰居，如果K=N時，即為整個數據集。KNN算法是數據挖掘十大算法之一，是較為常用的分類器。

所謂K近鄰算法是對于一個新的測試數據點，在給定的訓練集中對測試數據進行分類，對于提前給定的K值，在訓練數據集中根據距離的遠近找到與測試數據最接近的K個數據點，在這K個數據中，分別查看這K個數據分別屬于哪一個類，如果多數屬于某一個類，那么將該測試數據就分到那個類中去，這個測試數據點就分類完成。

KNN算法中需要找到與測試數據最接近的K個實例，這里度量鄰居的方式是采用歐氏距離。歐氏距離是常見的兩點之間或多點之間的距離表示方法，是m維空間中兩點之間的真實距離，又稱為歐幾里德度量。二維空間中點i與點j之間歐氏距離的計算公式為

其中，(xi,yi)為數據點i的坐標值,D值為數據點i與j之間的距離。

傳統KNN算法流程：

輸入 (1)數據測試點x；(2)訓練數據集；(3)設置K。

輸出x的分類結果。

步驟1 設定參數選擇合適的K值；

步驟2 對于測試數據點x，在訓練數據集中利用歐氏距離計算出與數據點x最近的K個數據點；

步驟3 查看并記錄K個數據點所屬的類別Ci，(i=1，2，3，…，C，C為訓練數據集總共的類別數)；

步驟4 對相同類的數據點進行相加，把數據點x分類到數目最多的那個類中。

傳統的KNN算法也存在某些不足：(1)當訓練數據集不平衡時，數據集中的某一個類所擁有的數據占整個數據集的一大部分，在搜索K個鄰居時，得到的結果將偏重于擁有數據較多的類，所得結果受到影響，不一定正確；(2)K值需要人工設定，K值的大小對KNN算法結果有直接的影響，李航博士在文獻[13]中闡述：K值過小容易發(fā)生過擬合，K值過大忽略了訓練數據集中大量有用的信息。所以K值選擇尤為重要，算法采用交叉驗證法選擇最優(yōu)K值。

2 AKNN算法

針對傳統KNN算法需要針對不同的數據集設置不同K值的局限性，本文提出了兩種自動K值的檢測方法，分別為AKNN1和AKNN2算法。

2.1 AKNN1算法

第一種改進的KNN算法是對每一個測試數據而言，在訓練集中找到K個鄰居，統計每一個K值下得到的所有鄰居，將測試數據點歸為類別數出現次數最多的那個類。

算法1 AKNN1算法框架。

輸出x的分類結果。

算法流程：

步驟2 設置l個計數器{cou1=0,cou2=0,…,coul=0}，分別表示k個近鄰樣本所對應的類別計數；

步驟3 選擇離x最近的k個訓練樣本{y1,y2,…,yk}?T進行分析，如果yi=Cj，則couj=couj+1；

步驟4k=k+1，如果k

步驟5 得到最大的couj，將x放入類Cj中。

AKNN1算法需要使用不同K值做多次KNN運算，對于每次鄰域中的類別數進行多次疊加計數。

2.2 AKNN2算法

第二種改進的KNN算法是對每一個測試數據點而言，先統計每一個K值下鄰居出現次數最多的類，之后再統計出這些類中出現次數最多的類，那么測試數據點就歸為此時統計出來的類中去。

兩種改進算法的不同在于：第一種改進算法AKNN1是在2+3+4+…+K(K值為設定的Kmax值)個數據點進行統計，將測試數據點歸為出現次數最多的類；第二種改進算法AKNN2是在每個K值下統計出現次數最多的類，最后在Kmax個出現次數最多的那幾類中做統計，將測試數據點歸為這Kmax個類中出現次數最多的類中。

3 實驗結果與分析

為驗證所提算法的有效性，實驗使用了3組人工設置的不規(guī)則數據和5組UCI數據，這3組不規(guī)則數據的分布如圖1所示。

這3組不規(guī)則數據中，Connected數據集共有150個樣本，含3個互相連接的類，3個類中樣本點的數目分別為47,30和73個。每個類都是符合超球型的分布。Spiral數據包含160個樣本，表現為兩個互相纏繞的螺旋，每個螺旋的樣本數據為80個。Stick含有300個數據點，可分為4個類，每個類的樣本為100,50,100和50個點。5個UCI數據集為IRIS、Glass，Soybean，Wine和Live數據。IRIS數據包含150個樣本點，可分為3類，每類的樣本數為50個。Glass數據包括214個分類樣本，一共分為6類，每類樣本數為70，76，17，13，9和29。Soybean數據一共有4類共47個點，每類分別為10，10，10和17個點。Wine數據集有3類178個數據，每類為59，71和47個數據點。

圖1 3種人工測試集

實驗中將改進的KNN算法與傳統KNN算法中K值為1，3，5，7和9的正確率做比較，得到的實驗結果如表1所示。

表1 各算法數據實驗值

3.1 數據處理

在選擇訓練集和測試集上采用交叉驗證[14]方法，訓練集和測試集的比值為1∶2，隨機選擇2/3的數據集作為訓練集，剩余數據作為測試數據集。

3.2 距離度量

實驗采用兩點之間的距離來尋找測試數據點的鄰居，在K值下尋找到最近的K個鄰居。實驗用歐氏距離[15]來計算兩點之間的距離，特征空間中兩個實例的距離可以反應出兩個實例之間的相似程度。

3.3 參數設置

對于傳統的KNN算法并不能很好地判斷K的具體大小，所以在傳統的KNN算法中，對K的取值為1，3，5，7和9。

3.4 實驗結果分析

如表1所示，對于傳統的KNN算法來說，首先對于不同的K值，得到的分類結果不同。對于3個人工測試集，Connected和Stick數據集的實驗數值波動不大，但對于Spiral數據，傳統算法的正確率從1.00～0.98再到0.75有所下降，然而K為7時又上升到0.95，K為9時下降到0.38，從這些數值可知，實驗結果波動幅度較大。而對于AKNN1改進算法，實驗值在K=9時從0.96變化到0.78才有了波動，其它數據值在K為1，3，5和7時非常穩(wěn)定。AKNN2算法的實驗值總體來說相對穩(wěn)定，變化幅度較小，只是在K為5變化到K為7時有小幅變動。

實驗中的5組UCI真實數據集中，IRIS，Live和Wine數據集的結果比較穩(wěn)定，而從對Soybean數據的分析看來，各算法的數據正確率都在1.00，隨著K的增加KNN算法的正確率最先發(fā)生變化，隨后AKNN1和AKNN2算法的正確率相繼發(fā)生了變化。而Glass數據集整體數值變化雖然沒有人工數據集Spiral變化的幅度大，但是對于AKNN1和AKNN2算法來說變化的幅度就大得多了，從實驗數值來看，兩種改進算法的實驗值都較為穩(wěn)定。

綜合6組數據集的實驗結果，傳統KNN算法雖然有部分實驗結果正確率較高，但總體的分類結果正確率波動較大，不能準確得到理想的分類結果。而對于論文中改進的KNN算法，無需已知K值，分類結果更穩(wěn)定、更具有代表性，達到了預想的最佳分類效果。

4 結束語

本文提出了一種改進的KNN分類算法，該算法自適應進行KNN算法，解決了傳統KNN算法使用固定K值而得不到一個穩(wěn)定具有代表性的實驗結果的缺點。從實驗的結果來看，分類的正確率有所提高，分類結果更具代表性。但是，本文所提算法需要進行大量計算，開銷較大，有待于進一步提高。

[1] 樊東輝,王治和.基于聚類的KNN算法改進[J].電腦知識與技術,2011,7(35):9033-9037.

[2] 張順,張化祥.用于多標記學習的K近鄰改進算法[J].計算機應用研究,2011,28(12):4445-4450.

[3] 楊柳,于劍,景麗萍.一種自適應的大間隔近鄰分類算法[J].計算機研究與發(fā)展,2013,50(11):2269-2277.

[4] 王增民,王開玨.基于熵權的K最臨近算法改進[J].計算機工程與應用,2009,45(30):129-131.

[5] 焦淑紅,孫志帥.基于GPCA的KNNY與SVM融合的人臉識別方法[J].電子科技,2016,29(2):74-76.

[6] 王邦軍,李凡長.基于改進協方差特征的李-KNN分類算法[J].模式識別與人工智能，2012,27(2):174-178.

[7] 鄧箴,包宏.用模擬退火算法改進的KNN分類算法[J].計算機與應用化學,2010,27(3):303-307.

[8] 劉應東,?；菝?基于K-最近鄰圖的小樣本KNN分類算法[J].計算機工程,2011,37(9):198-200.

[9] 張著應,黃玉龍.一個高效的KNN分類算法[J].計算機科學,2008,35(3):170-173.

[10] 鄧振云,龔永紅.基于局部相關性的KNN分類算法[J].廣西師范大學學報，2016,34(1):52-58.

[11] 張瑩.基于自然最近鄰的分類算法研究[D].重慶:重慶大學,2015.

[12] 李航.統計學習方法[M].北京:清華大學出版社,2012.

[13] 范永東.模型選擇中的交叉驗證方法綜述[D].太原:山西大學,2013.

[14] 羅四維,黃雅平.聚類分析中的相似性度量及應用研究[D].北京:北京交通大學,2012.

An Adaptive Improved Algorithm forK-nearest Neighbors

SHEN Lili，LIU Cong，JIANG Linhua，WU Chunxue

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science & Technology, Shanghai 200093, China)

Since the value ofkcannot be determined by the traditional k-nearest neighbor algorithm, a novel k-nearest neighbor improved algorithm is proposed. This algorithm is based on the traditional k-nearest neighbor algorithm, but the results are handled in different ways. We choose different values of k for each tasting data. Then, we count the numbers of the data belonging to each cluster. Finally, the test data belongs to the cluster that has the maximum of numbers. Compared with the traditional k-nearest neighbor algorithm, this improved algorithm avoids the disadvantage that how to choose the best value of k due to the great influence of different values of k on classification results. The innovation of our algorithm can be adaptive to the classification results. This algorithm does not consider the problem of the real value of k. According to the results of experiment, the improved algorithm is much more stable than the traditional algorithm with the result of classification closer to the real value.

k-nearest neighbors; classification; adaptive

2016- 09- 20

沈莉莉(1992-)，女，碩士研究生。研究方向：計算智能。劉叢(1983-)，男，博士，講師。研究方向：計算智能等。蔣林華(1977-)，男，博士，教授，博士生導師。研究方向：電子光學圖像處理等。鄔春學(1964-)，男，博士，教授。研究方向：嵌入式系統及應用等。

10.16180/j.cnki.issn1007-7820.2017.07.008

TP301.6

A

1007-7820(2017)07-029-04