KNN的kd tree搜尋過程是不是就是決策樹的訓練過程？

1樓：

我覺得另外乙個答主的總結很到位：

不過認真想想，也不過是樹這種模型在描述問題的一種靈活形式吧。

確實如此，對測試樣本進行判斷，都是在「樹」模型的基礎上搜尋：1）在k-NN模型中的初衷是提高搜尋速度，提供一種訓練樣本集的儲存方式；2）在DT中「分而治之」的思想，這種層級結構很顯然符合樹模型。

總結一下不同之處：

樹模型中的節點判斷不同。

k-NN在建樹的過程中，順次及迴圈採用x的特徵方向或屬性。即利用第乙個特徵方向上的中位數等作為劃分依據，分成兩個子空間；然後繼續採用下乙個特徵方向或屬性，依次類推；如果屬性用完了，如果在子空間中仍然存在樣本點；則從第乙個特徵方向或屬性開始，繼續對子空間劃分；直到子空間內沒有樣本點。

DT，有乙個關鍵的特徵或屬性選擇的過程（如資訊增益、增益率或基尼係數等），未必是從第乙個屬性開始；並且，同一條支路上的屬性依據不會重複——不知道「支路」這個詞，我是不是用對了。

樹的形態不同。

k-NN的樹的結果，如果採用中位數等，更接近平衡樹；

DT，則沒有這種趨勢，並且依賴於劃分選擇依據（如資訊增益、增益率或基尼係數等）、預剪枝和後剪枝的方式，有較大差異。

樹的終止條件不同：

k-NN直到劃分的子空間中沒有樣本。

DT，有多種終止方式：

在某屬性上，所有的樣本屬於同乙個類別；

所有屬性被用盡；

所有樣本被用盡；

符合預剪枝的條件；

（當然上述內容都是共知的，在此只是稍微按照個人理解總結下，拋磚引玉，輕拍）

2樓：

決策樹的決策過程很像KNN的近鄰搜尋過程

kNN的kd樹實現，是建立了一棵索引樹，目的是便於查詢，是先找到葉子節點，再從葉子節點回溯相鄰節點的過程。

而決策樹的決策過程，只是根據決策節點找到相應葉子節點，獲取分類的過程，少乙個回溯呢。

感覺建樹過程倒是有些像，都是選擇劃分維度，然後遞迴建樹的過程，只不過劃分維度的標準不同。不過認真想想，也不過是樹這種模型在描述問題的一種靈活形式吧。比如搜尋樹中，對於節點大小的比較，進而引起的快速搜尋，仔細想來，也是乙個原理呢。