K近鄰算法PPT

1、K近鄰算法 什么是K-近鄰算法所謂K近鄰算法，即K-Nearest Neighbor algorithm，簡(jiǎn)稱(chēng)KNN算法，單從名字來(lái)猜想，可以簡(jiǎn)單粗暴的認(rèn)為是：K個(gè)最近的鄰居，當(dāng)K=1時(shí)，算法便成了最近鄰算法，即尋找最近的鄰居。為何要找鄰居？打個(gè)比方來(lái)說(shuō)，假設(shè)你來(lái)到一個(gè)陌生的村莊，現(xiàn)在你要找到與你有著相似特征的人群融入他們，所謂入伙。用官方的話(huà)來(lái)說(shuō)，所謂K近鄰算法，即是給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的K個(gè)實(shí)例（也就是上面說(shuō)的K個(gè)鄰居），這K個(gè)實(shí)例的多數(shù)屬于某個(gè)類(lèi)，就把該輸入實(shí)例分類(lèi)到這個(gè)類(lèi)中。2022-2-52算法舉例如上圖所示，有兩類(lèi)不同的樣本數(shù)據(jù)，分別

2、用藍(lán)色的小正方形和紅色的三角形表示，而圖正中間的那個(gè)綠色的圓所標(biāo)示的數(shù)據(jù)則是待分類(lèi)的數(shù)據(jù)。問(wèn)題：給這個(gè)綠色的圓分類(lèi)？如果K=3，綠色圓點(diǎn)的最近的3個(gè)鄰居是2個(gè)紅色小三角形和1個(gè)藍(lán)色小正方形，少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類(lèi)點(diǎn)屬于紅色的三角形一類(lèi)。如果K=5，綠色圓點(diǎn)的最近的5個(gè)鄰居是2個(gè)紅色三角形和3個(gè)藍(lán)色正方形，還是少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定綠色的這個(gè)待分類(lèi)點(diǎn)屬于藍(lán)色的正方形一類(lèi)。2022-2-53K近鄰算法內(nèi)容2022-2-54K近鄰模型K近鄰法使用的模型實(shí)際上對(duì)應(yīng)于特征空間的劃分。模型有三個(gè)基本要素距離度量、k值的選擇和分類(lèi)決策規(guī)則決定。K近鄰法中，當(dāng)訓(xùn)練集

3、、距離度量、k值以及分類(lèi)決策規(guī)則確定后，對(duì)于任何一個(gè)新的輸入實(shí)例，它所屬的類(lèi)唯一地確定。這相當(dāng)于根據(jù)上述要素將特征空間劃分為一些子空間，確定子空間里的每個(gè)點(diǎn)所屬的類(lèi)。2022-2-55K近鄰的三個(gè)基本要素2022-2-56K近鄰的三個(gè)基本要素 K值的選擇如果選擇較小的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)非常敏感。換句話(huà)說(shuō)，k值的減小意味著整體模型變得復(fù)雜，容易發(fā)生過(guò)擬合。如果選擇較大的k值，就相當(dāng)于用較大鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)。其優(yōu)點(diǎn)是可以減少學(xué)

4、習(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值得選擇反映了對(duì)近似誤差與估計(jì)誤差之間的權(quán)衡，通常由交叉驗(yàn)證選擇最優(yōu)的k.2022-2-57K近鄰的三個(gè)基本要素 分類(lèi)決策規(guī)則K近鄰中的分類(lèi)決策規(guī)則往往是多數(shù)表決，即由輸入實(shí)例的K個(gè)鄰近的訓(xùn)練實(shí)例中的多數(shù)類(lèi)決定輸入實(shí)例的類(lèi)。對(duì)應(yīng)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。2022-2-58K近鄰法的實(shí)現(xiàn)：kd樹(shù) 構(gòu)造kd樹(shù)Kd樹(shù)是一種對(duì)k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對(duì)其進(jìn)行快速檢索的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。Kd樹(shù)是二叉樹(shù)，表示對(duì)k維空間的一個(gè)劃分。構(gòu)造kd樹(shù)相當(dāng)于不斷地用垂直于坐

5、標(biāo)軸的超平面將k維空間切分，構(gòu)成一系列的k維超矩形區(qū)域。Kd樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)k維超矩形區(qū)域。方法：構(gòu)造根結(jié)點(diǎn)，使根結(jié)點(diǎn)對(duì)應(yīng)于k維空間中包含所有實(shí)例點(diǎn)的超矩形區(qū)域；通過(guò)遞歸方法，不斷地對(duì)k維空間進(jìn)行切分，生成子結(jié)點(diǎn)。在超矩形區(qū)域（結(jié)點(diǎn)）上選擇一個(gè)坐標(biāo)軸和在此坐標(biāo)軸上的一個(gè)切分點(diǎn)，確定一個(gè)超平面，這個(gè)超平面通過(guò)選定的切分點(diǎn)并垂直于選定的坐標(biāo)軸，將當(dāng)前超矩形區(qū)域切分為左右兩個(gè)子區(qū)域（子結(jié)點(diǎn)）；這時(shí)，實(shí)例被分到兩個(gè)子區(qū)域。這個(gè)過(guò)程直到子區(qū)域內(nèi)沒(méi)有實(shí)例時(shí)終止。在此過(guò)程中，將實(shí)例保存在相應(yīng)的結(jié)點(diǎn)上。2022-2-59K近鄰法的實(shí)現(xiàn)：kd樹(shù)2022-2-510K近鄰法的實(shí)現(xiàn)：kd樹(shù)2022-2-511

