監督學習（二）：決策樹模型

  決策樹是機器學習模型較常用的一種方法，李航老師《統計學習方法》詳細的描述了決策樹的生成和剪枝，本文根據書中的内容，對決策樹進行了總結。

目錄

• 監督學習（二）：決策樹模型
• • 1.決策樹不确定性的度量方法
  • 2. 決策樹的特征篩選準則
  • 3. 決策函數的損失函數評估
  • 4. 決策樹最優模型的建構步驟
  • 5. 決策樹的優缺點分析

1.決策樹不确定性的度量方法

  （1）不确定性的了解

  下圖為事件A是否發生的機率分布，事件發生記為1，讨論事件A的不确定性。

  1）我們考慮一種極端的情況，若 p=1或 p=0，表示為事件A必定發生或事件A不可能發生，即不确定性為0。

  2) 若 p>1/2，即事件A發生的機率大于事件A不發生的機率，我們傾向于預測事件A是發生的；若p<1/2，即事件A不發生的機率小于事件A發生的機率，我們傾向于預測事件A是不發生的。若p=1/2，即事件A發生的機率等于事件A不發生的機率，我們無法作出預測，即事件A的不确定性達到最大，以緻于我們無從預測，或者可以了解成事件A太複雜了，複雜的我們隻能靠運氣去猜測事件A是否發生。

  （2）決策樹不确定性的度量方法

  本文用熵和基尼指數去衡量資料集的不确定性，假設資料集包含了K類，每個類的大小和比例分别為Di 和 pi，i = 1,2,…K。

  1）熵的不确定性度量方法

  在資訊論和機率論統計中，熵是表示随機變量不确定性的度量，令熵為H§，則：

  熵越大，資料集的不确定性就越大。

  2）基尼指數的不确定度量方法

  資料集的基尼指數定義為：

  基尼指數越大，資料集的不确定性越大。

2. 決策樹的特征篩選準則

  假設資料集A共有K個特征，記為xi，i=1,2,…K。資料集A的不确定性越大，則資料集A包含的資訊也越多。假設資料集A的資訊為H（A），經過特征xi篩選後的資訊為H(A|xi)，定義資訊增益g(A,xi)為兩者的內插補點，即：

  g(A,xi) = H(A) - H(A|xi)

  選擇使資料集A資訊增益最大的特征作為篩選特征，數學表示為：

  x = max( g(A,xi) ) = max( H(A) - H(A|xi) )

3. 決策函數的損失函數評估

  令決策樹的葉節點數為T，損失函數為：

  其中C(T)為決策樹的訓練誤差，決策樹模型用不确定性表示，不确定性越大，則訓練誤差亦越大。T表示決策樹的複雜度懲罰，α參數權衡訓練資料的訓練誤差與模型複雜度的關系，意義相當于正則化參數。

  考慮極端情況：當α趨于0的時候，最優決策樹模型的訓練誤差接近 0，模型處于過拟合；當α趨于無窮大的時候，最優決策樹模型是由根節點組成的單節點樹。

4. 決策樹最優模型的建構步驟

  将資料集A通過一定的比例劃分為訓練集和測試集。

  決策樹的損失函數：

  決策樹最優模型的建構步驟包括訓練階段和測試階段：

  訓練階段

  （1）最小化決策樹的不确定性值得到的生成模型，即 決策樹生成；

  （2）通過決策樹剪枝，得到不同的正則化參數α下的最優決策樹模型，即 決策樹剪枝。

  下面重點讨論訓練階段的決策樹生成步驟和決策樹剪枝步驟。

  決策樹生成步驟：

  （1） 根據決策樹的特征篩選準則，選擇資料集資訊增益最大的特征；

  （2） 重複第一個步驟，直到所有葉節點的不确定性為0 。

  決策樹剪枝步驟：

  （1） 将正則化參數α從小到大分成不同的區間

，對決策樹的非葉節點進行剪枝，令該節點為T，以該節點為根節點的子樹為Tt。

  （2） 當α滿足如下條件時：

  即節點為單節點樹的損失函數與子樹Tt的損失函數相等，而剪枝後的複雜度降低了，泛化性能較好，是以，對該節點進行剪枝。

  （3）周遊所有非葉節點，得到每個剪枝後的最優子樹與對應的α參數 。

  備注：決策樹生成和剪枝步驟隻給出大緻架構，具體請參考李航《統計學習方法》。

  測試階段：

  通過測試集評估不同α參數下的最優決策樹模型，選擇測試誤差最小的最優決策樹模型和相應的正則化參數α。

5. 決策樹的優缺點分析

  優點：

  算法簡單，模型具有很強的解釋性

  可以用于分類和回歸問題

  缺點：

  決策樹模型很容易出現過拟合現象，即訓練資料集的訓練誤差很小，測試資料集的測試誤差很大，且不同的訓練資料集建構的模型相差也很大。實際項目中，我們往往不是單獨使用決策樹模型，為了避免決策樹的過拟合，需對決策樹結合內建算法使用，如bagging算法和boosting算法。