機器學習演算法之決策樹（一）
標題：
決策樹的基本概念
決策樹演算法執行的基本流程
如何選擇最優的劃分方式
信息增益
信息熵
定義公式
來源與推導
應用方式
增益率
基尼係數
1. 決策樹的基本概念
決策樹（decision tree）是一種常見的機器學習方法，它基於樹形結構來對樣本進行決策，恰似人類面臨決策問題時大腦的相當自然的一種處理機制。
舉個例子，當我們要判斷一個西瓜是否是好瓜的時候，我們就要對「這是好瓜嗎？」這個問題進行一系列的判斷或「子決策」，像是先看它的顏色，然後看它的紋路，再試試它的觸感…等等等等，這個決策過程我們可以用圖形表示：
決策過程的最終結論將會對應我們的判斷結果，而決策過程中的每一次判定都是對某個屬性的「測試」，如「色澤=？」「根蒂=？」；每個測試的結果要麼導出最終結果，要麼導出下一個判定問題，並且，每一次判定都會在上一次決策所劃分好的範圍內進行判定，例如，在「色澤=青綠」之後判定「根蒂=？」就是在判斷青綠色的瓜的根蒂。
2. 決策樹演算法執行的基本流程
一般來說，一棵決策樹包含一個根節點，若干個內部節點和若干個葉節點。
決策樹學習的目的是為了產生一棵泛化能力強，即能夠處理未知示例能力強的決策樹。決策樹的基本流程遵循簡單且直觀的「分而治之」（divide-and-conquer）策略：
從上圖，我們可以看出，在決策樹的基本演算法中，有三種情況會導致遞歸返回：
3. 如何選擇最優劃分方式
決策樹的關鍵就在於如何選擇劃分方式。一般而言，隨著劃分過程不斷進行，我們希望決策樹的分支節點所包含的樣本儘可能屬於同一類別（舉西瓜例，即儘可能讓好瓜都和好瓜分一起，壞瓜都和壞瓜分一起），即節點的純度（purity）越來越高。
a. 信息增益
ID3決策樹採用的劃分方式是通過計算信息增益來得到想要的結果，在這裡，信息增益表示對於選擇的屬性進行一次劃分後的結果所提供的「信息」是否更加有利於我們區分樣本類別，它的計算方式如下：
假定離散屬性a有V個可能的取值{a1,a2...aV}，若使用a來對樣本集合D進行劃分，則會產生V個分支節點。其中，第v個分支節點包含了D中所有在屬性a上取值為av的樣本，我們這裡將其記為Dv。然後我們便可以根據信息熵的計算公式計算Dv的信息熵，再考慮到不同的分支節點所包含的樣本數不同，給分支節點賦予權重（即讓樣本數越多的分支節點能夠造成的影響越大）。於是，我們就可以計算出用屬性a對樣本集D進行劃分所得的信息增益(information gain):
一般而言，信息增益越大，則意味著用屬性a來進行劃分所獲得的「純度提升」就越大。因此我們可以用信息增益來對決策樹的劃分屬性進行選擇，從而使得選擇屬性的公式為：
即選擇能夠使信息增益達到最大的屬性。
i. 信息熵
要理解信息增益的概念，我們還需要從信息熵開始介紹。
A. 定義公式
信息熵(information entropy)是度量樣本集合純度最常用的一種指標。假定當前樣本集合D中第k類樣本所佔的比例為pk(k=1,2...,∣Y∣)（其中∣Y∣表示測試的最終結果數，以西瓜例子為例，就是「好瓜」和「壞瓜」，因此∣Y∣=2）則D的信息熵定義為：
注意：
B. 來源與推導
此處資料參考：[維基百科：熵 (資訊理論)](https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)
熵的概念起源於物理學，用於度量一個熱力學系統的無序度（混亂度）。而在信息世界，熵越高則表明能傳輸的信息越低（不確定性高），熵越低則表明傳輸的信息越多（不確定性低）。
要度量信息熵，我們先來看這樣一個例子：
如果我們有一枚硬幣，它出現正面和反面的機會均等，那麼，它的結果不外乎兩個：0（反面）或1（正面），這個時候，「拋一枚硬幣觀察正反面」這個事件的熵就是一比特（bit），因為結果只有兩個並且互相獨立。若進行n次獨立試驗，那麼它的熵則為n，因為這個事件的熵可以用長度為n的比特流來表示。
依據Boltzmann』s H-theorem，香農把隨機變數X的熵值H定義如下，其值域為{x1,...xn}：
其中l[X]表示隨機變數X的信息量，公式為：
這裡p(X)為隨機變數X的概率密度函數，對數部分除了取ln，也可以取log2,log10，這三個都是比較常見的取法，分別代表了信息熵的三個單位「nat」(對應對數底e)，「bit」（對應對數底2），「Hart」（對應對數底10）
並且由於信息量具有可加性，兩個隨機變數的概率密度函數相乘即為兩個隨機變數的信息量相加：
因此，要計算一個系統中有限樣本的信息熵時，可以採用公式：
ii. 應用方式
我們以西瓜書中提供的例子來介紹信息增益用於決策樹劃分的實際應用方式，該例子使用了西瓜數據集2.0：
這個數據集包含17個訓練樣本，並且∣Y∣=2。在決策學習開始時，我們先根據根節點所包含的D中的所有樣例（其中正例（好瓜）佔p1=8/17反例（壞瓜）占 p2=9/17計算根節點的信息熵：
然後，我們再計算當前屬性集合中每個屬性的信息熵。我們以屬性「色澤」為例，它分為3個可能的取值{青綠，烏黑，淺白}，然後根據這個屬性，我們對樣本進行三個劃分：
D1(色澤=青綠)，D2（色澤=烏黑），D3(色澤=淺白)
子集D1包含編號{1,4,6,10,13,17}，其中正例佔p1=3/6，反例佔p2=3/6，子集D2和D3以此類推，由此我們可以得到3個分支點的信息熵分別為：
然後我們就可以得到「色澤」的信息增益為：
類似的，我們得到其它信息熵的增益分別為：
我們可以觀察得到，紋理的信息增益是最大的，因此，我們選擇紋理作為下一步的劃分屬性。下面是根據「紋理」對根節點進行劃分的結果：
然後，決策樹學習演算法將對每個分支點進行下一步的劃分，我們以分支節點（「紋理」=清晰）為例，基於該節點的樣本集合D1計算出各屬性的信息增益：
我們可以看到，「根蒂」、「臍部」、「觸感」3個屬性都取得了最大的信息增益，因此，我們可以任選其中之一作為劃分屬性。類似的，我們對每個節點進行上述操作，最後可以得到決策樹：
b. 增益率
實際上，信息增益準則對可取值數目較多的屬性有所偏好（即屬性取值較多容易使信息增益偏大）。為什麼會出現這種情況？因為信息增益其實認定了一個死理就是如果根據某個特徵劃分後得到的數個樣本集純度越高那麼這個劃分方式的信息增益就越大，那麼理論上講，只要該特徵中包含的屬性越多，劃分後的每個樣本集合中的樣本數量就越傾向於更小，樣本越少樣本集合「純度」自然就更容易變高，一個極端的例子就是，如果我們把西瓜數據集中的「編號」也當成用於劃分的特徵，那麼它劃分後的每個樣本集都是100%純的，因為屬性「1」到「17」下的每個樣本集合都只包含一個樣本，這個樣本要麼是「好瓜」要麼是「壞瓜」，不存在不純變為「不好不壞瓜」的可能性，那麼這個特徵劃分後的信息增益自然就是其它特徵拍馬也趕不上的。
為了減少這種不利影響，C4.5決策樹演算法便引入了增益率。增益率定義為：
其中
IV(a)稱為屬性a的固有值（intrinsic value），又稱為分裂信息度量。屬性a的可能取值數目越多（V越大），IV(a)的值通常也會越大，我們可以把它看作是對於「屬性」過多的一個「懲罰」。
但是，需要注意的是，增益率準則又會對可取值數目較少的屬性有所偏好（可見追求二者的平衡是多麼麻煩的事情），因此，C4.5演算法採用了一個啟發式劃分方式：
c. 基尼係數
還有一種決策樹CART決策樹使用基尼係數(Gini index)來選擇劃分屬性。數據集D的純度可以用基尼值來度量：
直觀來說，Gini(D)反映了從數據集D中隨機抽取兩個樣本，其類別標記不一致的概率。因此，Gini(D)越小，則數據集D的純度越高。
屬性a的基尼指數定義為：
於是，我們在候選屬性集合A中，選擇那個使得劃分後基尼指數最小的屬性作為最優劃分屬性。
決策樹作為機器學習中最基礎的演算法之一，是一種相當具有特色的模型，並且，這可能是我們第一個接觸的能對非線性數據集進行分類的演算法，它獨特的結構能夠幫助數據工作者理解要處理的數據。決策樹的應用範圍相當廣，不過在現今，決策樹已經較少單獨作為一個模型整體被使用，因為決策樹的判斷始終是基於單個條件進行的，容易被人為改變特徵的方式攻擊（就像垃圾郵件的製造者會對某些垃圾郵件特徵進行規避），它更常會被用作某些比較複雜的演算法中的基石，例如集成學習中的隨機森林。我們現在所講到的決策樹其實也有相當多的缺陷，特別是容易過擬合，因此下一篇中我會介紹一下如何通過「剪枝」來通過減少過擬合從而優化我們的決策樹。
資料參考來源：
清華大學出版社-周志華《機器學習》
維基百科-信息熵
AI遇見機器學習
mltoai
TAG:機器學習 |