機(jī)器學(xué)習(xí)算法與實(shí)踐 課件 第3章 K近鄰

第三章K近鄰K-近鄰算法（K-NearestNeighbor，KNN）是一種基于一定距離測(cè)度的抽樣檢驗(yàn)方法，屬于監(jiān)督學(xué)習(xí)，所以使用算法時(shí)必須有已知標(biāo)記的訓(xùn)練集。K-近鄰算法既可用于分類也可用于回歸。在處理分類問(wèn)題時(shí)，該方法只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分類樣本所屬的類別。處理回歸問(wèn)題的流程與分類問(wèn)題相似，區(qū)別在于樣本的輸出標(biāo)記為距離其最近的一個(gè)或者幾個(gè)樣本的標(biāo)記的加權(quán)平均值。13.1算法原理在分類問(wèn)題中，給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)于任何一個(gè)待分類樣本，在訓(xùn)練數(shù)據(jù)集中找到與該樣本最鄰近的K個(gè)樣本（也就是最近的K個(gè)鄰居），那么即可以使用這K個(gè)樣本中的多數(shù)類別標(biāo)記作為待分類樣本的類別標(biāo)記。特別的，必須保證訓(xùn)練數(shù)據(jù)集中的每個(gè)樣本都有類別標(biāo)記。在回歸問(wèn)題中，樣本的標(biāo)記為連續(xù)變量，因此一般將待處理樣本的K個(gè)最近鄰的標(biāo)記的加權(quán)平均值作為輸出（以距離的倒數(shù)為權(quán)重）。除此之外，還可以指定一個(gè)半徑，將半徑范圍內(nèi)的全部鄰居的標(biāo)記的加權(quán)平均值作為輸出。23.1算法原理圖中的樣本有兩個(gè)類別，分別以正方形和三角形表示，而圖正中間的圓形代表待分類樣本。

首先假設(shè)我們選擇K的值為3，圓形樣本最近的3個(gè)鄰居是2個(gè)三角形和1個(gè)正方形，少數(shù)從屬于多數(shù)，基于統(tǒng)計(jì)的方法，判定這個(gè)待分類樣本屬于三角形一類。

如果我們選擇K的值為5，那么圓形樣本最近的5個(gè)鄰居是2個(gè)三角形和3個(gè)正方形，還是少數(shù)從屬于多數(shù)，可以判定這個(gè)待分類點(diǎn)屬于正方形一類。33.1算法原理K-近鄰算法的基本流程為：1）計(jì)算已經(jīng)正確分類的數(shù)據(jù)集中每個(gè)樣本與待分

類樣本之間的距離；2）按照距離遞增次序?qū)?shù)據(jù)集中的樣本排序；3）選取與待分類樣本距離最小的K個(gè)樣本；4）確定該K個(gè)樣本所在類別的出現(xiàn)頻率；5）返回該K個(gè)樣本出現(xiàn)頻率最高的類別作為待分

類樣本的預(yù)測(cè)類別。43.1算法原理K值的選擇會(huì)對(duì)算法的結(jié)果產(chǎn)生重大影響：K值較小意味著只有與待分類樣本較近的已知樣本才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用，但容易發(fā)生過(guò)擬合K值較大可以減少學(xué)習(xí)的估計(jì)誤差，但是學(xué)習(xí)的近似誤差增大，因?yàn)檫@時(shí)與待分類樣本較遠(yuǎn)的已知樣本也會(huì)對(duì)預(yù)測(cè)起作用，容易使預(yù)測(cè)發(fā)生錯(cuò)誤。K值一般選擇一個(gè)奇數(shù)值，因?yàn)樗惴ㄖ械姆诸悰Q策規(guī)則往往是多數(shù)表決，奇數(shù)取值可防止出現(xiàn)鄰居中不同類別樣本數(shù)量相等的情況。53.2距離度量方法

在K-近鄰算法以及其他很多機(jī)器學(xué)習(xí)算法中都會(huì)涉及到距離的計(jì)算，距離度量方式對(duì)算法的性能有很大的影響。

