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

kNN （k-nearest neighbors）作為一個(gè)入門級(jí)模型，因?yàn)榧群唵斡挚煽浚瑢?duì)非線性問題支持良好，雖然需要保存所有樣本，但是仍然活躍在各個(gè)領(lǐng)域中，并提供比較穩(wěn)健的識(shí)別結(jié)果。

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

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

第一種：分類

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

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

第二種：回歸

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

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

綠色是擬合出來的曲線，用的是 sklearn 里面的 KNeighborsRegressor，可以看得出對(duì)非線性回歸問題處理的很好，但是還可以再優(yōu)化一下，k 個(gè)鄰居中，根據(jù)他們離測試點(diǎn)坐標(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 值，不考慮其他點(diǎn)（sklearn的做法），這樣得到的 Y 值就相對(duì)比較靠譜了：

這樣誤差就小多了，前面不考慮距離 y 值平均的方法在 sklearn 中稱為 uniform，后一種用距離做權(quán)重的稱為 distance。

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

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

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

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

第三種：One-class 識(shí)別

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

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

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

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

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

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

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

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

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

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

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

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

或者曼哈頓距離：

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

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

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

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

多項(xiàng)式核（POLY）：

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

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

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

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

Kai Yu 在 《Kernel Nearest-Neighbor Algorithm》中論證過基于核方法的 kNN 分類器比傳統(tǒng) kNN 分類器表現(xiàn)的更好，因?yàn)閮H僅是距離測量方式改變了一下，所以總體時(shí)間和傳統(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)行了驗(yàn)證，結(jié)果表明核化過的 kNN 分類器精度明顯好于傳統(tǒng)的 kNN，和 SVM 有得一拼：

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

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

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

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

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

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

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

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

如果我們的 kNN 使用了核方法的話，kd 樹就沒法用了，因?yàn)槟菚r(shí)候特征被映射到了高維的希爾伯特空間里去了，有可能無限維度，kd 樹就得靠邊站了。

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

第六種：超球體空間分割

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

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

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

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

因?yàn)榉秶阉饕仓恍枰蕾嚲嚯x計(jì)算，和矢量到底有幾個(gè)維度沒有關(guān)系，也不需要像 kdtree 一樣數(shù)坐標(biāo)軸。因此 ball-tree 除了構(gòu)造時(shí)間長點(diǎn)外，整體效率超過 kdtree，并且在矢量維度較高時(shí)，性能不會(huì)像 kdtree 一樣下降，同時(shí)還支持核化版本的 kNN。

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

第七種：冗余樣本剔除

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

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

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

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

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

話題總結(jié)

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

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

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

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

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