當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

机器学习理论《统计学习方法》学习笔记：第三章 k近邻法

發(fā)布時間：2024/10/8 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了机器学习理论《统计学习方法》学习笔记：第三章 k近邻法小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

機(jī)器學(xué)習(xí)理論《統(tǒng)計(jì)學(xué)習(xí)方法》學(xué)習(xí)筆記：第三章 k近鄰法

3 k近鄰法
- 3.1 K近鄰算法
- 3.2 K近鄰模型
- - 3.2.1 模型
  - 3.2.2 距離度量
  - 3.2.3 K值的選擇
  - 3.2.4 分類決策規(guī)則
- 3.3 K近鄰法的實(shí)現(xiàn)：kd樹
- - 3.3.1 構(gòu)造kd樹
  - 3.3.2 搜索kd樹
- 本章概要

3 k近鄰法

K近鄰法（k-nearest neighbor,k-NN）是一種基本分類與回歸方法。K近鄰法的輸入為實(shí)例的特征向量，對應(yīng)于特征空間的點(diǎn)；輸出為實(shí)例的類別，可以取多類。
K近鄰法假設(shè)給定一個數(shù)據(jù)集，其中的實(shí)例類別已定。分類時，對新的實(shí)例，根據(jù)其K個最鄰近實(shí)例的類別，通過多數(shù)表決等方式進(jìn)行預(yù)測。因此，K近鄰法不具有顯式的學(xué)習(xí)過程。
K近鄰法實(shí)際上利用訓(xùn)練數(shù)據(jù)集對特征向量空間進(jìn)行劃分，并作為其分類的模型。K值的選擇、距離度量、及分類決策規(guī)則是K鄰近法的三個基本要素。

3.1 K近鄰算法

K近鄰算法簡單、直觀：給定一個訓(xùn)練數(shù)據(jù)集，對新的輸入實(shí)例，對新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的K個實(shí)例，這K個實(shí)例的多數(shù)屬于某個類，就把該輸入實(shí)例分為這個類。

K近鄰法
輸入：訓(xùn)練數(shù)據(jù)集 $T={(x1,y1),(x2,y2),?,(xN,yN)}T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $xi∈X?Rnx_i\in X \subseteq R^n$ ,為實(shí)例的特征向量， $yi∈Y={c1,c2,?,ck}y_i\in Y=\{c_1,c_2,\cdots,c_k\}$ 為實(shí)例的類別， $i=1,2,?,Ni=1,2,\cdots,N$ ；實(shí)例特征向量x。
輸出：實(shí)例x所屬的類y。
（1）根據(jù)給定的距離度量，在訓(xùn)練集 $T$ 中找出與x最鄰近的K個點(diǎn)，涵蓋這K個點(diǎn)的x的領(lǐng)域記作 $N_k(x)$ .
（2）在 $N_k(x)$ 中根據(jù)分類決策規(guī)則（如多數(shù)表決）決定x的類別y： $y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,Ky=arg\space max_{c_j}\sum_{x_i\in N_k(x)}I(y_i=c_j),i=1,2,\cdots,N;j=1,2,\cdots,K$ , $I$ 為指示函數(shù)，即當(dāng) $y_i=c_j$ 時 $I$ 為1，否則 $I$ 為 $0$ .

K近鄰法的特殊情況是 $k = 1$ 的情形，稱為最近鄰算法。對于輸入的實(shí)例點(diǎn)（特征向量）x，最近鄰法將訓(xùn)練數(shù)據(jù)集中與x最鄰近點(diǎn)的類作為x的類。
K近鄰法沒有顯式的學(xué)習(xí)過程。

3.2 K近鄰模型

K近鄰法使用的模型實(shí)際上對應(yīng)于特征空間的劃分，模型由三個基本要素：距離度量、K值得選擇、分類決策規(guī)則決定。

3.2.1 模型

K近鄰法中，當(dāng)訓(xùn)練集、距離度量（如歐式距離）、K值及分類決策規(guī)則（如多數(shù)表決）確定后，對于任何一個新的輸入實(shí)例，它所屬的類唯一的確定。這相當(dāng)于根據(jù)上述要素將特征空間劃分為一些子空間，確定子空間里每個點(diǎn)所屬的類。
特征空間中，對每個訓(xùn)練實(shí)例點(diǎn) $x_i$ ，距離該點(diǎn)比其他點(diǎn)更近的所有點(diǎn)組成的一個區(qū)域，叫做單元（cell）。每個訓(xùn)練實(shí)例點(diǎn)擁有一個單元，所有訓(xùn)練實(shí)例點(diǎn)的單元構(gòu)成對特征空間的一個劃分。最近鄰法將實(shí)例 $x_i$ 的類 $y_i$ 作為其單元中所有點(diǎn)的類標(biāo)記（Class Label）。這樣，每個單元的實(shí)例點(diǎn)的類別是確定的。
K近鄰法的模型對應(yīng)特征空間的一個劃分。

