0
雷鋒網 AI 科技評論按，本文作者韋易笑，本文首發于知乎專欄簡單代碼，雷鋒網 AI 科技評論獲其授權轉載。以下為原文：
kNN （k-nearest neighbors）作為一個入門級模型，因為既簡單又可靠，對非線性問題支持良好，雖然需要保存所有樣本，但是仍然活躍在各個領域中，并提供比較穩健的識別結果。
說到這里也許你會講，kNN 我知道啊，不就是在特征空間中找出最靠近測試樣本的 k 個訓練樣本，然后判斷大多數屬于某一個類別，那么將它識別為該類別。
這就是書上/網絡上大部分介紹 kNN 的說辭，如果僅僅如此，我也不用寫這篇文章了。事實上，kNN 用的好，它真能用出一朵花來，越是基礎的東西越值得我們好好玩玩，不是么？
第一種：分類
避免有人不知道，還是簡單回顧下 kNN 用于分類的基本思想。
針對測試樣本 Xu，想要知道它屬于哪個分類，就先 for 循環所有訓練樣本找出離 Xu 最近的 K 個鄰居（k=5），然后判斷這 K個鄰居中，大多數屬于哪個類別，就將該類別作為測試樣本的預測結果，如上圖有 4 個鄰居是紅色，1 是綠色，那么判斷 Xu 的類別為“紅色”。
第二種：回歸
根據樣本點，描繪出一條曲線，使得到樣本點的誤差最小，然后給定任意坐標，返回該曲線上的值，叫做回歸。那么 kNN 怎么做回歸呢？
你有一系列樣本坐標（xi, yi），然后給定一個測試點坐標 x，求回歸曲線上對應的 y 值。用 kNN 的話，最簡單的做法就是取 k 個離 x 最近的樣本坐標，然后對他們的 y 值求平均：
綠色是擬合出來的曲線，用的是 sklearn 里面的 KNeighborsRegressor，可以看得出對非線性回歸問題處理的很好，但是還可以再優化一下，k 個鄰居中，根據他們離測試點坐標 x 的距離 d 的倒數 1/d 進行加權處理：
w = [ 1 / d[i] for i in range(k) ]
y = sum([ (w[i] * y[i]) for i in range(k) ]) / sum(w)
如果 x 剛好和某樣本重合，di = 0 的話，1/d 就正無窮了，那么直接取該樣本的 y 值，不考慮其他點（sklearn的做法），這樣得到的 Y 值就相對比較靠譜了：
這樣誤差就小多了，前面不考慮距離 y 值平均的方法在 sklearn 中稱為 uniform，后一種用距離做權重的稱為 distance。
這里曲線擬合的效果非常漂亮，你用梯度下降或者最小二乘法做擬合根本達不到這樣的效果，即便支持向量回歸 SVR 也做不到這么低的誤差率。如果你覺得有些過擬合的話，可以調節 K 的值，比如增加 K 值，可以讓曲線更加平滑一些。
更好的做法是 wi 設置為 exp(-d) ，這樣 d=0 的時候取值 1，d 無窮大的時候，接近 0：
w[i] = math.exp(-d[i])
這樣即使 x 和某個訓練樣本重合或者非常接近也不會把該 wi 弄成無窮大，進而忽略其他樣本的權重，避免了 sklearn 里面那種碰到離群點都非要過去繞一圈的問題，曲線就會更平滑。
第三種：One-class 識別
One-class 分類/識別又稱為：異常點/離群點檢測，這個非常有用。假設我們的 app 需要識別 5 種不同的用戶手勢，一般的分類器只會告訴你某個動作屬于 1-5 哪個類型，但是如果是用戶進行一些非手勢的普通操作，我們需要識別出來“不屬于任何類型”，然后需要在手勢模塊中不進行任何處理直接忽略掉。
這個事情用傳統分類器非常困難，因為負樣本是無窮多，多到沒法列舉所有額外的手勢，我們只能收集正樣本。這和 0-9 數字手寫識別是一樣的，比如用戶寫了個 A 字母，我們需要判斷某個輸入圖像不是 0-9 中任何一個，但是我們除了 0-9 的樣本外沒法枚舉所有例外的可能。
這時候 One-class 識別器一直扮演著舉足輕重的作用，我們將 0-9 的所有樣本作為“正樣本”輸入，測試的時候檢測檢測測試值是否也屬于同類別，或者屬于非法的負類別。kNN 來做這件事情是非常容易的，我們用 NN-d 的本地密度估計方法：
方法是對待測試樣本 z ，先在訓練樣本中找到一個離他最近的鄰居 B，計算 z 到 b 點的距離為 d1，然后再在訓練樣本中找到一個離 B 最近的點 C，計算 BC 距離為 d2，如果：
d1 <= alpha * d2 # alpha 一般取 1
那么接受 z 樣本（識別為正類別），否則拒絕它（識別為負類別）。這個方法比較簡單，但是如果局部樣本太密集的話，d2 非常小，容易識別為負類別被拒絕。所以更成熟的做法是在訓練樣本中找到 k 個離 B 最近的樣本點 C1 - Ck，然后把 d2 設置成 C1 - Ck 到 B 的距離的平均值。這個方法稱為 kNN-d，識別效果比之前只選一個 C 的 NN-d 會好很多。
進一步擴展，你還可以選擇 j 個離 z 最近的 B 點，用上面的方法求出 j 個結果，最后投票決定 z 是否被接受，這叫 j-kNN-d 方法，上面說到的方法就是 j = 1 的特殊情況。
對比 SVM 的 ONE_CLASS 檢測方法，(j) kNN-d 有接近的識別效果，然而當特征維度增加時，SVM 的 ONE_CLASS 檢測精度就會急劇下降，而 (j) kNN-d 模型就能獲得更好的結果。
LIBSVM 里的三大用法：分類，回歸，ONE_CLASS（離群點檢測），同時也是監督學習中的三類主要問題，這里我們全部用 kNN 實現了一遍，如果你樣本不是非常多，又不想引入各種包依賴，那么 kNN 是一個最簡單可靠的備用方案。
第四種：搭配核函數
俗稱 Kernel based kNN，SVM 之所以取得較大發展就是在引入核函數之后，而核函數并不是 SVM 特有，其他模型也都可以嫁接核函數，這種方法統稱為 “核方法”。
kNN 中最關鍵的一步就是求距離 d(xi, xj)，這個距離有很多種求法，比如傳統歐氏距離：
或者曼哈頓距離：
其實就是在距離函數上做文章，那么 kNN 引入核方法以后同樣是在距離函數上做文章。
基本思想是將線性不可分的低維度特征矢量映射到線性可分的高維特征空間中（有可能是無限維），矢量 x 映射到高維空間后稱為 φ(x)，那么核函數 K(xi, xj) 代表兩個高維空間矢量的內積，或者點乘：
K(xi, xj) = φ(xi) . φ(xj)
常用的核函數和 SVM 一樣，有這么幾個，比如常用的高斯核（RBF）：
多項式核（POLY）：
以及線性核（相當于傳統歐式坐標系下點乘）：
那么高維空間里兩個點的距離，核化以后距離的平方可以表達為：
經過一次變換后，我們把 φ(xi) 和 φ(xj) 消除掉了，完全用關于 xi, xj 的核函數來表達距離，并不需要直接將 xi，xj 變換到高維空間才求距離，而是直接用核函數計算出來。
核方法如果你不熟悉，完全可以直接跳過，隨機挑選一個核函數，帶入到距離公式中用來求解 kNN 兩個樣本點的距離即可。
Kai Yu 在 《Kernel Nearest-Neighbor Algorithm》中論證過基于核方法的 kNN 分類器比傳統 kNN 分類器表現的更好，因為僅僅是距離測量方式改變了一下，所以總體時間和傳統 kNN 分類器仍然類似，但是效果好了很多：
在不同的數據集上，核化 kNN 都能比傳統 kNN 表現的更精確和穩定，他們使用 US Postal Service 數據和 BUPA Live Disorder 數據進行了驗證，結果表明核化過的 kNN 分類器精度明顯好于傳統的 kNN，和 SVM 有得一拼：
同樣，Shehroz Khan 等人在《Kernels for One-Class Nearest Neighbour Classification》驗證了核化 kNN 在 One-Class 分類問題上取得了比 SVM One-class 更優秀的識別能力，在數個數據集上達到了 87% - 95% 的準確率。
第五種：搭配空間分割技術
針對大規模樣本時 kNN 性能不高的問題，大家引入了很多空間分割技術，比如 kdtree：
就是一種空間二分數據結構，構建很簡單，選擇一個切割坐標軸（所有樣本在該坐標軸上方差最大）并將樣本按該坐標軸的值排序，從中位切割成左右兩個部分，然后繼續遞歸切割，直到當前節點只有一個樣本為止。
搜索的話就先遞歸找到目標點 z 所在的葉子節點，以該節點包含的樣本 x 作為 “當前最近點”，再以 x 到 z 的距離 d 為半徑，z 為圓心對整棵樹進行遞歸范圍搜索（如果某子樹范圍和球體不相交就不往下遞歸），最近點一定落在該范圍中，一旦找到更近的點就即時縮小范圍。
kdtree 網上有很多文章和代碼，篇幅問題不打算細說，只想強調一點，網上大部分 kdtree 都是幫你找到最近的鄰居，但是最近的前 k 個鄰居怎么找？大部分文章都沒說，少部分說了，還是錯的（只是個近似結果）。
你需要維護一個長度為 K 的優先隊列（或者最大堆），在找到最近鄰居的基礎上，將兄弟節點鄰近的樣本都填充到隊列里，直到隊列里裝滿 k 個樣本，此時以 z 為圓心，隊列里第 k 個離 z 最近的樣本為半徑，對 kd 樹做一次范圍搜索（前 k 個點一定落在該范圍內），搜索過程中不斷更新優先隊列并及時根據最新的第 k 個樣本離 z 的距離調整半徑。
這樣你就能精確的找出前 k 個離 z 最近的樣本了。kd 樹和維度相關，當樣本維度不高時，kd 樹很快，但是樣本維度高了以后，kd 樹的性能就會開始下降了。同時 kd 樹因為要計算坐標軸，所以僅僅適合在歐氏空間里進行切割。
如果我們的 kNN 使用了核方法的話，kd 樹就沒法用了，因為那時候特征被映射到了高維的希爾伯特空間里去了，有可能無限維度，kd 樹就得靠邊站了。
所以我們需要超球體空間分割法。
第六種：超球體空間分割
其實就是 sklearn 里面的 ball-tree，也是一種空間二分法，但是它不依賴坐標軸，只需要求解兩個樣本之間的距離就能構造出來，這天生適合引入核技巧：
先從把所有樣本放到一個超球體里開始，找到一個樣本當球心 x0，使得所有其他樣本到它的最大距離最短。然后找到一個離 x0 最遠的點 x1，再找到離 x1 最遠的點為 x2，然后把球體內所有樣本按照離 x1 最近分配給 x1，離 x2 最近就分配到 x2，然后構建兩個子球體，再用上面的方法重新調整球心，然后遞歸下去，直到只包含一個樣本，就不再切割，類似 kdtree。
還有一種做法是，將樣本全部放在最底層的葉子節點上，每個葉子節點包含很多個樣本，判斷切割的方式是某個節點所包含的樣本數如果少于閾值就不切割，否則進行切割。
進行范圍搜索時和 kdtree 一樣，先判斷頂層節點的超球體是否和目標點 z 為圓心的目標球體相交（兩個球體半徑相加是否 >= 兩球心之間的距離），如果不相交就跳過，相交的話繼續把該節點的左右兩個子球體拿過來判斷相交，相交的話遞歸重復上面步驟，直到抵達葉子節點。
因為范圍搜索也只需要依賴距離計算，和矢量到底有幾個維度沒有關系，也不需要像 kdtree 一樣數坐標軸。因此 ball-tree 除了構造時間長點外，整體效率超過 kdtree，并且在矢量維度較高時，性能不會像 kdtree 一樣下降，同時還支持核化版本的 kNN。
Kai Yu 等人用郵政數據進行過測試，當樣本數量增加，不規律性上升時，即便映射到高維核空間里，也會出現線性不可分的情況，此時 SVM 的準確度就會下降，而裝配了 ball-tree 的核化 kNN 此時就能表現出較高的準確性，同時兼具良好的查詢性能。
第七種：冗余樣本剔除
kNN 性能提升還可以通過在盡量不影響分類結果的情況下剔除冗余樣本來提升性能，比如經典的 Condensed Nearest Neighbours Data Reduction 算法：
簡單的講就是先將樣本點刪除，然后用其他樣本判斷這個點，如果判斷結果正確，則認為是一個冗余點，可以刪除，如果不正確就要保留。
經過 reduction 過后的樣本數據和原來的不一樣，求解結果是一個近似解，只要誤差可控，可以極大的提高 kNN 的搜索性能，效果如下：
由圈圈變成點的是被剔除的樣本，從左到右可以看出基本上是邊緣部分的有限幾個樣本被保留下來了，結果非常誘人。
由于前面的空間分割技術并不會影響求解結果，所以大規模 kNN 一般是先上一個 ball-tree，還嫌不夠快就上冗余樣本剔除。唯一需要注意的地方是冗余剔除會影響 one-class 識別或其他依賴密度計算的東西，需要做一些額外處理。
話題總結
還有很多擴展用法，比如搜索前 k 個最近鄰居時加一個距離范圍 d，只搜索距離目標 d 以內的樣本，這樣可以間接解決部分 one-class 問題，如果同時離所有樣本都很遠，就能返回 “什么都不是”，這個 d 的選取可以根據同類樣本的平均密度乘以一個 alpha 來計算。
在分類時，同時選取了多個鄰居進行結果投票前同樣可以根據距離對投票結果加權，比如前面提到的距離的倒數，或者 exp(-d) 當權重。
kNN 因為實現簡單，誤差可控（有證明），能處理非線性問題所以仍然活躍在各種應用當中，前面咱們又介紹了如何拓展它的用途，如何引入核函數降低它誤差，以及如何使用空間分割等技術提高它的性能。
總之，雖然很簡單，但確實值得好好玩玩，一套實現良好的 kNN 庫除了分類、回歸、異常識別外，搭配超球體空間切割還能做很多聚類相關的事情。用的好了，它不會讓你失望，可以成為你的一把有力的輔助武器，當主武器沒法用時拿出來使喚下。
雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。
