一. k-NN算法【有監(jiān)督】
1. 概念
(1) 原理：K近鄰是一種多類劃分的模型蛛枚，基于實(shí)例棍弄，不需要訓(xùn)練该园。當(dāng)一個(gè)樣本與數(shù)據(jù)集中的k個(gè)樣本最相近時(shí)兆解， 若這k個(gè)樣本中的大多數(shù)屬于某一個(gè)類別， 則該樣本也應(yīng)該屬于這個(gè)類別亲雪。
(2) 兩類問題
在分類問題中勇凭，KNN用來預(yù)測(cè)種類。使用“投票法”义辕，選擇這k個(gè)樣本中出現(xiàn)最多的類別來作為測(cè)試樣本的類別虾标。
在回歸問題中，KNN用來預(yù)測(cè)一個(gè)值灌砖。使用“平均法”璧函，將k個(gè)樣本的實(shí)值輸出的平均值作為測(cè)試樣本的輸出。
2. 算法流程
(1) 輸入：載入數(shù)據(jù)基显，并初始化k值
(2) 計(jì)算測(cè)試數(shù)據(jù)到每一個(gè)訓(xùn)練數(shù)據(jù)的距離
(3) 按距離排序蘸吓，取 TOP k 個(gè)最近的訓(xùn)練數(shù)據(jù)
(4) 取頻率最高的類作為測(cè)試數(shù)據(jù)的預(yù)測(cè)類別
3. 算法的泛化誤差
給定測(cè)試樣本x，設(shè)其最近鄰樣本為z撩幽，最近鄰（1-NN）出錯(cuò)率就是x與z類別標(biāo)記不同的概率
即库继，1NN的泛化錯(cuò)誤率≤2倍的貝葉斯最優(yōu)分類器錯(cuò)誤率
c*=argmax P(c*|x)????為貝葉斯最優(yōu)分類器的結(jié)果
二. 距離度量
1. 歐氏距離（Euclidean Distance）
兩點(diǎn)間的最短距離，它將樣本的不同屬性（即各指標(biāo)或各變量量綱）之間的差別等同看待窜醉，這一點(diǎn)有時(shí)不能滿足實(shí)際要求宪萄。
? ??????????????????????????????????????????????
2.?曼哈頓距離（Manhattan Distance）
也叫L1距離，指在曼哈頓從一個(gè)十字路口開車到另外一個(gè)十字路口的實(shí)際距離榨惰。依賴座標(biāo)系統(tǒng)的轉(zhuǎn)度拜英，當(dāng)坐標(biāo)軸變動(dòng)時(shí)，點(diǎn)間的距離就會(huì)不同琅催。
? ?????????????????????????????????????????
3.?切比雪夫距離（Chebyshev Distance）
又叫“棋盤距離”，“軸上最長(zhǎng)距離”恢暖，指“王”在棋盤上移動(dòng)的距離（可以朝任意方向走）
? ?????????????????????????????????????????????????????
4.閔可夫斯基距離（Minkowski Distance）
不是一種距離，而是距離的定義狰右。
定義兩點(diǎn)：? ?以及 ?
則????????????????? ? （p是一個(gè)變參數(shù)）
(1) p=1時(shí)杰捂，曼哈頓距離（對(duì)應(yīng)L1-范數(shù)）
(2)?p=2時(shí)，歐氏距離（對(duì)應(yīng)L2-范數(shù)）
(3)?p→∞ 時(shí)棋蚌，切比雪夫距離
5.?標(biāo)準(zhǔn)化歐氏距離（Standardized Euclidean distance）
(1)?閔氏距離的缺點(diǎn)：
① 將各個(gè)分量的量綱(scale)嫁佳，也就是“單位”當(dāng)作相同的看待了
② 沒有考慮各個(gè)分量的分布（期望、方差等）可能是不同的谷暮。
③?各個(gè)維度必須是互相獨(dú)立的蒿往，也就是“正交”的
(2) 改進(jìn)：標(biāo)準(zhǔn)化歐氏距離
①?設(shè)樣本集X的均值為μ，標(biāo)準(zhǔn)差為σ
? ??標(biāo)準(zhǔn)化：????? ??????（數(shù)學(xué)期望為0湿弦，方差為1）
②加權(quán)歐式距離：? ? （將方差的倒數(shù)看成是一個(gè)權(quán)重）
三. k值選取
1. 隨著k值增大瓤漏，分類界面更加平滑
(1) k值小：學(xué)習(xí)的近似誤差會(huì)減小，模型復(fù)雜蔬充，對(duì)近鄰的實(shí)例點(diǎn)分類敏感蝶俱，容易過擬合。
(2) k值大饥漫，學(xué)習(xí)的估計(jì)誤差會(huì)減小榨呆，模型簡(jiǎn)單，對(duì)輸入實(shí)例預(yù)測(cè)不準(zhǔn)確
2. 誤差
(1)?近似誤差：關(guān)注訓(xùn)練集庸队，如果k值小了會(huì)出現(xiàn)過擬合的現(xiàn)象积蜻，對(duì)現(xiàn)有的訓(xùn)練集能有很好的預(yù)測(cè)，但是對(duì)未知的測(cè)試樣本將會(huì)出現(xiàn)較大偏差的預(yù)測(cè)彻消。模型本身不是最接近最佳模型竿拆。
(2)?估計(jì)誤差：關(guān)注測(cè)試集，估計(jì)誤差小了說明對(duì)未知數(shù)據(jù)的預(yù)測(cè)能力好证膨。模型本身最接近最佳模型如输。但K取太大并不能提高正確率，而且算法效率會(huì)低央勒。
(3)?在應(yīng)用中不见，K值一般取一個(gè)比較小的數(shù)值，通常采用交叉驗(yàn)證法來選取最優(yōu)的K值崔步。
四. kd樹（K-dimension tree）
1. kNN的缺點(diǎn)
K近鄰在高維情況下時(shí)稳吮，待預(yù)測(cè)樣本需要與依次與所有樣本求距離，則對(duì)于n個(gè)m維的樣本井濒，復(fù)雜度為O(mn)灶似，成為測(cè)試階段的嚴(yán)重瓶頸。
2. 使用kd樹優(yōu)化
(1) 定義：是一種以二叉樹的形式存儲(chǔ)數(shù)據(jù)的方法瑞你，表示對(duì)k維空間的一個(gè)劃分酪惭。用于高維空間中的搜索，比如范圍搜索和最近鄰搜索者甲。
(2) 原理：不斷用垂直于坐標(biāo)軸的超平面將K維空間劃分為兩部分春感，分別記作左子樹(<)、右子樹(≥)虏缸，構(gòu)成一系列的K維超矩形區(qū)域鲫懒。
(3) 優(yōu)勢(shì)：kd樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)k維超矩形區(qū)域。 利用kd樹可以省去對(duì)大部分?jǐn)?shù)據(jù)點(diǎn)的搜索刽辙， 從而減少搜索的計(jì)算量窥岩。
(4) 構(gòu)造方法
① 建立根節(jié)點(diǎn)；?
② 選取方差最大的特征作為分割特征宰缤； （選擇較為分散的一維）
③ 選擇該特征的中位數(shù)作為分割點(diǎn)颂翼； （交替x軸晃洒、y軸）
④ 將數(shù)據(jù)集中，該特征小于中位數(shù)的給左子樹疚鲤，大于中位數(shù)的傳遞給根節(jié)點(diǎn)的右子樹锥累；?
⑤ 重復(fù)②-④，直到所有數(shù)據(jù)都被建立到KD Tree的節(jié)點(diǎn)上為止集歇。
(5) 搜索方法
① 利用kd樹桶略，從根節(jié)點(diǎn)開始向下訪問，根據(jù)目標(biāo)★在分割特征中小于(大于)當(dāng)前節(jié)點(diǎn)诲宇，選擇向左(向右)移動(dòng)
② 遞歸：當(dāng)?shù)竭_(dá)葉節(jié)點(diǎn)际歼，就將其保存為 “當(dāng)前最近點(diǎn)”??
③ 回溯，從葉節(jié)點(diǎn)再返回到根節(jié)點(diǎn)姑蓝，若當(dāng)前節(jié)點(diǎn)更接近鹅心，那么它就更新為?“當(dāng)前最近點(diǎn)” ?
④ 檢查：作為父節(jié)點(diǎn)?是否有另一子樹更近，若有則更新為?“當(dāng)前最近點(diǎn)” ?
（以?到★的距離為半徑畫超球體纺荧，若與另一超平面空間相交旭愧，尋找該空間是否有更近點(diǎn)?）
⑤ 回溯：以?到★的距離為半徑畫超球體，若與節(jié)點(diǎn)?的父節(jié)點(diǎn)?被分割的超平面相交宙暇，說明當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)所在子樹有可能含更近的點(diǎn)输枯，則需要對(duì)這個(gè)兄弟節(jié)點(diǎn)遞歸執(zhí)行①-④。若不相交占贫，則無需更新桃熄，繼續(xù)回溯。
⑥ 結(jié)束：當(dāng)回退到根節(jié)點(diǎn)時(shí)型奥，停止搜索瞳收。
參考：
[1]?機(jī)器學(xué)習(xí)之KNN（k近鄰）算法詳解——CSDN
