決策樹decision tree是一顆樹，用于分類和回歸問題，本文先介紹分類樹。決策樹可以認為是if-then規則的集合，或者定義在特征空間與類空間上的條件概率分布。

優點：可讀性、分類速度快。

分類決策樹是一種描述對實例進行分類的樹形結構。決策樹由結點和有向邊組成。結點有兩種類型：内部結點和葉結點。内部結點表示一個特征或屬性，葉結點表示一個類。

用決策樹分類時：從根結點開始，根據實例的某一特征将實例分配到對應子結點；每一個子結點對應着特征的某個取值。如此遞歸的對實例進行分配，直至達到葉結點。最後将實例分配到葉結點所在的類中。

決策樹的學習：

目标：根據給定訓練集構建一個決策樹模型，使它能夠對實例進行正确的分類。

本質：從訓練數據集歸納出一組分類規則，得到一顆與訓練數據集矛盾較少的一棵樹；或者由訓練數據集選擇一個最優的條件概率模型。是一個特征空間劃分的問題。

決策樹的學習主要由3大塊組成：

1. 特征選擇
2. 決策樹生成
3. 剪枝

選擇對訓練數據有分類能力的特征，準則：信息增益或信息增益比。

分類能力：訓練數據的類别在該特征下各子集的分類純度越高代表分類能力越強。

• 信息增益

經驗熵=随機變量不确定性的度量，不确定性越大，熵越大

條件熵=已知随機變量X的條件下随機變量Y的不确定性

信息增益=經驗熵-條件熵，表示得知特征X的信息，使得Y的不确定性減少的程度

信息增益取決于特征，信息增益大的特征具有更強的分類能力。

經驗熵

條件熵

信息增益

• 信息增益比

信息增益有個缺點是某個特征的取值越多其條件熵越小，信息增益越大。例如對于特征 ID每個ID都是唯一的，ID中隻有一個樣本，其條件熵為0。信息增益比可以解決這一問題。

根據信息增益/信息增益比最大的方法找到根結點對應的特征。

決策樹的生成

• ID3算法：在決策樹各個結點上應用信息增益準則選擇特征，遞歸地構建決策樹。

停止條件：當信息增益小于阈值；沒有更多特征；所有結點都是同一類

算法步驟：

ID3算法隻有樹的生成，所以該算法産生的樹容易過拟合。

• C4.5算法

C4.5與ID3唯一的區别就是用信息增益比代替信息增益

決策樹的剪枝

上述算法都是基于局部最優解得到決策樹，并未考慮全局損失函數。這樣生成的樹對訓練數據拟合很好，但是生成的樹過于複雜往往産生過拟合。因此，全局損失函數需考慮樹的複雜度，簡化生成的決策樹。

決策樹的剪枝就是将子樹剪掉，用父節點替代原先的子結點，從而簡化決策樹。

操作手段有了，還需要确定決定是否剪枝的标準，如果剪掉的子樹不會增加很多熵值，同時會大大減少結點個數，則選擇剪枝。也就是說我們需要在熵值增加和結點數減少之間進行權衡，轉化為公式：

剪枝算法：

輸入：決策樹T、參數alpha

輸出：修剪後的子樹t

1)計算每個結點的經驗熵

2）遞歸地從樹的葉結點向上回縮，如果子樹的損失函數更小則得到子樹。

3）重複2）直到不能繼續為止。

CART算法

CART是一種分類回歸樹，是二叉樹，内部結點的特征由是和否構成。CART回歸樹用平方誤差最小化準則，對分類數用基尼系數最小化準則進行特征選擇。

• 回歸樹的生成

1）回歸樹劃分後顯然用該特征空間劃分上的y的平均值作為結點的預測值

2）劃分後的預測誤差用平方誤差來抽象

3）對特征和取值遍曆選擇預測誤差最小的特征作為切分變量、某個取值作為切分變量

4）依次用上述方法将輸入空間劃分為兩個區域，生成一棵回歸樹。

• 分類數的生成

1）損失函數用基尼系數代替熵，樣本集合的不确定性越大、基尼系數越大、熵越大。因此本優化問題為找到基尼系數最小的特征和取值。

2）二叉樹：特征一次分為是否為某個取值

3）停止條件：結點中樣本個數小于阈值；基尼系數小于阈值==基本屬于一類；沒有更多特征

• CART剪枝

整體思路：将子樹從下往上依次剪枝得到子樹序列，然後通過交叉驗證法在驗證數據集上得到損失函數（平方誤差或基尼系數）最小的子樹。子數确定後最優的alpha也确定了。

alpha越小子樹結點數的權重越小，樹越大；alpha越大決策樹越簡單。

1）子樹序列對應着alpha序列，從下往上剪形成子樹序列，對應着alpha從小到大。

對于某個内部結點，剪枝與否的損失函數對比如下：

2）對一顆決策樹内部每一結點計算g(t)，按g(t)從小到大排序子樹直至根節點，alpha達到某一個g(t)值意味着對該内部結點剪枝。

3）算法

模型優缺點

1）優點：

• 簡單易懂，易于解釋。 可視化。
• 幾乎不需要數據預處理。 其他技術通常需要數據歸一化，需要創建虛拟變量和删除空白值。 但是請注意，此模塊不支持缺失值。缺失值要處理。
• 使用樹(即預測數據)的成本是用于訓練樹的數據點數量的對數。
• 能夠處理數值和分類數據。 然而，scikit-learn實現目前還不支持分類變量。
• 能夠處理多輸出問題。
• 使用白盒模型。 如果給定的情況在一個模型中是可觀察到的，那麼對這個條件的解釋很容易用布爾邏輯來解釋。 相比之下，在黑盒模型中(例如，在人工神經網絡中)，結果可能更難解釋。
• 可以使用統計測試來驗證模型。 這使得解釋模型的可靠性成為可能。
• 即使生成數據的真實模型在某種程度上違反了它的假設，它也能很好地執行。

2）缺點：

• 決策樹學習者可以創建過于複雜的樹，不能很好地概括數據。 這叫做過拟合。 為了避免這個問題，需要使用修剪、設置葉子節點所需的最小樣本數量或設置樹的最大深度等機制。
• 決策樹可能是不穩定的，因為數據中的小變化可能導緻生成完全不同的樹。 通過在集成學習中使用決策樹，可以緩解這個問題。
• 決策樹的預測既不是平滑的，也不是連續的，而是如上圖所示的分段常數近似。 因此，他們不擅長外推
• 學習最優決策樹的問題是已知的np -完全在幾個方面的最優性，甚至簡單的概念。 因此，實際的決策樹學習算法是基于啟發式算法，如貪婪算法，在每個節點上做出局部最優決策。 這種算法不能保證返回全局最優決策樹。 這可以通過在集成學習器中訓練多棵樹來緩解，其中特征和樣本是随機采樣的替換。
• 有些概念很難學習，因為決策樹不容易表達它們，比如異或、奇偶校驗或多路複用問題。
• 如果某些類占主導地位，決策樹學習者會創建有偏差的樹。 因此，建議在拟合決策樹之前平衡數據集。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部