Deep learning - Probability and Information theories VI
Application:Decision tree(決策樹) and random forest(隨機森林)
- 廣泛使用的一種歸納推理演算法
- 對於干擾直相當敏感
Impurity measure(亂度的測量)
argmaxj,v(Impurity(Xparent)−Impurity(Xleft,Xright))
亂度為熵的非正式定義
- 給定一組標記過的樣本資料組
- X={(x(i),y(i))}Ni=1
- x 為一個向量, j–th 維度該樣本的一個特徵(Attribute)
- 向量元素 xj 代表著一個該資料對應該特徵的一個狀態(State of j-th attribute)
- y 為 x 經過一個隨機變數 X 所對應的一個標記狀態
- 由於隨機變數 X 是人決定的,所以可以將這個對應稱為一種標記
- 欲經一樹狀函數 f(規則),將樣本的特徵狀態 x(i) 可以映射到人為標記狀態 y(i) (Label)
- f(x(i))=y(i)
![]()
- Xparent 為決策樹裡其中一個父節點
- 代表一組子樣本資料
- Xparent⊆X
- Xleft、Xright 為對應於上述父節點的左右子節點
- 代表一組子樣本資料
- Xleft⊆XXright⊆X
- Xleft+Xright=Xparent
Impurity(Xparent)=H[Y~Empirical(Xparent)]
- 「父節點的亂度」為 Y~Empirical(Xparent) 的熵
- PY(y)=Xparent中的被標記比例為y的比例
Impurity(Xleft,Xright)=∑i=left,right|X(i)||Xparent|H[Y~Empirical(X(i))]
- |X(i)| 為該樣本資料組的數量
- 「子節點的亂度」為左右子點對 Y~Empirical(X(i)) 的熵,並依比對父點的資料量比例加總
- 「子節點的亂度」≦「父節點的亂度」
- 目標是找到一種父節點的資料分類方法,將「子節點的亂度」最小化
Impurity(Xparent)−Impurity(Xleft,Xright) 稱作「資訊獲利」(Information gain)
- 越大代表「子節點的亂度」越小
- 資料分類方法的一種效能評鑑
(j,v) :斷點
在 x 還沒判斷的特徵空間中找到 j–th 維度,選擇一個定值 v
節點中的資料必須符合 Rule 的規則
將父節點 Xparent={(x(i),y(i)):Rule} 分支為兩個節點
- Xleft={(x(i),y(i)):Rule∪{x(i)j<v}}
- Xright={(x(i),y(i)):Rule∪{x(i)j≥v}}

Decision tree
Training a decision tree
- 建構一根節點 {(x(i),y(i)):Rule=∅}
- 節點中的資料必須符合 Rule 的規則
- 最開始不設定規則 $$,所以此點資料等於 X
- 往下分支兩個子節點 Xleft、Xright
- 以 argmaxj,v(Impurity(Xparent)−Impurity(Xleft,Xright)) 為依據,找到符合的 Rule
- 對其子節點遞迴此步驟,直到該節點的亂度等於 0(Pure),也就是其節點的人為標記狀態全部相等
Random forests
隨機森林為多個決策樹所構成
- 決策樹模型可能會被訓練得非常高
- 越高的節點其 Rule 會越嚴格
- 在訓練資料樣本可以判斷很好,但是在測試資料樣本最壞可能完全無法利用
- 解決此問題讓決策樹可以更廣泛應用(Generalizability)
- 剪枝(Pruning):限制決策樹的高度,但可能葉節點中的標記狀態不會全部相等
- 隨機森林:多棵剪枝過的決策樹之集成
- 機器學習中的「集成」(Ensemble)
- 一般機器學習演算法只使用單一模型來學習,可能在該樣本之外會無法利用
- 結合多個弱機器學習以建構一個強穩的模型,避免過適現象(Overfit)的發生
Training a random forest
- 取得一個自助樣本(Bootstrap sample)
- 自助樣本:在原始的訓練資料集中隨機挑選 M 個樣本(挑選過可以重新再挑選)
- 使用自助養本,訓練過程中
- 隨機挑選 K 個特徵
- 在該範圍找到最好的斷點 (j,v) 來分支
- 重複第一第二步得到 T 個決策樹
- 由 T 個決策樹以多數決(Majority vote)來判斷測試資料樣本
- 每個決策樹對樣本有不同的見解,取其多數以判斷
- 隨機森林的訓練與決策樹的訓練有些許的不同
- 第一步與第二之一步

