雷鋒網(wǎng) AI 科技評論按，本文作者韋易笑，本文首發(fā)于知乎專欄簡單代碼，雷鋒網(wǎng) AI 科技評論獲其授權(quán)轉(zhuǎn)載。以下為原文：

kNN （k-nearest neighbors）作為一個入門級模型，因為既簡單又可靠，對非線性問題支持良好，雖然需要保存所有樣本，但是仍然活躍在各個領(lǐng)域中，并提供比較穩(wěn)健的識別結(jié)果。

說到這里也許你會講，kNN 我知道啊，不就是在特征空間中找出最靠近測試樣本的 k 個訓(xùn)練樣本，然后判斷大多數(shù)屬于某一個類別，那么將它識別為該類別。

這就是書上/網(wǎng)絡(luò)上大部分介紹 kNN 的說辭，如果僅僅如此，我也不用寫這篇文章了。事實上，kNN 用的好，它真能用出一朵花來，越是基礎(chǔ)的東西越值得我們好好玩玩，不是么？

第一種：分類

避免有人不知道，還是簡單回顧下 kNN 用于分類的基本思想。

針對測試樣本 Xu，想要知道它屬于哪個分類，就先 for 循環(huán)所有訓(xùn)練樣本找出離 Xu 最近的 K 個鄰居（k=5），然后判斷這 K個鄰居中，大多數(shù)屬于哪個類別，就將該類別作為測試樣本的預(yù)測結(jié)果，如上圖有 4 個鄰居是紅色，1 是綠色，那么判斷 Xu 的類別為“紅色”。

第二種：回歸

根據(jù)樣本點，描繪出一條曲線，使得到樣本點的誤差最小，然后給定任意坐標(biāo)，返回該曲線上的值，叫做回歸。那么 kNN 怎么做回歸呢？

你有一系列樣本坐標(biāo)（xi, yi），然后給定一個測試點坐標(biāo) x，求回歸曲線上對應(yīng)的 y 值。用 kNN 的話，最簡單的做法就是取 k 個離 x 最近的樣本坐標(biāo)，然后對他們的 y 值求平均：

綠色是擬合出來的曲線，用的是 sklearn 里面的 KNeighborsRegressor，可以看得出對非線性回歸問題處理的很好，但是還可以再優(yōu)化一下，k 個鄰居中，根據(jù)他們離測試點坐標(biāo) x 的距離 d 的倒數(shù) 1/d 進(jìn)行加權(quán)處理：

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，后一種用距離做權(quán)重的稱為 distance。

這里曲線擬合的效果非常漂亮，你用梯度下降或者最小二乘法做擬合根本達(dá)不到這樣的效果，即便支持向量回歸 SVR 也做不到這么低的誤差率。如果你覺得有些過擬合的話，可以調(diào)節(jié) K 的值，比如增加 K 值，可以讓曲線更加平滑一些。

更好的做法是 wi 設(shè)置為 exp(-d) ，這樣 d=0 的時候取值 1，d 無窮大的時候，接近 0：

w[i] = math.exp(-d[i])

這樣即使 x 和某個訓(xùn)練樣本重合或者非常接近也不會把該 wi 弄成無窮大，進(jìn)而忽略其他樣本的權(quán)重，避免了 sklearn 里面那種碰到離群點都非要過去繞一圈的問題，曲線就會更平滑。

第三種：One-class 識別

One-class 分類/識別又稱為：異常點/離群點檢測，這個非常有用。假設(shè)我們的 app 需要識別 5 種不同的用戶手勢，一般的分類器只會告訴你某個動作屬于 1-5 哪個類型，但是如果是用戶進(jìn)行一些非手勢的普通操作，我們需要識別出來“不屬于任何類型”，然后需要在手勢模塊中不進(jìn)行任何處理直接忽略掉。

這個事情用傳統(tǒng)分類器非常困難，因為負(fù)樣本是無窮多，多到?jīng)]法列舉所有額外的手勢，我們只能收集正樣本。這和 0-9 數(shù)字手寫識別是一樣的，比如用戶寫了個 A 字母，我們需要判斷某個輸入圖像不是 0-9 中任何一個，但是我們除了 0-9 的樣本外沒法枚舉所有例外的可能。

