k近鄰模型和算法

1、k近鄰模型和算法2.1 K近鄰模型K近鄰法使用的模型實(shí)際上對(duì)應(yīng)于對(duì)特征空間的劃分。模型由三個(gè)基本要素 一-距離度量、k值得選擇和分類規(guī)則決定。2.1.1模型K近鄰法中，當(dāng)訓(xùn)練集、距離度量（如歐式距離X k值及分類決策規(guī)則（如 多數(shù)表決）確定后，對(duì)于任何一個(gè)新的輸入實(shí)例，它所屬的類唯一確定。這相當(dāng) 于根據(jù)上述要素將特征空間劃分為一些子空間，確定子空間里的每個(gè)點(diǎn)所述的 類。這一事實(shí)從最近鄰算法中可以看得很清楚。特征空間中，對(duì)每個(gè)實(shí)例點(diǎn)土，距離該點(diǎn)比其他店更近的所有點(diǎn)組成一個(gè)區(qū) 域，叫做單元。每個(gè)訓(xùn)練實(shí)例點(diǎn)擁有一個(gè)單元，所有訓(xùn)練實(shí)例點(diǎn)的單元構(gòu)成對(duì)特 征空間的一個(gè)劃分。最近鄰法將實(shí)例七的類作為其單元中

2、所有點(diǎn)的類標(biāo)記。這 樣，每個(gè)單元的實(shí)例點(diǎn)的類別時(shí)確定的。下圖是二維特征空間劃分的一個(gè)例子。特征空間中兩個(gè)實(shí)例點(diǎn)的距離是兩個(gè)點(diǎn)相似程度的反映。K近鄰模型的特征 空間一般是n維實(shí)數(shù)向量空間Rn。使用的距離是歐式距離，但也可以是其他距 離，如更一般的Lp或閩科夫斯基距離。設(shè)特征空間穴是n維實(shí)數(shù)向量空間Rn，X，Xj 5, 土 -(X.,七，一,七元X = (x ,x(2),.,X (n)T, x ,x 的L 距離定義為j j jji j 的 PL (x ,x )=尤卜，一xi p pP i j I i j ) l=1/這里p 2 L當(dāng)p = 2時(shí)，稱為歐式距離，即xil=1P = 1時(shí)，稱為曼哈頓距

3、離，L(x.,x)=乎l=1x/ x l當(dāng)P = 8時(shí)，它是各個(gè)距離坐標(biāo)的最大值，即L (x , x ) = max xi 一 xi8 i j / i J2.1.3 K值的選擇k值的選擇會(huì)對(duì)k近鄰法的結(jié)果產(chǎn)生重大影響。如果選擇較小的k值，就相當(dāng)于用較小的鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，“學(xué) 習(xí)”的近似誤差會(huì)減小，只有與輸入實(shí)例較近的(相似的)訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測(cè) 結(jié)果起作用。但缺點(diǎn)是“學(xué)習(xí)”的估計(jì)誤差會(huì)增大，預(yù)測(cè)結(jié)果會(huì)對(duì)近鄰的實(shí)例點(diǎn) 非常敏感。如果近鄰的實(shí)例點(diǎn)恰巧是噪聲，預(yù)測(cè)就會(huì)出錯(cuò)。換句話說(shuō)，k值得減 小就意味著整體模型變得復(fù)雜，容易發(fā)生過(guò)擬合。如果選擇較大的k值，就相當(dāng)于用較大鄰域中的訓(xùn)練實(shí)例進(jìn)行

4、預(yù)測(cè)。其優(yōu)點(diǎn) 是可以減少學(xué)習(xí)的估計(jì)誤差。但缺點(diǎn)是學(xué)習(xí)的近似誤差會(huì)增大。這時(shí)與輸入實(shí)例 較遠(yuǎn)的(不相似的)訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用，是預(yù)測(cè)發(fā)生錯(cuò)誤。K值得增大 就意味著整體的模型變得簡(jiǎn)單。如果k=N，那么無(wú)論輸入實(shí)例是什么，都將簡(jiǎn)單的預(yù)測(cè)它屬于在訓(xùn)練實(shí)例中 最多的類。這時(shí)，模型過(guò)于簡(jiǎn)單，完全忽略訓(xùn)練實(shí)例中的大量有用信息，是不可 取的。K近鄰法中的分類決策規(guī)則往往是多數(shù)表決，即由輸入實(shí)例的k個(gè)鄰近的訓(xùn) 練實(shí)例中的多數(shù)類決定輸入實(shí)例的類。多數(shù)表決規(guī)則有如下解釋：如果分類的損失函數(shù)為0-1損失函數(shù)，分類函數(shù) 為f : Rn c , c，,c 12 k那么誤分類的概率是P(Y 豐 f (X) = 1 P

5、(Y = f (X)對(duì)給定的實(shí)例1即，其最近鄰的k個(gè)訓(xùn)練實(shí)例點(diǎn)構(gòu)成集合Nk(。如果涵蓋Nk (1)的區(qū)域的類別是C那么誤分類概率是1 EI(yt。C,) = 1 一 1 ZI(y. =c.)土 wNK (1)Xi wNK (X)I KI KZ I (y = c )要使誤分類概率最小即經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，就要使% wNk (x) 1 J最大，所以多數(shù)表決規(guī)則等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。2.2 K近鄰算法輸入：訓(xùn)練數(shù)據(jù)集T = (% ,y ),(x ,y )，(x ,y ) 1122N N其中 1 w* jRn為實(shí)例的特征向量 y wy =c，c，c為實(shí)例的類別 其中， i為實(shí)例 的特征向量， i1 2 k 為實(shí)例 的類別，i=1,2, . ,N;實(shí)例特征向量x；輸出：實(shí)例x所屬的類y。根據(jù)給定的距離度量，在訓(xùn)練集T中找出與x最鄰近的k個(gè)點(diǎn)，涵蓋這 k個(gè)點(diǎn)的x鄰域記作Nk (1)；在Nk(1)中根據(jù)分類決策規(guī)則(如多數(shù)表決)決定x的類別y：y = arg max Z I(y. = c ), i = 1,2,. N; J = 1,2,., K cj X. wNk (X)