1. 核心思想
如果一個樣本在特徵空間中的k個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。也就是說找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。
下面看一個例子，
一個程序員面試結束後，想想知道是否拿到offer，他在網上找到幾個人的工作經歷和大概薪資，如下，X為年齡，Y為工資;
當k取1的時候，我們可以看出距離最近的no offer，因此得到目標點為不被錄用。
當k取3的時候，我們可以看出距離最近的三個，分別是有offer 和no offer，根據投票決定 offer的票數較高為2 ，所以被錄用。
算法流程
1. 準備數據，對數據進行預處理，常用方法，特徵歸一化、類別型特徵的處理、高維組合特徵的處理、組合特徵的處理、文本表示模型的模型處理、Word2Vec、圖像數據不足時的處理方法
2. 選用合適的數據結構存儲訓練數據和測試元組，根據模型驗證方法，把樣本劃分不同的訓練集和測試集，比如holdout只需要劃分為兩個部分，交叉驗證劃分為k個子集，自助法跟著模型來
3. 設定參數，如k的取值，這個涉及到超參數調優的問題，網絡搜索、隨機搜索、貝葉斯算法等
4.維護一個大小為k的的按距離由大到小的優先級隊列，用於存儲最近鄰訓練元組。隨機從訓練元組中選取k個元組作為初始的最近鄰元組，分別計算測試元組到這k個元組的距離，將訓練元組標號和距離存入優先級隊列
5. 遍歷訓練元組集，計算當前訓練元組與測試元組的距離，將所得距離L 與優先級隊列中的最大距離Lmax
6. 進行比較。若L>=Lmax，則捨棄該元組，遍歷下一個元組。若L < Lmax，刪除優先級隊列中最大距離的元組，將當前訓練元組存入優先級隊列。
7. 遍歷完畢，計算優先級隊列中k 個元組的多數類，並將其作為測試元組的類別。
8. 測試元組集測試完畢後計算誤差率，繼續設定不同的k值重新進行訓練，最後取誤差率最小的k 值。
簡單來說，knn算法最重要的是三個要素：K值選擇,距離度量,分類決策規則，
K的選擇
如k的取值，這個涉及到超參數調優的問題，k的取值對結果會有很大的影響。K值設置過小會降低分類精度，增加模型複雜度；若設置過大，且測試樣本屬於訓練集中包含數據較少的類，則會增加噪聲，降低分類效果。通常，K值的設定採用交叉檢驗的方式（以K=1，K=2，K=3依次進行），K折交叉驗證如下：
1） 將全部訓練集S分成K個不相交的子集，假設S中的訓練樣例個數為m，那麼每一個子集有m/k個訓練樣例。
（2） 每次從分好的子集中，選出一個作為測試集，另外k-1個作為訓練集。
（3） 根據訓練集得到模型。
（4） 根據模型對測試集進行測試，得到分類率。
（5） 計算k次求得的分類率的平均值，作為模型的最終分類率。
以五折交叉驗證為例;
分別得出K=1時的平均分類準確度、K=1時的平均分類準確度……選出最優K值
距離度量
在KNN算法中，常用的距離有三種，分別為曼哈頓距離、歐式距離和閔可夫斯基距離。
距離通式：
當p=1時，稱為曼哈頓距離
當p=2時，稱為歐式距離
當p=∞時，
分類決策規則
：
1.多數表決：少數服從多數，即訓練集裡和預測的樣本特徵最近的K個樣本，預測為裡面有最多類別數的類別
2.加權表決：根據各個鄰居與測試對象距離的遠近來分配相應的投票權重。最簡單的就是取兩者距離之間的倒數，距離越小，越相似，權重越大，將權重累加，最後選擇累加值最高類別屬性作為該待測樣本點的類別，類似大眾評審和專家評審。
這兩種確簡單直接，在樣本量少，樣本特徵少的時候有效，只適合數據量小的情況。因為我們經常碰到樣本的特徵數有上千以上，樣本量有幾十萬以上，如果我們這要去預測少量的測試集樣本，算法的時間效率很成問題。因此，這個方法我們一般稱之為蠻力實現。比較適合於少量樣本的簡單模型的時候用。一個是KD樹實現，一個是球樹實現。
閱讀更多 sandag 的文章
