kNN一句話概述
kNN算法：測量不同特征值之間的距離進行分類
舉個栗子：電影類型分類
一、問題
問題描述：已知 6 部電影的打斗鏡頭、接吻鏡頭和電影類型，以及新電影的打斗鏡頭、接吻鏡頭蔓榄，預(yù)測新電影類型。
數(shù)學(xué)表達：已知 6 個樣本的特征向量 ( x(1), x(2) ) 和類型（標記）默刚，以及新樣本的特征向量甥郑，預(yù)測新樣本類型。
-
數(shù)學(xué)符號：
m 部電影 —— m 個樣本n 個特征向量 ( X(1), X(2), ... , X(n)) —— ( 打斗鏡頭荤西、接吻鏡頭澜搅、... )
第 i 個樣本的特征向量為 ( x i(1), x i(2), ... , x i(n) )
m 個樣本的特征向量為
( x 1(1), x 1(2), ... , x 1(n)
x 2(1), x 2(2), ... , x 2(n)
... , ... , ... , ...
x m(1), x m(2), ... , x m(n) )預(yù)測值 ( Y ) —— ( 電影類型 )
如下圖所示：
編號/電影名稱 (m) 打斗鏡頭 (X(1)) 接吻鏡頭 (X(2)) 電影類型 (Y) 1 California Man 3 104 愛情片 2 omitted 2 100 愛情片 3 omitted 1 81 愛情片 4 omitted 101 10 動作片 5 omitted 99 5 動作片 6 omitted 88 2 動作片 7 omitted 18 90 ?
二、kNN算法步驟
1. 計算未知點與已知類別點的距離
- 歐氏距離
d= \sqrt [] { \sum_{k = 1}^{n} {(x_1^k - x_2^k)^2}}- 曼哈頓距離
d= \sqrt [] { \sum_{k = 1}^{n} {|x_1^k- x_2^k|}}- 切比雪夫距離
d= max(|x_1^1-x_2^1|,|x_1^2-x_2^2|,...,|x_1^n-x_2^n|)- 閔可夫斯基距離
d= \sqrt [p] { \sum_{k = 1}^{n} {|x_1^k - x_2^k|^p}}
p為 1 時邪锌，閔可夫斯基距離即曼哈頓距離
p為 2 時勉躺，閔可夫斯基距離即歐氏距離
p為 ∞ 時，閔可夫斯基距離即切比雪夫距離
按照歐式距離計算觅丰，樣本 1 與 新電影歐式距離計算：
d = \sqrt [] { (3 - 18)^2 + (104 - 90)^2}=20.5
如圖：
編號/電影名稱 (m) 與新電影的距離 1 California Man 20.5 2 omitted 18.7 3 omitted 19.2 4 omitted 115.3 5 omitted 117.4 6 omitted 118.9
2. 按照距離遞增次序排序
如圖：
編號/電影名稱 (m) 與新電影的距離 2 omitted 18.7 1 omitted 20.5 3 omitted 19.2 4 omitted 115.3 5 omitted 117.4 6 omitted 118.9
3. 選取與新電影距離最小的 k 個點
這里令 k 為 4饵溅，與新電影距離最近的 2 個點依次為第 2 個樣本、第 1 個樣本妇萄、第 3 個樣本和第 4 個樣本蜕企，其中愛情片的數(shù)量為 3，動作片的數(shù)量為 1冠句，則愛情片出現(xiàn)的頻率為：
p(love) = 3 / 4
動作片出現(xiàn)的頻率為：
p(action) = 1 / 4
注：例子的樣本數(shù)很小轻掩，為更好地說明問題，k值取得較大
4. 確定前k個點所在類別的出現(xiàn)頻率
p(love) > p(action)懦底，因此愛情片出現(xiàn)的頻率更高
5. 返回前k個點出現(xiàn)最高頻率的類別唇牧，即預(yù)測類別
新電影的類別為愛情片
- 待更新
參考：《機器學(xué)習(xí)實戰(zhàn)》【美】Peter Harrington
