本文為大家介紹了機器學習中常用的決策樹算法以及相關術語，并基于天氣數據集進行決策樹算法（ID3、CART算法）實現過程的手動推導。

決策樹是最重要的機器學習算法之一，其可被用于分類和回歸問題。本文中，我們將介紹分類部分。

什么是決策樹？

決策樹（Decision Tree）是一個具有樹形結構的分類和預測工具，其中的每個內部節點表示對屬性的測試，每個分支代表測試的結果，并且每個葉子節點（終端節點）都有一個類別標簽。

上圖是一個小型決策樹。決策樹的一個重要優勢在于其高度的可解釋性。在上圖中，如果身高大于180厘米或身高小于180厘米且體重大于 80公斤為男性，否則為女性。你是否思考過我們如何得到類似于上圖的決策樹，下面我將使用天氣數據集對此進行解釋。

在此之前，我將解釋一下相關的術語。

熵（Entropy）

在機器學習中，熵是對正在處理的信息中隨機性的一種度量。熵越高，從該信息得出結論就越難。

信息增益（Information Gain）

信息增益可以定義為隨機變量或信號通過觀察另一個隨機變量所獲得的信息量，其可以被視為父節點的熵與子節點的加權平均熵的差。

基尼不純度（Gini Impurity）

基尼不純度是一種度量方法，如果數據是根據子集中標簽的分布被隨機標記的，則基尼不純度用來度量從集合中隨機選擇的數據被不正確標記的頻率。

基尼不純度的下界為0，如果數據集僅包含一個類別，那么基尼不純度則為0。

有很多算法可以構建決策樹。它們分別是：

1. CART（Classification and Regression Trees）：使用基尼不純度作為度量標準；

2. ID3（Iterative Dichotomiser 3）：使用熵和信息增益作為度量標準。

本文將介紹ID3算法。一旦理解ID3后，就可以輕松地使用CART實現相同的功能。

使用ID3算法進行分類

下面，我們基于天氣數據集來確定是否踢足球。

這里，自變量將決定因變量。其中，自變量是天氣預報（outlook），溫度（Temperature），濕度（Humidity）和風力（Wind），因變量是是否踢足球（Played football（yes/no））。

第一步，我們必須為決策樹找到父節點。為此，有以下步驟：

1. 計算類別變量（即因變量）的熵。

E（S） = -［（9/14）log（9/14） + （5/14）log（5/14）］ = 0.94

注意：這里通常將對數的底數設置為2。這里共有14個“yes/no”。其中有9個是“y

es”，5個“no”。在此基礎上，我們計算出了上面的概率。

從上面天氣預報（outlook）的數據中，我們可以輕松得到下表：

2. 現在我們需要計算加權平均熵，即我們已經計算出的每個特征的權重總和乘以概率。

E（S， outlook） = （5/14）*E（3，2） + （4/14）*E（4，0） + （5/14）*E（2，3） = （5/14）（-（3/5）log（3/5）-（2/5）log（2/5））+ （4/14）（0） + （5/14）（（2/5）log（2/5）-（3/5）log（3/5）） = 0.693

下一步是計算信息增益，它是上面我們計算的父節點的熵與加權平均熵之間的差。

IG（S， outlook） = 0.94 - 0.693 = 0.247

類似地，計算溫度（Temperature）、濕度（Humidity）和風力（Wind）的信息增益。

IG（S， Temperature） = 0.940 - 0.911 = 0.029

IG（S， Humidity） = 0.940 - 0.788 = 0.152

IG（S， Windy） = 0.940 - 0.8932 = 0.048

現在選擇具有最大熵增益的特征。天氣預報（outlook）特征是有最大熵增益的特征，因此它構成了決策樹的第一個節點（根節點）。

現在我們的數據如下所示：

由于在天氣預報（Outlook）特征為多云（overcast）時，因變量的結果僅僅有“Yes”這一種類別，因此我們可以將其設置為“Yes”。這意味著如果天氣預報（outlook）特征為多云（overcast），我們就可以踢足球。現在我們的決策樹如下所示。

接下來是在決策樹中找到下一個節點。我們在晴天（sunny）下找一個節點。我們需確定在溫度（Temperature）、濕度（Humidity）或風力（Wind）中誰有更高的信息增益。

計算父節點晴天（sunny）的熵E（sunny）：

E（sunny） = （-（3/5）log（3/5）-（2/5）log（2/5）） = 0.971

計算溫度（Temperature）的信息增益IG（sunny， Temperature）：

E（sunny， Temperature） = （2/5）*E（0，2） + （2/5）*E（1，1） + （1/5）*E（1，0）=2/5=0.4

現在計算信息增益：

IG（sunny， Temperature） = 0.971–0.4 =0.571

類似地，我們可以得到：

IG（sunny， Humidity） = 0.971

IG（sunny， Windy） = 0.020

這里的IG（sunny， Humidity）是最大值。因此，濕度（Humidity）是晴天（sunny）的子節點。

對于上表中的濕度（Humidity），如果濕度正常（normal），則因變量為“Yes”；如果濕度高（high），則因變量為“No”。與上面方法類似，我們可以找到下雨（Rain）的子節點。

注意：熵大于0的分支需要進一步拆分。

最終，我們可以得到如下的決策樹：

使用CART算法進行分類

使用CART進行分類的過程與ID3算法類似，但是其使用基尼不純度來替代熵作為度量標準。

1. 第一步我們需找到決策樹的根節點，為此需計算因變量的基尼不純度。

Gini（S） = 1 - ［（9/14）2 + （5/14）2］ = 0.4591

2. 下一步，我們將計算基尼增益（Gini Gain）。

首先，我們要找到天氣預報（Outlook）、溫度（Temperature）、濕度（Humidity）和風力（Wind）的加權平均基尼不純度。

首先考慮天氣預報（Outlook）：

Gini（S， outlook） = （5/14）gini（3，2） + （4/14）*gini（4，0）+ （5/14）*gini（2，3） = （5/14）（1 - （3/5）2 - （2/5）2） + （4/14）*0 + （5/14）（1 - （2/5）2 - （3/5）2）= 0.171+0+0.171 = 0.342

Gini gain （S， outlook） = 0.459 - 0.342 = 0.117

Gini gain （S， Temperature） = 0.459 - 0.4405 = 0.0185

Gini gain （S， Humidity） = 0.459 - 0.3674 = 0.0916

Gini gain（S， windy） = 0.459 - 0.4286 = 0.0304

我們需要選擇一個具有最高基尼增益的特征，天氣預報（outlook）的基尼增益最高，因此我們可以選擇它作為我們的根節點。

現在，你應該知道了如何進行接下來的操作，即重復我們在ID3算法中的相同步驟。

決策樹的優缺點

優點：

決策樹具有高度可解釋性；

需要很少的數據預處理；

適用于低延遲應用。

缺點：

很可能對噪聲數據產生過擬合。決策樹越深，由噪聲產生過擬合的可能性就越大。一種解決方案是對決策樹進行剪枝。
編輯：hfy