k 近鄰是什么
k 近鄰法是機器學習中最基本的分類和回歸方法，也稱為kNN算法。通常k近鄰法用于分類問題。
k近鄰法假定給定一個訓練數(shù)據(jù)集汹族，其中實例類別已定讼昆。分類時托享，對新的實例，根據(jù)其K個最近鄰的訓練實例類別浸赫，一般通過多數(shù)表決的方式來進行預測闰围。
例如，有兩堆水果既峡，一堆是橙子羡榴，一堆是柚子，新拿到一個水果运敢，判斷是橙子還是柚子校仑。一般來說忠售，柚子更大更紅。那么判斷和該水果最相近的 3 個水果是什么迄沫，比如 3 個最近的鄰居是柚子稻扬，那么我們可以判斷新拿到的水果是柚子，這就是 kNN 算法羊瘩。
k近鄰算法
k近鄰算法簡單泰佳，直觀有效。
輸入：給定一個訓練數(shù)據(jù)集T={(x1, y1), (x2, y2), ..., (xn, yn)}, 其中xi為實例的特征向量尘吗，yi為實例的類別乐纸。
輸出：實例x所屬的類y。
- 根據(jù)給定的距離度量摇予， 在訓練集T中尋找與x最近鄰的k個點汽绢，涵蓋這k個點的x的鄰域記作Nk(x)
-
在Nk(x)中根據(jù)分類決策規(guī)則(如多數(shù)表決)決定x的類別y：
其中I為指示函數(shù)，當yi = cj時I為1侧戴，否則I為0
特別的宁昭，當k=1時，稱為最近鄰算法酗宋。注意积仗，k近鄰法沒有顯示的學習過程。
K近鄰模型
k近鄰模型對應于特征空間的劃分蜕猫。模型由3個基本要素構成:
- K值選擇
- 距離度量
- 分類決策規(guī)則
當訓練集寂曹，距離度量，k值以及分類決策規(guī)則確定后回右，對于新輸入的任何一個實例隆圆，它所屬的類別唯一的確定。
距離度量
特征空間中的兩個實例點是兩個實例點相似程度的反映.k近鄰模型的特征空間一般是n維的實數(shù)向量空間翔烁。
當p=2時渺氧，則是歐式距離。即:
當p=1時蹬屹，則為曼哈頓距離
當p=∞時侣背，則是各個坐標距離的最大值。
k值選擇
k值的選擇會對k近鄰的結果產(chǎn)生重大影響慨默。
如果選擇較小的k值贩耐，則學習的近似誤差減小，估計誤差增大厦取，預測結果會對近鄰的實例點非常敏感潮太。如果近鄰點的實例點是噪聲點，則預測會出錯蒜胖。因此消别，較小的k值意味著整體模型會變得復雜，容易過擬合台谢。
如果選擇較大的k值寻狂，則學習的近似誤差增大，估計誤差減小朋沮。預測結果也會受到與輸入實例較遠的實例點的影響蛇券，造成預測錯誤。因此樊拓，較大的k值意味著整體模型變得簡單纠亚，容易欠擬合。
在應用中筋夏，一般k值選用一個比較小的數(shù)值蒂胞，通常采用交叉驗證法來選取最優(yōu)值。
分類決策規(guī)則
k近鄰法中的分類決策規(guī)則往往是多數(shù)表決条篷，即由輸入實例的 k 個鄰近的訓練實例的多數(shù)類決定輸入實例的類別骗随。
多數(shù)表決規(guī)則解釋如下: 如果分類損失函數(shù)為 0-1 損失函數(shù)，分類函數(shù)為：
那么誤分類的概率是:
對給定的實例 x 屬于特征向量集赴叹，最近鄰的 k 個訓練實例點構成集合 Nk(x). 如何涵蓋 Nk(x)的區(qū)域的類別是 cj鸿染，那么誤分類是:
要使誤分類率最小即經(jīng)驗風險最小， 就要使 ∑I(yi=cj)最大乞巧，所以多數(shù)表決規(guī)則等價于經(jīng)驗風險最小化
kd樹
kd樹是一種對k維空間中實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結構涨椒。kd樹是二叉樹，表示對k維空間的一個劃分绽媒。構造kd樹相當于不斷地用垂直于坐標軸的超平面將k維空間切分蚕冬，構成一系列的k維超矩形區(qū)域。kd樹的每個結點對應于一個k維超矩形區(qū)域是辕。
搜索 kd 樹
kd 樹的最近鄰搜索算法:
輸入:已構造 kd 樹播瞳；目標點 x
輸出: x 的最近鄰
1.在 kd 樹種找到含目標點 x 的葉結點: 從根節(jié)點處罰，遞歸地向下訪問 kd 樹免糕。若目標點 x 當前維的坐標小于切分店的坐標赢乓，移動到左子結點，否則移動到右子節(jié)點石窑，直到子節(jié)點為葉節(jié)點為止牌芋。
2.以此葉結點為"當前最近點"
3.遞歸地向上回退，在每個節(jié)點如下操作:
- 如果該結點保存的實例點比當前最近點距離目標點更近松逊，則以該實例點為"當前最近點"
- 檢查該子節(jié)點的父節(jié)點對應的另一子節(jié)點對應的區(qū)域是否有更近的點躺屁。
4.當回退到根節(jié)點時，搜索結束经宏。最后的"當前最近點"即為 x 的最近鄰點
一般犀暑，實例點是隨機分布的驯击，kd 樹搜索的平均計算復雜度是 O(logN). kd 樹更適應于訓練實例數(shù)遠大于空間維數(shù)時的 k 近鄰搜索。
總結
下一篇文章會用 kNN 分類器來實現(xiàn)一個推薦系統(tǒng)引擎系統(tǒng)耐亏，敬請期待徊都。
