電子發(fā)燒友App
本文為大家介紹了機器學(xué)習(xí)中常用的決策樹算法以及相關(guān)術(shù)語，并基于天氣數(shù)據(jù)集進行決策樹算法（ID3、CART算法）實現(xiàn)過程的手動推導(dǎo)。
決策樹是最重要的機器學(xué)習(xí)算法之一，其可被用于分類和回歸問題。本文中，我們將介紹分類部分。
什么是決策樹？
決策樹（Decision Tree）是一個具有樹形結(jié)構(gòu)的分類和預(yù)測工具，其中的每個內(nèi)部節(jié)點表示對屬性的測試，每個分支代表測試的結(jié)果，并且每個葉子節(jié)點（終端節(jié)點）都有一個類別標(biāo)簽。
上圖是一個小型決策樹。決策樹的一個重要優(yōu)勢在于其高度的可解釋性。在上圖中，如果身高大于180厘米或身高小于180厘米且體重大于 80公斤為男性，否則為女性。你是否思考過我們?nèi)绾蔚玫筋愃朴谏蠄D的決策樹，下面我將使用天氣數(shù)據(jù)集對此進行解釋。
在此之前，我將解釋一下相關(guān)的術(shù)語。
熵（Entropy）
在機器學(xué)習(xí)中，熵是對正在處理的信息中隨機性的一種度量。熵越高，從該信息得出結(jié)論就越難。
信息增益可以定義為隨機變量或信號通過觀察另一個隨機變量所獲得的信息量，其可以被視為父節(jié)點的熵與子節(jié)點的加權(quán)平均熵的差。
基尼不純度（Gini Impurity）
基尼不純度是一種度量方法，如果數(shù)據(jù)是根據(jù)子集中標(biāo)簽的分布被隨機標(biāo)記的，則基尼不純度用來度量從集合中隨機選擇的數(shù)據(jù)被不正確標(biāo)記的頻率。
基尼不純度的下界為0，如果數(shù)據(jù)集僅包含一個類別，那么基尼不純度則為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實現(xiàn)相同的功能。
使用ID3算法進行分類
下面，我們基于天氣數(shù)據(jù)集來確定是否踢足球。
這里，自變量將決定因變量。其中，自變量是天氣預(yù)報（outlook），溫度（Temperature），濕度（Humidity）和風(fēng)力（Wind），因變量是是否踢足球（Played football（yes/no））。
第一步，我們必須為決策樹找到父節(jié)點。為此，有以下步驟：
1. 計算類別變量（即因變量）的熵。
E（S） = -［（9/14）log（9/14） + （5/14）log（5/14）］ = 0.94
注意：這里通常將對數(shù)的底數(shù)設(shè)置為2。這里共有14個“yes/no”。其中有9個是“y
es”，5個“no”。在此基礎(chǔ)上，我們計算出了上面的概率。
從上面天氣預(yù)報（outlook）的數(shù)據(jù)中，我們可以輕松得到下表：
2. 現(xiàn)在我們需要計算加權(quán)平均熵，即我們已經(jīng)計算出的每個特征的權(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
下一步是計算信息增益，它是上面我們計算的父節(jié)點的熵與加權(quán)平均熵之間的差。
IG（S， outlook） = 0.94 - 0.693 = 0.247
類似地，計算溫度（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ù)報（outlook）特征是有最大熵增益的特征，因此它構(gòu)成了決策樹的第一個節(jié)點（根節(jié)點）。
現(xiàn)在我們的數(shù)據(jù)如下所示：
由于在天氣預(yù)報（Outlook）特征為多云（overcast）時，因變量的結(jié)果僅僅有“Yes”這一種類別，因此我們可以將其設(shè)置為“Yes”。這意味著如果天氣預(yù)報（outlook）特征為多云（overcast），我們就可以踢足球。現(xiàn)在我們的決策樹如下所示。
接下來是在決策樹中找到下一個節(jié)點。我們在晴天（sunny）下找一個節(jié)點。我們需確定在溫度（Temperature）、濕度（Humidity）或風(fēng)力（Wind）中誰有更高的信息增益。
計算父節(jié)點晴天（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
現(xiàn)在計算信息增益：
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é)點。
對于上表中的濕度（Humidity），如果濕度正常（normal），則因變量為“Yes”；如果濕度高（high），則因變量為“No”。與上面方法類似，我們可以找到下雨（Rain）的子節(jié)點。
注意：熵大于0的分支需要進一步拆分。
最終，我們可以得到如下的決策樹：
使用CART算法進行分類
使用CART進行分類的過程與ID3算法類似，但是其使用基尼不純度來替代熵作為度量標(biāo)準(zhǔn)。
1. 第一步我們需找到?jīng)Q策樹的根節(jié)點，為此需計算因變量的基尼不純度。
Gini（S） = 1 - ［（9/14）2 + （5/14）2］ = 0.4591
2. 下一步，我們將計算基尼增益（Gini Gain）。
首先，我們要找到天氣預(yù)報（Outlook）、溫度（Temperature）、濕度（Humidity）和風(fēng)力（Wind）的加權(quán)平均基尼不純度。
首先考慮天氣預(yù)報（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
我們需要選擇一個具有最高基尼增益的特征，天氣預(yù)報（outlook）的基尼增益最高，因此我們可以選擇它作為我們的根節(jié)點。
現(xiàn)在，你應(yīng)該知道了如何進行接下來的操作，即重復(fù)我們在ID3算法中的相同步驟。
決策樹的優(yōu)缺點
優(yōu)點：
決策樹具有高度可解釋性；
需要很少的數(shù)據(jù)預(yù)處理；
適用于低延遲應(yīng)用。
缺點：
很可能對噪聲數(shù)據(jù)產(chǎn)生過擬合。決策樹越深，由噪聲產(chǎn)生過擬合的可能性就越大。一種解決方案是對決策樹進行剪枝。
編輯：hfy
工商網(wǎng)監(jiān)
評論