01距離度量02KNN算法本章目錄03KD樹劃分04KD樹搜索01距離度量02KNN算法03KD樹劃分04KD樹搜索1.距離度量距離度量歐氏距離(Euclideandistance)

電影分類距離度量曼哈頓距離(Manhattandistance)

想象你在城市道路里，要從一個(gè)十字路口開車到另外一個(gè)十字路口，駕駛距離是兩點(diǎn)間的直線距離嗎？顯然不是，除非你能穿越大樓。實(shí)際駕駛距離就是這個(gè)“曼哈頓距離”。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區(qū)距離(CityBlockdistance)。距離度量切比雪夫距離(Chebyshevdistance)

二個(gè)點(diǎn)之間的距離定義是其各坐標(biāo)數(shù)值差絕對(duì)值的最大值。國(guó)際象棋棋盤上二個(gè)位置間的切比雪夫距離是指王要從一個(gè)位子移至另一個(gè)位子需要走的步數(shù)。由于王可以往斜前或斜后方向移動(dòng)一格，因此可以較有效率的到達(dá)目的的格子。上圖是棋盤上所有位置距f6位置的切比雪夫距離。距離度量閔可夫斯基距離(Minkowskidistance)

距離度量漢明距離(Hammingdistance)

漢明距離是使用在數(shù)據(jù)傳輸差錯(cuò)控制編碼里面的，漢明距離是一個(gè)概念，它表示兩個(gè)（相同長(zhǎng)度）字對(duì)應(yīng)位不同的數(shù)量，我們以表示兩個(gè)字之間的漢明距離。對(duì)兩個(gè)字符串進(jìn)行異或運(yùn)算，并統(tǒng)計(jì)結(jié)果為1的個(gè)數(shù)，那么這個(gè)數(shù)就是漢明距離。距離度量余弦相似度

01距離度量02KNN算法03KD樹劃分04KD樹搜索2.KNN算法2.KNN算法

2.KNN算法

2.KNN算法算法流程如下：1.計(jì)算測(cè)試對(duì)象到訓(xùn)練集中每個(gè)對(duì)象的距離2.按照距離的遠(yuǎn)近排序3.選取與當(dāng)前測(cè)試對(duì)象最近的k的訓(xùn)練對(duì)象，作為該測(cè)試對(duì)象的鄰居4.統(tǒng)計(jì)這k個(gè)鄰居的類別頻次5.k個(gè)鄰居里頻次最高的類別，即為測(cè)試對(duì)象的類別K=3K=501距離度量02KNN算法03KD樹劃分04KD樹搜索3.K-D-Tree劃分KD樹劃分

①

KD樹劃分

①②②

KD樹劃分

①②②③③

KD樹劃分

①②②③③④

KD樹劃分

①③③④②②KD樹劃分樣本空間結(jié)構(gòu)圖

01距離度量02KNN算法03KD樹劃分04KD樹搜索4.K-D-Tree搜索KD樹搜索

1.首先要找到該目標(biāo)點(diǎn)的葉子節(jié)點(diǎn)，然后以目標(biāo)點(diǎn)為圓心，目標(biāo)點(diǎn)到葉子節(jié)點(diǎn)的距離為半徑，建立一個(gè)超球體，我們要找尋的最近鄰點(diǎn)一定是在該球體內(nèi)部。搜索（4,4）的最近鄰時(shí)。首先從根節(jié)點(diǎn)（6,4）出發(fā)，將當(dāng)前最近鄰設(shè)為（6,4），對(duì)該KD樹作深度優(yōu)先遍歷。以（4,4）為圓心，其到（6,4）的距離為半徑畫圓（多維空間為超球面），可以看出（7,2）右側(cè)的區(qū)域與該圓不相交，所以（7,2）的右子樹全部忽略。KD樹搜索

2.返回葉子結(jié)點(diǎn)的父節(jié)點(diǎn)，檢查另一個(gè)子結(jié)點(diǎn)包含的超矩形體是否和超球體相交，如果相交就到這個(gè)子節(jié)點(diǎn)尋找是否有更加近的近鄰,有的話就更新最近鄰。接著走到（6,4）左子樹根節(jié)點(diǎn)（4,5），與原最近鄰對(duì)比距離后，更新當(dāng)前最近鄰為（4,5）。以（4,4）為圓心，其到（4,5）的距離為半徑畫圓，發(fā)現(xiàn)（6,4）右側(cè)的區(qū)域與該圓不相交，忽略該側(cè)所有節(jié)點(diǎn)，這樣（6,4）的整個(gè)右子樹被標(biāo)記為已忽略。KD樹搜索

3.如果不相交直接返回父節(jié)點(diǎn)，在另一個(gè)子樹繼續(xù)搜索最近鄰。4.當(dāng)回溯到根節(jié)點(diǎn)時(shí)，算法結(jié)束，此時(shí)保存的最近鄰節(jié)點(diǎn)就是最終的最近鄰。遍歷完（4,5）的左右葉子節(jié)點(diǎn)，發(fā)現(xiàn)與當(dāng)前最優(yōu)距離相等，不更新最近鄰。所以（4,4）的最近鄰為（4,5）。參考文獻(xiàn)[1]AndrewNg.MachineLearning[EB/OL].StanfordUniversity,2014./course/ml[2]李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,2019.[3]周志華.機(jī)器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016.[4]CoverTM,HartPE.Nearestneighborpatternclassification[J].IEEETrans.inf.theory,1953,13(1):21-27.[5]HastieT.,TibshiraniR.,FriedmanJ.TheElementsofStatisticalLearning[M].NewYork:Springer,2001.[6]CHRISTOPHERM.BISHOP.PatternRecognitionandMachineLearning[M].NewYork:Spr