常用的距離計(jì)算方式如下： 1.閔科夫斯基距離（Minkowskidistance） 2.歐幾里德距離（Euclideandistance） 3.曼哈頓距離（Manhattandistance） 4.切比雪夫距離（Chebyshevdistance） 5.余弦相似度（Cosinesimilarity） 6.皮爾遜相關(guān)系數(shù)（Pearsoncorrelationcoefficient） 7.杰卡德相似系數(shù)（Jaccardsimilaritycoefficient） 8.馬氏距離（Mahalanobisdistance）6

3.2距離度量方法

7

3.2距離度量方法

8

3.2距離度量方法

9

3.2距離度量方法

10

3.3搜索優(yōu)化方法

當(dāng)數(shù)據(jù)集和特征數(shù)量較大時(shí)，K-近鄰算法的距離計(jì)算成本可能會(huì)較高。在近鄰搜索的過(guò)程中，算法會(huì)有較高的計(jì)算成本。因此，為了提高K-近鄰算法的搜索效率，可以考慮使用特殊的結(jié)構(gòu)來(lái)存儲(chǔ)已知樣本，以減少距離計(jì)算的次數(shù)。11

3.3.1

k-d樹 k-d樹（k-dimensionalTree）是針對(duì)暴力搜索效率低下而提出的基于樹的數(shù)據(jù)結(jié)構(gòu)。

基本思想：若A點(diǎn)距離B點(diǎn)非常遠(yuǎn)，B點(diǎn)距離C點(diǎn)非常近，可知A點(diǎn)與C點(diǎn)很遠(yuǎn)，因此不需要準(zhǔn)確計(jì)算它們之間的距離。通過(guò)這種方式，對(duì)于具有k個(gè)特征的n個(gè)樣本來(lái)說(shuō)，近鄰搜索的計(jì)算成本可以降低至O[knlog(??)]以下，可以顯著改善暴力搜索在大樣本容量數(shù)據(jù)集中的表現(xiàn)。12

3.3.1

k-d樹例1：假設(shè)數(shù)據(jù)集有2個(gè)特征、6個(gè)樣本，如T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}。使用k-d樹算法確定樣本點(diǎn)的劃分空間分割線。

13

3.3.1

k-d樹首先，選擇劃分特征，即確定分割線是垂直于X軸還是Y軸。分別計(jì)算X軸和Y軸方向樣本的方差，得知X軸方向的方差最大，所以首先對(duì)X軸進(jìn)行劃分，確定分割線的X軸坐標(biāo)。然后基于上述步驟，對(duì)Y軸進(jìn)行同樣劃分操作。14

3.3.1

k-d樹最后，對(duì)依然有樣本存在的子空間再按X軸進(jìn)行劃分，直至子空間不再有樣本為止。由于此時(shí)的每個(gè)子空間僅包含一個(gè)樣本，因此可直接按剩余樣本劃分空間區(qū)域。15

3.3.1

k-d樹k-d樹的構(gòu)建過(guò)程可以總結(jié)為：1）構(gòu)造根結(jié)點(diǎn)，使根結(jié)點(diǎn)對(duì)應(yīng)于k維空間中包含所有樣本點(diǎn)的超矩形區(qū)域；2）通過(guò)遞歸的方法，不斷地對(duì)k維空間進(jìn)行切分，生成子結(jié)點(diǎn)。3）重復(fù)上述過(guò)程直到子區(qū)域內(nèi)沒(méi)有樣本時(shí)終止。在此過(guò)程中，將樣本保存在相應(yīng)的結(jié)點(diǎn)上。4）通常，循環(huán)的依次選擇坐標(biāo)軸對(duì)空間切分。16

3.3.1

