k 近鄰是什么
k 近鄰法是機(jī)器學(xué)習(xí)中最基本的分類和回歸方法，也稱為kNN算法。通常k近鄰法用于分類問題。
k近鄰法假定給定一個訓(xùn)練數(shù)據(jù)集，其中實(shí)例類別已定。分類時，對新的實(shí)例，根據(jù)其K個最近鄰的訓(xùn)練實(shí)例類別，一般通過多數(shù)表決的方式來進(jìn)行預(yù)測。
例如，有兩堆水果，一堆是橙子，一堆是柚子，新拿到一個水果，判斷是橙子還是柚子。一般來說，柚子更大更紅。那么判斷和該水果最相近的 3 個水果是什么，比如 3 個最近的鄰居是柚子，那么我們可以判斷新拿到的水果是柚子，這就是 kNN 算法。
k近鄰算法
k近鄰算法簡單，直觀有效。
輸入：給定一個訓(xùn)練數(shù)據(jù)集T={(x1, y1), (x2, y2), ..., (xn, yn)}, 其中xi為實(shí)例的特征向量，yi為實(shí)例的類別。
輸出：實(shí)例x所屬的類y。
- 根據(jù)給定的距離度量， 在訓(xùn)練集T中尋找與x最近鄰的k個點(diǎn)，涵蓋這k個點(diǎn)的x的鄰域記作Nk(x)
-
在Nk(x)中根據(jù)分類決策規(guī)則(如多數(shù)表決)決定x的類別y：
其中I為指示函數(shù)，當(dāng)yi = cj時I為1，否則I為0
特別的，當(dāng)k=1時，稱為最近鄰算法。注意，k近鄰法沒有顯示的學(xué)習(xí)過程。
K近鄰模型
k近鄰模型對應(yīng)于特征空間的劃分。模型由3個基本要素構(gòu)成:
- K值選擇
- 距離度量
- 分類決策規(guī)則
當(dāng)訓(xùn)練集，距離度量，k值以及分類決策規(guī)則確定后，對于新輸入的任何一個實(shí)例，它所屬的類別唯一的確定。
距離度量
特征空間中的兩個實(shí)例點(diǎn)是兩個實(shí)例點(diǎn)相似程度的反映.k近鄰模型的特征空間一般是n維的實(shí)數(shù)向量空間。
當(dāng)p=2時，則是歐式距離。即:
當(dāng)p=1時，則為曼哈頓距離
當(dāng)p=∞時，則是各個坐標(biāo)距離的最大值。
k值選擇
k值的選擇會對k近鄰的結(jié)果產(chǎn)生重大影響。
如果選擇較小的k值，則學(xué)習(xí)的近似誤差減小，估計(jì)誤差增大，預(yù)測結(jié)果會對近鄰的實(shí)例點(diǎn)非常敏感。如果近鄰點(diǎn)的實(shí)例點(diǎn)是噪聲點(diǎn)，則預(yù)測會出錯。因此，較小的k值意味著整體模型會變得復(fù)雜，容易過擬合。
如果選擇較大的k值，則學(xué)習(xí)的近似誤差增大，估計(jì)誤差減小。預(yù)測結(jié)果也會受到與輸入實(shí)例較遠(yuǎn)的實(shí)例點(diǎn)的影響，造成預(yù)測錯誤。因此，較大的k值意味著整體模型變得簡單，容易欠擬合。
在應(yīng)用中，一般k值選用一個比較小的數(shù)值，通常采用交叉驗(yàn)證法來選取最優(yōu)值。
分類決策規(guī)則
k近鄰法中的分類決策規(guī)則往往是多數(shù)表決，即由輸入實(shí)例的 k 個鄰近的訓(xùn)練實(shí)例的多數(shù)類決定輸入實(shí)例的類別。
多數(shù)表決規(guī)則解釋如下: 如果分類損失函數(shù)為 0-1 損失函數(shù)，分類函數(shù)為：
那么誤分類的概率是:
對給定的實(shí)例 x 屬于特征向量集，最近鄰的 k 個訓(xùn)練實(shí)例點(diǎn)構(gòu)成集合 Nk(x). 如何涵蓋 Nk(x)的區(qū)域的類別是 cj，那么誤分類是:
要使誤分類率最小即經(jīng)驗(yàn)風(fēng)險最小， 就要使 ∑I(yi=cj)最大，所以多數(shù)表決規(guī)則等價于經(jīng)驗(yàn)風(fēng)險最小化
kd樹
kd樹是一種對k維空間中實(shí)例點(diǎn)進(jìn)行存儲以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。kd樹是二叉樹，表示對k維空間的一個劃分。構(gòu)造kd樹相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分，構(gòu)成一系列的k維超矩形區(qū)域。kd樹的每個結(jié)點(diǎn)對應(yīng)于一個k維超矩形區(qū)域。
搜索 kd 樹
kd 樹的最近鄰搜索算法:
輸入:已構(gòu)造 kd 樹；目標(biāo)點(diǎn) x
輸出: x 的最近鄰
1.在 kd 樹種找到含目標(biāo)點(diǎn) x 的葉結(jié)點(diǎn): 從根節(jié)點(diǎn)處罰，遞歸地向下訪問 kd 樹。若目標(biāo)點(diǎn) x 當(dāng)前維的坐標(biāo)小于切分店的坐標(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)如下操作:
- 如果該結(jié)點(diǎn)保存的實(shí)例點(diǎn)比當(dāng)前最近點(diǎn)距離目標(biāo)點(diǎn)更近，則以該實(shí)例點(diǎn)為"當(dāng)前最近點(diǎn)"
- 檢查該子節(jié)點(diǎn)的父節(jié)點(diǎn)對應(yīng)的另一子節(jié)點(diǎn)對應(yīng)的區(qū)域是否有更近的點(diǎn)。
4.當(dāng)回退到根節(jié)點(diǎn)時，搜索結(jié)束。最后的"當(dāng)前最近點(diǎn)"即為 x 的最近鄰點(diǎn)
一般，實(shí)例點(diǎn)是隨機(jī)分布的，kd 樹搜索的平均計(jì)算復(fù)雜度是 O(logN). kd 樹更適應(yīng)于訓(xùn)練實(shí)例數(shù)遠(yuǎn)大于空間維數(shù)時的 k 近鄰搜索。
總結(jié)
下一篇文章會用 kNN 分類器來實(shí)現(xiàn)一個推薦系統(tǒng)引擎系統(tǒng)，敬請期待。
