1. 寫在前面

如果想從事數據挖掘或者機器學習的工作，掌握常用的機器學習算法是非常有必要的, 常見的機器學習算法：

• 監督學習算法：邏輯迴歸，線性迴歸， 決策樹 ，樸素貝葉斯，K近鄰，支持向量機，集成算法Adaboost等

• 無監督算法：聚類，降維，關聯規則, PageRank等

爲了詳細的理解這些原理，曾經看過西瓜書，統計學習方法，機器學習實戰等書，也聽過一些機器學習的課程，但總感覺話語裏比較深奧，讀起來沒有耐心，並且 理論到處有，而實戰最重要 ， 所以在這裏想用最淺顯易懂的語言寫一個 白話機器學習算法理論+實戰系列 。

個人認爲，理解算法背後的idea和使用，要比看懂它的數學推導更加重要。idea會讓你有一個直觀的感受，從而明白算法的合理性，數學推導只是將這種合理性用更加嚴謹的語言表達出來而已，打個比方，一個梨很甜，用數學的語言可以表述爲糖分含量90%，但只有親自咬一口，你才能真正感覺到這個梨有多甜，也才能真正理解數學上的90%的糖分究竟是怎麼樣的。如果算法是個梨，本文的首要目的就是先帶領大家咬一口。另外還有下面幾個目的：

• 檢驗自己對算法的理解程度，對算法理論做一個小總結

• 能開心的學習這些算法的核心思想， 找到學習這些算法的興趣，爲深入的學習這些算法打一個基礎。

• 每一節課的理論都會放一個實戰案例，能夠真正的做到學以致用，既可以鍛鍊編程能力，又可以加深算法理論的把握程度。

• 也想把之前所有的筆記和參考放在一塊，方便以後查看時的方便。

學習算法的過程，獲得的不應該只有算法理論，還應該有樂趣和解決實際問題的能力！

今天是白話機器學習算法理論+實戰的第一篇， 我們從決策樹開始。

大綱如下：

• 決策樹是什麼（生活中其實超級常見，只是沒有注意罷了）

• 決策樹的構造（要不要去打籃球，問問它就知道了）

• 決策樹的生成算法（ID3，C4.5，CART算法簡介）

• 決策樹的代碼底層實現（看看決策樹構建底層代碼張什麼樣子，更深的理解）

• 決策樹實戰（使用Sklearn實現好的決策樹，對泰坦尼克號乘客的生存做出預測）

OK， let's go !

2. 決策樹是什麼？

決策樹其實在我們生活中非常常見，只是我們缺少了一雙發現的眼睛。不信？舉個相親的例子吧:

這個女孩做決定的方式，就是基於決策樹做的決定。又一臉茫然：我都把樹給畫好了（畫工太差，湊合着看吧） 這就是棵決策樹了，我們在生活中做選擇的時候，往往背後都是基於這麼一個結構，只不過我們都沒有注意罷了。 當然工作原理也就非常簡單了，只要有這麼一棵樹在那，當面對一個新的情況時，我們就不停的這樣問，根據回答，就可以最後得出答案了。（比如，女孩可以再心目中根據擇偶標準建立一個這樣的樹，當再有人給推薦對象時，就直接給他這棵樹，讓他自己比對，然後告訴他：決策樹代表我的心。） 但是這個樹究竟要怎麼構造出來比較好呢， 這個有講究，不能隨便的構造，否則，有可能找不着對象。後面會重點說。好了， 引出了決策樹之後，也得說點正經的知識了：

那麼問題來了，究竟如何構造出一個決策樹來呢？

3. 決策樹的學習（構造）

上面的那種決策樹是怎麼構造出來的呢？這就是決策樹的學習構成，即根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確的分 類。包括三個過程： 特徵選擇、決策樹生成和決策樹剪枝 。這三個過程分別對應下面的問題：

好了，上面的話是不是又有點官方了啊，並且可能還出現了例如過擬合，泛化能力，剪枝等生詞，不要着急，還是以找對象的那個例子來理解這三個問題就是下面這樣：

