機器學習筆記-決策樹跟分類規則

決策樹(Decision Tree)

決策樹學習，建立一顆樹結構的模型。此模型由一系列邏輯決策構成。在此結構中決策點代表某個屬性上的決策，分支表示決策選擇項，樹的葉子節點是一系列聯合決策的結論。

決策樹通過分而治之（Divide and conquer）方式-遞歸劃分（recurisive partitioning）來建立。在這個建立過程中，我們從代表所有數據的根節點出發，選擇通向目標分類的特性把樣本拆分成不同的組,如此直至觸及停止標準。有幾類停止標準, 節點上的所有或幾乎所有的樣本都是屬于同一類;沒有特征能對樣本進行繼續分類了;樹已經觸及預定義的大小限制.

建立決策樹面對的第一個挑戰就是從哪個特征著手進行切分。如果我們切分出來的分段數據僅包含一類數據，那我們說這個“一致”（Pure）的。 

我們用熵來度量一個集合的無序程度。度量無序程度還可以用基尼不純度（Gini impurity）。這里我先學習了熵。

             c 

    Entropy(S) = Σ  -Pi log2(Pi)

             i=1

熵計算公式中各個部分的意義如下。在一個分段S上有c個類層次。Pi是第i個類層次的占比。

  有了一致性衡量的熵，我們就可以來解決如何拆分樣本。這里就得說到信息增益（Information Gain）

    InfoGain(F) = Entropy(S1) - Entropy(S2)

信息增益就是樣本拆分前后的熵的差值。拆分后的熵的計算公式如下：

                   n 

    Entropy(S) = Σ  wi Entropy(Pi)

              i=1

這個就是拆分后各部分的熵Entropy(Pi)如這一部分在總樣本中所占比的乘積的總和。

信息增益越高表明分拆越有效。

決策樹算法：

a. C5.0

  在C5.0里我們用熵（entropy）來衡量一致性。熵為0則表示樣本是完全同質的。熵值越高則表示越無序。 

當樹膨脹到一定大小后會導致決策過于特殊化, 得出的模型過擬合?？朔爽F象的做法有pre-pruning跟post-pruning。 pre-pruning就是當決策點達到某個量時或者決策節點中只包含少量樣本是就停止樹的構建。pre-pruning無法預知會不會遺漏掉某些細微的但是有相當重要的模式。

pre-pruning之外的另一個方法就是post-pruning。當樹構建的相當大后，我們用某些基于誤碼率的修剪標準來修建樹。這個方式通常比pre-pruning更有效。

在post-pruning的過程有連個可能的處理，一個是子樹提升（subtree raising）,還有一個是子樹置換（subtree replacement）

C5.0很容易通過調整訓練選項來在過擬合跟欠擬合間達成平衡。

C5.0比C4.5增加了自適應增強（adaptive boosting）.前一個分類器分錯的樣本會被用來訓練下一個分類器。AdaBoost方法對于噪聲數據和異常數據很敏感。但在一些問題中，AdaBoost方法相對于大多數其它學習算法而言，不會很容易出現過擬合現象。AdaBoost方法中使用的分類器可能很弱（比如出現很大錯誤率），但只要它的分類效果比隨機好一點（比如兩類問題分類錯誤率略小于0.5），就能夠改善最終得到的模型。而錯誤率高于隨機分類器的弱分類器也是有用的，因為在最終得到的多個分類器的線性組合中，可以給它們賦予負系數，同樣也能提升分類效果。

除了自適應增強，C5.0還可以提供一個成本矩陣（cost matrix）來修正模型。

http://sjchen.im.nuu.edu.tw/MachineLearning/final/CLS_DT.pdf

分類規則（classification rule）

分類規則表示的是if-else形式的知識,規則由先導（antecedent）跟后繼（consequence）構成一個假設。

One rule算法

RIPPER算法（Repeated Incremental Pruning to Produce Error Reduction）

發展

修剪

優化

從決策樹到規則