6、K近鄰法的實(shí)現(xiàn)：kd樹(shù) 搜索kd樹(shù)利用kd樹(shù)可以省去大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計(jì)算量。這里以最近鄰為例，同樣的方法可以應(yīng)用到K近鄰。給定一個(gè)目標(biāo)點(diǎn)，搜索其最近鄰。首先找到包含目標(biāo)點(diǎn)的葉結(jié)點(diǎn)；然后從該葉結(jié)點(diǎn)出發(fā)，依次回退到父結(jié)點(diǎn)；不斷查找與目標(biāo)點(diǎn)最鄰近的結(jié)點(diǎn)，當(dāng)確定不可能存在更近的結(jié)點(diǎn)時(shí)終止。這樣搜索就被限制在空間的局部區(qū)域上，效率大為提高。包含目標(biāo)點(diǎn)的葉結(jié)點(diǎn)對(duì)應(yīng)包含目標(biāo)點(diǎn)的最小超矩形區(qū)域。以此葉結(jié)點(diǎn)的實(shí)例點(diǎn)作為當(dāng)前最近點(diǎn)。目標(biāo)點(diǎn)的最近鄰一定在以目標(biāo)點(diǎn)為中心并通過(guò)當(dāng)前最近點(diǎn)的超球體內(nèi)部。然后返回當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)，如果父結(jié)點(diǎn)的另一子結(jié)點(diǎn)的超矩形區(qū)域與超球體相交，那么在相交的區(qū)域內(nèi)尋找與目標(biāo)

7、點(diǎn)更近的實(shí)例點(diǎn)。如果存在這樣的點(diǎn)，將此點(diǎn)作為新的當(dāng)前最近點(diǎn)。2022-2-512K近鄰法的實(shí)現(xiàn)：kd樹(shù) 搜索kd樹(shù)算法轉(zhuǎn)到更上一級(jí)的父結(jié)點(diǎn)，繼續(xù)上述過(guò)程。如果父結(jié)點(diǎn)的另一子結(jié)點(diǎn)的超矩形區(qū)域與超球體不相交，或不存在比當(dāng)前最近點(diǎn)更近的點(diǎn)，則停止搜索。例：例：給定一個(gè)如圖所示的kd樹(shù)，根結(jié)點(diǎn)為A，其子結(jié)點(diǎn)為B,C等。樹(shù)上共存儲(chǔ)7個(gè)實(shí)例點(diǎn)；另有一個(gè)輸入目標(biāo)實(shí)例點(diǎn)S，求S的最近鄰解：首先在kd樹(shù)中找到包含S的葉結(jié)點(diǎn)D，以點(diǎn)D作為近似最鄰。真正最近鄰一定在以點(diǎn)S為中心通過(guò)點(diǎn)D的圓的內(nèi)部。然后返回結(jié)點(diǎn)D的父結(jié)點(diǎn)B，在結(jié)點(diǎn)B的另一子結(jié)點(diǎn)F的區(qū)域內(nèi)搜索最近鄰。結(jié)點(diǎn)F的區(qū)域與圓不想交，不可能有最近鄰。繼續(xù)返回上一級(jí)父結(jié)