3.2.2 距離度量

特征空間中兩個實(shí)例點(diǎn)的距離是兩個實(shí)例點(diǎn)相似度的反映。K近鄰模型的特征空間一般是n為實(shí)數(shù)向量空間 $R^n$ 。使用的距離是歐式距離，也可以是其他距離，如更一般的 $L_p$ 距離或者M(jìn)inkowshi距離。
設(shè)特征空間 $X$ 是n維實(shí)數(shù)向量空間 $R^n$ , $xi,xj∈X,xi=(xi(1),xi(2),?,xi(n))T,xj=(xj(1),xj(2),?,xj(n))Tx_i,x_j\in X,x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},\cdots,x_j^{(n)})^T$ ， $x_i,x_j$ 的 $L_p$ 的距離定義為： $Lp(xi,xj)=(∑l=1n∣xi(l)?xj(l)∣p)1pL_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{1\over p}$ 這里 $p≥1p\ge 1$ 。
當(dāng) $p = 2$ 時，稱為歐式距離，即 $L2(xi,xj)=(∑l=1n∣xi(l)?xj(l)∣2)12L_2(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2)^{1\over 2}$
當(dāng) $p = 1$ 時，稱為曼哈頓距離，即 $L1(xi,xj)=∑l=1n∣xi(l)?xj(l)∣L_1(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|$
當(dāng) $p=∞p=\infty$ 時，是各個坐標(biāo)距離的最大值，即 $L∞(xi,xj)=maxl∣xi(l)?xj(l)∣L_{\infty}(x_i,x_j)=max_l|x_i^{(l)}-x_j^{(l)}|$
二維空間中，P不同取值時，與原點(diǎn)的 $L_p$ 距離為 $1(L_p=1)$ 的點(diǎn)的圖形。

3.2.3 K值的選擇

K值的選擇對K近鄰法的結(jié)果產(chǎn)生重大影響。
如果選擇較小的K值，就相當(dāng)于較小的鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測，學(xué)習(xí)的近似誤差會減小，只有與輸入實(shí)例較近的（相似的）訓(xùn)練實(shí)例才會對預(yù)測實(shí)例起作用。但缺點(diǎn)是學(xué)習(xí)的估計(jì)誤差會增大，預(yù)測結(jié)果會對近鄰的實(shí)例點(diǎn)非常敏感。如果鄰近的實(shí)例點(diǎn)恰巧是噪聲，預(yù)測就會出錯。換句話說，K值的減小意味著整體模型變得復(fù)雜，容易發(fā)生過擬合。
如果選擇較大的K值，就相當(dāng)于用較大領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測。其優(yōu)點(diǎn)是可以減少學(xué)習(xí)的估計(jì)誤差，但缺點(diǎn)是學(xué)習(xí)的近似誤差會增大。這時與輸入實(shí)例較遠(yuǎn)的（不相似的）訓(xùn)練實(shí)例也會對預(yù)測起作用，使預(yù)測發(fā)生錯誤。K值的增大就意味著整體的模型變得簡單。
如果K=N，那么無論輸入實(shí)例是什么，都將簡單的預(yù)測它屬于在訓(xùn)練實(shí)例中最多的類。這時，模型過于簡單，完全忽略訓(xùn)練實(shí)例中的大量有用信息，是不可取的。
在應(yīng)用中，K值一般取一個比較小的數(shù)值。通常采用交叉驗(yàn)證法來選取最優(yōu)的K值。

3.2.4 分類決策規(guī)則

K近鄰法中的分類決策規(guī)則往往是多數(shù)表決，即由輸入實(shí)例的K個鄰近的訓(xùn)練實(shí)例中的多數(shù)類決定輸入實(shí)例的類。
多數(shù)表決規(guī)則有如下解釋：如果分類的損失函數(shù)為0-1損失函數(shù)，分類函數(shù)為 $f:Rn→{c1,c2,?,ck}f:R^n\to \{c_1,c_2,\cdots,c_k\}$ 那么誤分類的概率是 $P(Y≠f(X))=1?P(Y=f(X))P(Y\neq f(X))=1-P(Y=f(X))$ 對給定的實(shí)例 $x∈Xx\in X$ ，其最近鄰的K個訓(xùn)練實(shí)例點(diǎn)構(gòu)成集合 $N_k(x)$ .
如果涵蓋 $N_k(x)$ 的區(qū)域的類別是 $c_j$ ，那么誤分類率是 $1k∑xi∈Nk(x)I(yi≠cj)=1?1k∑xi∈Nk(x)I(yi=cj){1\over k}\sum_{x_i\in {N_k(x)}}I(y_i\neq c_j)=1-{1\over k}\sum_{x_i\in {N_k(x)}}I(y_i= c_j)$
要使誤分類最小即經(jīng)驗(yàn)風(fēng)險最小，就要使 $1k∑xi∈Nk(x)I(yi=cj){1\over k}\sum_{x_i\in {N_k(x)}}I(y_i= c_j)$ 最大，所以多數(shù)表決規(guī)則等價于經(jīng)驗(yàn)風(fēng)險最小化。

3.3 K近鄰法的實(shí)現(xiàn)：kd樹

實(shí)現(xiàn)k近鄰法時，主要考慮的問題是如何對訓(xùn)練數(shù)據(jù)進(jìn)行快速k近鄰搜索，在特征空間的維數(shù)大，及訓(xùn)練數(shù)據(jù)容量大時尤為重要。
K近鄰法最簡單的實(shí)現(xiàn)方法就是線性掃描。這時要計(jì)算輸入實(shí)例與每一個實(shí)例的距離，當(dāng)訓(xùn)練集很大時，計(jì)算非常耗時，這種方法是不可行的。
為了提高K近鄰搜索的效率，可以考慮使用特殊的結(jié)構(gòu)存儲訓(xùn)練數(shù)據(jù)，以減少計(jì)算距離的次數(shù)。具體方法有很多，下面介紹其中的kd樹方法。

3.3.1 構(gòu)造kd樹

kd樹是一種對k維空間中的實(shí)例點(diǎn)進(jìn)行存儲，以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。kd樹是二叉樹，表示對k維空間的一個劃分（partition）。構(gòu)造kd樹相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分，構(gòu)成一系列的k維超矩形區(qū)域。kd樹的每個結(jié)點(diǎn)對應(yīng)于一個k維超矩形區(qū)域。
構(gòu)造kd樹的方法如下：構(gòu)造根節(jié)點(diǎn)，使根節(jié)點(diǎn)對應(yīng)于K維空間中，包含所有實(shí)例點(diǎn)的超矩形區(qū)域；通過下面的遞歸方法，不斷地對K維空間進(jìn)行切分，生成子結(jié)點(diǎn)。在超矩形區(qū)域（結(jié)點(diǎn)）上選擇一個坐標(biāo)軸和在此坐標(biāo)軸上的一個切分點(diǎn)，確定一個超平面，這個超平面通過選定的切分點(diǎn)并垂直于選定的坐標(biāo)軸，將當(dāng)前超矩形區(qū)域切分為左右兩個子區(qū)域（子結(jié)點(diǎn)）；這時，實(shí)例被分到兩個子區(qū)域，這個過程直到子區(qū)域內(nèi)沒有實(shí)例時終止（終止時的結(jié)點(diǎn)為葉結(jié)點(diǎn)）。在此過程中，將實(shí)例保存在相應(yīng)的結(jié)點(diǎn)上。
通常，依次選擇坐標(biāo)軸對空間切分，選擇訓(xùn)練實(shí)例點(diǎn)在選定坐標(biāo)軸上的中位數(shù)為切分點(diǎn)，這樣得到的kd樹是平衡的。注意，平衡的kd樹搜索時的效率未必是最優(yōu)的。

構(gòu)造平衡kd樹
輸入：k維空間數(shù)據(jù)集 $T={x1,x2,?,xN}T=\{x_1,x_2,\cdots,x_N\}$ 其中 $xi=(xi(1),xi(2),?,xi(k))T,i=1,2,?,Nx_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(k)})^T,i=1,2,\cdots,N$
輸出：kd樹
（1）開始：

