本文為大家介紹了機(jī)器學(xué)習(xí)中常用的決策樹算法以及相關(guān)術(shù)語，并基于天氣數(shù)據(jù)集進(jìn)行決策樹算法（ID3、CART算法）實(shí)現(xiàn)過程的手動推導(dǎo)。

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

什么是決策樹？

決策樹（Decision Tree）是一個(gè)具有樹形結(jié)構(gòu)的分類和預(yù)測工具，其中的每個(gè)內(nèi)部節(jié)點(diǎn)表示對屬性的測試，每個(gè)分支代表測試的結(jié)果，并且每個(gè)葉子節(jié)點(diǎn)（終端節(jié)點(diǎn)）都有一個(gè)類別標(biāo)簽。

上圖是一個(gè)小型決策樹。決策樹的一個(gè)重要優(yōu)勢在于其高度的可解釋性。在上圖中，如果身高大于180厘米或身高小于180厘米且體重大于 80公斤為男性，否則為女性。你是否思考過我們?nèi)绾蔚玫筋愃朴谏蠄D的決策樹，下面我將使用天氣數(shù)據(jù)集對此進(jìn)行解釋。

在此之前，我將解釋一下相關(guān)的術(shù)語。

熵（Entropy）

在機(jī)器學(xué)習(xí)中，熵是對正在處理的信息中隨機(jī)性的一種度量。熵越高，從該信息得出結(jié)論就越難。

信息增益（Information Gain）

信息增益可以定義為隨機(jī)變量或信號通過觀察另一個(gè)隨機(jī)變量所獲得的信息量，其可以被視為父節(jié)點(diǎn)的熵與子節(jié)點(diǎn)的加權(quán)平均熵的差。

基尼不純度（Gini Impurity）

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

基尼不純度的下界為0，如果數(shù)據(jù)集僅包含一個(gè)類別，那么基尼不純度則為0。

有很多算法可以構(gòu)建決策樹。它們分別是：

1. CART（Classification and Regression Trees）：使用基尼不純度作為度量標(biāo)準(zhǔn)；

2. ID3（Iterative Dichotomiser 3）：使用熵和信息增益作為度量標(biāo)準(zhǔn)。

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

使用ID3算法進(jìn)行分類

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

這里，自變量將決定因變量。其中，自變量是天氣預(yù)報(bào)（outlook），溫度（Temperature），濕度（Humidity）和風(fēng)力（Wind），因變量是是否踢足球（Played football（yes/no））。

第一步，我們必須為決策樹找到父節(jié)點(diǎn)。為此，有以下步驟：

1. 計(jì)算類別變量（即因變量）的熵。

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

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

es”，5個(gè)“no”。在此基礎(chǔ)上，我們計(jì)算出了上面的概率。

從上面天氣預(yù)報(bào)（outlook）的數(shù)據(jù)中，我們可以輕松得到下表：

2. 現(xiàn)在我們需要計(jì)算加權(quán)平均熵，即我們已經(jīng)計(jì)算出的每個(gè)特征的權(quán)重總和乘以概率。

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

下一步是計(jì)算信息增益，它是上面我們計(jì)算的父節(jié)點(diǎn)的熵與加權(quán)平均熵之間的差。

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

類似地，計(jì)算溫度（Temperature）、濕度（Humidity）和風(fēng)力（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

現(xiàn)在選擇具有最大熵增益的特征。天氣預(yù)報(bào)（outlook）特征是有最大熵增益的特征，因此它構(gòu)成了決策樹的第一個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)）。

現(xiàn)在我們的數(shù)據(jù)如下所示：

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

接下來是在決策樹中找到下一個(gè)節(jié)點(diǎn)。我們在晴天（sunny）下找一個(gè)節(jié)點(diǎn)。我們需確定在溫度（Temperature）、濕度（Humidity）或風(fēng)力（Wind）中誰有更高的信息增益。

計(jì)算父節(jié)點(diǎn)晴天（sunny）的熵E（sunny）：

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

計(jì)算溫度（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

現(xiàn)在計(jì)算信息增益：

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

類似地，我們可以得到：

IG（sunny， Humidity） = 0.971

IG（sunny， Windy） = 0.020

這里的IG（sunny， Humidity）是最大值。因此，濕度（Humidity）是晴天（sunny）的子節(jié)點(diǎn)。

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

注意：熵大于0的分支需要進(jìn)一步拆分。

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

使用CART算法進(jìn)行分類

使用CART進(jìn)行分類的過程與ID3算法類似，但是其使用基尼不純度來替代熵作為度量標(biāo)準(zhǔn)。

1. 第一步我們需找到?jīng)Q策樹的根節(jié)點(diǎn)，為此需計(jì)算因變量的基尼不純度。

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

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

首先，我們要找到天氣預(yù)報(bào)（Outlook）、溫度（Temperature）、濕度（Humidity）和風(fēng)力（Wind）的加權(quán)平均基尼不純度。

首先考慮天氣預(yù)報(bào)（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

我們需要選擇一個(gè)具有最高基尼增益的特征，天氣預(yù)報(bào)（outlook）的基尼增益最高，因此我們可以選擇它作為我們的根節(jié)點(diǎn)。

現(xiàn)在，你應(yīng)該知道了如何進(jìn)行接下來的操作，即重復(fù)我們在ID3算法中的相同步驟。

決策樹的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

需要很少的數(shù)據(jù)預(yù)處理；

適用于低延遲應(yīng)用。

缺點(diǎn)：

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