K近鄰算法優化設計策略

李馳 段雨梅

摘要：K近鄰算法作為一種簡單有效且易于實現的機器學習算法被廣泛應用于模式識別的各領域。為了提高該算法的準確度和執行效率，需要在算法設計的多個環節上進行策略的優化。針對提高該算法的準確度，首先探討了K值的選擇問題，然后對幾種距離度量的方法進行了分析比較，最后對分類決策規則問題進行了闡述。針對提高算法的執行效率，從樣本數篩選、維度降低和搜索空間優化三個方面進行了分析，從而降低了該算法的計算復雜度。

關鍵詞：K近鄰;K值選擇;距離度量;分類決策規則;Kd樹

中圖分類號：TP18 文獻標識碼：A

文章編號：1009-3044（2019）31-0200-03

K近鄰算法是機器學習中經典而簡單的算法，它既可以用于分類，也可以用于回歸，甚至在異常點檢測問題（one-class）上也可以使用。該算法依賴周圍有限個近鄰樣本，而不是通過判別類域的方法來預測待測點的類別，所以針對類與類交叉嚴重或者不同類別重疊較多的情況較其他分類法有一定的優勢。該算法的實現步驟是：首先計算已知類別數據集中的每個點與待測點之間的距離，然后選取其中距離值最小的K個點，最后統計出這K個點中出現頻率最高的類別就是待測點的類別。K近鄰算法雖然簡單，但是要讓它真正有效的運行，必須要在設計的多個環節上進行策略的優化，本文對此進行分析和討論。

1K值的選擇

K近鄰算法中K值的確定對算法的準確性影響是很大的。但是這個值的選擇是比較困難的，直觀認為既不能太小也不能太大。

K值如果太小，雖然會讓學習的近似誤差變小，但是同時會使得學習的估計誤差變大。這樣使得預測結果直接只受近鄰的少數幾個實例點的影響，而如果它們又恰巧是噪聲點，則預測出錯的可能性就增大了。太小的K值會導致整體模型變得復雜，容易發生過擬合。一個極端的情況是K等于1，如圖1虛線小圓圈所示，離問號處最近點的類別是圓形（很明顯，它是一個噪點），于是我們就錯誤的將問號處的點劃歸為圓形類別，而直觀告訴我們，其實它更應該屬于三角形類別。

另一方面，K值如果太大，雖然會讓學習的估計誤差變小，但是同時會使得學習的近似誤差變大。K值太大，固然使得考慮的實例點增多，但是也會讓一些離預測點很遠，沒什么相關陛的實例點來參與到預測決策中，而且有時靠著數量眾多還起到了比較大的決策作用，這顯然是不太合理的。太大的K值會導致整體模型變得簡單，容易發生欠擬合。一個極端的情況就是K等于N（N為樣本點的總數），如圖1虛線大圓圈所示，無論問號點在哪個位置，也無論其他點如何分布，最終我們都簡單地認為它屬于所有樣本點中類別最多的那個類，即這里的圓形類，顯然這是不合適的。

既然K值既不能太小也不能太大，那應該如何選擇。很顯然，我們希望得到如圖1中實線中圓圈所示對應的K等于9的值。解決方式一種是使用交叉驗證。交叉驗證是一種常用的模型選擇方法，它的基本思想就是通過多次反復將數據集分為一部分訓練集，另一部分為測試集，然后嘗試在這些訓練集中取不同的K值，測試集中觀察它們的誤差，最后選出最小誤差對應的K值。常用的交叉驗證法有簡單交叉驗證、L折交叉驗證和留一交叉驗證。另一種解決思路就是嘗試使用一些智能算法，例如遺傳算法等，將預測誤差率設置為目標函數，不斷地迭代推演K值，找出使得目標函數值最小的K值。

2距離的度量

2.1傳統的距離度量

2.2余弦距離度量