這時候 One-class 識別器一直扮演著舉足輕重的作用，我們將 0-9 的所有樣本作為“正樣本”輸入，測試的時候檢測檢測測試值是否也屬于同類別，或者屬于非法的負(fù)類別。kNN 來做這件事情是非常容易的，我們用 NN-d 的本地密度估計方法：

方法是對待測試樣本 z ，先在訓(xùn)練樣本中找到一個離他最近的鄰居 B，計算 z 到 b 點的距離為 d1，然后再在訓(xùn)練樣本中找到一個離 B 最近的點 C，計算 BC 距離為 d2，如果：

d1 <= alpha * d2     # alpha 一般取 1

那么接受 z 樣本（識別為正類別），否則拒絕它（識別為負(fù)類別）。這個方法比較簡單，但是如果局部樣本太密集的話，d2 非常小，容易識別為負(fù)類別被拒絕。所以更成熟的做法是在訓(xùn)練樣本中找到 k 個離 B 最近的樣本點 C1 - Ck，然后把 d2 設(shè)置成 C1 - Ck 到 B 的距離的平均值。這個方法稱為 kNN-d，識別效果比之前只選一個 C 的 NN-d 會好很多。

進(jìn)一步擴(kuò)展，你還可以選擇 j 個離 z 最近的 B 點，用上面的方法求出 j 個結(jié)果，最后投票決定 z 是否被接受，這叫 j-kNN-d 方法，上面說到的方法就是 j = 1 的特殊情況。

對比 SVM 的 ONE_CLASS 檢測方法，(j) kNN-d 有接近的識別效果，然而當(dāng)特征維度增加時，SVM 的 ONE_CLASS 檢測精度就會急劇下降，而 (j) kNN-d 模型就能獲得更好的結(jié)果。

LIBSVM 里的三大用法：分類，回歸，ONE_CLASS（離群點檢測），同時也是監(jiān)督學(xué)習(xí)中的三類主要問題，這里我們?nèi)坑?kNN 實現(xiàn)了一遍，如果你樣本不是非常多，又不想引入各種包依賴，那么 kNN 是一個最簡單可靠的備用方案。

第四種：搭配核函數(shù)

俗稱 Kernel based kNN，SVM 之所以取得較大發(fā)展就是在引入核函數(shù)之后，而核函數(shù)并不是 SVM 特有，其他模型也都可以嫁接核函數(shù)，這種方法統(tǒng)稱為 “核方法”。

kNN 中最關(guān)鍵的一步就是求距離 d(xi, xj)，這個距離有很多種求法，比如傳統(tǒng)歐氏距離：

或者曼哈頓距離：

其實就是在距離函數(shù)上做文章，那么 kNN 引入核方法以后同樣是在距離函數(shù)上做文章。

基本思想是將線性不可分的低維度特征矢量映射到線性可分的高維特征空間中（有可能是無限維），矢量 x 映射到高維空間后稱為 φ(x)，那么核函數(shù) K(xi, xj) 代表兩個高維空間矢量的內(nèi)積，或者點乘：

K(xi, xj) = φ(xi) . φ(xj)

常用的核函數(shù)和 SVM 一樣，有這么幾個，比如常用的高斯核（RBF）：

多項式核（POLY）：

以及線性核（相當(dāng)于傳統(tǒng)歐式坐標(biāo)系下點乘）：

那么高維空間里兩個點的距離，核化以后距離的平方可以表達(dá)為：

經(jīng)過一次變換后，我們把 φ(xi) 和 φ(xj) 消除掉了，完全用關(guān)于 xi, xj 的核函數(shù)來表達(dá)距離，并不需要直接將 xi，xj 變換到高維空間才求距離，而是直接用核函數(shù)計算出來。

核方法如果你不熟悉，完全可以直接跳過，隨機(jī)挑選一個核函數(shù)，帶入到距離公式中用來求解 kNN 兩個樣本點的距離即可。

Kai Yu 在 《Kernel Nearest-Neighbor Algorithm》中論證過基于核方法的 kNN 分類器比傳統(tǒng) kNN 分類器表現(xiàn)的更好，因為僅僅是距離測量方式改變了一下，所以總體時間和傳統(tǒng) kNN 分類器仍然類似，但是效果好了很多：

