• 本章討論的是分類問題中的K近鄰法

3.1 K近鄰算法

算法簡述：

• 當K取3時，綠色點屬於紅類；當K取5時，綠色點屬於藍類。
• 在右圖中，距離度量採用歐氏距離。

3.2 K近鄰模型

3.2.1 模型

• 沒有類似於感知機模型的函數表示，理解理解。

• 若K=1，則爲最近鄰模型。測試實例在哪個訓練實例點的單元（上圖的方框）範圍內就屬於哪個類別。

3.2.2 距離度量

Lp距離

• p=1時， 稱爲曼哈頓距離。（1，0）和（0.5，0.5）到（0，0）的距離是一樣的 
• p=2時，稱爲歐式距離
• p=無窮，它是各個座標距離的最大值。座標裏的最大值即爲距離。

3.2.3 K值的選擇

• 交叉驗證！！！！ 用驗證集定K值。

3.2.4 分類決策規則

• 取經驗風險最小化的類別。

3.3  k 近鄰法的實現：kd樹

（用的時候再補）