除了以上這類定義距離的方式之外，在有些領域的K近鄰分類算法中采用一種稱為余弦定理的度量方式來定義距離更為合適。例如在使用K近鄰算法對新聞進行分類時，我們可以將某篇新聞中對應的TF-IDF值f即新聞中出現該關鍵詞的頻數占總數的百分比）使用特征向量表示出來。如果兩篇新聞的內容很相似，則它們必然在很多維度上的TF-IDF值相似，從而我們可以通過比較這兩篇新聞對應的特征向量的夾角來考察它們的相似度。樣本數為r，維度為n，第i個樣本和第i個樣本夾角余弦公式如下：

這個值在0到1之間，值越大，夾角越小，說明越相似。

另外，傳統的K近鄰算法在計算距離的時候，不同維度的重要性考慮是一樣的，但是有些時候應該是有重有輕的。例如在新聞分類中，實詞要比虛詞的重要性高很多，名詞可能又比動詞的重要性高一點。同樣一個詞出現在新聞標題或者段首就比出現在段中的重要性要高。可以考慮在每個維度上追加一個口作為權重系數，將公式3修改為如下公式：相應的公式1和2也可以做同樣的處理。

2.3核函數距離度量

還有一種將核函數運用到距離度量的方法，其基本思想是將線性不可分的低維度特征向量映射到線性可分的高維度特征向量空間中，映射函數為ψ（x），則核函數KK（xi，yj）=ψ（xi）·ψ（xj）。常用的核函數有高斯核、多項核和線性核。相應的，距離公式變為如下：

在樣本數據集的分布呈現非高斯分布和非橢圓分布時，使用核函數的距離度量，在分類精度上往往優于傳統的距離度量，尤其在one-class異常檢測問題上。

2.4歸一化處理

最后，在計算距離的時候還要考慮一個歸一化問題。當一個實例的不同維度的數值由于量綱單位不同或者特征不同導致大小范圍差異很大。如果不做歸一化處理，則可能出現某個維度的數值因為很小，其變化信息就會淹沒在另一個維度的大數值中幾乎不起作用。常見的歸一化處理有以下幾種：

3分類決策規則

3.1傳統分類決策規則

這樣，決定待測點的分類就不僅僅是考慮哪個類的數量多了，還要綜合考慮它們離待測點的距離因素。采用加權法之后，如圖2的情況，待測點的類別很可能就屬于圓形了。因為盡管虛線圓圈內圓形數量不占優勢，但加權考慮距離后勝出。

4計算復雜度的解決

K近鄰算法是一種惰性算法，該算法不會提前訓練樣本，而是等到要進行預測時才進行數據計算。因為每次預測時要計算待預測樣本和每一個訓練樣本的距離，而且要對距離進行排序找到最近的K個樣本。當訓練樣本數大、特征向量維數很高時計算復雜度高，對內存和系統資源的開銷比較大，從而導致算法效率不高。為此，我們要從樣本數篩選、維度降低和搜索空間優化三個方面來考慮解決方案。

4.1樣本數篩選

當樣本數量很多時，為了減少計算量，我們可以對樣本進行挑選。簡單的挑選原則就是選擇有代表性的，保證不同類別的樣本數量比較均衡。但這些原則比較主觀隨意，很難操作。具有可操作性的減少訓練樣本數量的方法有剪輯法和壓縮法兩種。剪輯法的思路是去掉那些會造成錯誤分類的樣本或者被其他類別樣本包圍著的樣本;而壓縮法的思路是考慮到處于決策邊界附近的樣本比遠離決策邊界的樣本對分類起的作用更大，從而將遠離決策邊界的樣本去掉。文獻【11】給出了一種篩選樣本數的方法，具體做法如下：首先確定一個來自類1的樣本點xio然后找出離點xi1，最近的且屬于類2的樣本點xi1，即xi1=NN（xio），如此交替迭代，有xi，j+1=NN（xij），直到兩個樣本彼此互為最近鄰就終止迭代。這些交替來自兩類的最近鄰序列就構成了樣本xio的最近鄰鏈。最后設置一個閾值，只保留每條最近鄰鏈中的最后一條或者幾條鏈中的樣本點，其余樣本點都去掉，從而得到一個較小的訓練樣本集。

