樹模型演算法

『壹』 kruskal演算法Kruskal演算法

克魯斯卡爾演算法是一種用於構建最小生成樹的常用演算法，當處理含有 n 個頂點的連通網 WN=(V,{E}) 時，其步驟如下：

首先，從一個初始狀態開始，構建一個僅包含 n 個頂點且邊集為空的子圖，視每個頂點為獨立的樹根，形成一個由 n 棵樹組成的森林。接著，從所有邊 E 中挑選權值最小的邊，如果這條邊連接的兩個頂點在不同的樹中，就將其添加到子圖中，合並兩棵樹；若兩個頂點已屬於同一棵樹，則跳過該邊，繼續尋找下一條權值最小的邊。這個過程一直持續到森林中只剩下一棵樹，即子圖的邊數達到 n-1 條，此時的子圖即為最小生成樹。

舉個例子，我們可以這樣操作：首先對所有的邊按權值排序，如圖所示，從AD開始連接，逐步構建。然後在剩下的邊中，避免選擇已形成連通的邊，如BC或EF，盡管它們可能是最短的。最終，通過這種方式選擇邊，直到所有頂點連通，形成最小生成樹。

最後的結構如下圖所示，所有頂點已通過邊連通，完成了最小生成樹的構建。

(1)樹模型演算法擴展閱讀

K r u s k a l演算法每次選擇n- 1條邊，所使用的貪婪准則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。K r u s k a l演算法分e 步，其中e 是網路中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。

『貳』 構建決策樹的三種演算法是什麼

構建決策樹的三種主要演算法包括CHAID、CART以及ID3。
1. CHAID演算法
CHAID，即卡方自動相互關系檢測，是一種歷史悠久的決策樹構建演算法。它特別適用於因變數為分類型的情況。
2. CART演算法
CART（分類與回歸樹）演算法於20世紀80年代中期被提出。它與CHAID的分割邏輯相似，但在變數選擇上，CART使用基尼系數等指標，而不是卡方檢驗。
3. ID3演算法
ID3演算法也是80年代中期的產物，稱為迭代的二分器。其獨特之處在於使用信息增益作為變數選擇的標准，選擇最能減少分類所需信息的屬性進行節點分裂。
決策樹的優點在於其直觀性和易於理解。它能夠直觀展示數據特點，用戶無需深入了解復雜知識即可理解。數據准備過程相對簡單，決策樹也能處理數值和非數值屬性。此外，它能夠在較短的時間內對大量數據源進行分析，並生成有效結果。決策樹模型可通過靜態測試輕松評估，從而確定模型的可信度。而且，一旦生成了決策樹模型，便能輕易推導出相應的邏輯表達式。以上內容參考了網路關於決策樹的介紹。

『叄』 樹模型總結

Decision Tree -(Bagging)-> Random Forest -(Boosting)-> Gradient Boosting->XGBoost

【1】 https://zhuanlan.hu.com/p/34534004
【2】 https://www.hu.com/question/41354392/answer/545973472

決策樹是一個有監督的分類模型，本質是選擇一個能帶來最大信息增益的特徵值進行分裂，直到到達結束條件或者葉子節點純度到達一定閾值。
決策樹的每個非葉子節點表示一個特徵屬性上的測試，每個分支代表這個特徵屬性在某個值域上的輸出。葉子節點存放一個類別，將存放的類別作為決策結果。
按照分裂指標不同，決策樹分為ID3，C4.5，和CART。
1. ID3：以信息增益為劃分標准
信息增益的計算基於信息熵（度量樣本集合純度指標）

ID3的缺陷：
假設每個記錄有一個屬性「ID」，若按照ID來進行分割的話，由於ID是唯一的，因此在這一個屬性上，能夠取得的特徵值等於樣本的數目，也就是說ID的特徵值很多。那麼無論以哪個ID為劃分，葉子結點的值只會有一個，純度很大，得到的信息增益會很大，但這樣劃分出來的決策樹是沒意義的。由此可見，ID3決策樹偏向於取值較多的屬性進行分割，存在一定的偏好。為減小這一影響，有學者提出C4.5的分類演算法。

