k近鄰(K-Nearest Neighbor, 簡稱KNN)算法既可以用于分類問題也可以用回歸問題．兩者最大的區(qū)別在于最終決策時方法的選擇，對于分類問題來說，采用多數(shù)表決法；而對于回歸問題來說，采用選擇平均法；
在此只總結(jié)分類問題中的ｋ近鄰模型．

一. Ｋ近鄰模型

ｋ近鄰算法對于分類問題的大致描述：對于給定的訓(xùn)練數(shù)據(jù)集，有新的實例輸入，在訓(xùn)練數(shù)據(jù)集中找到與該實例最鄰近的ｋ個實例，這個ｋ個實例中大多數(shù)屬于哪個類別，則把這個新的實例歸為這個類別．

通過以上，可以看出當(dāng)訓(xùn)練數(shù)據(jù)集確定后，并指定鄰近度量(距離度量)方法，ｋ值以及決策規(guī)則(上述的規(guī)則被稱為多數(shù)表決)后，對于任何一個新的輸入實例，都有唯一確定的類別．因此，ｋ近鄰模型由距離度量，ｋ值和決策規(guī)則這三個要素組成．

１. 距離度量

在ｋ近鄰模型中一般使用的距離是歐式距離，當(dāng)然也可以是其他距離．
比如閔可夫斯基距離

當(dāng)式中ｐ＝1時，稱為曼哈頓距離；ｐ＝２時稱為歐式距離；當(dāng)ｐ＝∞時稱為切比雪夫距離，切比雪夫距離定義為各坐標(biāo)數(shù)值差的最大值，其公式為：

當(dāng)然，選擇不同的距離度量確定的鄰近點也是不同的．

2. k值的選擇

如果ｋ值的選擇過小，比如極端值ｋ＝１(這時算法稱為最近鄰算法), 結(jié)果將會歸為最近鄰的那一個點所屬的類別，但是當(dāng)這個最近鄰點為噪聲，那么預(yù)測將會出錯．也就是說ｋ值的減少會增大模型的復(fù)雜程度，容易發(fā)生過擬合．

如果ｋ值的選擇過大，比如極端值ｋ＝Ｎ(N為樣本容量), 那么無論輸入什么實例，預(yù)測的結(jié)果均為訓(xùn)練集中最多的類，這時模型又過于簡單．

在實際應(yīng)用中，通常會采用交叉驗證的方法選擇最優(yōu)的ｋ值．

3. 決策規(guī)則

對于分類問題的ｋ近鄰模型來說，常用的決策規(guī)則是多數(shù)表決，即由輸入實例的ｋ個鄰近的訓(xùn)練實例中的多數(shù)類別來決定輸入實例的類別．
多數(shù)表決規(guī)則等價于誤分類率最小化(即經(jīng)驗風(fēng)險最小化).

參考：
李航博士著＜統(tǒng)計學(xué)習(xí)方法＞