一猖败、模型

1.1概念

?k-近鄰算法是一種基本分類與回歸方法领虹，我們這里只討論分類問(wèn)題中的 k-近鄰算法届宠。k-近鄰算法的輸入為實(shí)例的特征向量，對(duì)應(yīng)于特征空間的點(diǎn)鸟蜡；輸出為實(shí)例的類別膜赃，可以取多類。給定一個(gè)訓(xùn)練數(shù)據(jù)集矩欠，對(duì)新的輸入實(shí)例财剖，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的k的實(shí)例悠夯，這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例歸為此類躺坟。k=1時(shí)沦补，為最鄰近算法。

由于kNN方法主要靠周圍有限的鄰近的樣本咪橙，而不是靠判別類域的方法來(lái)確定所屬類別的夕膀，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，kNN方法較其他方法更為適合美侦。

1.2算法描述

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

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

1.3k近鄰法優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：精度高攘已、對(duì)異常值不敏感、無(wú)數(shù)據(jù)輸入假定

缺點(diǎn)：計(jì)算復(fù)雜度高怜跑、空間復(fù)雜度好样勃，適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型

1.4KNN算法思想

1 計(jì)算已知類別中數(shù)據(jù)集的點(diǎn)與當(dāng)前點(diǎn)的距離。[即計(jì)算所有樣本點(diǎn)跟待分類樣本之間的距離]

2 按照距離遞增次序排序性芬。[計(jì)算完樣本距離進(jìn)行排序]

選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)峡眶。[選取距離樣本最近的k個(gè)點(diǎn)]

4 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率。[針對(duì)這k個(gè)點(diǎn)批旺，統(tǒng)計(jì)下各個(gè)類別分別有多少個(gè)]

5 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類幌陕。[k個(gè)點(diǎn)中某個(gè)類別最多诵姜，就將樣本劃歸改點(diǎn)

二汽煮、三要素

K近鄰法中，當(dāng)訓(xùn)練集棚唆、距離度量暇赤、K值和分類決策規(guī)則確定后，對(duì)于任何一個(gè)新的輸入實(shí)例宵凌，它所屬的類唯一確定鞋囊。

2.1距離度量

特征空間中兩個(gè)實(shí)例點(diǎn)的距離是兩個(gè)實(shí)例點(diǎn)相似程度的反映，K近鄰模型的特征空間一般是n維實(shí)數(shù)向量空間瞎惫，使用的距離為歐氏距離(P=2)溜腐。也可使用其他距離译株。

2.2K值的選擇

? ? K值較小，近似誤差會(huì)減小挺益，但估計(jì)誤差會(huì)增大歉糜，容易過(guò)擬合。K值較大則相反望众，但模型會(huì)變得簡(jiǎn)單乱豆，起不到預(yù)測(cè)作用棕兼。

? ? 在應(yīng)用中，K應(yīng)該是一個(gè)比較小的值，通常采用交叉驗(yàn)證來(lái)選最優(yōu)K值错负。

2.3分類決策規(guī)則

多數(shù)表決規(guī)則

三、算法

3.1線性掃描

計(jì)算耗時(shí)搓茬，方法不可行兽掰。

3.2kd樹(shù)

kd樹(shù)是二叉樹(shù)，表示對(duì)k維空間的劃分佳恬。構(gòu)造kd樹(shù)相當(dāng)于不斷用垂直于坐標(biāo)軸的超平面將k維空間切分润文，構(gòu)建一系列的k維超矩形區(qū)域，kd樹(shù)的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)超矩形區(qū)域殿怜。

3.2.1構(gòu)建kd樹(shù)

1典蝌、開(kāi)始：構(gòu)造根節(jié)點(diǎn)，對(duì)應(yīng)于包含T的K維空間的超矩形區(qū)域头谜。

2骏掀、選擇為坐標(biāo)軸，T中軸向坐標(biāo)的中位數(shù)為切分點(diǎn)柱告，將切分點(diǎn)對(duì)應(yīng)的超平面將超矩形區(qū)域分為兩個(gè)子區(qū)域截驮。每個(gè)子區(qū)域?yàn)橐粋€(gè)子節(jié)點(diǎn)。

3际度、重復(fù)

我們有二維數(shù)據(jù)集T={(6,5),(1,-3),(-6,-5),(),(),(),(),(),(),(),(),()}

將他們?cè)谧鴺?biāo)系中表示如下：

開(kāi)始：選擇x為坐標(biāo)軸葵袭，中位數(shù)為6（這個(gè)6是先根據(jù)x坐標(biāo)排序，一共13個(gè)點(diǎn)乖菱，取長(zhǎng)度的中數(shù)坡锡，），即得到（6窒所，5）為切分點(diǎn)鹉勒，切分整個(gè)區(qū)域

