1奄抽，什么是決策樹看蚜？
決策樹是一種機器學習算法叫搁，我們可以使用決策樹來處理分類問題。決策樹的決策（分類）過程可以用一個倒著的樹形結(jié)構(gòu)來形象的表達出來供炎，因此得名決策樹渴逻。
決策樹是一個包含根節(jié)點、若干內(nèi)部節(jié)點和若干葉子節(jié)點的樹形結(jié)構(gòu)音诫。決策樹的根節(jié)點包含樣本全集惨奕，內(nèi)部節(jié)點對應(yīng)特征屬性，葉子節(jié)點表示決策的結(jié)果竭钝。
使用決策樹進行判斷時墓贿，從根節(jié)點開始，測試待分類數(shù)據(jù)的特征屬性值蜓氨，應(yīng)該走哪條分支聋袋，循環(huán)這樣判斷，直到葉子節(jié)點為止穴吹。最終到達的這個葉子節(jié)點幽勒，就是決策樹的最終決策結(jié)果。
決策樹模型的學習過程一般有三個階段：
- 特征選擇：選擇哪些屬性作為樹的節(jié)點港令。
- 生成決策樹：生成樹形結(jié)構(gòu)啥容。
-
決策樹剪枝：是決策樹的一種優(yōu)化手段，比如剪去一些不必要的屬性節(jié)點顷霹。一般有“預(yù)剪枝”和“后剪枝”兩種咪惠。
- 剪枝的目的是防止過擬合現(xiàn)象，提高泛化能力淋淀。
- 預(yù)剪枝是在決策樹的生成過程中就進行剪枝遥昧，缺點是有可能造成欠擬合。
- 后剪枝是在決策樹生成之后再進行剪枝，缺點是計算量較大炭臭。
我們來看一個例子永脓。
比如我們根據(jù)天氣是否晴朗和是否刮風來決定是否去踢球？當天氣晴朗并且不刮風的時候鞋仍，我們才去踢球常摧。
此時，就可以將這個決策過程用一個樹形結(jié)構(gòu)來表示威创，如下：
這就是一顆最簡單的決策樹落午，我們可以用它來判斷是否要去踢球。最上方是樹的根節(jié)點肚豺，最下方是樹的葉子節(jié)點板甘。方框里是判斷條件，圓形中是決策的結(jié)果详炬。
當然盐类，實際的使用過程中，判斷條件并不會這么簡單呛谜，也不會讓我們自己手動畫圖在跳。實際應(yīng)用中，我們會讓程序自動的隐岛，從一堆樣本數(shù)據(jù)集中構(gòu)造出這顆決策樹猫妙，這個程序自動構(gòu)建決策樹的過程就是機器學習的過程。
最終構(gòu)造出來的這棵決策樹就是機器學習的結(jié)果聚凹，叫做模型割坠。最后，我們可以向模型中輸入一些屬性條件妒牙，讓模型給出我們判斷結(jié)果彼哼。
2歇终，如何構(gòu)建決策樹鳖轰？
比如我們有如下數(shù)據(jù)集：
| 序號 | 條件:天氣晴朗? | 條件:是否刮風? | 結(jié)果:去踢球嗎? |
|---|---|---|---|
| 1 | 是 | 否 | 去 |
| 2 | 是 | 是 | 不去 |
| 3 | 否 | 是 | 不去 |
| 4 | 否 | 否 | 不去 |
可以看到這個表格中有4 行（第一行表頭不算）蘸劈，4 列數(shù)據(jù)痘括。
一般在機器學習中，最后一列稱為目標(target)乱灵，前邊的列都稱為特征(features)孵延。
我們要根據(jù)這個數(shù)據(jù)集苟跪，來構(gòu)建一顆決策樹旗们，那如何構(gòu)建呢蚓哩？
首先，需要確定使用哪個屬性作為第一個判斷條件上渴，是先判斷天氣晴朗岸梨，還是先判斷是否刮風喜颁？也就是，讓天氣晴朗作為樹的根節(jié)點盛嘿，還是讓是否刮風作為樹的根節(jié)點洛巢？
解決這個問題需要用到信息熵和信息純度的概念括袒，我們先來看什么是信息熵次兆。
3，什么是信息熵锹锰？
1948 年芥炭，克勞德·香濃在他的論文“通信的數(shù)學原理”中提到了信息熵（一般用H 表示），度量信息熵的單位是比特恃慧。
就是說园蝠，信息量的多少是可以量化的。一條信息量的多少與信息的不確定性有關(guān)痢士，可以認為彪薛，信息量就等于不確定性的多少（信息的不確定度）。
信息熵的計算公式如下：
該公式的含義是：
- 待分類的事物可以分在多個分類中怠蹂，這里的
n就是分類的數(shù)目善延。 -
H(X)表示熵，數(shù)學含義是城侧，所有類別包含的信息期望值易遣。 -
-㏒p(Xì)表示符號的信息值，p(Xì)是選擇該分類的概率嫌佑。 - 公式中的
log一般以2 為底豆茫。
總之，就是要知道屋摇，信息量的多少是可以用數(shù)學公式計算出來的揩魂，用信息論中的專業(yè)術(shù)語就叫做信息熵。信息熵越大炮温，信息量也就越大肤京。
3.1，計算信息熵
那么我們就來計算一下上面表格數(shù)據(jù)的信息熵茅特。我們只關(guān)注“結(jié)果”那一列：
| 結(jié)果:去踢球嗎? |
|---|
| 去 |
| 不去 |
| 不去 |
| 不去 |
根據(jù)表格忘分，我們可以知道，所有的分類共有2 種白修，也就是“去” 和“不去”妒峦，“去”出現(xiàn)了1 次，“不去”出現(xiàn)了3 次兵睛。
分別計算“去” 和“不去” 出現(xiàn)的概率：
P(去) = 1 / 4 = 0.25P(不去) = 3 / 4 = 0.75
然后肯骇，根據(jù)熵的計算公式來計算“去”和“不去” 的信息熵窥浪，其中l(wèi)og 以2 為底：
H(去) = 0.25 * log 0.25 = -0.5H(不去) = 0.74 * log 0.75 = -0.31127812445913283
所以，整個表格含有的信息量就是：
H(表格) = -(H(去) + H(不去)) = 0.81127812445913283
3.2笛丙，用代碼實現(xiàn)信息熵的計算
將計算信息熵的過程用Python 代碼實現(xiàn)漾脂，如下：
import math
# 本函數(shù)用于計算一組數(shù)據(jù)的信息熵
# data_set 是一個列表，代表一組數(shù)據(jù)
# data_set 的元素data 也是一個列表
def calc_ent(data_set):
labels = {} # 用于統(tǒng)計每個label 的數(shù)量
for data in data_set:
label = data[-1] # 只用最后一個元素做計算
if label not in labels:
labels[label] = 0
labels[label] += 1
ent = 0 # 熵
n = len(data_set) # 數(shù)據(jù)條數(shù)
# 計算信息熵
for label in labels:
prob = float(labels[label]) / n # label 的概率
ent -= prob * math.log(prob, 2) # 根據(jù)信息熵公式計算
return ent
下面用該函數(shù)來計算表格的信息熵：
# 將表格轉(zhuǎn)化為 python 列表
# "yes" 表示"去"
# "no" 表示"不去"
data_set = [['yes'], ['no'], ['no'], ['no']]
ent = calc_ent(data_set)
print(ent) # 0.811278124459
可見胚鸯，用代碼計算出來的結(jié)果是 0.811278124459骨稿，跟我們手算的結(jié)果 0.81127812445913283 是一樣的（保留的小數(shù)位數(shù)不同）。
4姜钳，什么是信息純度坦冠？
信息的純度與信息熵成反比：
- 信息熵越大，信息量越大哥桥，信息越雜亂辙浑，純度越低。
- 信息熵越小拟糕，信息量越小判呕，信息越規(guī)整，純度越高送滞。
經(jīng)典的“不純度”算法有三種侠草，分別是：
-
信息增益，即
ID3 算法累澡，Information Divergence梦抢，該算法由Ross Quinlan于1975 年提出，可用于生成二叉樹或多叉樹愧哟。- ID3 算法會選擇信息增益最大的屬性來作為屬性的劃分奥吩。
-
信息增益率，即
C4.5 算法蕊梧，是Ross Quinlan在ID3 算法的基礎(chǔ)上改進而來霞赫，可用于生成二叉樹或多叉樹。 -
基尼不純度肥矢，即
CART 算法端衰，Classification and Regression Trees，中文為分類回歸樹甘改。- 只支持二叉樹旅东，即可用于分類數(shù)，又可用于回歸樹十艾。分類樹用基尼系數(shù)做判斷抵代，回歸樹用偏差做判斷。
- 基尼系數(shù)本身反應(yīng)了樣本的不確定度忘嫉。
- 當基尼系數(shù)越小的時候荤牍，樣本之間的差異性越小案腺，不確定程度越低。
-
CART 算法會選擇基尼系數(shù)最小的屬性作為屬性的劃分康吵。
信息增益是其中最簡單的一種算法劈榨，后兩者都是由它衍生而來。本篇文章中晦嵌，我們只詳細介紹信息增益同辣。
基尼系數(shù)是經(jīng)濟學中用來衡量一個國家收入差距的常用指標。當基尼系數(shù)大于
0.4的時候耍铜，說明財富差異較大邑闺〉埃基尼系數(shù)在0.2-0.4之間說明分配合理棕兼，財富差距不大。
5抵乓，ID3 算法
ID3 算法也就是信息增益伴挚，在根據(jù)某個屬性劃分數(shù)據(jù)集的前后，信息量發(fā)生的變化灾炭。
信息增益的計算公式如下：
該公式的含義：
- 簡寫就是：
G = H(父節(jié)點) - H(所有子節(jié)點) - 也就是：父節(jié)點的信息熵減去所有子節(jié)點的信息熵茎芋。
- 所有子節(jié)點的信息熵會按照子節(jié)點在父節(jié)點中的出現(xiàn)的概率來計算，這叫做歸一化信息熵蜈出。
信息增益的目的在于田弥，將數(shù)據(jù)集劃分之后帶來的純度提升，也就是信息熵的下降铡原。如果數(shù)據(jù)集在根據(jù)某個屬性劃分之后偷厦，能夠獲得最大的信息增益，那么這個屬性就是最好的選擇燕刻。
所以只泼，我們想要找到根節(jié)點，就需要計算每個屬性作為根節(jié)點時的信息增益卵洗，那么獲得信息增益最大的那個屬性请唱，就是根節(jié)點。
5.1过蹂，計算信息增益
為了方便看十绑，我將上面那個表格放在這里：
| 序號 | 條件:天氣晴朗? | 條件:是否刮風? | 結(jié)果:去踢球嗎? |
|---|---|---|---|
| 1 | 是 | 否 | 去 |
| 2 | 是 | 是 | 不去 |
| 3 | 否 | 是 | 不去 |
| 4 | 否 | 否 | 不去 |
我們已經(jīng)知道了，信息增益等于按照某個屬性劃分前后的信息熵之差酷勺。
這個表格劃分之前的信息熵我們已經(jīng)知道了本橙，就是我們在上面計算的結(jié)果：
-
H(表格) = 0.81127812445913283。
接下來鸥印，我們計算按照“天氣晴朗”劃分的信息增益勋功。按照“天氣晴朗”劃分后有兩個表格坦报。
表格1，“天氣晴朗”的值為“是”：
| 序號 | 條件:天氣晴朗? | 條件:是否刮風? | 結(jié)果:去踢球嗎? |
|---|---|---|---|
| 1 | 是 | 否 | 去 |
| 2 | 是 | 是 | 不去 |
分類共有2 種狂鞋，也就是“去” 和“不去”片择，“去”出現(xiàn)了1 次，“不去”出現(xiàn)了1 次骚揍。
所以字管，“去” 和“不去” 出現(xiàn)的概率均為0.5：
P(去) = P(不去) = 1 / 2 = 0.5
然后，“去”和“不去” 的信息熵信不，其中l(wèi)og 以2 為底：
H(去) = H(不去) = 0.5 * log 0.5 = -0.5
所以嘲叔，表格1 含有的信息量就是：
H(表格1) = -(H(去) + H(不去)) = 1
表格2，“天氣晴朗”的值為“否”：
| 序號 | 條件:天氣晴朗? | 條件:是否刮風? | 結(jié)果:去踢球嗎? |
|---|---|---|---|
| 3 | 否 | 是 | 不去 |
| 4 | 否 | 否 | 不去 |
所有的分類只有1 種抽活，是“不去”硫戈。所以：
P(不去) = 1
然后，“不去” 的信息熵下硕，其中l(wèi)og 以2 為底：
H(不去) = 1 * log 1 = 0
所以丁逝，表格2 含有的信息量就是：
H(表格2) = 0
總數(shù)據(jù)共有4 份：
- 表格1 中有2 份，概率為 2/4 = 0.5
- 表格2 中有2 份梭姓，概率為 2/4 = 0.5
所以霜幼，最終按照“天氣晴朗”劃分的信息增益為：
G(天氣晴朗) = H(表格) - (0.5*H(表格1) + 0.5*H(表格2)) = H(表格) - 0.5 = 0.31127812445913283。
5.2誉尖，ID3 算法的缺點
當我們計算的信息增益多了罪既，你會發(fā)現(xiàn)，ID3 算法傾向于選擇取值比較多的屬性作為（根）節(jié)點铡恕。
但是有的時候琢感，某些屬性并不會影響結(jié)果（或者對結(jié)果的影響不大），那此時使用ID3 選擇的屬性就不恰當了没咙。
為了改進ID3 算法的這種缺點猩谊，C4.5 算法應(yīng)運而生。
6祭刚，C4.5 算法
C4.5 算法對ID3 算法的改進點包括：
- 采用信息增益率牌捷，而不是信息增益，避免ID3 算法有傾向于選擇取值多的屬性的缺點涡驮。
- 加入了剪枝技術(shù)暗甥，防止ID3 算法中過擬合情況的出現(xiàn)。
- 對連續(xù)的屬性進行離散化的處理捉捅，使得C4.5 算法可以處理連續(xù)屬性的情況撤防，而ID3 只能處理離散型數(shù)據(jù)。
- 處理缺失值棒口，C4.5 也可以針對數(shù)據(jù)集不完整的情況進行處理寄月。
當然C4.5 算法也并不是沒有缺點辜膝，由于 C4.5算法需要對數(shù)據(jù)集進行多次掃描，所以算法效率相對較低漾肮。
ID3 和C4.5 都是基于信息熵厂抖，所以涉及大量的對數(shù)運算。而 CART 算法基于基尼系數(shù)克懊，不涉及對數(shù)運算忱辅。
7，CART 算法
CART 算法全稱為分類回歸樹谭溉，基于基尼系數(shù)墙懂。
基尼系數(shù)的計算公式如下：
該公式表示的含義是：
- 整個數(shù)據(jù)集共有 k 個類別。
- 第 n 個類別的概率為 Pn扮念。
基尼系數(shù)的效果與熵模型高度近似损搬，而且避免了對數(shù)運算，因此CART 算法的執(zhí)行效率較高扔亥。
本篇文章主要介紹了決策樹的基本原理场躯，決策樹的算法一般有三種谈为，分別是ID3 算法旅挤，C4.5 算法，CART 算法伞鲫，其中重點介紹了ID3 算法的計算過程粘茄。
下篇會介紹如何用決策樹來解決實際問題。
（完秕脓。）
