基于距離度量的K近鄰基本分類算法研究

張大偉 李明艷

（北海職業學院 廣西·北海 536000）

0 引言

K近鄰分類算法（KNN，K-NearestNeighbor）是數據分類技術中最傳統的算法之一，它是由Cover和Hart在1968年提出來的。所謂K最近鄰，就是未知樣本周邊K個最近的鄰居的意思，意為每個未知樣本都可以用它最接近的K個鄰近值來表示，俗語“你的薪水約是你最好的6個朋友的平均薪水”與K近鄰分類算法有異曲同工之妙。K近鄰分類算法以其穩定性好、準確率高等特點廣泛的應用于分類與回歸。[1]

1 距離度量

在數學中，歐幾里得距離（度量）是歐幾里得空間中兩點間“普通”（即直線）距離。歐幾里得距離也稱歐氏距離，在數據分析及挖掘中經常被提及，例如聚類或計算相似度。[2]曼哈頓距離是幾何學用語，由十九世紀的明可夫斯基首先提出，其用來標明兩個點在標準坐標系上的絕對軸距總和。

曼哈頓距離是指在曼哈頓城市中，從一個紅綠燈駕車到另外一個路口的距離，也稱為城市街區距離。圖1中藍色實線是曼哈頓距離，紅色虛線代表歐氏距離，也就是直線距離，而紫色和綠色代表等價的曼哈頓距離。[3]如下所示公式1和公式2分別代表歐氏距離和曼哈頓距離的計算方法，其中a和b代表兩個點。

圖1：曼哈頓距離與歐氏距離

2 K近鄰分類算法

2.1 K近鄰分類算法定義

K近鄰分類算法是對“近朱者赤近墨者黑”這句話的完美詮釋。若要判斷某個未知樣本屬于哪個分類，只需要找到最接近該樣本的K個鄰居，這些鄰居中哪種分類占比最大，K近鄰分類算法就認為該樣本就屬于此分類。[6]如圖2所示在K=3的時候（內圓與綠色有3個最近的圖形，2個紅色三角形）K近鄰分類算法推測綠色的圓形是紅色三角形；同理在K=5的時候（外圓與綠色有5個最近的圖形，3個藍色矩形）K近鄰分類算法將推測綠色圓形為藍色矩形。

圖2：K近鄰分類算法原理

2.2 K近鄰算法的計算過程

K近鄰分類算法本質上是一種統計學習方法，在程序運行時數據集就被加載到內存開始分類，從而無須進行前期訓練。在判斷未知的樣本時，以該樣本為中心尋找與其最接近的K個元素進行判斷，通常K是一個不大的整數，根據實際需要進行限定。[7]

K近鄰分類算法的計算過程：

（1）利用距離算法（如明可夫斯基距離）度量未知樣本與已知樣本之間的距離；

（2）對所有樣本按距離遞增排序；

（3）選取與未知樣本距離最小的K個點；

（4）計算前K個樣本所屬類別的數量；

（5）統計出K個樣本中，出現頻率最高的類別作為未知樣本的預測分類。

2.3 距離的度量方式對K近鄰分類算法的影響

K近鄰分類算法主要任務是基于距離度量，找出與未知（被測）樣本距離最近的K個點，其三個基本要素：K值的選擇、距離度量以及分類決策規則。距離的度量是對訓練樣本與測試樣本相似程度的描述，這個相似程度就是K個樣本選擇的依據，在K近鄰分類算法中，如果特征是連續的，那么距離度量一般用明可夫斯基距算法；如果特征是離散的，一般采用其它的距離度量算法，如漢明距離。[8]運用K近鄰分類算法進行分類預測時，距離的度量算法不同，得到的結果可能不同。因此，在實際應用中需要對數據集的分類結果進行評價（這是評估模型存在的價值），從而采取最優的距離度量算法。[9]

2.4 K值的選擇對分類結果的影響

如果選擇較小的K值，就相當于用較小的領域中的訓練實例進行預測，“學習”的近似誤差會減小，只有與輸入實例較近或相似的訓練實例才會對預測結果起作用，與此同時帶來的問題是“學習”的估計誤差會增大，換句話說，K值的減小就意味著整體模型變得復雜，容易發生過擬合，（偏差小方差大）；如果選擇較大的K值，就相當于用較大領域中的訓練實例進行預測，其優點是可以減少學習的估計誤差，但缺點是學習的近似誤差會增大。這時候，與輸入實例較遠（不相似的）訓練實例也會對預測器作用，使預測發生錯誤，且K值的增大就意味著整體的模型變得簡單。[10]

3 結語

K近鄰分類算法優點非常突出，其理論成熟、精度高且簡單易于理解，既可以用于分類又可以用于回歸在機器學習中有著較高的利用；但其缺點與優點一樣突出，其計算復雜度和空間復雜度都較高適用于數值型和標稱型的數據。在實際應用中采取不同的K值或不同的距離度量方法都有可能影響最終的分類結果，良好的評價模型結合實際的情況預估是提高分類有效率的不可或缺的方法。