再次劃分區(qū)域

以為y坐標(biāo)軸，選擇中位數(shù)吵取，可知左邊區(qū)域?yàn)?3禽额，右邊區(qū)域?yàn)?12。所以左邊區(qū)域切分點(diǎn)為（1皮官，-3）脯倒，右邊區(qū)域切分點(diǎn)坐標(biāo)為（17实辑，-12）

再次對(duì)區(qū)域進(jìn)行切分，同上步藻丢，我們可以得到切分點(diǎn)徙菠，切分結(jié)果如下：

最后分割的小區(qū)域內(nèi)只剩下一個(gè)點(diǎn)或者沒(méi)有點(diǎn)。我們得到最終的kd樹(shù)如下圖

3.2.2搜索kd樹(shù)(最近鄰搜索)

（p為將要查找分類的點(diǎn)郁岩，S為所查找的鄰近點(diǎn)集合婿奔，）

1.根據(jù)p的x坐標(biāo)和kd樹(shù)的結(jié)點(diǎn)向下進(jìn)行搜索（如果樹(shù)的結(jié)點(diǎn)是以x=c?來(lái)切分的，那么如果p的坐標(biāo)小于c问慎，則走左子結(jié)點(diǎn)萍摊，否則走右子結(jié)點(diǎn)）。

2.到達(dá)葉子結(jié)點(diǎn)時(shí)如叼，將其標(biāo)記為已訪問(wèn)冰木。如果S中不足k個(gè)點(diǎn)，則將該結(jié)點(diǎn)加入到S中笼恰；如果S不空且當(dāng)前結(jié)點(diǎn)與p點(diǎn)的距離小于S中最長(zhǎng)的距離踊沸，則用當(dāng)前結(jié)點(diǎn)替換S中離p最遠(yuǎn)的點(diǎn)。

3.如果當(dāng)前結(jié)點(diǎn)不是根節(jié)點(diǎn)社证，執(zhí)行（a）逼龟；否則，結(jié)束算法追葡。

（a）回退到當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)腺律，此時(shí)的結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)（回退之后的結(jié)點(diǎn)）。將當(dāng)前結(jié)點(diǎn)標(biāo)記為已訪問(wèn)宜肉，執(zhí)行（b）和（c）匀钧；如果當(dāng)前結(jié)點(diǎn)已經(jīng)被訪過(guò)，再次執(zhí)行（a）谬返。

（b）如果此時(shí)S中不足k個(gè)點(diǎn)之斯，則將當(dāng)前結(jié)點(diǎn)加入到S中；如果S中已有k個(gè)點(diǎn)遣铝，且當(dāng)前結(jié)點(diǎn)與p點(diǎn)的距離小于S中最長(zhǎng)距離佑刷，則用當(dāng)前結(jié)點(diǎn)替換S中距離最遠(yuǎn)的點(diǎn)。

（c）計(jì)算p點(diǎn)和當(dāng)前結(jié)點(diǎn)切分線的距離翰蠢。如果該距離大于等于S中距離p最遠(yuǎn)的距離并且S中已有k個(gè)點(diǎn)项乒，執(zhí)行3；如果該距離小于S中最遠(yuǎn)的距離或S中沒(méi)有k個(gè)點(diǎn)梁沧，從當(dāng)前結(jié)點(diǎn)的另一子節(jié)點(diǎn)開(kāi)始執(zhí)行1；如果當(dāng)前結(jié)點(diǎn)沒(méi)有另一子結(jié)點(diǎn)蝇裤，執(zhí)行3廷支。

我們來(lái)舉個(gè)例子：假設(shè)在上述建立好的kd樹(shù)中查找p(-1,-5)的3個(gè)鄰近點(diǎn)频鉴。

我們來(lái)舉個(gè)例子：假設(shè)在上述建立好的kd樹(shù)中查找p(-1,-5)的3個(gè)鄰近點(diǎn)。

圖中紅點(diǎn)為p（-1恋拍，-5）

執(zhí)行算法中的1垛孔。

?·p點(diǎn)的-1與結(jié)點(diǎn)A的x軸坐標(biāo)6比較，-1<6施敢，向左走周荐。

?·p點(diǎn)的-5與結(jié)點(diǎn)B的y軸坐標(biāo)-3比較，較小僵娃，往左走概作。

·因?yàn)榻Y(jié)點(diǎn)C只有一個(gè)子結(jié)點(diǎn)，所以不需要進(jìn)行比較默怨，直接走到結(jié)點(diǎn)H讯榕。

