前言

關于寫作：

博主（暫且如此自稱）是北京某高校的計算機系研究生在讀吼蚁，入行AI領域時間不久，正在努力進修问欠。最近利用工作之余的時間正在學習李航博士的《統(tǒng)計學習方法》肝匆，一方面希望能夠通過寫作整理思路，另一方面顺献，分享學習心得也希望可以和志同道合的小伙伴們共同探討進步啦~

github傳送門：

GitHub - wyynevergiveup/Statistical-Learning-Method: 《統(tǒng)計學習方法》--李航實現(xiàn)學習過程中的算法以加深理解

系列文章：

1.《統(tǒng)計學習方法》筆記（一）統(tǒng)計學習及監(jiān)督學習概論 - 簡書

2.《統(tǒng)計學習方法》筆記（二）感知機模型 - 簡書

3.《統(tǒng)計學習方法》筆記（三）K近鄰法 - 簡書

4.《統(tǒng)計學習方法》筆記（四）樸素貝葉斯法 - 簡書

正文

3.1 K近鄰算法（K-NN）

3.1.1 概述

k近鄰法是一種基本分類與回歸方法旗国。因其多用與分類問題，本文只討論其在分類問題中的應用注整。

k近鄰算法的輸入為樣本的特征向量能曾，對應于特征空間中的點嫁怀；輸出為樣本所屬的類別。具體地借浊，k近鄰算法給定一個訓練數(shù)據(jù)集塘淑，其中的樣本類別已定。對新的樣本進行分類時蚂斤，根據(jù)與其最近鄰的k個樣本的類別存捺，通過多數(shù)表決等方式進行預測。

因此曙蒸，k近鄰算法不需要顯式的學習過程捌治，它實際上是利用訓練集對特征向量空間進行了劃分，并作為其分類的“模型”纽窟。

k近鄰算法的三要素：1）k值的選擇肖油；2）距離度量；3）分類決策規(guī)則臂港。

3.1.2 算法形式化定義

KNN算法形式化定義

3.2 k近鄰模型

k近鄰法使用的模型實際上對應于對特征空間的劃分森枪。模型由三個基本要素決定，分別為：k值的選擇审孽、距離度量和分類決策規(guī)則县袱。

3.2.1 k值的選擇

k值的選擇往往會對k近鄰法的結果產(chǎn)生重大影響。

選擇較小的k值佑力，就相當于在較小的鄰域中的訓練實例進行預測式散，近似誤差會減小，估計誤差會增大打颤。（什么是近似誤差和估計誤差暴拄？）在這種情況下，只有與輸入樣本較近的訓練樣本對結果預測起作用编饺，因此乖篷，預測結果會對近鄰的樣本點非常敏感，如果鄰近的實例點恰好存在噪聲反肋，預測就很有可能會出錯那伐。換句話說，k值的減小意味著整體模型變得復雜石蔗，容易過擬合罕邀。

選擇較大的k值，就相當于在較大的鄰域中的訓練實例進行預測养距，估計誤差會減小诉探，近似誤差會增大。在這種情況下棍厌，與輸入樣本距離較遠的訓練樣本也會對預測起作用肾胯，使得預測發(fā)生錯誤竖席。換句話說，k值的增大意味著整體的模型變得簡單敬肚，容易欠擬合毕荐。

現(xiàn)在，我們來解釋一下什么是近似誤差和估計誤差艳馒。（此答案來自網(wǎng)絡憎亚，個人認為這種理解方式簡單易懂，值的推薦弄慰。）

近似誤差第美，更關注于“訓練”。最小化近似誤差陆爽，即為使估計值盡量接近真實值什往，但是這個接近只是對訓練樣本（當前問題）而言，模型本身并不是最接近真實分布慌闭。換一組樣本别威，可能就不近似了。這種只管眼前不顧未來預測的行為贡必，即為過擬合兔港。

估計誤差庸毫，更關注于“測試”仔拟、“泛化”。最小化估計誤差飒赃，即為使估計系數(shù)盡量接近真實系數(shù)利花，但是此時對訓練樣本（當前問題）得到的估計值不一定是最接近真實值的估計值；但是對模型本身來說载佳，它能適應更多的問題（測試樣本）炒事。

3.2.2 距離度量

特征空間中的兩個實例點的距離是兩個實例點相似程度的度量。這里介紹一種比較一般（通用）的距離度量—— $L_p$ 距離（或 $Minkowski$ 距離）蔫慧。

假設特征空間X是n維實數(shù)向量空間 $R^n$ , $x_i,x_j \in X,x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T,$ $x_i,x_j$ 之間的 $L_p$ 距離定義為：

? ?????????????????????????????????????????????????????????????????????? $L_p(x_i, x_j) = (\sum_{l=1}^n\vert x_i^{(l)} - x_j^{(l)} \vert ^p )^{\frac{1}{p}}$

這里的 $p\geq 1$ 挠乳。

當 $p=2$ 時，稱為歐式距離姑躲。

? ?????????????????????????????????????????????????????????????????????? $L_2(x_i, x_j) = (\sum_{l=1}^n\vert x_i^{(l)} - x_j^{(l)} \vert ^2 )^{\frac{1}{2}}$

當時睡扬，稱為曼哈頓距離。

? ?????????????????????????????????????????????????????????????????????? $L_p(x_i, x_j) = \sum_{l=1}^n\vert x_i^{(l)} - x_j^{(l)} \vert$

當時黍析，它是各個坐標距離的最大值卖怜。

? ?????????????????????????????????????????????????????????????????????? $L{\infty}(x_i, x_j) = max_l \vert x_i^{(l)} - x_j^{(l)} \vert$

下圖為2維空間中，p取不同值時阐枣，與原點的 $L_p$ 距離為1的點的圖形马靠。

Lp距離間的關系

3.2.3 分類決策規(guī)則

k近鄰法中分類決策規(guī)則往往是多數(shù)表決奄抽，即由輸入實例的k個近鄰的訓練實例中的多數(shù)類決定輸入實例的類別。

多數(shù)表決規(guī)則有如下解釋：如果分類的損失為0-1損失函數(shù)甩鳄，分類函數(shù)為：

? ?????????????????????????????????????????????????????????????????????? $f:R^n \rightarrow \{ c_1, c_2, ... ,c_K\}$

那么誤分類的概率為：

? ?????????????????????????????????????????????????????????????????????? $P(Y\neq f(X)) = 1-P(Y=f(X))$

對給定的實例 $x \in X$ 逞度，其最鄰近的k個訓練實例點構成集合 $N_k(x)$ 。如果涵蓋 $N_k(x)$ 的區(qū)域的類別時 $c_j$ 妙啃，那么誤分類率時：

? ?????????????????????????????????????????????????????????????????????? $\frac{1}{k} \sum_{x \in N_k{(x)}} I(y_i\neq c_j) = 1-\frac{1}{k}\sum_{x \in N_k{(x)}} I(y_i = c_j)$

要使誤分類率最小第晰，就要使 $\sum_{x \in N_k{(x)}} I(y_i = c_j)$ 最大，所以多數(shù)表決規(guī)則等價于經(jīng)驗風險最小化彬祖。

3.3 k近鄰法的實現(xiàn)：kd樹

未完待續(xù)