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.生理性別 只有男跟女)
分割後會產生兩個不同方向的分支
- 名目屬性
名目屬性的資料沒有前後次序關係
可分割出不同值域的分支
每個分支的表示亦可以子集合的型態表示
- 順序屬性
- 連續性屬性