進(jìn)行算法中的2，標(biāo)記結(jié)點(diǎn)H已訪問(wèn)匙睹，將結(jié)點(diǎn)H加入到S中愚屁。

此時(shí)S=｛H｝

綠點(diǎn)為H（-4，-10）

執(zhí)行算法中的3痕檬，當(dāng)前結(jié)點(diǎn)H不是根結(jié)點(diǎn)

·執(zhí)行（a）霎槐，回退到父結(jié)點(diǎn)C，我們將結(jié)點(diǎn)C標(biāo)記為已訪問(wèn)

·執(zhí)行（b）梦谜，S中不足3個(gè)點(diǎn)栽燕，將結(jié)點(diǎn)C加入到S中

·執(zhí)行（c）計(jì)算p點(diǎn)和結(jié)點(diǎn)C切分線的距離，可是結(jié)點(diǎn)C沒(méi)有另一個(gè)分支改淑，我們開(kāi)始執(zhí)行算法中的3碍岔。

S=｛H，C｝

當(dāng)前結(jié)點(diǎn)C不是根結(jié)點(diǎn)

·執(zhí)行（a）朵夏，回退到父結(jié)點(diǎn)B蔼啦，我們將結(jié)點(diǎn)B標(biāo)記為已訪問(wèn)

·執(zhí)行（b），S中不足3個(gè)點(diǎn)仰猖，將結(jié)點(diǎn)B加入到S中

·執(zhí)行（c）計(jì)算p點(diǎn)和結(jié)點(diǎn)B切分線的距離鸵赫，兩者距離為?|（-3）-（-5）|=2躏升，小于S中的最大距離一睁。（S中的三個(gè)點(diǎn)與p的距離分別為

）复凳。所以我們需要從結(jié)點(diǎn)B的另一子節(jié)點(diǎn)D開(kāi)始算法中的1。此時(shí)S=｛H，C，B｝

從結(jié)點(diǎn)D開(kāi)始算法中的1

·p點(diǎn)的-1與結(jié)點(diǎn)D的x軸坐標(biāo)-2比較，-1 >? -2哈垢，向右走绑警。

·找到了葉子結(jié)點(diǎn)J，標(biāo)記為已訪問(wèn)拔第。

開(kāi)始算法中的2

·S不空惹悄，計(jì)算當(dāng)前結(jié)點(diǎn)J與p點(diǎn)的距離当纱，為18.2洋腮，大于S中的最長(zhǎng)距離

·所以我們不將結(jié)點(diǎn)J放入S中

此時(shí)集合S中仍為｛H伙狐，C唉侄，B｝

從結(jié)點(diǎn)I開(kāi)始算法中的1，結(jié)點(diǎn)I已經(jīng)是葉子結(jié)點(diǎn)

直接進(jìn)行到算法中的2

標(biāo)記結(jié)點(diǎn)I為已訪問(wèn)

計(jì)算當(dāng)前結(jié)點(diǎn)I和p點(diǎn)的距離為17.464嗽测，大于S中最長(zhǎng)距離绪励，不進(jìn)行替換疏魏。

S=｛D大莫，C，B｝

執(zhí)行算法中的3.

當(dāng)前結(jié)點(diǎn)I不是根結(jié)點(diǎn)

·執(zhí)行（a），回退到父結(jié)點(diǎn)D坪仇，但當(dāng)前結(jié)點(diǎn)D已經(jīng)被訪問(wèn)過(guò)杂腰。

·再次執(zhí)行（a），回退到結(jié)點(diǎn)D的父結(jié)點(diǎn)B皆刺，也標(biāo)記為訪問(wèn)過(guò)

·再次執(zhí)行（a）,回退到結(jié)點(diǎn)B的父結(jié)點(diǎn)A少辣，結(jié)點(diǎn)A未被訪問(wèn)過(guò)，標(biāo)記為已訪問(wèn)羡蛾。

·執(zhí)行（b）漓帅，結(jié)點(diǎn)A和p點(diǎn)的距離為12.207，大于S中的最長(zhǎng)距離痴怨，不進(jìn)行替換

·執(zhí)行（c）忙干，p點(diǎn)和結(jié)點(diǎn)A切分線的距離為7，大于S中的最長(zhǎng)距離浪藻，不進(jìn)行替換

S=｛D捐迫，C，B｝

執(zhí)行算法中的3爱葵，發(fā)現(xiàn)當(dāng)前結(jié)點(diǎn)A是根結(jié)點(diǎn)施戴，結(jié)束算法反浓。

得到p點(diǎn)的3個(gè)鄰近點(diǎn)，為（-6赞哗，-5）雷则、（1，-3）肪笋、（-2月劈，-1）