下面就圍繞着這三個問題展開了，究竟如何選擇特徵，又如何生成決策樹，生成決策樹之後，又如何剪枝。

爲了讓下面的知識不那麼大理論話，我用一個例子來進行展開：假設我又下面打籃球的一個數據集，我應該怎麼構造一棵樹出來以決定我是否去打籃球呢？

3.1 特徵選擇

就是我們應該怎麼去選擇特徵作爲分裂的節點？比如上面這個例子，特徵有天氣、溼度、溫度、颳風，我先考慮哪一個特徵進行分裂呢？

解決這個問題之前，得引入三個概念： 純度、信息熵和信息增益 。不要暈，這麼來理解吧，

• 可以把決策樹的構造過程理解成爲尋找純淨劃分的過程。數學上，我們可以用純度來表示，純度換一種方式來解釋就是讓目標變量的分歧最小。這樣有利於我們做出決策 這裏先舉個例子：假設我有三個集合，每個集合6個樣本：

• 信息熵表示了信息的不確定度，理解起來就是衡量一組樣本的混亂程度，樣本越混亂，越不容易做出決定。計算公式如下： p(i|t) 代表了節點 t 爲分類 i 的概率，其中 log2 爲取以 2 爲底的對數。這裏不是來介紹公式的，而是說存在一種度量，它能幫我們反映出來這個信息的不確定度。當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高。只需要舉個例子看看怎麼算一組樣本的信息熵：假設我有兩個集合：

那我們應該怎麼辦呢？ 其實用特徵對樣本進行劃分之後，會讓 混亂程度減小，就是熵變小，純度變高 ，簡單理解起來就是你分類了啊。

★

一開始，比如3次打籃球，3次不打，沒法做判斷，但是如果用颳風這個特徵來劃分一下子，相當於有了一個條件，這時候，可能颳風的條件下，有2次不打籃球，1次打籃球， 這不就純度提高了，有利於做出決策了，不去打。

”

這時候我們解決了如何選擇特徵的一個問題，就是我給定一個條件，如果使我的樣本純度增加的最高，也就是更利於我做出選擇，那麼我就選這個作爲分裂節點。 但是又有一個問題， 怎麼衡量這個純度提高了多少呢？

• 信息增益就是其中的一種方式，在得知特徵X的信息後，而使得類Y的信息的不確定性減少的程度。計算公式如下： 即劃分之前的信息熵與給定一個特徵a劃分樣本之後的信息熵之差，就是特徵a帶來的信息增益。好吧，公式可能說的有點暈，我們看看怎麼計算就可以啦， 就拿上面的那個例子，我把圖片放到這裏來： 看看上面每個特徵信息增益應該怎麼算：

如果不好理解上面的過程，我還畫了個圖理解： 根據上面的這個思路，我們就可以分別計算溼度，溫度，颳風的信息增益如下：

• Gain(D，天氣) = 0.02

• Gain(D , 溫度)=0.128（這個最大）

• Gain(D , 溼度)=0.020

• Gain(D , 颳風)=0.020

可以看出來，溫度作爲屬性的信息增益最大，所以，先以這個爲節點，劃分樣本。 然後我們要將上圖中第一個葉節點，也就是 D1={1-,2-,3+,4+}進一步進行分裂，往下劃分，計算其不同屬性（天氣、溼度、颳風）作爲節點的信息增益，可以得到：

• Gain(D , 溼度)=1

• Gain(D , 天氣)=1

• Gain(D , 颳風)=0.3115

我們能看到溼度，或者天氣爲 D1 的節點都可以得到最大的信息增益，這裏我們選取溼度作爲節點的屬性劃分。同理，我們可以按照上面的計算步驟得到完整的決策樹，結果如下：

這樣，如果有小夥伴再叫我去打籃球的話，就會有下面的對話：

★

我：今天的溫度怎麼樣？小夥伴：今天的溫度適中 我：今天的天氣怎麼樣？小夥伴：今天的天氣晴天 我：Go Play！