2. C4.5：基於信息增益率准則選擇最優分割屬性演算法
信息增益率通過引入一個被稱作分裂信息（Split information）的項來懲罰取值較多的屬性。

分子即ID3中計算的信息增益。分母由屬性a的特徵值個數決定，IV值越大，信息增益率越小，這樣就可以避免模型偏好特徵值多的屬性。
但是，如果使用這個公式，模型又會偏向特徵數少的特徵。因此，C4.5決策樹先從候選分裂屬性中找出信息增益高於平均水平的屬性，從中選擇增益率最高的。

對於連續值屬性來說，可取值數目不再有限，因此可以採用離散化技術（如二分法）進行處理。將屬性值從小到大排序，然後選擇中間值作為分割點，數值比它小的點被劃分到左子樹，數值不小於它的點被分到右子樹，計算分割的信息增益率，選擇信息增益率最大的屬性值進行分割。

3. CART：以基尼系數為准則選擇最優劃分屬性，可以應用於分類和回歸

CART是一棵二叉樹，採用二元切分法，每次把數據切成兩份，分別進入左子樹、右子樹。而且每個非葉子節點都有兩個孩子，所以CART的葉子節點比非葉子多1。相比ID3和C4.5，CART應用要多一些，既可以用於分類也可以用於回歸。CART分類時，使用基尼指數（Gini）來選擇最好的數據分割的特徵，gini描述的是純度，與信息熵的含義相似。CART中每一次迭代都會降低GINI系數。

Gini(D)反映了數據集D的純度，值越小，純度越高。我們在候選集合中選擇使得劃分後基尼指數最小的屬性作為最優化分屬性。

分類與回歸樹具有兩點特徵：

回歸樹優點：

組合分類器是將多個分類器的結果進行多票表決或者取平均值，以此作為最終結果。
Bagging的思想是每一次從原始數據中根據均勻概率分布有放回的抽取和原始數據大小相同的樣本集合，樣本點可能出現重復，然後對每一次產生的訓練集構造一個分類器，再對分類器進行組合。

構建組合分類器的好處：

隨機森林是一個多棵決策樹的組合分類器。主要包括兩方面：數據的隨機選取，以及待選特徵的隨機選取。

1.數據的隨機選取
第一，從原始的數據集中採取有放回的抽樣（bootstrap），構造子數據集，子數據集的數據量是和原始數據集相同的。不同子數據集的元素可以重復，同一個子數據集中的元素也可以重復。
第二，利用子數據集來構建子決策樹，將這個數據放到每個子決策樹中，每個子決策樹輸出一個結果。最後，如果有了新的數據需要通過隨機森林得到分類結果，就可以通過對子決策樹的判斷結果的投票，得到隨機森林的輸出結果了。如下圖，假設隨機森林中有3棵子決策樹，2棵子樹的分類結果是A類，1棵子樹的分類結果是B類，那麼隨機森林的分類結果就是A類。

與數據集的隨機選取類似，隨機森林中的子樹的每一個分裂過程並未用到所有的待選特徵，而是從所有的待選特徵中隨機選取一定的特徵，之後再在隨機選取的特徵中選取最優的特徵。這樣能夠使得隨機森林中的決策樹都能夠彼此不同，提升系統的多樣性，從而提升分類性能。

Boosting的每一次抽樣的樣本分布都是不一樣的。每一次迭代，都根據上一次迭代的結果，增加被錯誤分類的樣本的權重，使得模型能在之後的迭代中更加註意到難以分類的樣本，這是一個不斷學習的過程，也是一個不斷提升的過程，這也就是boosting思想的本質所在。迭代之後，將每次迭代的基分類器進行集成。那麼如何進行樣本權重的調整和分類器的集成是我們需要考慮的關鍵問題。

Gradient Boosting(GB)模型

思想就是迭代生成多個弱模型，將每個弱模型的結果相加。

Grandient Boosting模型演算法具有相似的步驟：
（1）初始化模型為常數值
（2）迭代生成基學習器（計算偽殘差-> 生成基學習器 -> 目標函數優化 -> 更新模型）

