機器學習導(dǎo)論-第3章 k-最近鄰和k-d樹算法

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

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

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

k

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

k

個樣本所屬的類別，其中樣本數(shù)最多的那個類就是該測試實例所屬的類別。k-最近鄰（kNN）法涉及到以下三個關(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)點:

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

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

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

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

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

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