”

這樣，打不打籃球，決策樹來告訴你。

3.2 決策樹的生成

決策樹的構造過程可以理解成爲尋找純淨劃分的過程。而衡量不純度的指標有三種，而每一種不純度對應一種決策樹的生成算法：

• 上面給出的信息增益（ID3算法，其實上面的構造決策樹的步驟就是著名的ID3算法）

• 信息增益比（C4.5算法）

• 基尼指數（CART算法）

後面第三大塊，會詳細介紹。

3.3 決策樹的剪枝

而關於剪枝，在這裏不講太多，因爲有點難理解，這裏只是簡單的介紹一下，順帶着說一下之前提到的生詞：過擬合，欠擬合，泛化能力等。想學習詳細步驟的可以參考下面給出的筆記參考《統計學習方法之決策樹》 《西瓜書之決策樹》。

既然要對決策樹進行剪枝，具體有哪些方法呢？一般來說，剪枝可以分爲“預剪枝”（Pre-Pruning）和“後剪枝”（Post-Pruning）。

• 預剪枝是在決策樹構造時就進行剪枝。方法是在構造的過程中對節點進行評估，如果對某個節點進行劃分，在驗證集中不能帶來準確性的提升，那麼對這個節點進行劃分就沒有意義，這時就會把當前節點作爲葉節點，不對其進行劃分。

• 後剪枝就是在生成決策樹之後再進行剪枝，通常會從決策樹的葉節點開始，逐層向上對每個節點進行評估。如果剪掉這個節點子樹，與保留該節點子樹在分類準確性上差別不大，或者剪掉該節點子樹，能在驗證集中帶來準確性的提升，那麼就可以把該節點子樹進行剪枝。方法是：用這個節點子樹的葉子節點來替代該節點，類標記爲這個節點子樹中最頻繁的那個類。

4. 決策樹的生成算法

4.1 ID3算法

這個算法就不多介紹了，上面的決策樹生成過程就是用的ID3算法，爲了白話一點，這裏不給出算法的步驟，具體的看統計學習方法裏面的算法步驟（包括什麼時候應該結束，這裏沒給出），這裏只需要記住，ID3算法計算的是 信息增益 。

ID3 的算法規則相對簡單，可解釋性強。同樣也存在缺陷，比如我們會發現 ID3 算法傾向於選擇取值比較多的屬性。

這種缺陷不是每次都會發生，只是存在一定的概率。在大部分情況下，ID3 都能生成不錯的決策樹分類。針對可能發生的缺陷，後人提出了新的算法進行改進。

4.2 在 ID3 算法上進行改進的 C4.5 算法

那麼 C4.5 都在哪些方面改進了 ID3 呢？

1. 採用信息增益比因爲 ID3 在計算的時候，傾向於選擇取值多的屬性。爲了避免這個問題，C4.5 採用信息增益率的方式來選擇屬性。

當屬性有很多值的時候，相當於被劃分成了許多份，雖然信息增益變大了，但是對於 C4.5 來說，屬性熵也會變大，所以整體的信息增益率並不大。上面那個例子，如果用C4.5算法的話，天氣屬性的信息增益比：

2. 採用悲觀剪枝ID3 構造決策樹的時候，容易產生過擬合的情況。在 C4.5 中，會在決策樹構造之後採用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。悲觀剪枝是後剪枝技術中的一種，通過遞歸估算每個內部節點的分類錯誤率，比較剪枝前後這個節點的分類錯誤率來決定是否對其進行剪枝。這種剪枝方法不再需要一個單獨的測試數據集。

3. 離散化處理連續屬性C4.5 可以處理連續屬性的情況，對連續的屬性進行離散化的處理。比如打籃球存在的“溼度”屬性，不按照“高、中”劃分，而是按照溼度值進行計算，那麼溼度取什麼值都有可能。該怎麼選擇這個閾值呢， C4.5 選擇具有最高信息增益的劃分所對應的閾值。

