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

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

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

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

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

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

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

常用的距離計算方式如下： 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ù)量較大時，K-近鄰算法的距離計算成本可能會較高。在近鄰搜索的過程中，算法會有較高的計算成本。因此，為了提高K-近鄰算法的搜索效率，可以考慮使用特殊的結(jié)構(gòu)來存儲已知樣本，以減少距離計算的次數(shù)。11

3.3.1

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

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

3.3.1

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

13

3.3.1

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

3.3.1

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

3.3.1

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

3.3.1

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

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

18

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

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

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

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

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

21

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

22

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

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

3.3.2球樹

24

3.3.2球樹

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

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

3.4本章小結(jié)本章主要介紹了K-近鄰算法，給出了其在處理分類和回歸問題時的原理和流程，并介紹了k-d樹和球樹兩種提升K-近鄰搜索效率的方法。K-近鄰算法簡單易懂且實用，但是因為每一次分類或者回歸，都要把已知數(shù)據(jù)樣本和測試樣本的距離全部計算一遍并搜索其中最近的K個鄰居，在數(shù)據(jù)量和數(shù)據(jù)維度很大的情況下，需要的計算資源會十