4.2維度降低

有些業務領域例如圖像處理或者文本處理會涉及很高的維度，如果不做降維處理而直接使用K近鄰算法會使得計算的空間復雜度和時間復雜度急劇上升，占用大量的計算機內存和CPU運行時間，甚至導致計算不可行。所以，對于使用K近鄰算法的高維數據通常都要進行降維處理。

降維的方式通常有兩種，一種叫作特征選擇，即從m個特征中直接去除掉一些不太相關的或者冗余的特征，最后保留n個特征的方法。這里n

特征提取的方法很多，主要有主成分分析PCA（PrincipalComponent Analysis），獨立成分分析、線型判別分析等。最常用的是PCA，它是通過對原始變量的相關矩陣或協方差矩陣內部結構的研究，將多個變量轉換為少數幾個綜合變量即主成分的降維方法。具體算法思想是數據從原來的坐標轉換到了新的坐標系，第一個新坐標軸的選擇是原始數據中方差最大的方向，第二個新坐標軸的選擇和第一個坐標軸正交且具有最大方差的方向，如此重復直到找到第n個新坐標軸。n值可以通過設定累加方差達到了總方差的一個很大比例，例如90%來確定。通常n遠遠小于m，所以PCA方法可以通過損失很少的信息來換取維度的大幅度降低。PCA的具體算法步驟往往要用到線性代數中計算協方差矩陣的特征值和特征向量來完成。

4.3搜索空間優化

傳統的K近鄰算法采用線性掃描，即當要預測分類時需要實時的計算待測點和每一個訓練樣本點的距離，才能得到距離最近的前K個點，一旦數據量大計算非常耗時。為了提高搜索效率，有一些優化搜索空間的方法可以提高搜索效率。

比較常用的有Kd樹（K-dimensionaltree）。Kd樹的思想類似與索引、二分法查找的思想，它把整個多維空間劃分為特定的幾個部分，將搜索鎖定到部分特定空間內，從而減少搜索范圍和次數，節省搜索時間。它首先需要構建一個二叉樹，將所有的訓練樣本點均衡的分布到這個樹上。雖然構造這個二叉樹也要一些時間，但這是在實時預測之前就已經完成的工作，不占用預測時間。然后在正式預測時就開始搜索，不同于線型掃描的全數遍歷，它一開始從根節點搜索，通過與節點的坐標值比較決定其繼續往左還是往右分支繼續查找，直到葉節點。這時得到的葉結點只能算“當前最近點”，需要繼續“回溯”到父節點及其另外一個分支去查找是否有更近的點，這個過程一直“回溯”到根節點才結束，最后得到的“當前最近點”才是真正的最近點。通過這種搜索法使得時間復雜度從傳統線性掃描的O（N）降低到了O（logN），大大提高了效率。Kd樹更適合解決樣本數很多的情況，而對維度很高的情況解決效率并不高。

另一種常用的搜索法叫ball樹，不像Kd樹依賴坐標軸劃分矩形空間，ball樹通過球體來進行空間分割。相較Kd樹，它的主要優勢是在處理數據集分布不均勻，維度很高的問題時效率仍然很高，同時還支持距離度量使用核函數的情況。

5總結

K近鄰算法借鑒了空間分類思想，通過將特征值映射到多維空間，再根據不同數據的類別屬性來判斷待測樣本和哪一類最相似。算法雖然很簡單，但是在一些細節的設計上還是有很多環節需要注意。本文從K值選擇、距離度量、分類決策規則和計算復雜度解決等多個方面對該算法進行了剖析。