4. 處理缺失值針對數據集不完整的情況，C4.5 也可以進行處理。假如我們得到的是如下的數據，你會發現這個數據中存在兩點問題。

• 第一個問題是，數據集中存在數值缺失的情況，如何進行屬性選擇？

• 第二個問題是，假設已經做了屬性劃分，但是樣本在這個屬性上有缺失值，該如何對樣本進行劃分？

  我們不考慮缺失的數值，可以得到溫度 D={2-,3+,4+,5-,6+,7-}。溫度 = 高：D1={2-,3+,4+} ；溫度 = 中：D2={6+,7-}；溫度 = 低：D3={5-} 。這裏 + 號代表打籃球，- 號代表不打籃球。比如 ID=2 時，決策是不打籃球，我們可以記錄爲 2-。

  針對將屬性選擇爲溫度的信息增爲：Gain(D′, 溫度)=Ent(D′)-0.792=1.0-0.792=0.208 屬性熵 =1.459, 信息增益率 Gain_ratio(D′, 溫度)=0.208/1.459=0.1426。

  D′的樣本個數爲 6，而 D 的樣本個數爲 7，所以所佔權重比例爲 6/7，所以 Gain(D′，溫度) 所佔權重比例爲 6/7，所以：

而對於上面的第二個問題，需要考慮權重。具體的參考《西瓜書之決策樹》 這裏只給出答案：

• 針對問題一， 就是假如有些樣本在某個屬性上存在值缺失，那麼我計算信息增益的時候，我不考慮這些樣本就可以了。但用了多少樣本，要在不考慮帶缺失值樣本的前提下計算的信息增益的基礎上，乘以一個權重。

• 針對問題二，如果出現樣本在該屬性上的值缺失， 則把該樣本劃分到所有的分支裏面，但是權重不一樣（這個權重就是每個分支裏的節點個數佔的總數比例），這樣，如果再往下劃分屬性，對於該樣本來說，算條件熵的時候，得考慮上他本身的一個權重了。

4.3 CART算法

CART 算法，英文全稱叫做 Classification And Regression Tree，中文叫做分類迴歸樹。ID3 和 C4.5 算法可以生成二叉樹或多叉樹，而 CART 只支持二叉樹。同時 CART 決策樹比較特殊，既可以作分類樹，又可以作迴歸樹。

首先，得先知道什麼是分類樹，什麼是迴歸樹？

我用下面的訓練數據舉個例子，你能看到不同職業的人，他們的年齡不同，學習時間也不同。

• 如果我構造了一棵決策樹，想要基於數據判斷這個人的職業身份，這個就屬於分類樹，因爲是從幾個分類中來做選擇。分類樹可以處理離散數據，也就是數據種類有限的數據，它輸出的是樣本的類別

• 如果是給定了數據，想要預測這個人的年齡，那就屬於迴歸樹。迴歸樹可以對連續型的數值進行預測，也就是數據在某個區間內都有取值的可能，它輸出的是一個數值。

4.3.1 CART分類樹的工作流程

我們通過上面已經知道決策樹的核心就是尋找純淨的劃分，因此引入了純度的概念。

在屬性選擇上，我們是通過統計“不純度”來做判斷的，ID3 是基於信息增益做判斷，C4.5 在 ID3 的基礎上做了改進，提出了信息增益率的概念。

實際上 CART 分類樹與 C4.5 算法類似，只是屬性選擇的指標採用的是 基尼係數 。

對，這裏又出現了一個新的概念，不要暈，這個東西本身反應了樣本的不確定度，當基尼係數越小的時候，說明樣本之間的差異性小，不確定程度低。這一點和熵的定義類似。

★

你可能在經濟學中聽過說基尼係數，它是用來衡量一個國家收入差距的常用指標。當基尼係數大於 0.4 的時候，說明財富差異懸殊。基尼係數在 0.2-0.4 之間說明分配合理，財富差距不大。

”

