機器學習總結-K近鄰（KNN）演算法

05-02

1. 引言

K近鄰演算法是一種基本的分類和回歸方法。在分類問題中，KNN演算法假設給定的訓練集的實例類別已經確定，對於新來的實例，KNN演算法根據其k個最近鄰的訓練集實例的類別，通過多數表決等方式對新實例的類別進行預測。
KNN演算法的三個基本要素是：k值的選擇（即輸入新實例要取多少個訓練實例點作為近鄰），距離度量方式（歐氏距離，曼哈頓距離等）以及分類的決策規則（常用的方式是取k個近鄰訓練實例中類別出現次數最多者作為輸入新實例的類別）。

2. 演算法實現

輸入：訓練數據集 $T= left{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) ight}$ ，其中 $x_i in chi subseteq R^n$ 為訓練實例的特徵向量， $y_iin gamma subseteq left{ c_1,c_2,c_3,...,c_k ight}$ 為訓練實例的類別。
輸出：新輸入實例 $x$ 所屬類別 $y$

(1) 根據給定的距離度量，在訓練集T中找到與 $x$ 最近的k個點，涵蓋這k個點的鄰域記為 $N_k(x)$
(2) 在 $N_k(x)$ 中根據分類決策規則（如多數表決）決定 $x$ 所屬的類別 $y$ ：

$y = arg max limits_{c_j} sum_{x_i in N_k(x)}{I(y_i=c_j)} , i = 1,2,3,...,N; j = 1,2,3,...,k$
其中I為指示函數，僅當 $y_i = c_j$ 時I(*)的值為1，否則為0.

距離度量方式

較為常用的距離度量方式是歐式距離，定義可以使用其他更為一般的 $L_p$ 距離或閔科夫斯基（Minkowski）距離.

設特徵空間 $chi$ 為n為實數向量空間 $R^n$ ， $x_i,x_j in chi,x_i=(x^{(1)}_i,x^{(2)}_i,x^{(3)}_i,...,x^{(n)}_i)^T$ ， $x_j=(x^{(1)}_j,x^{(2)}_j,x^{(3)}_j,...,x^{(n)}_j)^T$ ， $x_i,x_j$ 的 $L_p$ 距離可定義為：
$L_p(x_i,x_j) = (sum_{l=1}^{n}{|x_i^{(l)}-x_j^{(l)}|^p} )^{1/p}$ ………….閔科夫斯基距離

$L_p(x_i,x_j) = (sum_{l=1}^{n}{|x_i^{(l)}-x_j^{(l)}|^2} )^{1/2}$ …….....歐氏距離，p取2
$L_p(x_i,x_j) = sum_{l=1}^{n}{|x_i^{(l)}-x_j^{(l)}} |$ ……………..曼哈頓距離，p取1

$L_p(x_i,x_j) = max limits_l {|x_i^{(l)}-x_j^{(l)}} |$ ……………..p取 $infty$

更多距離度量方式可參考各種距離 - 我只想做一個努力的人 - 博客頻道 - CSDN.NET

k值選擇

一般會先選擇較小的k值，然後進行交叉驗證選取最優的k值。k值較小時，整體模型會變得複雜，且對近鄰的訓練實例點較為敏感，容易出現過擬合。k值較大時，模型則會趨於簡單，此時較遠的訓練實例點也會起到預測作用，容易出現欠擬合，特殊的，當k取N時，此時無論輸入實例是什麼，都會將其預測為屬於訓練實例中最多的類別。

分類決策規則

常採用多數表決規則。對於給定的實例 $xin chi$ ，其最近鄰的k個訓練實例點構成集合 $N_k(x)$ ，若涵蓋 $N_k(x)$ 的區域的類別為 $c_j$ ，則誤分類率為
$frac{1}{k}sum_{x_i in N_k(X)}{i(y_i e c_j)=1-frac{1}{k}}sum_{x_i in N_k(X)}{i(y_i = c_j)}$
要使誤分類率最小即經驗風險最小，此時要使得 $sum_{x_i in N_k(X)}{i(y_i = c_j)}$ 最大，因此多數表決規則等價與經驗風險最小化。

基礎KNN演算法實現

基礎KNN演算法實現(參考《機器學習實戰》)https://github.com/undersunshine/machine_learning_algorithms/tree/master/K_nearest_neighbor
推薦閱讀：

※python3機器學習經典實例-第五章構建推薦引擎21
※機器學習項目如何管理：工作內容
※Fenchel-Lengendre Duality觀點下的優化演算法們(I):前言
※Python預測分析核心演算法——Day4、5、6
※[貝葉斯一]之貝葉斯定理

TAG:機器學習 |