統計學習方法筆記——第三章 K近鄰法

K近鄰法（KNN）是一種基本的分類與迴歸的方法，這裏只介紹其分類問題。

KNN算法的基本思想：對於一個新的輸入數據點，在訓練集中找到與它距離最近的K個點，若這K個點中大部分屬於A類，則該數據點也屬於A類。

算法流程：

特殊地，若K=1，則相當於離輸入實例最近的一個樣本實例直接決定了它的類別。

KNN模型的三要素：距離度量、K值選擇、分類決策規則。

距離度量：數據點之間的距離有很多度量標準，一般來說可概括爲下式：

p=1稱爲曼哈頓距離，p=2稱爲歐氏距離，我們最常用的就是歐氏距離（如平面兩點間的距離公式）

K值選擇：K值若選得過小，則只有與輸入實例很近的訓練實例纔會起到預測作用，預測結果對近鄰實例點會變得非常敏感，容易產生過擬合現象；若K值選得過大，則離輸入實例較遠的訓練實例也會對也測結果產生影響，會降低預測的準確性。實際應用中，通常使用交叉驗證法來選取一個適當的K值。

分類決策規則：多數表決規則（參考上述KNN算法基本思想）

理由：

簡單來講，爲了使誤分類率最小（即經驗風險最小），則需要找到近鄰中的最多類別，即經驗風險最小化等價於多數表決。