1. GBDT推導
GBDT是以決策樹CART為基學習器的GB演算法，是迭代樹。

如前面所述，gbdt模型可以認為是是由k個基模型組成的一個加法運算式：

其中F是指所有基模型組成的函數空間。

那麼一般化的損失函數是預測值 y^與 真實值y之間的關系，如我們前面的平方損失函數，那麼對於n個樣本來說，則可以寫成：

更一般的，我們知道一個好的模型，在偏差和方差上有一個較好的平衡，而演算法的損失函數正是代表了模型的偏差面，最小化損失函數，就相當於最小化模型的偏差，但同時我們也需要兼顧模型的方差，所以目標函數還包括抑制模型復雜度的正則項，因此目標函數可以寫成：

好的模型需要具備兩個基本要素：一是要有好的精度（即好的擬合程度），二是模型要盡可能的簡單（復雜的模型容易出現過擬合，並且更加不穩定）因此，我們構建的目標函數右邊第一項是模型的誤差項，第二項是正則化項（也就是模型復雜度的懲罰項）
常用的誤差項有平方誤差和邏輯斯蒂誤差，常見的懲罰項有l1，l2正則，l1正則是將模型各個元素進行求和，l2正則是對元素求平方。

每一次迭代，都在現有樹的基礎上，增加一棵樹去擬合前面樹的預測結果與真實值之間的殘差

目標函數如上圖，最後一行畫圈部分實際上就是預測值和真實值之間的殘差

先對訓練誤差進行展開：

xgboost則對代價函數進行了二階泰勒展開，同時用到了殘差平方和的一階和二階導數

再研究目標函數中的正則項：

樹的復雜度可以用樹的分支數目來衡量，樹的分支我們可以用葉子結點的數量來表示

那麼樹的復雜度式子：右邊第一項是葉子結點的數量T，第二項是樹的葉子結點權重w的l2正則化，正則化是為了防止葉子結點過多

此時，每一次迭代，相當於在原有模型中增加一棵樹，目標函數中，我們用wq（x）表示一棵樹，包括了樹的結構以及葉子結點的權重，w表示權重（反映預測的概率），q表示樣本所在的索引號（反映樹的結構）

將最終得到的目標函數對參數w求導，帶回目標函數，可知目標函數值由紅色方框部分決定：

因此，xgboost的迭代是以下圖中gain式子定義的指標選擇最優分割點的：

那麼如何得到優秀的組合樹呢？

一種辦法是貪心演算法，遍歷一個節點內的所有特徵，按照公式計算出按照每一個特徵分割的信息增益，找到信息增益最大的點進行樹的分割。增加的新葉子懲罰項對應了樹的剪枝，當gain小於某個閾值的時候，我們可以剪掉這個分割。但是這種辦法不適用於數據量大的時候，因此，我們需要運用近似演算法。

另一種方法：XGBoost在尋找splitpoint的時候，不會枚舉所有的特徵值，而會對特徵值進行聚合統計，按照 特徵值的密度分布 ，構造直方圖計算特徵值分布的面積，然後劃分分布形成若干個bucket(桶)，每個bucket的面積相同，將 bucket邊界上的特徵值 作為splitpoint的候選， 遍歷所有的候選分裂點 來找到最佳分裂點。

上圖近似演算法公式的解釋：將特徵k的特徵值進行排序，計算特徵值分布，rk（z）表示的是對於特徵k而言，其特徵值小於z的權重之和占總權重的比例，代表了這些特徵值的重要程度，我們按照這個比例計算公式，將特徵值分成若干個bucket，每個bucket的比例相同，選取這幾類特徵值的邊界作為劃分候選點，構成候選集；選擇候選集的條件是要使得相鄰的兩個候選分裂節點差值小於某個閾值。

綜合以上所述，我們可以得到xgboost相比於GBDT的創新之處：

『肆』 克魯斯卡爾演算法

克魯斯卡爾演算法：是一種用來尋找最小生成樹的演算法。在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構成迴路，則放棄，選取次小邊。
基本思想：先構造一個只含 n 個頂點、邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，即子圖中含有 n減1條邊為止。