強而有力的樹-決策樹
2018/09/26

簡伯丞 | 國立中山大學資訊工程學系

191
 
 
 
決策樹被廣泛用於機器學習、模型預測等範疇,由於決策樹具有直觀、易於掌握等特性,這讓決策樹成為非常有力的工具。撰寫程式語言裡面的if-else就是一種類似決策樹的結構,如圖一所示,在一連串的if-else程式中有時令人感到暈頭轉向,但將每一個條件都當成一個節點來建立成一個樹狀結構之後,就可以很清楚明瞭的看到自己建立的架構。
 
 
透過決策樹,可以把左側巢狀的程式語言製作成右側淺顯易懂的樹狀圖(圖片來源:簡伯丞)
透過決策樹,可以把左側巢狀的程式語言製作成右側淺顯易懂的樹狀圖(圖片來源:簡伯丞)
 
決策樹,可以讓我們把想要預測或是歸納的資料透過對每個節點設定分類的規則生成一個樹狀圖,來輔助我們做決策與分析。例如:在AlphaGo的設計裡面,決策樹被用來搜尋最適合的落子位置,但每步棋有超過兩百多步的可能性,因此必須搭配特殊的演算法才能避免過度龐大的模型。決策樹在建立之後,還必須透過優化來移除一些被視為較差的分支;比如說:有一個節點的規則為「台灣的女性總統」,很明顯,這個分支下只有一個人符合該條件,所以這樣的節點並無法在一般的資料中達到良好的分類效果,移除這些樹枝就能進一步提升決策樹的預測能力與效率。
 
 
從該圖的決策樹中,我們可以判斷出溫度在120~125°C及濕度在5~7%時可以做出美味的披薩。(圖片來源:Medium/網址:https://medium.com/@yehjames)
從該圖的決策樹中,我們可以判斷出溫度在120~125°C及濕度在5~7%時可以做出美味的披薩。(圖片來源:Medium/網址:https://medium.com/@yehjames)
 
而提到能預測未知的決策樹即聯想到-馬可夫鏈(Markov Chain);在現實生活中,事件的發生很少是獨立的,俗話說「凡事必有因」,我們必須考慮到事件發生的前因後果才能準確分析,而馬可夫鏈的精神就是非獨立的條件機率,每一件事情發生的機率都跟上一個時間點的事件有關,根據這些規則我們可以建立一個馬可夫鏈模型來預測往後會發生的事件。舉例來說,有一個賭徒賭贏賺10元,賭輸虧10元,第n次賭博身上的錢則構成了一個馬可夫鏈,因為在n-1次是100元,第n次可能是110或是90元,狀態如圖二的S1~S3也是可以來回循環的。因此,馬可夫鏈可以說是結合機率的決策樹,也是AlphaGo用來預測對手下棋的方式之一。
 
 
一個簡單的馬可夫鏈,由S1, S2, S3三個狀態組成;右邊的矩陣則是將這些狀態之間的每一個機率做成一個馬可夫鏈的「轉移矩陣」。(圖片來源:演算法筆記/網址:http://www.csie.ntnu.edu.tw/~u91029/State2.html)
一個簡單的馬可夫鏈,由S1, S2, S3三個狀態組成;右邊的矩陣則是將這些狀態之間的每一個機率做成一個馬可夫鏈的「轉移矩陣」。(圖片來源:演算法筆記/網址:http://www.csie.ntnu.edu.tw/~u91029/State2.html)
 

決策樹概念簡單,並且具有強大的實用性。實務上在使用決策樹時,可依需求搭配適合的演算法進而增進效率。當然,決策樹的建立方法百百種,如何找到適合自己研究的建立方法才是最重要的。

 

副總編輯:國立中山大學資訊工程學系 陳坤志教授

總編輯:國立中山大學資訊工程學系 黃英哲教授

(本文由科技部補助「新媒體科普傳播實作計畫」執行團隊撰稿)