分類的過程本身是一個不確定度降低的過程，即純度的提升過程。所以 CART 算法在構造分類樹的時候，會選擇基尼係數最小的屬性作爲屬性的劃分。

下面給出基尼指數的計算公式：

• 由於CART算法中，只把類別分爲兩類，所以K=2，二分類問題概率表示：              p1(1-p1) + p2(1-p2)

• 我們看看這個基尼指數表示的是什麼：其實和信息增益一樣， 也是數據集的混亂程度只不過這裏換了一表示方法。看看怎麼算： 這樣，我們在選擇特徵的時候，就可以根據基尼指數最小來選擇特徵了。不用考慮HA(D),也就是不用考慮D在A的劃分之下本身樣本的一個混亂程度了。因爲每次都分兩個叉，不用擔心叉太多影響結果了。

根據這個，迴歸打籃球的例子，假設屬性 A 將節點 D 劃分成了 D1 和 D2，如下圖所示： 這時候，計算出D1和D2的基尼指數：

這樣，就可以分別計算其他屬性的基尼指數，然後進行劃分了。具體的例子，看《統計學習方法之決策樹》

4.3.2 如何使用CART算法來創建分類樹

上面已經知道了CART算法是基於基尼指數來做屬性劃分的。但是具體實現，我們可以使用寫好的代碼，調用sklearn包來實現就好了。

Python 的 sklearn 中，如果我們想要創建 CART 分類樹，可以直接使用 DecisionTreeClassifier 這個類。創建這個類的時候，默認情況下 criterion 這個參數等於 gini，也就是按照基尼係數來選擇屬性劃分，即默認採用的是 CART 分類樹。

下面，我們來用 CART 分類樹，給 iris 數據集構造一棵分類決策樹。iris 這個數據集，我在 Python 可視化中講到過，實際上在 sklearn 中也自帶了這個數據集。基於 iris 數據集，構造 CART 分類樹的代碼如下：

# encoding=utf-8
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
# 準備數據集
iris=load_iris()
# 獲取特徵集和分類標識
features = iris.data
labels = iris.target
# 隨機抽取33%的數據作爲測試集，其餘爲訓練集
train_features, test_features, train_labels, test_labels = train_test_split(features, labels, test_size=0.33, random_state=0)
# 創建CART分類樹
clf = DecisionTreeClassifier(criterion='gini')
# 擬合構造CART分類樹
clf = clf.fit(train_features, train_labels)
# 用CART分類樹做預測
test_predict = clf.predict(test_features)
# 預測結果與測試集結果作比對
score = accuracy_score(test_labels, test_predict)
print("CART分類樹準確率 %.4lf" % score)

運行結果：

CART分類樹準確率 0.9600

如果我們把決策樹畫出來，可以得到下面的圖示： 涉及到代碼了，簡單說一下上面的代碼：

我們能看到 sklearn 幫我們做了 CART 分類樹的使用封裝，使用起來還是很方便的。

4.3.3 CART迴歸樹的流程

CART 迴歸樹劃分數據集的過程和分類樹的過程是一樣的，只是迴歸樹得到的預測結果是連續值，而且評判“不純度”的指標不同。

在 CART 分類樹中採用的是基尼係數作爲標準，那麼在 CART 迴歸樹中，如何評價“不純度”呢？實際上我們要根據樣本的混亂程度，也就是樣本的離散程度來評價“不純度”。

樣本的離散程度具體的計算方式是，先計算所有樣本的均值，然後計算每個樣本值到均值的差值。我們假設 x 爲樣本的個體，均值爲 u。爲了統計樣本的離散程度，我們可以取差值的絕對值，或者方差。

其中差值的絕對值爲樣本值減去樣本均值的絕對值： 方差爲每個樣本值減去樣本均值的平方和除以樣本個數：

所以這兩種節點劃分的標準，分別對應着兩種目標函數最優化的標準，即用最小絕對偏差（LAD），或者使用最小二乘偏差（LSD）。這兩種方式都可以讓我們找到節點劃分的方法，通常使用最小二乘偏差的情況更常見一些。

我們可以通過一個例子來看下如何創建一棵 CART 迴歸樹來做預測。如何使用 CART 迴歸樹做預測。

這裏我們使用到 sklearn 自帶的波士頓房價數據集，該數據集給出了影響房價的一些指標，比如犯罪率，房產稅等，最後給出了房價。根據這些指標，我們使用 CART 迴歸樹對波士頓房價進行預測，代碼如下：

# encoding=utf-8
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
from sklearn.metrics import r2_score,mean_absolute_error,mean_squared_error
from sklearn.tree import DecisionTreeRegressor
# 準備數據集
boston=load_boston()
# 探索數據
print(boston.feature_names)
# 獲取特徵集和房價
features = boston.data
prices = boston.target
# 隨機抽取33%的數據作爲測試集，其餘爲訓練集
train_features, test_features, train_price, test_price = train_test_split(features, prices, test_size=0.33)
# 創建CART迴歸樹
dtr=DecisionTreeRegressor()
# 擬合構造CART迴歸樹
dtr.fit(train_features, train_price)
# 預測測試集中的房價
predict_price = dtr.predict(test_features)
# 測試集的結果評價
print('迴歸樹二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('迴歸樹絕對值偏差均值:', mean_absolute_error(test_price, predict_price))

運行結果（每次運行結果可能會有不同）：

['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO' 'B' 'LSTAT']
迴歸樹二乘偏差均值: 23.80784431137724
迴歸樹絕對值偏差均值: 3.040119760479042

我們能看到 CART 迴歸樹的使用和分類樹類似，只是最後求得的預測值是個連續值。

5. 決策樹的代碼底層實現

構造決策樹時， 需要解決的第一個問題就是，當前數據集上的哪個特徵在劃分數據集時起到決定 作用， 需要找到這樣的特徵，把原始數據集劃分爲幾個數據子集， 然後再在剩餘的特徵裏面進 一步劃分，依次進行下去， 所以分下面幾個步驟：

5.1 計算給定數據的香農熵

def calcShannonEnt(dataset):
    numEntries = len(dataset)     # 樣本數量
    labelCounts = {}
    for featVec in dataset:
        currentLabel = featVec[-1]         # 遍歷每個樣本，獲取標籤
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * math.log(prob, 2)
    
    return shannonEnt

5.2  按照給定的特徵劃分數據

# 按照給定特徵劃分數據集
def splitDataSet(dataset, axis, value):
    retDataSet = []
    for featVec in dataset:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

5.3  選擇最好的數據集劃分數據

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1   # 獲取總的特徵數
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    
    # 下面開始變量所有特徵， 對於每個特徵，要遍歷所有樣本， 根據遍歷的樣本劃分開數據集，然後計算新的香農熵
    for i in range(numFeatures):
        featList = [example[i] for example in  dataSet]   #  獲取遍歷特徵的這一列數據，接下來進行劃分
        uniqueVals = set(featList)              # 從列表中創建集合是Python語言得到唯一元素值的最快方法
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > bestInfoGain):
            bastInfoGain = infoGain
            bestFeature = i
    
    return bestFeature

5.4 遞歸的創建決策樹

# 返回最多的那個標籤
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
            classCount[vote] += 1
    sortedClassCount = sorted(classCount.values(), reverse=True)
    
    return sortedClassCount[0]

# 遞歸構建決策樹
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):   # 類別完全相同則停止劃分 這種 (1,2,'yes') (3,4,'yes')
        return classList[0]
    if len(dataSet[0]) == 1:          # 遍歷所有特徵時，(1, 'yes') (2, 'no')這種形式 返回出現次數最多的類別
        return majorityCnt(classList)
    
    bestFeat = chooseBestFeatureToSplit(dataSet)    # 選擇最好的數據集劃分方式,返回的是最好特徵的下標
    bestFeatLabel = labels[bestFeat]         # 獲取到那個最好的特徵
    myTree = {bestFeatLabel:{}}        # 創建一個myTree,保存創建的樹的信息
    del(labels[bestFeat])          # 從標籤中藥刪除這個選出的最好的特徵，下一輪就不用這個特徵了
    featValues = [example[bestFeat] for example in dataSet]    # 獲取到選擇的最好的特徵的所有取值
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)  # 這是個字典嵌套字典的形式
    
    return myTree