k-d樹構(gòu)建k-d樹時(shí)，關(guān)鍵需要解決2個(gè)問(wèn)題：1）選擇向量的哪一維進(jìn)行劃分？2）如何劃分?jǐn)?shù)據(jù)？對(duì)于第一個(gè)問(wèn)題，簡(jiǎn)單的解決方法可以是隨機(jī)選擇某一維或按順序選擇，但是更好的方法應(yīng)該是在數(shù)據(jù)比較分散的那一維進(jìn)行劃分。好的劃分方法可以使構(gòu)建的樹比較平衡，可以每次選擇中位數(shù)來(lái)進(jìn)行劃分，這樣第二個(gè)問(wèn)題也得到了解決。17

3.3.1

k-d樹如何利用k-d樹進(jìn)行最近鄰搜索？

18

3.3.1

k-d樹如何利用k-d樹進(jìn)行最近鄰搜索？

接著，由于被搜索點(diǎn)的劃分維度值3小于當(dāng)前節(jié)點(diǎn)的劃分維度的值7，因此將當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)(5,4)作為新的當(dāng)前節(jié)點(diǎn)。由于此時(shí)當(dāng)前節(jié)點(diǎn)到被搜索點(diǎn)的距離為2.83，小于全局最短距離，所以更新當(dāng)前最佳點(diǎn)為(5,4)。19

3.3.1

k-d樹如何利用k-d樹進(jìn)行最近鄰搜索？

繼續(xù)下去，由于被搜索點(diǎn)的劃分維度值2小于當(dāng)前節(jié)點(diǎn)的劃分維度值4，因此設(shè)當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)(2,3)為新的當(dāng)前節(jié)點(diǎn)。由于此時(shí)當(dāng)前節(jié)點(diǎn)到被搜索點(diǎn)的距離為1.41，小于全局最短距離，所以更新當(dāng)前最佳點(diǎn)為(2,3)，全局最短距離為1.4120

3.3.1

k-d樹如何利用k-d樹進(jìn)行最近鄰搜索？

21

3.3.1

k-d樹如何利用k-d樹進(jìn)行最近鄰搜索？

22

3.3.2球樹 k-d樹算法雖然提高了K-近鄰算法的搜索效率，但在處理非均勻數(shù)據(jù)集和高維數(shù)據(jù)時(shí)也會(huì)出現(xiàn)效率不高的情況。為了優(yōu)化k-d樹的算法策略，提出了球樹模型。

球樹將數(shù)據(jù)遞歸地劃分為由質(zhì)心c和半徑r定義的節(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)本質(zhì)上是一個(gè)空間，包含了若干個(gè)樣本點(diǎn)，每個(gè)空間內(nèi)有一個(gè)獨(dú)一無(wú)二的中心點(diǎn)23

3.3.2球樹

24

3.3.2球樹

首先建立根節(jié)點(diǎn)，找到包含所有樣本點(diǎn)的超球體，記錄球心位置，作為根節(jié)點(diǎn)。然后，找到所有點(diǎn)中距離最遠(yuǎn)的兩個(gè)點(diǎn)，并判斷其他樣本點(diǎn)與這兩個(gè)點(diǎn)的距離，距離哪個(gè)點(diǎn)最近，則將該樣本點(diǎn)劃分到該點(diǎn)的類內(nèi)，這兩個(gè)類即是根節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。分別對(duì)兩個(gè)子節(jié)點(diǎn)構(gòu)建超球體，記錄球心坐標(biāo)和半徑。25

3.3.2球樹重復(fù)上述過(guò)程直至樣本全部劃分完畢26

3.4本章小結(jié)本章主要介紹了K-近鄰算法，給出了其在處理分類和回歸問(wèn)題時(shí)的原理和流程，并介紹了k-d樹和球樹兩種提升K-近鄰搜索效率的方法。K-近鄰算法簡(jiǎn)單易懂且實(shí)用，但是因?yàn)槊恳淮畏诸惢蛘呋貧w，都要把已知數(shù)據(jù)樣本和測(cè)試樣本的距離全部計(jì)算一遍并搜索其中最近的K個(gè)鄰居，在數(shù)據(jù)量和數(shù)據(jù)維度很大的情況下，需要的計(jì)算資源會(huì)十