決策樹學習

統計學，數據挖掘和機器學習中的決策樹訓練，使用決策樹作為預測模型來預測樣本的類標。這種決策樹也稱作分類樹或回歸樹。在這些樹的結構里，葉子節點給出類標而內部節點代表某個屬性。

在決策分析中，一棵決策樹可以明確地表達決策的過程。在數據挖掘中，一棵決策樹表達的是數據而不是決策。

基本介紹

• 中文名：決策樹學習
• 領域：數據挖掘、機器學習

推廣

在數據挖掘中決策樹訓練是一個常用的方法。目標是創建一個模型來預測樣本的目標值。例如右圖。每個內部節點 對應於一個輸入屬性，子節點代表父節點的屬性的可能取值。每個葉子節點代表輸入屬性得到的可能輸出值。

一個描述鐵達尼號上乘客生存的決策樹

一棵樹的訓練過程為：根據一個指標，分裂訓練集為幾個子集。這個過程不斷的在產生的子集裡重複遞歸進行，即遞歸分割。當一個訓練子集的類標都相同時 遞歸停止。這種決策樹的自頂向下歸納 (TDITD) 是貪心算法的一種, 也是當前為止最為常用的一種訓練方法。

數據以如下方式表示:

其中Y是目標值，向量x由這些屬性構成, x1, x2, x3 等等，用來得到目標值。

決策樹的類型

在數據挖掘中，決策樹主要有兩種類型:

• 分類樹的輸出是樣本的類標。
  
• 回歸樹的輸出是一個實數 (例如房子的價格，病人待在醫院的時間等)。
  

術語分類和回歸樹 (CART) 包含了上述兩種決策樹, 最先由Breiman 等提出。分類樹和回歸樹有些共同點和不同點—例如處理在何處分裂的問題。

有些集成的方法產生多棵樹：

• 裝袋算法（Bagging）, 是一個早期的集成方法，用有放回抽樣法來訓練多棵決策樹，最終結果用投票法產生。
  
• 隨機森林（Random Forest） 使用多棵決策樹來改進分類性能。
  
• 提升樹（Boosting Tree） 可以用來做回歸分析和分類決策。
  
• 旋轉森林（Rotation forest） – 每棵樹的訓練首先使用主元分析法 (PCA)。
  

還有其他很多決策樹算法，常見的有:

• ID3算法
  
• C4.5算法
  
• CHi-squared Automatic Interaction Detector (CHAID)， 在生成樹的過程中用多層分裂。
  
• MARS可以更好的處理數值型數據。
  

模型表達式

構建決策樹時通常採用自上而下的方法，在每一步選擇一個最好的屬性來分裂。"最好" 的定義是使得子節點中的訓練集儘量的純。不同的算法使用不同的指標來定義"最好"。本部分介紹一些最常見的指標。

基尼不純度指標

在CART算法中， 基尼不純度表示一個隨機選中的樣本在子集中被分錯的可能性。基尼不純度為這個樣本被選中的機率乘以它被分錯的機率。當一個節點中所有樣本都是一個類時，基尼不純度為零。

假設y的可能取值為{1, 2, ..., m},令是樣本被賦予i的機率，則基尼指數可以通過如下計算：

信息增益

ID3，C4.5 和C5.0決策樹的生成使用信息增益。信息增益 是基於資訊理論中信息熵的理論。

決策樹的優點

與其他的數據挖掘算法相比，決策樹有許多優點:

• 易於理解和解釋 人們很容易理解決策樹的意義。
  
• 只需很少的數據準備 其他技術往往需要數據歸一化。
  
• 即可以處理數值型數據也可以處理類別型 數據。其他技術往往只能處理一種數據類型。例如關聯規則只能處理類別型的而神經網路只能處理數值型的數據。
  
• 使用白箱 模型. 輸出結果容易通過模型的結構來解釋。而神經網路是黑箱模型，很難解釋輸出的結果。
  
• 可以通過測試集來驗證模型的性能 。可以考慮模型的穩定性。
  
• 強健控制. 對噪聲處理有好的強健性。
  
• 可以很好的處理大規模數據 。
  

缺點

• 訓練一棵最優的決策樹是一個完全NP問題。因此, 實際套用時決策樹的訓練採用啟發式搜尋算法例如 貪心算法 來達到局部最優。這樣的算法沒辦法得到最優的決策樹。
  
• 決策樹創建的過度複雜會導致無法很好的預測訓練集之外的數據。這稱作過擬合。 剪枝機制可以避免這種問題。
  
• 有些問題決策樹沒辦法很好的解決,例如 異或問題。解決這種問題的時候，決策樹會變得過大。 要解決這種問題，只能改變問題的領域或者使用其他更為耗時的學習算法 (例如統計關係學習 或者 歸納邏輯編程).
  
• 對那些有類別型屬性的數據, 信息增益 會有一定的偏置。
  

延伸

決策圖

在決策樹中, 從根節點到葉節點的路徑採用匯合或與。 而在決策圖中, 可以採用 最小訊息長度 (MML)來匯合兩條或多條路徑。

用演化算法來搜尋

演化算法可以用來避免局部最優的問題。