沒想到你是這樣的「兔子」---kNN

01-28

導語：商業哲學家 Jim Rohn 說過一句話，「你，就是你最常接觸的五個人的平均。」那麼，在分析一個人時，我們不妨觀察和他最親密的幾個人。同理的，在判定一個未知事物時，可以觀察離它最近的幾個樣本，這就是 kNN（k最近鄰）的方法。

簡介

kNN還真是直接講例子最好懂。大家都喜歡兔子，所以就來說一說兔子的事情吧。

有一種兔子叫作悲傷（Grief），它們的平均身高是 50 厘米，平均體重 5 公斤。我們拿來一百個悲傷，分別測量它們的身高和體重，畫在坐標圖上，用綠色方塊表示。

還有一種兔子呢，叫作痛苦（Agony）。它們體型比較小，平均身高是 30 厘米，平均體重是 4 公斤。我們將一百個痛苦的身高和體重畫在同一個坐標圖上，用藍色三角表示。

最後一種兔子叫絕望（Despair）。它們的平均身高45厘米，但體重較輕，平均只有2.5公斤。一百隻絕望的數據用黃色圓圈表示。

在這些數據中，(身高,體重) 的二元組叫做特徵（features），兔子的品種則是分類標籤（class label）。我們想解決的問題是，給定一個未知分類的新樣本的所有特徵，通過已知數據來判斷它的類別。

北京十八環外有一個小樹林里經常出現這三種兔子。為了了解它們的生態環境，某研究團隊想知道三種兔子的數量比例；可是這些兔子又太過危險，不能讓人親自去做，所以要設計一個全自動的機器人，讓它自己去樹林里識別它遇到的每一個兔子的種類。啊，為了把故事講圓，還要假設他們經費不足，所以機器只有測量兔子的身高和體重的能力。

那麼現在有一迷之兔子，我們想判斷它的類別，要怎麼做呢？按照最普通的直覺，應該在已知數據里找出幾個和我們想探究的兔子最相似的幾個點，然後看看那些兔子都是什麼個情況；如果它們當中大多數都屬於某一類別，那麼迷之兔子大概率也就是那個類別了。

於是乎，我們給機器人預設一個整數 k，讓它去尋找距離最近的k個數據樣本進行分析。好，機器發現了一隻兔子，它長著八條腿，三十二隻眼睛，毛茸茸的小尾巴，齊刷刷的八十六顆獠牙，面相猙獰，散發著噩夢般的腐臭，發出來自地獄底處的咆哮… 差不多就是這個樣子（作者手繪）：

可我們的機器才識別不了那麼多，它只測量出這隻兔子身長 40 厘米，體重 2.7 公斤，就是下面圖中那顆閃閃發亮的紅星

kNN 演算法如何對這次觀測進行分類要取決於k的大小。直覺告訴我們迷之兔像是一隻絕望，因為除了最近的藍色三角外，附近其他都是黃色圓圈。的確，如果設 k=15，演算法會判斷這隻兔子是一隻絕望。但是如果設 k=1，那麼由於距離最近的是藍色三角，會判斷迷之兔子是一隻痛苦。

如果按照15NN和1NN的方法對這個二維空間上的每一個點進行分類，會形成以下的分割

在兩組分類中，1NN 的分類邊界明顯更「崎嶇」，但是對歷史樣本沒有誤判；而 15NN 的分類邊界更平滑，但是對歷史樣本有發生誤判的現象。選擇k的大小取決於對偏差和方差之間的權衡，本篇不進行更深探討，讀者在使用 kNN 時憑感覺選一個 k 就好。

距離函數

我們在上面的例子中把一個很重要的概念隱藏了起來，在選擇一個數量k還只是小問題，更重要的是距離的計算方法。畢竟，當我們說「最近的k個點」時，這個「近」是怎麼衡量的？

在數學中，一個空間上距離的嚴格定義如下：

設 MM 為一個空間，MM 上的一個距離函數是一個函數 d:M×M→R，滿足

? d(x,y)≥0 ?x,y∈M

? d(x,y)=0?（等價於符號，不知為何是方塊。。）x=y

? d(x,y)=d(y,x) ?x,y∈M

? d(x,z)≤d(x,y)+d(y,z) ?x,y,z∈M

兩個點 x,y 之間的距離就是 d(x,y)。