構(gòu)造根結(jié)點(diǎn)，根結(jié)點(diǎn)對應(yīng)于包含 $T$ 的k維空間的超矩形區(qū)域。
選擇 $x^{(1)}$ 為坐標(biāo)軸，以 $T$ 中所有實(shí)例的 $x^{(1)}$ 坐標(biāo)的中位數(shù)為切分點(diǎn)，將根結(jié)點(diǎn)對應(yīng)的超矩形區(qū)域切分為兩個子區(qū)域。切分由通過切分點(diǎn)并與坐標(biāo)軸 $x^{(1)}$ 垂直的超平面實(shí)現(xiàn)。
由根節(jié)點(diǎn)生成深度為1的左右子結(jié)點(diǎn)：左子結(jié)點(diǎn)對應(yīng)坐標(biāo) $x^{(1)}$ 小于切分點(diǎn)的子區(qū)域，右子結(jié)點(diǎn)對應(yīng)于坐標(biāo) $x^{(1)}$ 大于切分點(diǎn)的子區(qū)域。
將落在切分超平面上的實(shí)例點(diǎn)保存在根結(jié)點(diǎn)。

（2）重復(fù)：

對深度為 $j$ 的結(jié)點(diǎn)，選擇 $x^{(l)}$ 為切分的坐標(biāo)軸， $l=j(modk)+1l=j(mod\space k)+1$ ，以該結(jié)點(diǎn)的區(qū)域中所有實(shí)例的 $x^{(l)}$ 坐標(biāo)的中位數(shù)為切分點(diǎn)，將該結(jié)點(diǎn)對應(yīng)的超矩形區(qū)域切分為兩個子區(qū)域。切分由通過切分點(diǎn)并與坐標(biāo)軸 $x^{(l)}$ 垂直的超平面實(shí)現(xiàn)。
由該結(jié)點(diǎn)生成深度為 $j + 1$ 的左、右子節(jié)點(diǎn)：左子結(jié)點(diǎn)對應(yīng)坐標(biāo) $x^{(l)}$ 小于切分點(diǎn)的子區(qū)域，右子結(jié)點(diǎn)對應(yīng)坐標(biāo) $x^{(l)}$ 大于切分點(diǎn)的子區(qū)域。

