決策樹原理
決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。它提供一種在什么條件下會得到什么值的類似規(guī)則的方法。決策樹分為分類樹和回歸樹兩種，分類樹對離散變量做決策樹，回歸樹對連續(xù)變量做決策樹。也就是說，決策樹既可以用來解決分類問題，也可以解決回歸問題。
決策樹其實是一棵倒樹，它的根在最上面，葉子在下面。
決策樹由節(jié)點(node)和有向邊(directed edge)組成。節(jié)點有兩種類型：內(nèi)部節(jié)點(internal node)和葉節(jié)點(leaf node)。內(nèi)部節(jié)點表示一個特征或?qū)傩?，葉節(jié)點表示一個類。
下面我們通過一個小例子來看下，這棵樹到底怎么用
決定我們是否打籃球的因素有三個，是否下雨，溫度是否適合，是否是室內(nèi)。我們一步一步，通過判斷不同的條件，最后得出不同的結(jié)論。
我們首先選取了決定是否打籃球的條件，并且以是否下雨為根節(jié)點開始分裂，然后根據(jù)不同情況構(gòu)造了一棵樹，最后根據(jù)該樹的分枝，來決定是否打籃球。
概括來說，就是根據(jù)特征的值做判斷，最后得出不同的分類。
決策樹學(xué)習(xí)過程
那么決策樹要如何構(gòu)建呢？通常，這一過程可以概括為3個步驟：特征選擇、決策樹生成和修剪。
特征選擇：特征選擇是指從訓(xùn)練數(shù)據(jù)中眾多的特征中選擇一個特征作為當前節(jié)點的分裂標準，如何選擇特征有著很多不同量化評估標準標準，從而衍生出不同的決策樹算法。
決策樹生成：根據(jù)選擇的特征評估標準，從上至下遞歸地生成子節(jié)點，直到數(shù)據(jù)集不可分則停止決策樹生長。
剪枝：決策樹容易過擬合，一般來需要剪枝，縮小樹結(jié)構(gòu)規(guī)模、緩解過擬合。剪枝技術(shù)有預(yù)剪枝和后剪枝兩種。
特征選擇
特征選擇是為了選擇出對于訓(xùn)練數(shù)據(jù)具有分類能力的特征。比如說，使用某一個特征進行決策樹分類的結(jié)果與隨機分類的結(jié)果沒有任何區(qū)別，那么該特征就不具備分類能力，可以直接丟棄掉該特征。當然我們要選擇能夠分類出更好的類別的特征，作為根節(jié)點。
那么一般情況下該如何選擇特征呢，業(yè)界通常會使用信息增益的方式來選擇。
先來看幾個概念：
信息熵
條件熵
信息增益
信息熵
信息熵是信息的期望值，是用來衡量信息不確定性的指標。信息的不確定性越大，熵越大。
比如說對于拋硬幣事件，每次拋硬幣的結(jié)果就是一個不確定的信息。
如果根據(jù)我們的經(jīng)驗，一個均勻的硬幣正面和反面出現(xiàn)的概率是相等的，都是50%。所以我們很難判斷下一次是出現(xiàn)正面還是反面，所以這個事件的信息熵值很高。
但是如果該硬幣不是均勻的，并且根據(jù)歷史數(shù)據(jù)顯示，100次試驗中，出現(xiàn)正面的次數(shù)有98次，那么下一次拋硬幣，我們就很容易判斷結(jié)果了，故而該事件的信息熵很低。
其計算公式為：
其中：
P(X=i)為隨機變量 X 取值為 i 的概率
n 代表事件的 n 種情況
我們還是以上面拋硬幣的例子來求解下兩種情況下的信息熵各為多少
注意，由于編輯器的原因，以下所有 log(2) 均表示以2為底的對數(shù)
均勻硬幣
|
硬幣 |
P |
|
正面 |
0.5 |
|
反面 |
0.5 |
信息熵 = -0.5 * log(2)0.5 - 0.5 * log(2)0.5 = 1
非均勻硬幣
|
硬幣 |
P |
|
正面 |
0.98 |
|
反面 |
0.02 |
信息熵 = -0.98 * log(2)0.98 - 0.02 * log(2)0.02 = 0.14
思考：如果正面的概率是100%，那么此時的信息熵是多少呢
答：此時信息熵是0，也可以說明，信息熵是0到1之間的數(shù)值。
條件熵
條件熵是通過獲得更多的信息來減小不確定性。當我們知道的信息越多時，信息的不確定性越小。
比如說某個用戶曾經(jīng)購買了一種商品，但是我們沒有辦法僅僅根據(jù)這個信息來判斷，該用戶是否會再次購買該商品。但是如果我們增加一些條件，比如雙十一促銷活動信息之后，我們就能夠更加容易的發(fā)現(xiàn)用戶購買商品與促銷活動之間的聯(lián)系，并通過不同促銷力度時用戶購買的概率來降低不確定性。
其計算公式為：
其中：
Y 為條件
P(Y = v)表示 Y 有多種情況，當 Y 處于 v 的概率
H(X|Y = v)表示 Y 處于 v 條件時的信息熵
信息增儀
信息增益的定義就是信息熵減去條件熵
這里只是數(shù)學(xué)上的定義，那么該如何使用信息增益來創(chuàng)建決策樹呢，還是舉例來看。
在上圖中，我先按照某種條件，把紅點和黃框分成了如圖所示的兩類，接下來我們計算下熵值
父節(jié)點信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.97
上面子節(jié)點信息熵 = -(2/6log(2)2/6)-(4/6log(2)4/6) = 0.91
下面子節(jié)點信息熵 = -(2/4log(2)2/4)-(2/4log(2)2/4) = 1
此處兩個子節(jié)點其實就是某種條件下的信息熵，因為在分類的時候，是隱含了某種分類條件的。
下面根據(jù)條件熵的定義，可以得到條件熵
條件熵 = 上面子節(jié)點出現(xiàn)的概率 * 該條件下的信息熵 + 下面子節(jié)點出現(xiàn)的概率 * 該條件下的信息熵
= 6/10 * 0.91 + 4/10 * 1
= 0.946
再根據(jù)信息增益的定義，可以得到信息增益
信息增益 = 父節(jié)點信息熵 - 條件熵
= 0.97 - 0.946
= 0.024
再來看另一種分類方式
父節(jié)點信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.442
上面子節(jié)點信息熵 = -(6/6log(2)6/6)-(0/6log(2)0/6) = 0
下面子節(jié)點信息熵 = -(4/4log(2)4/4)-(0/4log(2)0/4) = 0
條件熵 = 0
信息增益 = 0.442
從圖中明顯可以看出，第二種分類是好于第一種的，而此時第二種的信息增益是較大的，由此可以得到，在通過信息增益來確定節(jié)點時，需要使用信息增益最大的那個特征。 也就是說，信息增益是相對于特征而言的，信息增益越大，特征對最終的分類結(jié)果影響也就越大，我們就應(yīng)該選擇對最終分類結(jié)果影響最大的那個特征作為我們的分類特征。
決策樹生成
構(gòu)建決策樹的工作原理：
拿到原始數(shù)據(jù)集，然后基于最好的屬性值劃分數(shù)據(jù)集，由于特征值可能多于兩個，因此此時可能存在大于兩個分支的數(shù)據(jù)集劃分。第一次劃分之后，數(shù)據(jù)集被向下傳遞到樹的分支的下一個結(jié)點。在這個結(jié)點上，我們可以再次劃分數(shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集。
構(gòu)建決策樹的算法有很多，比如 C4.5、ID3 和 CART，這些算法在運行時并不總是在每次劃分數(shù)據(jù)分組時都會消耗特征。ID3 和 C4.5 算法可以生成二叉樹或多叉樹，而 CART 只支持二叉樹。
基于 ID3 算法
ID3 算法其實就是計算信息增益，在決策樹各個結(jié)點上對應(yīng)信息增益準則（選取信息增益最大的）選擇特征，遞歸地構(gòu)建決策樹。
具體方法是：從根結(jié)點(root node)開始，對結(jié)點計算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點的特征，由該特征的不同取值建立子節(jié)點；再對子結(jié)點遞歸地調(diào)用以上方法，構(gòu)建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止，最后得到一個決策樹。
我們使用如下的數(shù)據(jù)集來演示下該如何通過 ID3 算法構(gòu)建決策樹，該數(shù)據(jù)集記錄的是某位客戶，在不同天氣下打高爾夫的情況。
|
weather |
temp |
wind |
play golf |
|
rainy |
hot |
false |
no |
|
rainy |
hot |
ture |
no |
|
overcast |
hot |
false |
yes |
|
sunny |
mild |
false |
yes |
|
sunny |
cool |
false |
yes |
|
sunny |
cool |
ture |
no |
|
overcast |
cool |
ture |
yes |
|
rainy |
mild |
false |
no |
|
rainy |
cool |
false |
yes |
|
sunny |
mild |
false |
yes |
|
rainy |
mild |
ture |
yes |
|
overcast |
mild |
ture |
yes |
|
overcast |
hot |
false |
yes |
|
sunny |
mild |
ture |
no |
計算根節(jié)點
我們首先來計算是否打高爾夫球的信息熵
|
是否打高爾夫 |
頻度 |
概率 |
信息熵 |
|
No |
5 |
5/14 = 0.36 |
-0.531 |
|
Yes |
9 |
9/14 = 0.64 |
-0.410 |
根據(jù)信息熵的計算公式可以得出，Play Golf 的信息熵為
H(play golf) = -[-0.531 + (-0.410) ] = 0.940
下面計算3種天氣狀況下的條件熵
以天氣狀況為節(jié)點
各種天氣狀況出現(xiàn)的概率
|
weather |
Yes |
No |
天氣狀況各情況出現(xiàn)頻度 |
概率 |
|
rainy |
2 |
3 |
5 |
5/14 = 0.36 |
|
overcast |
4 |
0 |
4 |
4/14 = 0.29 |
|
sunny |
3 |
2 |
5 |
5/14 = 0.36 |
各種天氣狀況下的條件熵
|
weather |
Yes（打高爾夫的概率） |
No（不打高爾夫的概率） |
信息熵 |
|
rainy |
2/5 = 0.4 |
3/5 = 0.6 |
0.971 |
|
overcast |
4/4 = 1 |
0/4 = 0 |
0 |
|
sunny |
3/5 = 0.6 |
2/5 = 0.4 |
0.971 |
以 weather 為節(jié)點的條件熵 0.36 * 0.971 + 0.29 * 0 + 0.36 * 0.971 = 0.69
此時的信息增益為 0.94 - 0.69 = 0.25
以溫度為節(jié)點
各種溫度出現(xiàn)的概率
|
temp |
Yes |
No |
溫度個情況出現(xiàn)頻度 |
概率 |
|
hot |
2 |
2 |
4 |
4/14 = 0.29 |
|
mild |
4 |
2 |
6 |
6/14 = 0.43 |
|
cool |
3 |
1 |
4 |