在不同的數(shù)據(jù)集上，核化 kNN 都能比傳統(tǒng) kNN 表現(xiàn)的更精確和穩(wěn)定，他們使用 US Postal Service 數(shù)據(jù)和 BUPA Live Disorder 數(shù)據(jù)進(jìn)行了驗證，結(jié)果表明核化過的 kNN 分類器精度明顯好于傳統(tǒng)的 kNN，和 SVM 有得一拼：

同樣，Shehroz Khan 等人在《Kernels for One-Class Nearest Neighbour Classification》驗證了核化 kNN 在 One-Class 分類問題上取得了比 SVM One-class 更優(yōu)秀的識別能力，在數(shù)個數(shù)據(jù)集上達(dá)到了 87% - 95% 的準(zhǔn)確率。

第五種：搭配空間分割技術(shù)

針對大規(guī)模樣本時 kNN 性能不高的問題，大家引入了很多空間分割技術(shù)，比如 kdtree：

就是一種空間二分?jǐn)?shù)據(jù)結(jié)構(gòu)，構(gòu)建很簡單，選擇一個切割坐標(biāo)軸（所有樣本在該坐標(biāo)軸上方差最大）并將樣本按該坐標(biāo)軸的值排序，從中位切割成左右兩個部分，然后繼續(xù)遞歸切割，直到當(dāng)前節(jié)點只有一個樣本為止。

搜索的話就先遞歸找到目標(biāo)點 z 所在的葉子節(jié)點，以該節(jié)點包含的樣本 x 作為 “當(dāng)前最近點”，再以 x 到 z 的距離 d 為半徑，z 為圓心對整棵樹進(jìn)行遞歸范圍搜索（如果某子樹范圍和球體不相交就不往下遞歸），最近點一定落在該范圍中，一旦找到更近的點就即時縮小范圍。

kdtree 網(wǎng)上有很多文章和代碼，篇幅問題不打算細(xì)說，只想強(qiáng)調(diào)一點，網(wǎng)上大部分 kdtree 都是幫你找到最近的鄰居，但是最近的前 k 個鄰居怎么找？大部分文章都沒說，少部分說了，還是錯的（只是個近似結(jié)果）。

你需要維護(hù)一個長度為 K 的優(yōu)先隊列（或者最大堆），在找到最近鄰居的基礎(chǔ)上，將兄弟節(jié)點鄰近的樣本都填充到隊列里，直到隊列里裝滿 k 個樣本，此時以 z 為圓心，隊列里第 k 個離 z 最近的樣本為半徑，對 kd 樹做一次范圍搜索（前 k 個點一定落在該范圍內(nèi)），搜索過程中不斷更新優(yōu)先隊列并及時根據(jù)最新的第 k 個樣本離 z 的距離調(diào)整半徑。

這樣你就能精確的找出前 k 個離 z 最近的樣本了。kd 樹和維度相關(guān)，當(dāng)樣本維度不高時，kd 樹很快，但是樣本維度高了以后，kd 樹的性能就會開始下降了。同時 kd 樹因為要計算坐標(biāo)軸，所以僅僅適合在歐氏空間里進(jìn)行切割。

如果我們的 kNN 使用了核方法的話，kd 樹就沒法用了，因為那時候特征被映射到了高維的希爾伯特空間里去了，有可能無限維度，kd 樹就得靠邊站了。

所以我們需要超球體空間分割法。

第六種：超球體空間分割

其實就是 sklearn 里面的 ball-tree，也是一種空間二分法，但是它不依賴坐標(biāo)軸，只需要求解兩個樣本之間的距離就能構(gòu)造出來，這天生適合引入核技巧：

先從把所有樣本放到一個超球體里開始，找到一個樣本當(dāng)球心 x0，使得所有其他樣本到它的最大距離最短。然后找到一個離 x0 最遠(yuǎn)的點 x1，再找到離 x1 最遠(yuǎn)的點為 x2，然后把球體內(nèi)所有樣本按照離 x1 最近分配給 x1，離 x2 最近就分配到 x2，然后構(gòu)建兩個子球體，再用上面的方法重新調(diào)整球心，然后遞歸下去，直到只包含一個樣本，就不再切割，類似 kdtree。

