[Machine Learning] Decision tree

林罡北
林罡北
Jul 20, 2017 · 8 min read

Descision tree,中文我們叫做「決策樹」

網路上我找到比較清楚的解釋如下:

決策樹的主要功能,是藉由分類已知的Instance(實例, 即:訓練範例)來建立一個樹狀結構,並從中歸納出 Instance裡、類別欄位與其它欄位間的隱藏規則。

引用自國立聯合大學 資訊管理學系 機器學習課程 (陳士杰)

白話一點說就是一種藉由分類已知的data來建立一個樹狀結構(model),並從中歸納出 data中各feature(attribute)間的隱藏規則,並藉由歸納出來的樹狀結構規則(model)把資料分類到各個可能的對應類別進行預測

而決策樹的代表有ID3、C4.5 、C5.0、CHAID及CART


1.舉個例子:

spam email classification descision tree

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為建立決策樹的步驟)

  1. 資料設定:將原始資料分成兩組,一部 分為訓練資料,一部分為測試資料
  2. 從訓練資料中未被挑選過的屬性選出「分類能力最好的屬性」做為樹的內部節點
  3. 將內部節點的所有不同資料產生出對應的分支
  4. 重複2~4的步驟,直到滿足終止條件
  5. 剪枝:使用測試資料來進行決策樹修剪 將以上1~4步驟不斷重複進行,直到所 有的新產生節點都是樹葉節點 為止。

終止條件:

  • 全部的 data 都為同一類
  • 沒有更多的 attribute 可以進行分類
  • 沒有 data 可以進行分類

好的,演算法的流程我們大略知道了
那麼要怎麼選出「訓練資料內分類能力最好的屬性」呢?


4.How to select the splitting attribute?

「分類能力最好」意思就是選擇該屬性進行子結點分割之後,所產生的子結點的分類是最相近的,也就是說

分割結果中,若具有較高同質性(Homogeneous)類別的節點,則該分割結果愈佳

Example:

compare classification case

比較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 個子集合之資料個數佔總資料集合的比率 (權重)

Split by A attribute
Information Gain def.

而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.生理性別 只有男跟女)
分割後會產生兩個不同方向的分支

  • 名目屬性

名目屬性的資料沒有前後次序關係
可分割出不同值域的分支
每個分支的表示亦可以子集合的型態表示

  • 順序屬性
  • 連續性屬性

Reference

AI — Ch14 機器學習(2), 決策樹 Decision Tree

決策樹學習 — 國立聯合大學 資訊管理學系 陳士杰教師

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade