Decision Tree - 充滿規則的算法

Decision Tree(決策樹)故名思義，用樹的圖樣去表達數個規則，根據那些規則來決定那些的結果，很多時候我們會把自己所考慮的因素決定，在腦裡建立一個決策的樹，當筆者在決定買一樣東西時，就例如近期很紅的Switch，會先考慮一下，自己是否真的需要和價錢這兩個決定性的誘因，那我就把自己的想法以決策樹表達出來之後，最後的決定還是先別進坑。

你可能會問這跟Machine Learning或者Data Mining有何關係，關係就大了，在這些課題上，會研究如何讓這棵決策樹由最開始的根(root node)，和自我生長成樹(tree node)和葉(Left node)。只要換上一幅較為有系統和正經的決策樹，就能知道這棵樹的結構，第一層的決定性的是對該貨品的需要性，如果真的需要的話，都不用考慮價錢了，所以到了第一層便停了。若果是不需要的活，倒是會看看價錢，便宜的話用作送禮也是不錯的選擇，貴的當然就不買了。其實這決策樹是由我的平日消費習慣而建立出來，也即是從每一次的消費行為中發掘這個決䇿模式，來決定會否大出血。

來到機器學習，Decision Tree亦一樣藉由學習已知的一組數據來學習和生長，其學習原理是把每一個特質(attribute)用作分成兩組數據，看看那一個特質會造成最大的Information Gain，從而決定利用該特質去作為分枝，也即是規則。這聽起來很抽象，回到剛才的例子，假設筆者有二十項購物紀錄，其中有12項是買了，8項的則是沒有買下來，所以在沒有任何機器或者資訊幫助之下，隨機地估計筆者會否買一件產品($P(buy)$)，概率為$12/20 = 0.6$，反之，沒有買的則是$8/20 = 1 - 0.6 = 0.4$。大家可以想像到只有約一半的機會能猜中，所以我們要想辦法的提高這個機率，才能準確地預測。原來筆者凡是一共8件是需要的，其中7件會買，1件會放棄；而12件不需要的，其中5件被買下，7件放棄。來到這裡，已知筆者需要某產品，買下的機會, $P(buy | needed)$會變成$7/8$；已知筆者不需要某產品，買下的機會, $P(buy | not.needed)$則是$5/12$。我們可以觀察到凡是有需要的物品，筆者很大機會就會把大買下來，因些借由"需要"這個因素(特質)，我們便能得到十分高的準確度，也造成很大的information gain。

要理解Information Gain，必先知道Information的定義，這裡的Information不是解作信息，而是一種純度(purity)的量度，筆者的購物紀錄很明顯混雜了買和不買這個群組的數據，純度也因些不會高，但若果用"需要"這個特質分成兩組紀錄，第一組的數據的純度大大提高，第二組沒有明顯的變化，為了量化purity，前人提供不少方法，包括：Entropy, Gini Index, Misclassification Rate等來量度一個群組裡的Impurity。在這裡，我們會用較多人用的Entropy作為例子：
$$Entropy = - P(buy)*log_2(P(buy)) - P(not.buy)*log_2(P(not.buy))$$
愈大的Entropy值，表示純度和Information愈低

Information Gain, IG(level), 正正形容純度的升降，正數的結果表示有所增長。
$IG(1) = I(0) - I(1)$

即是，最原始的紀錄的Entropy, I(0)為0.97，純度極低。至於分開後，第一組紀錄降至0.54，第二組紀錄卻不倒反升至0.98，綜合或者平均的information為$(0.54 * 8 + 0.98 * 12) / 20 = 0.80$，即是借由"需要"的這個因素，新的Information, I(1)降至0.8，換句話說，增長為$0.97 - 0.80 = 0.17$。

來到這裡，你已經學會如何評估Information Gain，只要把剛才的步驟套用在"價錢"這個因素，你會獲得其Information Gain，然後和"需要"的作比較，就當作"需要"的information gain是最大的，我們便把它作為分枝，那麼第一層的樹已經建立好了，可以進發第二層了！然後繼續剛才的動作，評估每一個特質，由於"需要"已被選擇了，所以"價錢"便自動當選做第二層的分枝，整棵樹的也因而建立好了！

由此，Decision Tree的Learning Algorithm可以概括為：
－計算每一個特質造成的Information Gain
－選出得到最大的Information Gain的特質，作為第一層的分枝
－再次計算其餘的特質和選出最佳的得質
－直到所有特質已成作分枝，或者觸發Stopping Rule(自定義)才停止

從剛才的例子，我們可以理解到Decision Tree能夠完成一些分類的工作，而這個模型的好處就是得出的結果相對容易解釋，從一組又一組的規則，可以看到，那個特質最影響目標變數。另外，若果Variable之間有非線性關係的話，都不會影響樹的性能，這跟線性和邏輯回歸不同，因為它並沒有作任何線性關係的假設。決策樹另一個賣點，便是不怕受到Outlier的干擾，佔少數的Outlier不會對Information Gain造成明顯的變化。有強的自然有弱，樹對數據中的小變化非常敏感，微少的變化也可能生成一個截然不同的樹。而另外一個問題是，當樹愈成長得愈複雜，愈旺盛，愈容易造成Overfitting，因此，需要一些Stopping Rule去停止生長，但當由的Criteria有很多的灰色地帶。決策的邊界平行於軸，以致邊界的形狀成梯級形，而不是一個Smooth的形狀。如果想知決策樹的應用，不妨看看筆者先前的文章。

Decision Tree在之後，亦在學術界被發掦光大，為了解決利用樹去處理一些Regression的預測問題，回歸樹因而發展出來，Information的定義亦改用為ANOVA，準確度用上Sum of Square Error作為指標，從而得出數字的結果。團結就是力量的 Random Forest也是Decision Tree的延伸，令Decision Tree的準確度更上一層樓。不用擔心，當你掌握好Decision Tree的基本原理，之後再多的變化也不怕。