還有一種做法是，將樣本全部放在最底層的葉子節(jié)點上，每個葉子節(jié)點包含很多個樣本，判斷切割的方式是某個節(jié)點所包含的樣本數(shù)如果少于閾值就不切割，否則進(jìn)行切割。

進(jìn)行范圍搜索時和 kdtree 一樣，先判斷頂層節(jié)點的超球體是否和目標(biāo)點 z 為圓心的目標(biāo)球體相交（兩個球體半徑相加是否 >= 兩球心之間的距離），如果不相交就跳過，相交的話繼續(xù)把該節(jié)點的左右兩個子球體拿過來判斷相交，相交的話遞歸重復(fù)上面步驟，直到抵達(dá)葉子節(jié)點。

因為范圍搜索也只需要依賴距離計算，和矢量到底有幾個維度沒有關(guān)系，也不需要像 kdtree 一樣數(shù)坐標(biāo)軸。因此 ball-tree 除了構(gòu)造時間長點外，整體效率超過 kdtree，并且在矢量維度較高時，性能不會像 kdtree 一樣下降，同時還支持核化版本的 kNN。

Kai Yu 等人用郵政數(shù)據(jù)進(jìn)行過測試，當(dāng)樣本數(shù)量增加，不規(guī)律性上升時，即便映射到高維核空間里，也會出現(xiàn)線性不可分的情況，此時 SVM 的準(zhǔn)確度就會下降，而裝配了 ball-tree 的核化 kNN 此時就能表現(xiàn)出較高的準(zhǔn)確性，同時兼具良好的查詢性能。

第七種：冗余樣本剔除

kNN 性能提升還可以通過在盡量不影響分類結(jié)果的情況下剔除冗余樣本來提升性能，比如經(jīng)典的 Condensed Nearest Neighbours Data Reduction 算法：

簡單的講就是先將樣本點刪除，然后用其他樣本判斷這個點，如果判斷結(jié)果正確，則認(rèn)為是一個冗余點，可以刪除，如果不正確就要保留。

經(jīng)過 reduction 過后的樣本數(shù)據(jù)和原來的不一樣，求解結(jié)果是一個近似解，只要誤差可控，可以極大的提高 kNN 的搜索性能，效果如下：

由圈圈變成點的是被剔除的樣本，從左到右可以看出基本上是邊緣部分的有限幾個樣本被保留下來了，結(jié)果非常誘人。

由于前面的空間分割技術(shù)并不會影響求解結(jié)果，所以大規(guī)模 kNN 一般是先上一個 ball-tree，還嫌不夠快就上冗余樣本剔除。唯一需要注意的地方是冗余剔除會影響 one-class 識別或其他依賴密度計算的東西，需要做一些額外處理。

話題總結(jié)

還有很多擴(kuò)展用法，比如搜索前 k 個最近鄰居時加一個距離范圍 d，只搜索距離目標(biāo) d 以內(nèi)的樣本，這樣可以間接解決部分 one-class 問題，如果同時離所有樣本都很遠(yuǎn)，就能返回 “什么都不是”，這個 d 的選取可以根據(jù)同類樣本的平均密度乘以一個 alpha 來計算。

在分類時，同時選取了多個鄰居進(jìn)行結(jié)果投票前同樣可以根據(jù)距離對投票結(jié)果加權(quán)，比如前面提到的距離的倒數(shù)，或者 exp(-d) 當(dāng)權(quán)重。

kNN 因為實現(xiàn)簡單，誤差可控（有證明），能處理非線性問題所以仍然活躍在各種應(yīng)用當(dāng)中，前面咱們又介紹了如何拓展它的用途，如何引入核函數(shù)降低它誤差，以及如何使用空間分割等技術(shù)提高它的性能。

總之，雖然很簡單，但確實值得好好玩玩，一套實現(xiàn)良好的 kNN 庫除了分類、回歸、異常識別外，搭配超球體空間切割還能做很多聚類相關(guān)的事情。用的好了，它不會讓你失望，可以成為你的一把有力的輔助武器，當(dāng)主武器沒法用時拿出來使喚下。

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。