【統(tǒng)計(jì)學(xué)習(xí)方法】 第3章 k近鄰法（一）

??近鄰法是一種基本分類與回歸分析方法。

??近鄰法的輸入為實(shí)例的特征向量，對應(yīng)于特征空間的點(diǎn)；輸出為實(shí)例的類別，可以取多類。

??近鄰法實(shí)際上利用訓(xùn)練數(shù)據(jù)集對特征向量空間進(jìn)行劃分，并作為其分類的“模型”。

??值的選擇、距離度量及分類決策規(guī)則是??近鄰法的三個(gè)基本要素。

本章先敘述??近鄰算法，然后討論??近鄰法的模型及三個(gè)基本要素，最后講述??近鄰算法的一個(gè)實(shí)現(xiàn)。

先講述??近鄰算法和三個(gè)基本要素。

給定一個(gè)訓(xùn)練數(shù)據(jù)集，對新輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的??個(gè)實(shí)例，這??個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分為這個(gè)類。

輸入：

??

其中，

??為實(shí)例的特征向量，??為實(shí)例的類別。

輸出：

實(shí)例??所屬的類??

1）根據(jù)給定的距離向量，在訓(xùn)練數(shù)據(jù)集中找出與??最鄰近的??個(gè)點(diǎn)。

2）在這??個(gè)點(diǎn)中根據(jù)分類規(guī)則決定??的類別??

k近鄰法使用的模型實(shí)際上對應(yīng)于對特征空間的劃分。由模型的三個(gè)基本要素——距離度量、k值的選擇和分類決策規(guī)則決定。

• 距離度量

特征空間中兩個(gè)實(shí)例點(diǎn)的距離是兩個(gè)實(shí)例點(diǎn)相似程度的反映。

設(shè)特征向量x是n維實(shí)數(shù)向量空間，??，??，??，

則：??的距離定義為，

??

?

??,曼哈頓距離

??,歐式距離

??，切比雪夫距離

?

• ??值的選擇
  

??值的選擇會對近鄰法的結(jié)果產(chǎn)生重大影響。

如果選擇較小的??值，就相當(dāng)于用較小的領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測，“學(xué)習(xí)”的近似誤差會減小，只有與輸入實(shí)例較近的訓(xùn)練實(shí)例才會對預(yù)測結(jié)果起作用。或者說，??值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合。

如果選擇較大的??值，就相當(dāng)于用較大領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測。其優(yōu)點(diǎn)是可以減少學(xué)習(xí)的估計(jì)誤差。??值的增大就意味著模型變得簡單。

• 分類決策規(guī)則

??近鄰法中的分類決策規(guī)則往往是多數(shù)表決，即由輸入實(shí)例的??個(gè)近鄰的訓(xùn)練實(shí)例中的多數(shù)類決定輸入實(shí)例的類。多數(shù)表決規(guī)則等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。