我們一般最常用的距離函數是歐氏距離，也稱作 L2 距離。如果 x=(x1,x2,…,xn) 和 y=(y1,y2,…,yn) 是 nn 維歐式空間 Rn 上的兩個點，那它們之間的 L2 距離是

L2 是更普遍的 Lp 距離在 p=2 時的特列。Lp 距離的函數 dp 定義如下：對於 1≤p<∞，有

還有 L∞ 距離

在實際應用中，距離函數的選擇應該根據數據的特性和分析的需要而定，本篇就不進行更深入的探討，一般情況下使用最常用的 L2 函數即可。

但是！注意！使用 kNN 時需要根據特徵數據的取值區間來調整坐標軸的比例，這個做法叫作標準化或者歸一化。為什麼要這麼做呢？拿上面的例子來說，一隻兔子的身長（cm）數值平均是它的體重（kg）的 10 倍左右，如果我們在這組數值上直接使用 L2 距離函數的話就會導致橫軸的距離比重明顯放大，分類結果也不合理，如下圖所示

如果把坐標軸成其他的單位，比如毫米和噸，並用相應的新數值來計算距離，又會得到完全不同的分類標準。甚至，在極端情況下，如果身高用納米並且體重用噸計量，那麼相比之下身高的數值會奇高無比，以至於兩點之間的距離是完全由身高決定的，體重則沒有任何權重。為了解決這個問題，我們應該在計算距離時把所有坐標軸進行歸一化。

在之前的例子中，由於橫軸數值大約是豎軸的 10 倍左右，所以我們將橫軸（身高）的數值壓縮 10 倍，即計算距離時使用

就可以得出合理的 kNN 分類。

一般來說，假設進行 kNN 分類使用的樣本的特徵是，取每一軸上的最大值減最小值

並且在計算距離時將每一個坐標軸除以相應的 Mj 以進行歸一化，即

便可以規避坐標軸比例失衡的問題。

概率 kNN

上面的kNN演算法返回的是對一組特徵的絕對分類，告訴我們這隻兔子被判斷為哪一個類別。可有時我們並不想知道一個確切地分類，而想知道它屬於某個分類的概率是多大。比如我們發現一隻身長 37 體重 4.8 的小兔兔，在下圖五角星的位置。

這隻兔子的特徵數據在悲傷和痛苦的分界處，機器不論判斷它屬於哪個類別都很有可能是錯的。這時，類似「它有一半可能性是痛苦，一半可能性是悲傷」的反饋會更有意義。

為了這個目的，我們同樣找找出距離問題特徵最近的 k 個樣本，但與其尋找數量最多的分類，我們統計其中每個類別的分別有多少個，再除以 kk 得到一個屬於每一個類別概率值。比如在上面的圖裡，距離五角星最近的 15 個樣本中，有 8 只悲傷和 7 只痛苦，由此判斷：它有 53% 的可能性是悲傷，47% 的可能性是痛苦，0%的可能性是絕望。

在整個二維空間中的每一個點上進行概率 kNN 演算法，可以得到每個特徵點是屬於某個類別的概率熱力圖，圖中顏色越深代表概率越大。

相比於絕對的分類，這些概率的計算會給我們更有效的表述以及更多的應用空間。比如說，我們知道悲傷兔子喜歡向我們的機器人上噴洒奇怪的粘液，毫無作用毫無意義的綠色的粘液，就像這樣（作者手繪）：

倒不是因為別的，我們就是覺得這種粘液很噁心，清洗起來也很麻煩，所以我們想讓機器人在測量並發現是悲傷之後馬上掉頭逃跑。但是如果機器發現了一隻體型接近痛苦的悲傷，並且普通的 kNN 演算法發生誤判，沒有馬上逃跑，那麼最後就會被噴了。所以我們使用概率 kNN 的演算法並且使用以下風控原則：只要發現兔子有 30% 以上的概率是悲傷，就馬上逃跑。從此之後，機器人就再也沒被噴過。

結語

不知你有沒有發現，我跟你講了這麼多關於兔子的事，卻絲毫沒有提及如何用代碼計算 kNN。這是因為 kNN 雖然思路簡單，但實現起來有一個問題，那就是計算量很大；當數據量很多時，拿一組特徵來和所有樣本依次計算距離並選取最近的 k 個，是非常耗費時間的。所以，在量化課堂接下來的文章中，我們將講解 kNN 的一個高效演算法—kd樹。

想看代碼的到這裡哦：一隻兔子幫你理解機器學習的kNN演算法-JoinQuant量化交易平台