AI筆記23 - Decision Tree

Tree Classifiers

這是ML裡面常用的一支方法。這牽涉到了information entroy的理論(?! 啥鬼東西)，從root開始建立tree classifier。

一開始所有的data set都放在root，然後greedy選擇目前能做出最好分類的feature，所謂做出最好分類稱為node purity，意即item可以明確歸類，不會有模糊不清的問題。接著所有的分類(decisions)就會被assign成leaves，在使用的過程就變成像是binary search tree那樣。


跟一般classificatier的目的不太一樣，一般來說classifier如下：

但是tree classifier並不找到此function mapping，而是提供一個tree model，也不需要input data x是一個d-dimensional vector R^d。

例子

這個例子是根據某些data來建立分類，不過slide實在太小了根本看不清楚:

可以看到在root先以"喜歡的語言"分類，但是接下來在不同的subtree分類條件又不一樣。

C4.5 algorithm

tree classifier的重點在怎麼衡量data中的成員的純度(homogeneinty)，其中一個方法稱為C4.5，這個給出的值如果在評估出純度低的時候(例如data中可以均分成不同的classess)，會是最大值。在純度很高的時候(data呈現單一class)會有最小值。