? 姓名：崔升? ? 學(xué)號(hào)：14020120005

? 轉(zhuǎn)載自：http://www.cnblogs.com/en-heng/p/5173704.html

【嵌牛導(dǎo)讀】：

?本文討論的kNN算法是監(jiān)督學(xué)習(xí)中分類方法的一種。所謂監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)，是指訓(xùn)練數(shù)據(jù)是? ?否有標(biāo)注類別，若有則為監(jiān)督學(xué)習(xí)，若否則為非監(jiān)督學(xué)習(xí)。監(jiān)督學(xué)習(xí)是根據(jù)輸入數(shù)據(jù)（訓(xùn)練數(shù)據(jù)）? ?學(xué)習(xí)一個(gè)模型，能對(duì)后來(lái)的輸入做預(yù)測(cè)。在監(jiān)督學(xué)習(xí)中，輸入變量與輸出變量可以是連續(xù)的，也可? ?以是離散的。若輸入變量與輸出變量均為連續(xù)變量，則稱為回歸；輸出變量為有限個(gè)離散變量，則? ?稱為分類；輸入變量與輸出變量均為變量序列，則稱為標(biāo)注[2]。

【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之kNN算法的簡(jiǎn)單介紹

【嵌牛提問(wèn)】：kNN是一種怎么的算法，其數(shù)學(xué)原理又是如何？

【嵌牛正文】：

1. 引言

頂級(jí)數(shù)據(jù)挖掘會(huì)議ICDM于2006年12月評(píng)選出了數(shù)據(jù)挖掘領(lǐng)域的十大經(jīng)典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Na?ve Bayes與 CART。 以前看過(guò)關(guān)于這些數(shù)據(jù)挖掘算法，但對(duì)背后數(shù)學(xué)原理未做過(guò)多探究，因而借此整理以更深入地理解這些算法。

2. kNN算法

kNN算法的核心思想非常簡(jiǎn)單：在訓(xùn)練集中選取離輸入的數(shù)據(jù)點(diǎn)最近的k個(gè)鄰居，根據(jù)這個(gè)k個(gè)鄰居中出現(xiàn)次數(shù)最多的類別（最大表決規(guī)則），作為該數(shù)據(jù)點(diǎn)的類別。

算法描述

訓(xùn)練集T={(x1,y1),(x2,y2),?,(xN,yN)}T={(x1,y1),(x2,y2),?,(xN,yN)}，其類別yi∈{c1,c2,?,cK}yi∈{c1,c2,?,cK}，訓(xùn)練集中樣本點(diǎn)數(shù)為NN，類別數(shù)為KK。輸入待預(yù)測(cè)數(shù)據(jù)xx，則預(yù)測(cè)類別

y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,K(1)(1)y=arg?maxcj?∑xi∈Nk(x)I(yi=cj),i=1,2,?,N;j=1,2,?,K

其中，涵蓋xx的k鄰域記作Nk(x)Nk(x)，當(dāng)yi=cjyi=cj時(shí)指示函數(shù)I=1I=1，否則I=0I=0。

分類決策規(guī)則

kNN學(xué)習(xí)模型：輸入XX，通過(guò)學(xué)習(xí)得到?jīng)Q策函數(shù)：輸出類別Y=f(X)Y=f(X)。假設(shè)分類損失函數(shù)為0-1損失函數(shù)，即分類正確時(shí)損失函數(shù)值為0，分類錯(cuò)誤時(shí)則為1。假如給xx預(yù)測(cè)類別為cjcj，即f(X)=cjf(X)=cj；同時(shí)由式子(1)(1)可知k鄰域的樣本點(diǎn)對(duì)學(xué)習(xí)模型的貢獻(xiàn)度是均等的，則kNN學(xué)習(xí)模型誤分類率為

1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1?1k∑xi∈Nk(x)I(yi=cj)(2)(2)1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1?1k∑xi∈Nk(x)I(yi=cj)

若要最小化誤分類率，則應(yīng)

maxcj∑xi∈Nk(x)I(yi=cj)maxcj?∑xi∈Nk(x)I(yi=cj)

所以，最大表決規(guī)則等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。

存在問(wèn)題

k值得選取對(duì)kNN學(xué)習(xí)模型有著很大的影響。若k值過(guò)小，預(yù)測(cè)結(jié)果會(huì)對(duì)噪音樣本點(diǎn)顯得異常敏感。特別地，當(dāng)k等于1時(shí)，kNN退化成最近鄰算法，沒(méi)有了顯式的學(xué)習(xí)過(guò)程。若k值過(guò)大，會(huì)有較大的鄰域訓(xùn)練樣本進(jìn)行預(yù)測(cè)，可以減小噪音樣本點(diǎn)的減少；但是距離較遠(yuǎn)的訓(xùn)練樣本點(diǎn)對(duì)預(yù)測(cè)結(jié)果會(huì)有貢獻(xiàn)，以至于造成預(yù)測(cè)結(jié)果錯(cuò)誤。下圖給出k值的選取對(duì)于預(yù)測(cè)結(jié)果的影響：

前面提到過(guò)，k鄰域的樣本點(diǎn)對(duì)預(yù)測(cè)結(jié)果的貢獻(xiàn)度是相等的；但距離更近的樣本點(diǎn)應(yīng)有更大的相似度，其貢獻(xiàn)度應(yīng)比距離更遠(yuǎn)的樣本點(diǎn)大?？梢约由蠙?quán)值wi=1/∥xi?x∥wi=1/‖xi?x‖進(jìn)行修正，則最大表決原則變成：

maxcj∑xi∈Nk(x)wi?I(yi=cj)maxcj?∑xi∈Nk(x)wi?I(yi=cj)

3. 參考資料

[1] Michael Steinbach and Pang-Ning Tan, The Top Ten Algorithms in Data Mining.

[2] 李航，《統(tǒng)計(jì)學(xué)習(xí)方法》.