Descision tree,中文我們叫做「決策樹」
網路上我找到比較清楚的解釋如下:
決策樹的主要功能,是藉由分類已知的Instance(實例, 即:訓練範例)來建立一個樹狀結構,並從中歸納出 Instance裡、類別欄位與其它欄位間的隱藏規則。
白話一點說就是一種藉由分類已知的data來建立一個樹狀結構(model),並從中歸納出 data中各feature(attribute)間的隱藏規則,並藉由歸納出來的樹狀結構規則(model)把資料分類到各個可能的對應類別進行預測
而決策樹的代表有ID3、C4.5 、C5.0、CHAID及CART
1.舉個例子:

Decision tree 圖例:
每個內部節點表示一個評估欄位
每個分枝代表一個可能的欄位輸出結果
每個樹葉節點代表不同分類的類別標記
上面這棵樹是分類垃圾信的決策樹,會按照以下規則進行分類
- 如果email address是myEployer.com的話 就是「一般信件」
(上圖內文是「無聊時再讀的郵件」,簡單來說就是一般信件) - 如果email address是myEployer.com而且Email內有“hockey”這個字的話
會被歸類成「立即閱讀」的郵件 - 但沒有“hockey”的話就被歸類成「垃圾郵件」
2.決策樹種類 — Category of data
決策樹基本上有分兩種
- 分類樹:分析是當預計結果可能為離散類型(例如三個種類的花,輸贏等)使用的概念。可分割出不同值域的分支,每個分支的表示亦可以以子集合的型態表示。
- 回歸樹:分析是當局域結果可能為實數(例如房價,患者住院時間等)使用的概念。可採用離散化的方式,將資料分割成許多區間,但是仍需要保持資料的順序性。
3.決策樹是怎麼建立的呢? — How to build descision tree ?
基本的演算法:
(2~4為建立決策樹的步驟)
- 資料設定:將原始資料分成兩組,一部 分為訓練資料,一部分為測試資料
- 從訓練資料中未被挑選過的屬性選出「分類能力最好的屬性」做為樹的內部節點
- 將內部節點的所有不同資料產生出對應的分支
- 重複2~4的步驟,直到滿足終止條件
- 剪枝:使用測試資料來進行決策樹修剪 將以上1~4步驟不斷重複進行,直到所 有的新產生節點都是樹葉節點 為止。
終止條件:
- 全部的 data 都為同一類
- 沒有更多的 attribute 可以進行分類
- 沒有 data 可以進行分類
好的,演算法的流程我們大略知道了
那麼要怎麼選出「訓練資料內分類能力最好的屬性」呢?
4.How to select the splitting attribute?
「分類能力最好」意思就是選擇該屬性進行子結點分割之後,所產生的子結點的分類是最相近的,也就是說
分割結果中,若具有較高同質性(Homogeneous)類別的節點,則該分割結果愈佳
Example:

比較Case1與Case2哪種分類方式好,顯而易見的是使用Case2的分法能讓子結點內的資料具有較高同質性
那又該怎麼使用算出「最好的分類方法」呢?
這時候就要介紹一下Entropy與 Information Gain
4–1.Entropy(熵)
Entropy在物理上的意義是「亂度」
根據熱力學第二定律:一個封閉系統的紊亂程度(科學術語上稱之為亂度,Entropy),將會持續上升。所謂的封閉系統,即是指在這個系統內的物質與力場,僅能交互作用,而不受外在因素的影響,亂度增加則是指是物質的組成粒子趨向分散的狀態,每個粒子趨向於獨立自主、穩定的合理狀態,也是機率最高的狀態。如同桌面乾淨變成桌面亂七八糟,就是亂度增加。
舉一個例子,想像現在有一個隔成兩半的空箱子,可以將它視為封閉系統,左邊裝的是氧氣分子,右邊則是氦氣分子,現在把中間的隔板抽開,那會發生什麼情形?箱子裡面的氣體一定不會乖乖的待在原本的地方,因為兩邊物質的質量不同,所以會各自分散開到充滿整個箱子,兩邊的氣體混合在一起,直到成為一個穩定的狀態。而從原本兩邊各都是相同的分子,到現在分散在一個箱子裡,即是亂度增加。
引用自 熱力學第二定律| 科學Online — 科技部高瞻自然科學教學資源平台
而把Entropy應用在決策樹上
我個人的理解是Entropy代表著資訊的亂度
一群資料Entropy越大,代表該群資訊亂度越亂
(單純個人理解,有錯誤歡迎指正)
但不好意思,我無法清楚解釋為什麼是由以下這個公式做計算,以及這個公式所代表的物理意義,要請大家自己Google了
Entropy的定義如下:

pi為各個類別出現的機率
從定義中可以知道,Entropy是介於0 ~ 1的值,越靠近1代表越亂度越高,越靠近0代表越單純。
藉由下面這個範例,可以發現左邊的框框中的類別數量(2類)相較右邊(1類)來得多,也就代表資訊亂度較亂

4–2. Information Gain(資訊獲利)
上面介紹了Entropy,我們可以依據計算各種分類方式結果的亂度大小,藉此找出最佳的分類方式
假設屬性 A 中有 v 個不同值 {a1 , a2 ,…, av },而資料集合 D 會因為這 些不同值而產生(分割)出 v 個不同的資料子集合 {D1 , D2 ,…, Dv }
- Info(D):資料集合 D 整體的亂度
- Info(Dj):資料子集合 Dj 的亂度,其中 j = 1, 2, …, v

上圖代表的是:第 j 個子集合之資料個數佔總資料集合的比率 (權重)


而Information Gain就是 「分割前的資訊亂度」 減 「分割後的資訊亂度」
- Gain值愈大,表示屬性A內資料的凌亂程度愈小,用來分類資料會愈佳
- Gain值愈小,表示屬性A內資料的凌亂程度愈大,用來分類資料會愈差

4–3.屬性選擇指標
以上介紹的是基本的屬性選擇的判斷方法
這篇文章中我們主要是介紹Information Gain
但也還有其他方式能夠去計算使用哪種屬性,分類效果較佳
常用的屬性選擇指標有:
- 資訊獲利 (Information Gain) — ID3、C4.5、C5.0
- 吉尼係數 (Gini Index) — CART
- χ2獨立性檢定 — CHAID
5. Type of decision tree
- Classification Tree (離散類型)
E.g. 動物種類分類、郵件分類
- Regression Tree (連續性數值分類)
E.g. 房價分類、病患住院時間分類
- CART: Classification And Regression Tree
綜合 Classification Tree 與 Regression Tree
6.總結
首先一開始我們先對純度做量化,這就是Entropy的概念,如果Entropy越小,表示這個集合裡面的元素越單純。
之後我們利用Information gain來決定哪一種attribute比較好,算出利用attribute A來split dataset D,將這些partitions的entropy算出來加起來,可以知道分出來的partition純不純,再來計算attribute A的Information gain我們就可以知道以A來分類效果好不好。
不同類型資料屬性與處理方式介紹
- 二元屬性
二元屬性的資料只有兩個不同的值
(Ex.生理性別 只有男跟女)
分割後會產生兩個不同方向的分支
- 名目屬性
名目屬性的資料沒有前後次序關係
可分割出不同值域的分支
每個分支的表示亦可以子集合的型態表示
- 順序屬性
- 連續性屬性