機(jī)器學(xué)習(xí)導(dǎo)論-第3章 k-最近鄰和k-d樹算法

第3章k-最近鄰和k-d樹算法掌握k-最近鄰法的基本原理。熟悉k-最近鄰法的三個(gè)關(guān)鍵要素和優(yōu)缺點(diǎn)。熟悉k的取值對k-最近鄰法的影響因素。熟悉k-d樹的構(gòu)建過程。本章學(xué)習(xí)目標(biāo)3.1k-最近鄰法3.2k-d樹第3章

k-最近鄰和k-d樹算法3.1k-最近鄰法3.1.1k-最近鄰法的基本思想距離度量，特征空間中樣本點(diǎn)的距離是樣本點(diǎn)間相似程度的反映。算法超參數(shù)

k的取值。決策規(guī)則，例如，對于分類任務(wù)，采取少數(shù)服從多數(shù)的“投票法”；對于回歸任務(wù)，采用取平均值的規(guī)則。給定一個(gè)訓(xùn)練樣本集，對于待預(yù)測類別標(biāo)簽的新輸入測試實(shí)例，可以在特征空間中計(jì)算它與所有訓(xùn)練樣本的距離，然后在訓(xùn)練樣本集中找到與該測試實(shí)例最鄰近的

k

個(gè)訓(xùn)練樣本，統(tǒng)計(jì)這

k

個(gè)樣本所屬的類別，其中樣本數(shù)最多的那個(gè)類就是該測試實(shí)例所屬的類別。k-最近鄰（kNN）法涉及到以下三個(gè)關(guān)鍵要素：3.1k-最近鄰法3.1.2距離度量閔可夫斯基距離（Minkowskidistance）曼哈頓距離（Manhattandistance）3.1k-最近鄰法3.1.2距離度量歐氏距離（Euclideandistance）切比雪夫距離（Chebyshevdistance）漢明距離（Hammingdistance

）

3.1k-最近鄰法3.1.3k值的選擇3.1k-最近鄰法3.1.3k值的選擇如果選擇較小的k值優(yōu)點(diǎn):

訓(xùn)練誤差會(huì)減小，只有與輸入的測試實(shí)例較近或相似的訓(xùn)練樣本才會(huì)對預(yù)測結(jié)果起作用。缺點(diǎn):泛化誤差會(huì)增大，預(yù)測結(jié)果會(huì)對近鄰的訓(xùn)練樣本非常敏感。如果近鄰的訓(xùn)練樣本恰巧是噪聲，則預(yù)測就會(huì)出錯(cuò)。如果選擇較大的k值優(yōu)點(diǎn):可以減小泛化誤差。缺點(diǎn):訓(xùn)練誤差會(huì)增大。ｋ值太大會(huì)使模型整體變得簡單，容易發(fā)生欠擬合。3.1k-最近鄰法3.1.4k-最近鄰法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)算法簡單，易于理解，既可以用于分類任務(wù)也可以用于回歸任務(wù)，且適用于多分類和非線性分類問題。沒有顯式的訓(xùn)練過程，k值是唯一的超參數(shù)，在確定k值后，直接進(jìn)行預(yù)測。由于kNN法并不關(guān)注樣本的類別數(shù)量，因此在處理類別交叉或重疊較多的待分類樣本時(shí)，選用kNN法比較合適。缺點(diǎn)當(dāng)訓(xùn)練樣本集較大、樣本的特征向量維數(shù)較高時(shí)計(jì)算量大，耗時(shí)長，時(shí)間復(fù)雜度高；需要大量的內(nèi)存，空間復(fù)雜度高。當(dāng)存在樣本不平衡問題時(shí)，對稀有類別的預(yù)測準(zhǔn)確度低。k值的選取沒有一個(gè)良好的準(zhǔn)則。適用數(shù)據(jù)范圍數(shù)值型和標(biāo)稱型

3.1k-最近鄰法3.2k-d樹第3章

k-最近鄰和k-d樹算法k-d樹是一種對k維空間中的實(shí)例點(diǎn)進(jìn)行存儲(chǔ)以便對其進(jìn)行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。k-d樹是二叉樹，表示對k維空間的一個(gè)劃分（partition)。構(gòu)造k-d樹相當(dāng)于不斷地用垂直于坐標(biāo)軸的超平面將k維空間切分，構(gòu)成一系列的k維超矩形區(qū)域。k-d樹的每個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)k維超矩形區(qū)域。3.2k-d樹3.2k-d樹3.2.1如何構(gòu)建k-d樹圖3-3二叉搜索樹的一個(gè)例子

①3.2.1如何構(gòu)建k-d

樹構(gòu)建k-d樹的過程如下：

①②②3.2.1如何構(gòu)建k-d

樹

①②②③③3.2.1如何構(gòu)建k-d

樹

①②②③③④

3.2.1如何構(gòu)建k-d

樹①③③④②②3.2.1如何構(gòu)建k-d

樹

（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），對該KD樹作深度優(yōu)先遍歷。以（4,4）為圓心，其到（6,4）的距離為半徑畫圓（多維空間為超球面），可以看出（7,2）右側(cè)的區(qū)域與該圓不相交，所以（7,2）的右子樹全部忽略。3.2.2如何在k-d樹中搜索

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

（3）如果不相交直接返回父節(jié)點(diǎn)，在另一個(gè)子樹繼續(xù)搜索最近鄰。（4）當(dāng)回溯到根節(jié)點(diǎn)時(shí)，算