這就是ID3算法的底層代碼。

可以參考隱形眼鏡分類的這個項目：https://github.com/zhongqiangwu960812/MLProjects/tree/master/MachineLearningInAction/DecisionTree

6. 決策樹Sklearn實戰

不知不覺，篇幅有點超過想像，所以這裏沒法詳細的介紹Sklearn中的決策樹對Titanic尼克號人的生存預測，那麼就先簡單的介紹一下Sklearn中決策樹怎麼用，然後實戰項目參考後面的鏈接吧。

6.1 sklearn 中的決策樹模型

首先，我們需要掌握 sklearn 中自帶的決策樹分類器 DecisionTreeClassifier，方法如下：

clf = DecisionTreeClassifier(criterion='entropy')

到目前爲止，sklearn 中只實現了 ID3 與 CART 決策樹，所以我們暫時只能使用這兩種決策樹，在構造 DecisionTreeClassifier 類時，其中有一個參數是 criterion，意爲標準。它決定了構造的分類樹是採用 ID3 分類樹，還是 CART 分類樹，對應的取值分別是 entropy 或者 gini：

• entropy: 基於信息熵，也就是 ID3 算法，實際結果與 C4.5 相差不大；

• gini：默認參數，基於基尼係數。CART 算法是基於基尼係數做屬性劃分的，所以 criterion=gini 時，實際上執行的是 CART 算法。

我們通過設置 criterion='entropy’可以創建一個 ID3 決策樹分類器，然後打印下 clf，看下決策樹在 sklearn 中是個什麼東西？

DecisionTreeClassifier(class_weight=None, criterion='entropy', max_depth=None,
            max_features=None, max_leaf_nodes=None,
            min_impurity_decrease=0.0, min_impurity_split=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, presort=False, random_state=None,
            splitter='best')

這裏我們看到了很多參數，除了設置 criterion 採用不同的決策樹算法外，一般建議使用默認的參數，默認參數不會限制決策樹的最大深度，不限制葉子節點數，認爲所有分類的權重都相等等。當然你也可以調整這些參數，來創建不同的決策樹模型。

這些參數代表的含義如下： 在構造決策樹分類器後，我們可以使用 fit 方法讓分類器進行擬合，使用 predict 方法對新數據進行預測，得到預測的分類結果，也可以使用 score 方法得到分類器的準確率。

下面這個表格是 fit 方法、predict 方法和 score 方法的作用。

6.2 Titanic 乘客生存預測

這個具體的看後面的參考筆記吧，有點多。

7. 總結

花費了一天的時間，才整理完了白話機器學習算法第一篇決策樹，雖然說白話，但是難免會有代碼和公式，但這些都是必須要知道的，也是基礎。後面的項目實戰應該好好練練，因爲光有理論，可能很快就會忘記了，所以得多練。

參考：

• http://note.youdao.com/noteshare?id=d7c88adb49a4500a18a1b9662a8fd0dd&sub=EDFC5B4E5196440381D46261A2BCB99D

• http://note.youdao.com/noteshare?id=5db5352df6b3e5130cff7c508658ee2d&sub=3A5B312A580948D0816313FD45B8E899

• http://note.youdao.com/noteshare?id=3caf31ca2b3bae95b38ae25e35f37787&sub=F983373BBC064EBFB4DCC656535FB6D5

• http://note.youdao.com/noteshare?id=cff65e21bd4bd9c21206608edec65f9f&sub=45E434F63B5341F7BC2AD1DF7E5FA6F4

• https://blog.csdn.net/c406495762/article/details/76262487

• https://blog.csdn.net/c406495762/article/details/75663451