機器學習實戰（3）—— KNN 原理部分

k 近鄰（k-Nearest Neighbor，簡稱 kNN）學習是一種監督學習方法。

原理：

給定測試樣本，基於某種距離度量找出訓練集中與其最靠近的 k 個訓練樣本，然後基於這 k 個 “鄰居” 的信息來進行預測。

在分類任務中，可使用 “投票法”，即選擇這 k 個樣本中出現次數最多的類別標記作爲預測結果。還可以基於距離遠近加權平均或加權投票，距離越近的樣本權重越大。

k 近鄰是一種 “懶惰學習”，沒有顯式的訓練過程！

只是把樣本保存起來，當有需要預測的樣本時，直接根據距離等預測。

下圖中，綠色樣本應該預測到哪一類中呢？

當 k = 1，預測爲紅色三角形一類

當 k = 3，預測爲紅色三角形一類

當 k = 5，預測爲藍色矩形一類

顯然，k 是一個重要參數，當 k 選擇不同值時，分類結果可能不同。

如果採用不同的距離計算方式，“鄰近” 的樣本可能有顯著差異。

k 鄰近法的 3 個基本要素：

（1）距離度量  （2）k 值的選擇  （3）分類決策規則

k 鄰近算法的數學描述：

輸入：訓練數據集 T={（x1，y1），（x2，y2），...，（xN , yN) }

其中，x 爲實例的特徵向量，y 爲實例的類別

輸出：實例 x 所屬的類 y

（1）根據給定的距離度量，在訓練集 T 中找出與 x 最鄰近的 k 個點，涵蓋這 k 個點的 x 的鄰域記作 Nk（x）

（2）在 Nk（x）中根據分類決策規則（如多類表決）決定 x 的類別 y：

argument of the maximum/minimum

arg max f(x): 當 f(x) 取最大值時，x 的取值

arg min f(x)：當 f(x) 取最小值時，x 的取值

I 爲指示函數，即當 yi=cj 時 I 爲 1，否則 I 爲 0，即多數表決，找出最多的類別。

k 鄰近法的特殊情況是 k=1 的情形，稱爲最近鄰法，最近鄰法將訓練數據集中與 x 最鄰近點的類作爲 x 的類。

（1 ) 距離度量：

距離在某種程度上是一種相似程度的反映

比如上海距離蘇州很近，距離哈爾濱較遠，從某種程度上認爲上海和蘇州的相似性大於上海和哈爾濱的相似性。

k 近鄰模型一般使用的是歐氏距離（小學初中就學過了）

其實還有其他距離：

如 Lp 距離、Minkowski（閔可夫斯基）距離

（1）距離度量：

設特徵空間 X 是 n 維實數向量空間 Rn， xi，xjX，

xi=（xi（1）xi（2） ，..., xi（n）)T      

xj=（xi（1）xi（2） ，..., xi（n）)T, 

xi , xj 的 Lp 距離定義爲：

當 p=2 時，爲歐氏距離：

其實就是大家超級熟悉的：

就是常說的，兩點之間的直線段長度（3 維以上圖形無法表示！）

當 p=1 時，爲曼哈頓距離：

曼哈頓距離的由來：

曼哈頓距離的命名原因是從規劃爲方型建築區塊的城市（如曼哈頓）間，最短的行車路徑而來，紅色、藍色、黃色三者的曼哈頓距離相等，綠色爲歐氏距離。

如果圖中一個白色正方形的邊長爲 1

左下角座標爲（0,0），往右、上是正向

則紅色路線的曼哈頓距離爲：

|6-0| + |6-0| = 12

當 p= 時，爲各個座標距離的最大值，即：

（小提示：爲無窮大）

近似誤差：可以理解爲對現有訓練集的訓練誤差。

估計誤差：可以理解爲對測試集的測試誤差。

近似誤差關注訓練集，如果近似誤差小了會出現過擬合的現象，對現有的訓練集能有很好的預測，但是對未知的測試樣本將會出現較大偏差的預測。模型本身不是最接近最佳模型。

估計誤差關注測試集，估計誤差小了說明對未知數據的預測能力好。模型本身最接近最佳模型。

(2) k 值選擇

k 值的選擇會對 k 近鄰的結果產生重大影響。

如果 k 選的較小，相當於用較小的鄰域中的訓練實例進行預測，預測結果會對鄰近   的實例點非常敏感，如果鄰近的點是噪聲預測就會錯，k 減小意味着模型變得複雜，容易發生過擬合，即近似誤差小，估計誤差大。

如果 k 選擇較大，相當於用較大的鄰域中的訓練實例進行預測，近似誤差大，估計誤差小，意味着模型變得簡單，較遠處（不相似的）訓練實例也會起着預測作用，可能會欠擬合。

k 一般取一個較小的數值，通常採用交叉驗證法選取最佳的 k 值。

監督學習是選擇模型 f 作爲作爲決策函數，對於給定的輸入 X，由 f（X） 給出相應的輸出 Y ，這個輸出的預測值 f（X）和真實值 Y 可能一致也可能不一致，用一個損失函數（loss function）來度量預測錯誤的程度，損失函數是 f（X ) 和 Y 的非負實值函數，記作 L (Y , f（X) )

機器學習中常見的損失函數：

（1）0-1 損失函數（0-1 loss function）

預測值爲 f（X），真實值爲 Y

即預測正確則沒有損失（損失爲 0），預測錯誤損失爲 1

預測是否正確的標準是：預測值是否等於目標值

（2）平方損失函數（quadratic loss functon）

（3）絕對損失函數（absolute loss function）

（4）對數損失函數（logarithmic loss function）

3）分類決策規則

k 鄰近法中的分類決策規則往往是多數表決，即由輸入實例的 k 個鄰近的訓練實例中的多數類決定輸入實例的類。

說得通俗一點，就是等權重投票選出最多票數的！

多數表決規則有着如下解釋：

如果分類的損失函數爲 0-1 損失，分類函數爲

(即通過 f 分類模型能將輸入分類爲 c1，c2，...,cK）

則錯誤分類的概率爲：

上式左邊是誤分類概率，右邊是 1 減去正確分類的概率

因爲兩概率之和爲 1

這就是 KNN 算法的原理，你學會了麼？

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/bDQjXO4afrE_wxfNwjaqmA