（3）直到兩個子區(qū)域沒有實(shí)例存在時停止。從而形成kd樹的區(qū)域劃分。

3.3.2 搜索kd樹

如何利用kd樹進(jìn)行k近鄰搜索？

利用kd樹可以省去對大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計(jì)算量。
給定一個目標(biāo)點(diǎn)，搜索其最近鄰。首先找到包含目標(biāo)點(diǎn)的葉結(jié)點(diǎn)。然后從葉結(jié)點(diǎn)出發(fā)，依次回退到父結(jié)點(diǎn)，不斷查找與目標(biāo)點(diǎn)最鄰近的結(jié)點(diǎn)，當(dāng)確定不可能存在更近的結(jié)點(diǎn)時終止。這樣的搜索就被限制在空間的局部區(qū)域上，效率大為提高。
包含目標(biāo)點(diǎn)的葉結(jié)點(diǎn)對應(yīng)包含目標(biāo)點(diǎn)的最小超矩形區(qū)域。以此葉結(jié)點(diǎn)的實(shí)例點(diǎn)作為當(dāng)前最近點(diǎn)。目標(biāo)點(diǎn)的最近鄰一定在以目標(biāo)點(diǎn)為中心，并通過當(dāng)前最近點(diǎn)的超球體的內(nèi)部。然后返回當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)，如果父結(jié)點(diǎn)的另一子結(jié)點(diǎn)的超矩形區(qū)域與超球體相交，那么在相交的區(qū)域內(nèi)尋找與目標(biāo)點(diǎn)更接近的實(shí)例點(diǎn)。如果存在這樣的點(diǎn)，將此點(diǎn)作為新的當(dāng)前最近點(diǎn)。算法轉(zhuǎn)到更上一級的父結(jié)點(diǎn)，繼續(xù)上述過程。如果父結(jié)點(diǎn)的另一子結(jié)點(diǎn)的超矩形區(qū)域與超球體不相交，或不存在比當(dāng)前最近點(diǎn)更近的點(diǎn)，則停止搜索。

