點擊上方關注，All in AI中國
作者：Georgios Drakos
決策樹誕生於70多年前，如今已經成為最強大的機器學習工具之一。決策樹的主要優點是一種"白盒"方法。這意味著人們可以輕鬆地解釋他們的決策，而神經網絡的複雜性通常過高。
它也可以表示為if-then規則集，以提高可讀性。本文的目的是介紹決策樹學習的基本理論基礎，並提出ID3（迭代二分法3）算法。
決策樹用於分類和迴歸問題，在這裡我們將討論分類問題。
決策樹是什麼？
決策樹就像一棵倒置的樹，其根位於頂部。決策樹通過將樹從樹根到樹葉節點（決策）向下排序來對實例進行分類，該節點提供實例的分類。決策樹中的每個節點都指定了對實例的某些屬性的測試，並且從該節點下降的每個分支對應於該屬性的一個可能值。
舉例說明一學習決策樹。通過樹對其分類，然後返回與該葉相關分類(是或否)。這棵樹根據是否適合打網球來劃
例如，實例（Outlook = Sunny，Temperature = Hot，Humidity = High，Wind = Strong）將被歸類為否定實例（即，樹預測PlayTennis = no）。
是什麼讓它與眾不同？
- 它與其他工具不同，因為它可以直觀地工作，即一個接一個地做出決定。
- 非參數：快速高效。
那麼如何構建呢？
有幾種算法可以構建決策樹，其中一些是：
- CART（分類和迴歸樹）→使用基尼指數（分類）作為指標。
- ID3（迭代二分法3）→使用熵功能和信息增益指標。
在此，我們將重點關注ID3算法。
什麼是ID3算法？
ID3從"應該在樹根處測試哪個屬性？"這個問題開始。為了回答這個問題，每個實例屬性都使用稱為信息增益的統計測試進行評估，該測試測量給定屬性根據訓練樣例分離訓練樣例的程度，並對他們的目標進行分類。選擇最佳屬性並將其用作樹的根節點處的測試。
對每個分支重複此過程。這意味著我們在可能的決策樹空間中執行自上而下的貪婪搜索，其中算法從不回溯到重新考慮先前的選擇。
什麼是熵？
熵是信息理論中常用的一種度量，它表徵了實例的同質性。如果目標屬性可以採用c個不同的值，那麼相對於該c-分類的S的熵定義為：
其中pi是屬於i類的S的比例。另請注意，如果目標屬性可以採用c個可能的值，則熵可以與log2（c）一樣大。
布爾目標分類的示例：
假設S是14個例子的集合，包括9個正例和5個負例 [9 +，5-]（c = 2）。然後S的熵是：
請注意，如果S的所有成員屬於同一個類，則熵為0。如果所有成員都是正數（p⊕= 1），那麼p⊖= 0，並且無法提取新信息。當p⊕= 1時，接收方知道所繪製的例子是正例，因此不需要發送消息，並且熵為零。另一方面，當p⊕=p⊖=0.5時，它會實現最大化。
相對於布爾分類的熵函數，作為正例的比例p+將在0和1之間變化。
什麼是信息增益？
信息增益只是根據此屬性對示例進行分區所導致的熵的預期減少。更確切地說，屬性A的信息增益Gain（S，A）相對於示例集合S被定義為：
Gain（S，A）是關於目標函數值的信息，給定一些其他屬性A的值。
示例：假設S是由包含Wind的屬性描述的訓練示例日的集合，其可以具有Weak值或Strong值。S包含9個正例和5個負例一共14個例子，也就是[9+，5-]。假設6個正例和2個負例具有Wind = Weak，其餘的例子具有Wind=Strong。由於通過屬性Wind對原始14個示例進行排序而導致的信息增益可以被計算為：
信息增益正是ID3用於在生長樹的每個步驟中選擇最佳屬性的度量。
相對於目標分類，溼度提供了比風更大的信息增益。這裡E代表熵，S代表原始集合的例子。給定最初收集的9個正的和5個負的例子，[9+，5 -]，根據它們的溼度對它們進行排序，會產生[3+，4 -](溼度=高)和[6+，1 -](溼度=正常)的集合。此分區獲得的信息為.151，而屬性Wind的增益僅為.048。
應用ID3算法的一個說明性示例
在此示例中，目標屬性為打網球，其值為yes或no。必須通過考慮屬性（Outlook, Temperature, Humidity, Wind）來預測。
訓練目標概念打網球的示例
該算法的第一步是選擇根節點的屬性。ID3確定每個屬性的信息增益，並選擇信息增益最高的那個。
因此，選擇Outlook作為根節點的決策屬性，並且在根目錄下為每個可能的值（即Sunny，Overcast和Rain）創建分支。請注意，Overcast所有樣例只有正例，因此成為目標分類為Yes的葉結點（也稱葉子節點）。因此，決策樹的這個節點稱為葉節點。相反，對於Outlook = Sunny和Outlook = Rain，我們有非零熵，決策樹將在這些節點下面進一步闡述。
選擇新屬性和劃分訓練示例的過程僅考慮與該節點相關聯的訓練示例。此外，排除了在樹中較高的屬性，因此任何給定的屬性最多隻能沿決策樹的任何路徑出現一次。對於每個新葉節點都要繼續進行這個過程，直到滿足兩個條件中的任何一個：（1）沿著該路徑已經包括通過樹的每個屬性，或者（2）熵為零。
由ID3的第一步產生的部分學習的決策樹。訓練示例被分類到相應的後代節點。
我們可以觀察到ID3的偏愛：
- 較短的樹將超越較長的樹。
- 放置高信息的樹獲得靠近根的屬性。
結論
最終得出的結論是：
- 學習樹可以表示為if-then規則集
- 信息增益測量是指導ID3爬山搜索的評估功能。
- ID3通過從根向下增長決策樹來推斷決策樹，並貪婪地為添加到樹中的每個新決策分支選擇下一個最佳屬性。
- ID3包括對較小決策樹的偏好，為了對可用的訓練樣例進行分類，只需要根據需要增大決策樹。
閱讀更多 AI中國 的文章
