k近鄰法（k-nearest neighbor, kNN）是一種基本分類與回歸方法，其基本做法是：給定測試實例，基于某種距離度量找出訓練集中與其最靠近的k個實例點，然後基于這k個最近鄰的信息來進行預測。

通常，在分類任務中可使用“投票法”，即選擇這k個實例中出現最多的标記類别作為預測結果；在回歸任務中可使用“平均法”，即将這k個實例的實值輸出标記的平均值作為預測結果；還可基于距離遠近進行加權平均或加權投票，距離越近的實例權重越大。

k近鄰法不具有顯式的學習過程，事實上，它是懶惰學習（lazy learning）的著名代表，此類學習技術在訓練階段僅僅是把樣本保存起來，訓練時間開銷為零，待收到測試樣本後再進行處理。

本文隻讨論分類問題中的k近鄰法，下一篇文章将會介紹KNN分類的實際案例。

KNN（k-NearestNeighbor）又被稱為近鄰算法，它的核心思想是：物以類聚，人以群分

假設一個未知樣本數據x需要歸類，總共有ABC三個類别，那麼離x距離最近的有k個鄰居，這k個鄰居裡有k1個鄰居屬于A類，k2個鄰居屬于B類，k3個鄰居屬于C類，如果k1>k2>k3，那麼x就屬于A類，也就是說x的類别完全由鄰居來推斷出來。

所以我們可以總結出其算法步驟為：

• 計算測試對象到訓練集中每個對象的距離
• 按照距離的遠近排序
• 選取與當前測試對象最近的k的訓練對象，作為該測試對象的鄰居
• 統計這k個鄰居的類别頻率
• k個鄰居裡頻率最高的類别，即為測試對象的類别

我們可以簡化為：找鄰居 投票決定

優點

• 非常簡單的分類算法沒有之一，人性化，易于理解，易于實現
• 适合處理多分類問題，比如推薦用戶

缺點

• 屬于懶惰算法，時間複雜度較高，因為需要計算未知樣本到所有已知樣本的距離
• 樣本平衡度依賴高，當出現極端情況樣本不平衡時，分類絕對會出現偏差
• 可解釋性差，無法給出類似決策樹那樣的規則

由KNN的自身屬性所決定的，基于現有類别計算距離投票選擇，所以不能發現新的類别，但對于固定類别，KNN的簡單易用的特性就完全的顯示出來了，在某些分類上，比SVM，決策樹等有着并不遜色的性能。在進行固定類别分類的時候，模型選擇的時可以以KNN作為基礎标準進行模型選擇，說不定會有意外的驚喜。目前KNN應用比較成熟的方向主要有，内容的推薦，文本的識别等。

KNN算法在實際應用時，最主要的參數主要有三個：距離算法的選擇、K值的選擇、投票時的權重計算

5.1距離算法的選擇

目前主流的距離計算的算法主要有以下幾種：

• 歐式距離：是應用最多的距離計算算法
• 曼哈頓距離：應用相對較少，可在交叉驗證中選擇查看
• 餘弦距離：兩個向量之間的夾角大小，主要用來計算文本相似性

5.2K值的選擇

K值指的是，在進行分類投票時，選擇多少距離最小的類别進行投票，K值的大小會對分類器的結果産生直接的影響，這個可以通過交叉驗證确定最佳K值。

5.3投票時的權重計算

k近鄰默認的投票方法是分類決策規則往往是多數表決，即由輸入實例的k個鄰近的訓練實例中的多數類，決定輸入實例的類。即在取出的K個分類中，出現最多的分類及分類的結果。

同時也可采用對K個臨近的記錄不同的距離進行加權，距離近的權重高，距離遠的權重低來進行投票。常用的距離加權函數為高斯函數。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!