用kd樹的最近鄰搜索
輸入：已構(gòu)造的kd樹，目標(biāo)點(diǎn)x；
輸出：x的最近鄰；
(1)在kd樹中找出包含目標(biāo)點(diǎn)x的葉結(jié)點(diǎn)：從根結(jié)點(diǎn)出發(fā)，遞歸地向下訪問kd樹。若目標(biāo)點(diǎn)x當(dāng)前維的坐標(biāo)小于切分點(diǎn)的坐標(biāo)，則移動到左子結(jié)點(diǎn)，否則移動到右子結(jié)點(diǎn)。直到子結(jié)點(diǎn)為葉結(jié)點(diǎn)為止。
(2)以此葉結(jié)點(diǎn)“當(dāng)前最近點(diǎn)”。
(3)遞歸地向上回退，在每個結(jié)點(diǎn)進(jìn)行以下操作：
（a）如果該結(jié)點(diǎn)保存的實(shí)例點(diǎn)比當(dāng)前最近點(diǎn)距離目標(biāo)更近，則以該實(shí)例點(diǎn)為當(dāng)前最近點(diǎn)。
（b）當(dāng)前最近點(diǎn)一定存在于該結(jié)點(diǎn)一個子結(jié)點(diǎn)對應(yīng)的區(qū)域。檢查該子結(jié)點(diǎn)的父結(jié)點(diǎn)的另一子結(jié)點(diǎn)對應(yīng)的區(qū)域是否有更近的點(diǎn)。具體地，檢查另一子結(jié)點(diǎn)對應(yīng)的區(qū)域是否與以目標(biāo)點(diǎn)為球心、以目標(biāo)點(diǎn)與當(dāng)前最近點(diǎn)間的距離為半徑的超球體相交。
如果相交，可能在另一個子結(jié)點(diǎn)對應(yīng)的區(qū)域內(nèi)存在距目標(biāo)點(diǎn)更近的點(diǎn)，移動到另一個子結(jié)點(diǎn)。接著，遞歸地進(jìn)行最近鄰搜索。
如果不相交，向上回退。
(4)當(dāng)回退到根結(jié)點(diǎn)時，搜索結(jié)束。最后的當(dāng)前最近點(diǎn)即為x的最近鄰點(diǎn)。

如果實(shí)例點(diǎn)是隨機(jī)分布的，kd樹搜索的平均計(jì)算復(fù)雜度是 $O(logN)O(log\space N)$ ，這里 $N$ 是訓(xùn)練實(shí)例數(shù)。kd樹更適用于訓(xùn)練實(shí)例數(shù)遠(yuǎn)大于空間維數(shù)時的k近鄰搜索。當(dāng)空間維數(shù)接近訓(xùn)練實(shí)例數(shù)時，它的效率會迅速下降，幾乎接近線性掃描。

本章概要

k近鄰法是基本且簡單的分類與回歸方法。k近鄰法的基本做法是：對給定的訓(xùn)練實(shí)例點(diǎn)和輸入實(shí)例點(diǎn)，首先確定輸入實(shí)例點(diǎn)的k個最近鄰訓(xùn)練實(shí)例點(diǎn)，然后利用這k個訓(xùn)練實(shí)例點(diǎn)的類的多數(shù)來預(yù)測輸入實(shí)例點(diǎn)的類。

k近鄰模型對應(yīng)于基于訓(xùn)練數(shù)據(jù)集對特征空間的一個劃分。k近鄰法中，當(dāng)訓(xùn)練集、距離度量、k值及分類決策規(guī)劃確定后，其結(jié)果唯一確定。

k近鄰法三要素：距離度量、k值的選擇、分類決策規(guī)則。常用的距離度量是歐氏距離及更一般的

L_p

距離。k值小時，k近鄰模型更復(fù)雜；k值大時，k近鄰模型更簡單。k值的選擇反映了對近似誤差與估計(jì)誤差之間的權(quán)衡，通常由交叉驗(yàn)證選擇最優(yōu)的k。常用的分類決策規(guī)則是多數(shù)表決，對應(yīng)于經(jīng)驗(yàn)分線最小化。

k近鄰法的實(shí)現(xiàn)，需要考慮如何快速搜索k個最近鄰點(diǎn)。kd樹是一種便于對k維空間中的數(shù)據(jù)進(jìn)行快速檢索的數(shù)據(jù)結(jié)構(gòu)。kd樹是二叉樹，表示對k維空間的一個劃分，其每個結(jié)點(diǎn)對應(yīng)于k維空間劃分中的一個超矩形區(qū)域。利用kd樹可以省去對大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計(jì)算量。

總結(jié)

以上是生活随笔為你收集整理的机器学习理论《统计学习方法》学习笔记：第三章 k近邻法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇：机器学习理论《统计学习方法》学习笔记：第
下一篇：机器学习理论《统计学习方法》学习笔记：第