[Machine Learning] Decision tree

林罡北
8 min readJul 20, 2017

--

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

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

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

林罡北
林罡北

Written by 林罡北

Founder of TroublesLab, F2E & Web/App Developer

No responses yet

Write a response