About Decision Tree決策樹

決策樹 Decision Tree

根部 root：資料從根部的節點進入決策樹

子節點 child node：每一個節點代表「是」或「否」的問題點。答案代表前往下一個問題的前進路徑。

葉部節點 leaf node：決策過程一再重複，直到資料到達葉部節點為止

形式：二分式、三分式、 混合式

Attribute屬性選擇的準則：

• Information Gain(Entropy) :

• Information Gain Ratio :

• Gini Index(population diversity : measure the impurity of an attribute respect to classes

• MDL : Minimum Description Length
  
  選擇 ”最重要的屬性” 做為分隔變數
  　

• 分散度定義：一群物件分散的程度，能使"分散度"or"亂度" 降得最低，即為最佳分隔變數，有以下三種測量方法:

  • Min (P1, P2)

  • P1*P2

  • Entropy(亂度)-P1logP1-P2logP2

• 停止的條件(當Leaf Node滿足下列條件 即停止)

  • objects 皆為同一類

  • 沒有屬性可以降低"分散度"
    
    用lift來判定經由data mining所產生的績效

• Lift =p(class sample)/p(class population) 樣本/母體
  例如:當我們寄信件給整個母體中的 60%個顧客時所得到的回應是當中的80%
  則LIFT為: LIFT=0.8/0.6=1.3
  　

• Decision Tree 之錯誤率
  每個Leaf Node 之錯誤率先計算
  再將所有 Node加權 算出平均錯誤率

CART (Classification And Regression Tree)

1. 找出起始的分隔

2. 培養出整棵樹The building phase: constructs a "perfect" tree. The pruning phase: prevents "over-fitting"， but there is no single best pruning algorithm

3. 評估每個節點的錯誤率

4. 計算整個決策樹的錯誤率

5. 修剪決策樹

6. 確認入選的分支決策樹

7. 評估分支樹

8. 評估最佳的分支樹

9. 將代價列入考量

應用

• 電腦輔助診斷與判病結局

• 物理學上微粒判定

• 行銷上的預測

CHAID (Chi-xquared

1. 培養決策樹

2. 選擇分隔變數

3. 卡分分析檢驗

4. 重新分隔類別

5. 評鑑入選的分隔變數

6. 限制決策樹的成長

1R

1. 對於資料中的每一種屬性都建立一個1 level的決策樹，假若有n個屬性那我們就會有n個決策樹，

2. 從這些決策樹中取分類錯誤率最小，當作預測新資料類別的規則。

==============================

decision-tree induction

決策樹的推導(Decision tree induction)是一種使用樹狀架構的方法來做分類，結點代表不同的feature，樹枝為feature的值，而樹葉則是不同的分類類別(class label)。

這 種方式是先找一個最佳的特徵作為根節點，所有的資料以此根節點為判斷根據，進行分類，分類在每一個分支的資料再選出最佳的特徵作為根節點，再進行分類，形 式一棵子樹，如此的過程一直重複，直到在一個分支內的所有資料都屬於同一個類別，推導過程才算結束，這個最終的分支就會形式樹葉，裡面記載著該樹葉內的資 料所屬的類別，這樣就會形式一棵決策樹。

詳細的決策樹推導演算法如下：

樹的大小決定於分支的節點數，希望用最少的節點就可以分出結果，因此要如何才能選到最好的feature呢?原則上希望使分支後的每ㄧ個節點，就所要預測的變數而言，同質性越高越好(homogeneous)，可利用Information theory 的entropy理論來定義評估標準，同質性高者包含較少資訊，因此entropy比較小。

若ㄧ個節點包含S種預測值，且每ㄧ種預測值在該節點中的出現頻率為則該節點的entropy為

ㄧ個好的feature應該使得其subset的entropy最小，因此一個好的分類結點應該有最大的information gain，其定義為：

(split 前該結點的entropy) –(split 後各子結點的entropy的總和平均)，因為希望split後子結點的entropy的總和平均越小越好，所以gain 越大越好。