機器學習： 決策樹

一、決策樹算法簡介

決策樹思想的來源非常樸素，程式設計中的條件分支結構就是if-else結構，最早的決策樹就是利用這類結構分割資料的一種分類學習方法

決策樹：

• 是一種樹形結構，本質是一顆由多個判斷節點組成的樹
• 其中每個内部節點表示一個屬性上的判斷，
• 每個分支代表一個判斷結果的輸出，
• 最後每個葉節點代表一種分類結果。

怎麼了解這句話？通過一個對話例子

想一想這個女生為什麼把年齡放在最上面判斷！！！！！！！！！

上面案例是女生通過定性的主觀意識，把年齡放到最上面，那麼如果需要對這一過程進行量化，該如何處理呢？

此時需要用到資訊論中的知識：資訊熵，資訊增益

二、決策樹分類原理

1 熵

1.1 概念

實體學上，熵 Entropy 是“混亂”程度的量度。

系統越有序，熵值越低；系統越混亂或者分散，熵值越高。

1948年香農提出了資訊熵（Entropy） 的概念。

資訊理論：

1. 從資訊的完整性上進行的描述:

   當系統的有序狀态一緻時，資料越集中的地方熵值越小，資料越分散的地方熵值越大。

   2.從資訊的有序性上進行的描述:

   當資料量一緻時，系統越有序，熵值越低；系統越混亂或者分散，熵值越高。

“資訊熵” (information entropy)是度量樣本集合純度最常用的一種名額。

假定目前樣本集合 D 中第 k k k 類樣本所占的比例為 p k ( k = 1 , 2 , . . . , ∣ y ∣ ) p_k(k = 1, 2,. . . , |y|) pk​(k=1,2,...,∣y∣)

p k = C k D p_k = \frac{C^k}{D} pk​=DCk​​​ , D D D為樣本的所有數量， C k C^k Ck為第 k k k類樣本的數量。

則 D D D的資訊熵定義為（log是以2為底，lg是以10為底）：

其中： E n t ( D ) Ent(D) Ent(D) 的值越小，則 D D D 的純度越高

1.2 案例

課堂案例：
假設我們沒有看世界杯的比賽，但是想知道哪支球隊會是冠軍，
我們隻能猜測某支球隊是或不是冠軍，然後觀衆用對或不對來回答，
我們想要猜測次數盡可能少，你會用什麼方法？

答案：
二分法：
假如有 16 支球隊，分别編号，先問是否在 1-8 之間，如果是就繼續問是否在 1-4 之間，
以此類推，直到最後判斷出冠軍球隊是哪支。
如果球隊數量是 16，我們需要問 4 次來得到最後的答案。那麼世界冠軍這條消息的資訊熵就是 4。

那麼資訊熵等于4，是如何進行計算的呢？
Ent(D) = -（p1 * logp1 + p2 * logp2 + ... + p16 * logp16），
其中 p1, ..., p16 分别是這 16 支球隊奪冠的機率。
當每支球隊奪冠機率相等都是 1/16 的時：Ent(D) = -（16 * 1/16 * log1/16） = 4
每個事件機率相同時，熵最大，這件事越不确定。
           

練習：

籃球比賽裡，有4個球隊 {A,B,C,D} ，獲勝機率分别為{1/2, 1/4, 1/8, 1/8}

求Ent(D)

答案：

2 決策樹的劃分依據一----資訊增益

2.1 概念

資訊增益： 以某特征劃分資料集前後的熵的內插補點。熵可以表示樣本集合的不确定性，熵越大，樣本的不确定性就越大。是以可以使用劃分前後集合熵的內插補點來衡量使用目前特征對于樣本集合D劃分效果的好壞。

資訊增益 = entroy(前) - entroy(後)

注：資訊增益表示得知特征X的資訊而使得類Y的資訊熵減少的程度

定義與公式：

假定離散屬性a有 V 個可能的取值：

假設離散屬性性别有2（男，女）個可能的取值

若使用a來對樣本集 D 進行劃分，則會産生 V 個分支結點,

其中第v個分支結點包含了 D 中所有在屬性a上取值為 a v a^v av的樣本，記為 D v D^v Dv，我們可根據前面給出的資訊熵公式計算出 D v D^v Dv的資訊熵，再考慮到不同的分支結點所包含的樣本數不同，給分支結點賦予權重 ∣ D v ∣ ∣ D ∣ \frac{|D^v|}{|D|} ∣D∣∣Dv∣​

即樣本數越多的分支結點的影響越大，于是可計算出用屬性a對樣本集 D 進行劃分所獲得的"資訊增益" (information gain)

其中：

特征a對訓練資料集D的資訊增益Gain(D,a)，定義為集合D的資訊熵 E n t ( D ) Ent(D) Ent(D)與給定特征a條件下D的資訊條件熵 E n t ( D ∣ a ) E n t ( D ∣ a ) Ent(D|a)Ent(D∣a) Ent(D∣a)Ent(D∣a)之差，即公式為：

資訊熵的計算：

條件熵的計算：

其中：

D v D^v Dv表示a屬性中第v個分支節點包含的樣本數

C k v C^{kv} Ckv表示a屬性中第v個分支節點包含的樣本數中，第 k k k個類别下包含的樣本數

一般而言，資訊增益越大，則意味着使用屬性 a 來進行劃分所獲得的"純度提升"越大。 是以，我們可用資訊增益來進行決策樹的劃分屬性選擇，著名的 ID3 決策樹學習算法 [Quinlan,1986] 就是以資訊增益為準則來選擇劃分屬性。

其中，ID3 名字中的 ID 是 Iterative Dichotomiser (疊代二分器)的簡稱

2.2 案例

如下圖，第一列為論壇号碼，第二列為性别，第三列為活躍度，最後一列使用者是否流失。

我們要解決一個問題：性别和活躍度兩個特征，哪個對使用者流失影響更大？

通過計算資訊增益可以解決這個問題，統計上右表資訊

其中Positive為正樣本（已流失），Negative為負樣本（未流失），下面的數值為不同劃分下對應的人數。

可得到三個熵：

a.計算類别資訊熵

整體熵：

b.計算性别屬性的資訊熵(a=“性别”)

c.計算性别的資訊增益(a=“性别”)

b.計算活躍度屬性的資訊熵(a=“活躍度”)

c.計算活躍度的資訊增益(a=“活躍度”)

活躍度的資訊增益比性别的資訊增益大，也就是說，活躍度對使用者流失的影響比性别大。 在做特征選擇或者資料分析的時候，我們應該重點考察活躍度這個名額。

3 決策樹的劃分依據二----資訊增益率

3.1 概念

在上面的介紹中，我們有意忽略了"編号"這一列.若把"編号"也作為一個候選劃分屬性，則根據資訊增益公式可計算出它的資訊增益為 0.9182，遠大于其他候選劃分屬性。

計算每個屬性的資訊熵過程中,我們發現,該屬性的值為0, 也就是其資訊增益為0.9182. 但是很明顯這麼分類,最後出現的結果不具有泛化效果.無法對新樣本進行有效預測.

實際上，資訊增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，著名的 C4.5 決策樹算法 [Quinlan,1993] 不直接使用資訊增益，而是使用"增益率" (gain ratio) 來選擇最優劃分屬性

增益率： 增益率是用前面的資訊增益Gain(D, a)和屬性a對應的"固有值"(intrinsic value) [Quinlan,1993]的比值來共同定義的。

其中：

屬性 a 的可能取值數目越多(即 V 越大)，則 IV(a) 的值通常會越大.

3.2 案例

3.2.1 案例一

a.計算類别資訊熵

b.計算類别屬性的資訊熵(性别、活躍度)

c.計算活躍度的資訊增益(性别、活躍度)

d.計算屬性分裂資訊度量

用分裂資訊度量來考慮某種屬性進行分裂時分支的數量資訊和尺寸資訊，我們把這些資訊稱為屬性的内在資訊（instrisic information）。資訊增益率用資訊增益/内在資訊，會導緻屬性的重要性随着内在資訊的增大而減小（也就是說，如果這個屬性本身不确定性就很大，那我就越不傾向于選取它），這樣算是對單純用資訊增益有所補償。

e.計算資訊增益率

活躍度的資訊增益率更高一些，是以在建構決策樹的時候，優先選擇

通過這種方式，在選取節點的過程中，我們可以降低取值較多的屬性的選取偏好。

3.2.2 案例二

如下圖，第一列為天氣，第二列為溫度，第三列為濕度，第四列為風速，最後一列該活動是否進行。

我們要解決：根據下面表格資料，判斷在對應天氣下，活動是否會進行？

該資料集有四個屬性，屬性集合A={ 天氣，溫度，濕度，風速}， 類别标簽有兩個，類别集合L={進行，取消}

a.計算類别資訊熵

類别資訊熵表示的是所有樣本中各種類别出現的不确定性之和。根據熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的資訊量就越多。

E n t ( D ) = − 9 14 l o g 2 9 14 − 5 14 l o g 2 5 14 = 0.940 Ent(D)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.940 Ent(D)=−149​log2​149​−145​log2​145​=0.940

b.計算每個屬性的資訊熵

每個屬性的資訊熵相當于一種條件熵。他表示的是在某種屬性的條件下，各種類别出現的不确定性之和。屬性的資訊熵越大，表示這個屬性中擁有的樣本類别越不“純”。

c.計算資訊增益

資訊增益 = 熵 - 條件熵，在這裡就是 類别資訊熵 - 屬性資訊熵，它表示的是資訊不确定性減少的程度。如果一個屬性的資訊增益越大，就表示用這個屬性進行樣本劃分可以更好的減少劃分後樣本的不确定性，當然，選擇該屬性就可以更快更好地完成我們的分類目标。

資訊增益就是ID3算法的特征選擇名額。

假設我們把上面表格1的資料前面添加一列為"編号",取值(1–14). 若把"編号"也作為一個候選劃分屬性,則根據前面步驟: 計算每個屬性的資訊熵過程中,我們發現,該屬性的值為0, 也就是其資訊增益為0.940. 但是很明顯這麼分類,最後出現的結果不具有泛化效果.此時根據資訊增益就無法選擇出有效分類特征。是以，C4.5選擇使用資訊增益率對ID3進行改進。

d.計算屬性分裂資訊度量

用分裂資訊度量來考慮某種屬性進行分裂時分支的數量資訊和尺寸資訊，我們把這些資訊稱為屬性的内在資訊（instrisic information）。資訊增益率用資訊增益/内在資訊，會導緻屬性的重要性随着内在資訊的增大而減小（也就是說，如果這個屬性本身不确定性就很大，那我就越不傾向于選取它），這樣算是對單純用資訊增益有所補償。

e.計算資訊增益率

天氣的資訊增益率最高，選擇天氣為分裂屬性。發現分裂了之後，天氣是“陰”的條件下，類别是”純“的，是以把它定義為葉子節點，選擇不“純”的結點繼續分裂。

在子結點當中重複過程1~5，直到所有的葉子結點足夠"純"。

現在我們來總結一下C4.5的算法流程

while(目前節點"不純")：
    1.計算目前節點的類别熵(以類别取值計算)
    2.計算目前階段的屬性熵(按照屬性取值吓得類别取值計算)
    3.計算資訊增益
    4.計算各個屬性的分裂資訊度量
    5.計算各個屬性的資訊增益率
end while
目前階段設定為葉子節點
           

3.3 為什麼使用C4.5要好

1.用資訊增益率來選擇屬性

克服了用資訊增益來選擇屬性時偏向選擇值多的屬性的不足。

2.采用了一種後剪枝方法

避免樹的高度無節制的增長，避免過度拟合資料

3.對于缺失值的處理

在某些情況下，可供使用的資料可能缺少某些屬性的值。假如〈x，c(x)〉是樣本集S中的一個訓練執行個體，但是其屬性A的值A(x)未知。

處理缺少屬性值的一種政策是賦給它結點n所對應的訓練執行個體中該屬性的最常見值；

另外一種更複雜的政策是為A的每個可能值賦予一個機率。

例如，給定一個布爾屬性A，如果結點n包含6個已知A=1和4個A=0的執行個體，那麼A(x)=1的機率是0.6，而A(x)=0的機率是0.4。于是，執行個體x的60%被配置設定到A=1的分支，40%被配置設定到另一個分支。

C4.5就是使用這種方法處理缺少的屬性值。

4 決策樹的劃分依據三 ----基尼值和基尼指數

4.1 概念

CART 決策樹 [Breiman et al.,1984] 使用"基尼指數" (Gini index)來選擇劃分屬性.

CART 是Classification and Regression Tree的簡稱，這是一種著名的決策樹學習算法,分類和回歸任務都可用

基尼值Gini(D)： 從資料集D中随機抽取兩個樣本，其類别标記不一緻的機率。故，Gini(D)值越小，資料集D的純度越高。

資料集 D 的純度可用基尼值來度量:

p k = C k D p_k = \frac{C_k}{D} pk​=DCk​​， D為樣本的所有數量， C k C^k Ck 為第 k k k 類樣本的數量。

基尼指數Gini_index(D)：

一般，選擇使劃分後基尼系數最小的屬性作為最優化分屬性。

4.2 案例

請根據下圖清單，按照基尼指數的劃分依據，做出決策樹。

序号	是否有房	婚姻狀況	年收入	是否拖欠貸款
1	yes	single	125k	no
2	no	married	100k	no
3	no	single	70k	no
4	yes	married	120k	no
5	no	divorced	95k	yes
6	no	married	60k	no
7	yes	divorced	220k	no
8	no	single	85k	yes
9	no	married	75k	no
10	no	Single	90k	yes

1，對資料集非序列标号屬性{是否有房，婚姻狀況，年收入}分别計算它們的Gini指數，取Gini指數最小的屬性作為決策樹的根節點屬性。

第一次大循環

2，根節點的Gini值為

3，當根據是否有房來進行劃分時，Gini指數計算過程為：

4，若按婚姻狀況屬性來劃分，屬性婚姻狀況有三個可能的取值{married，single，divorced}，分别計算劃分後的Gini系數增益。

​ {married} | {single,divorced}

​ {single} | {married,divorced}

​ {divorced} | {single,married}

對比計算結果，根據婚姻狀況屬性來劃分根節點時取Gini指數最小的分組作為劃分結果，即:

{married} | {single,divorced}

5，同理可得年收入Gini：

對于年收入屬性為數值型屬性，首先需要對資料按升序排序，然後從小到大依次用相鄰值的中間值作為分隔将樣本劃分為兩組。例如當面對年收入為60和70這兩個值時，我們算得其中間值為65。以中間值65作為分割點求出Gini指數。

根據計算知道，三個屬性劃分根節點的指數最小的有兩個：年收入屬性和婚姻狀況，他們的指數都為0.3。此時，選取首先出現的屬性【married】作為第一次劃分。

第二次大循環

6，接下來，采用同樣的方法，分别計算剩下屬性，其中根節點的Gini系數為（此時是否拖欠貸款的各有3個records）

7，對于是否有房屬性，可得：

8，對于年收入屬性則有：

經過如上流程，建構的決策樹，如下圖：

現在我們來總結一下CART的算法流程

while(目前節點"不純")：
    1.周遊每個變量的每一種分割方式，找到最好的分割點
    2.分割成兩個節點N1和N2
end while
每個節點足夠“純”為止
           

5 小結

5.1 常見決策樹的啟發函數比較

名稱	提出時間	分支方式	備注
ID3	1975	資訊增益	ID3隻能對離散屬性的資料集構成決策樹
C4.5	1993	資訊增益率	優化後解決了ID3分支過程中總喜歡偏向選擇值較多的 屬性
CART	1984	Gini系數	可以進行分類和回歸，可以處理離散屬性，也可以處理連續屬性

5.1.1 ID3 算法

存在的缺點

​ (1) ID3算法在選擇根節點和各内部節點中的分支屬性時，采用資訊增益作為評價标準。資訊增益的缺點是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會提供太多有價值的資訊.

​ (2) ID3算法隻能對描述屬性為離散型屬性的資料集構造決策樹。

5.1.2 C4.5算法

做出的改進(為什麼使用C4.5要好)

​ (1) 用資訊增益率來選擇屬性

​ (2) 可以處理連續數值型屬性

​ (3)采用了一種後剪枝方法

​ (4)對于缺失值的處理

C4.5算法的優缺點

​ 優點：

​ 産生的分類規則易于了解，準确率較高。

​ 缺點：

​ 在構造樹的過程中，需要對資料集進行多次的順序掃描和排序，因而導緻算法的低效。

​ 此外，C4.5隻适合于能夠駐留于記憶體的資料集，當訓練集大得無法在記憶體容納時程式無法運作。

5.1.3 CART算法

CART算法相比C4.5算法的分類方法，采用了簡化的二叉樹模型，同時特征選擇采用了近似的基尼系數來簡化計算。

C4.5不一定是二叉樹，但CART一定是二叉樹。

5.1.4 多變量決策樹(multi-variate decision tree)

同時，無論是ID3, C4.5還是CART,在做特征選擇的時候都是選擇最優的一個特征來做分類決策，但是大多數，分類決策不應該是由某一個特征決定的，而是應該由一組特征決定的。這樣決策得到的決策樹更加準确。這個決策樹叫做多變量決策樹(multi-variate decision tree)。在選擇最優特征的時候，多變量決策樹不是選擇某一個最優特征，而是選擇最優的一個特征線性組合來做決策。這個算法的代表是OC1，這裡不多介紹。

如果樣本發生一點點的改動，就會導緻樹結構的劇烈改變。這個可以通過內建學習裡面的随機森林之類的方法解決。

5.2 決策樹變量的兩種類型：

1. 數字型（Numeric）：變量類型是整數或浮點數，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作為分割條件（排序後，利用已有的分割情況，可以優化分割算法的時間複雜度）。
2. 名稱型（Nominal）：類似程式設計語言中的枚舉類型，變量隻能從有限的選項中選取，比如前面例子中的“婚姻情況”，隻能是“單身”，“已婚”或“離婚”，使用“=”來分割。

5.3 如何評估分割點的好壞？

如果一個分割點可以将目前的所有節點分為兩類，使得每一類都很“純”，也就是同一類的記錄較多，那麼就是一個好分割點。

比如上面的例子，“擁有房産”，可以将記錄分成了兩類，“是”的節點全部都可以償還債務，非常“純”；“否”的節點，可以償還貸款和無法償還貸款的人都有，不是很“純”，但是兩個節點加起來的純度之和與原始節點的純度之差最大，是以按照這種方法分割。

建構決策樹采用貪心算法，隻考慮目前純度差最大的情況作為分割點。

三、cart剪枝

1 為什麼要剪枝

圖形描述

• 橫軸表示在決策樹建立過程中樹的結點總數，縱軸表示決策樹的預測精度。
• 實線顯示的是決策樹在訓練集上的精度，虛線顯示的則是在一個獨立的測試集上測量出來的精度。
• 随着樹的增長，在訓練樣集上的精度是單調上升的， 然而在獨立的測試樣例上測出的精度先上升後下降。

出現這種情況的原因：

• 原因1：噪聲、樣本沖突，即錯誤的樣本資料。
• 原因2：特征即屬性不能完全作為分類标準。
• 原因3：巧合的規律性，資料量不夠大。

剪枝 (pruning)是決策樹學習算法對付"過拟合"的主要手段。

在決策樹學習中，為了盡可能正确分類訓練樣本，結點劃分過程将不斷重複，有時會造成決策樹分支過多，這時就可能因訓練樣本學得"太好"了，以緻于把訓練集自身的一些特點當作所有資料都具有的一般性質而導緻過拟合。是以，可通過主動去掉一些分支來降低過拟合的風險。

如何判斷決策樹泛化性能是否提升呢？

• 可使用前面介紹的留出法，即預留一部分資料用作"驗證集"以進行性 能評估。例如對下表的西瓜資料集，我們将其随機劃分為兩部分，其中編号為 {1，2，3，6， 7， 10， 14， 15， 16， 17} 的樣例組成訓練集，編号為 {4， 5， 8， 9， 11， 12， 13} 的樣例組成驗證集。

  

假定咱們采用資訊增益準則來劃分屬性選擇，則上表中訓練集将會生成一棵下面決策樹。

為便于讨論，我們對圈中的部分結點做了編号。

接下來，我們一起看一下，如何對這一棵樹進行剪枝。

2 常用的剪枝方法

決策樹剪枝的基本政策有"預剪枝" (pre-pruning)和"後剪枝"(post- pruning) 。

• 預剪枝是指在決策樹生成過程中，對每個結點在劃分前先進行估計，若目前結點的劃分不能帶來決策樹泛化性能提升，則停止劃分并将目前結點标記為葉結點;
• 後剪枝則是先從訓練集生成一棵完整的決策樹，然後自底向上地對非葉結點進行考察，若将該結點對應的子樹替換為葉結點能帶來決策樹泛化性能提升，則将該子樹替換為葉結點。

2.1 預剪枝

首先，基于資訊增益準則，我們會選取屬性"臍部"來對訓練集進行劃分，并産生 3 個分支，如下圖所示。然而，是否應該進行這個劃分呢？預剪枝要對劃分前後的泛化性能進行估計。

在劃分之前，所有樣例集中在根結點。

• 若不進行劃分，該結點将被标記為葉結點，其類别标記為訓練樣例數最多的類别，假設我們将這個葉結點标記為"好瓜"。
• 用前面表的驗證集對這個單結點決策樹進行評估。則編号為 {4，5，8} 的樣例被分類正确。另外 4個樣例分類錯誤，于是驗證集精度為 3 7 ∗ 100 % = 42.9 % \frac{3}{7}*100\% = 42.9\% 73​∗100%=42.9%

在用屬性"臍部"劃分之後，上圖中的結點2、3、4分别包含編号為 {1，2，3， 14}、 {6，7， 15， 17}、 {10， 16} 的訓練樣例，是以這 3 個結點分别被标記為葉結點"好瓜"、 “好瓜”、 “壞瓜”。

此時，驗證集中編号為 {4， 5， 8，11， 12} 的樣例被分類正确，驗證集精度為 5 7 ∗ 100 % = 71.4 % > 42.9 % \frac{5}{7}*100\% = 71.4\% > 42.9\% 75​∗100%=71.4%>42.9%于是，用"臍部"進行劃分得以确定。

然後，決策樹算法應該對結點2進行劃分，基于資訊增益準則将挑選出劃分屬性"色澤"。然而，在使用"色澤"劃分後，編号為 {5} 的驗證集樣本分類結果會由正确轉為錯誤，使得驗證集精度下降為 57.1 % 57.1\% 57.1%。于是，預剪枝政策将禁 止結點2被劃分。

對結點3，最優劃分屬性為"根蒂"，劃分後驗證集精度仍為 71.4 % 71.4\% 71.4%。這個 劃分不能提升驗證集精度，于是，預剪枝政策禁止結點3被劃分。

對結點4，其所含訓練樣例己屬于同一類，不再進行劃分.

于是，基于預剪枝政策從上表資料所生成的決策樹如上圖所示，其驗證集精度為 71.4%. 這是一棵僅有一層劃分的決策樹，亦稱"決策樹樁" (decision stump).

2.2 後剪枝

後剪枝先從訓練集生成一棵完整決策樹，繼續使用上面的案例，從前面計算，我們知前面構造的決策樹的驗證集精度為 42.9 % 42.9\% 42.9%

後剪枝首先考察結點6，若将其領銜的分支剪除則相當于把6替換為葉結點。替換後的葉結點包含編号為 {7， 15} 的訓練樣本，于是該葉結點的類别标記為"好瓜"，此時決策樹的驗證集精度提高至 57.1 % 57.1\% 57.1%。于是，後剪枝政策決定剪枝，如下圖所示。

然後考察結點5，若将其領銜的子樹替換為葉結點，則替換後的葉結點包含編号為 {6，7，15}的訓練樣例，葉結點類别标記為"好瓜’；此時決策樹驗證集精度仍為 57.1 % 57.1\% 57.1%。于是，可以不進行剪枝.

對結點2，若将其領銜的子樹替換為葉結點，則替換後的葉結點包含編号 為 {1， 2， 3， 14} 的訓練樣例，葉結點标記為"好瓜"此時決策樹的驗證集精度提高至 71.4 % 71.4\% 71.4%。于是，後剪枝政策決定剪枝.

對結點3和1，若将其領銜的子樹替換為葉結點，則所得決策樹的驗證集 精度分别為 71.4 % 71.4\% 71.4% 與 42.9 % 42.9\% 42.9%，均未得到提高，于是它們被保留。

最終，基于後剪枝政策所生成的決策樹就如上圖所示，其驗證集精度為 71.4 % 71.4\% 71.4%。

對比兩種剪枝方法，

• 後剪枝決策樹通常比預剪枝決策樹保留了更多的分支。
• 一般情形下，後剪枝決策樹的欠拟合風險很小，泛化性能往往優于預剪枝決策樹。
• 但後剪枝過程是在生成完全決策樹之後進行的。 并且要自底向上地對樹中的所有非葉結點進行逐一考察，是以其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大得多.

四、特征工程-特征提取

什麼是特征提取呢？

1 特征提取

1.1 定義

将任意資料（如文本或圖像）轉換為可用于機器學習的數字特征

注：特征值化是為了計算機更好的去了解資料

特征提取分類：

• 字典特征提取(特征離散化)
• 文本特征提取
• 圖像特征提取（深度學習将介紹）

1.2 特征提取API

sklearn.feature_extraction

2 字典特征提取

作用：對字典資料進行特征值化

sklearn.feature_extraction.DictVectorizer(sparse=True,…)

• DictVectorizer.fit_transform(X)
  • X:字典或者包含字典的疊代器傳回值
  • 傳回sparse矩陣
• DictVectorizer.get_feature_names() 傳回類别名稱

2.1 應用

我們對以下資料進行特征提取

[{'city': '北京','temperature':100},
{'city': '上海','temperature':60},
{'city': '深圳','temperature':30}]
           

2.2 流程分析

• 執行個體化類DictVectorizer
• 調用fit_transform方法輸入資料并轉換（注意傳回格式）

from sklearn.feature_extraction import DictVectorizer

def dict_demo():
    """
    對字典類型的資料進行特征抽取
    :return: None
    """
    data = [{'city': '北京','temperature':100}, 
    		{'city': '上海','temperature':60}, 
   			{'city': '深圳','temperature':30}]
    # 1、執行個體化一個轉換器類
    transfer = DictVectorizer(sparse=False)
    # 2、調用fit_transform
    data = transfer.fit_transform(data)
    print("傳回的結果:\n", data)
    # 列印特征名字
    print("特征名字：\n", transfer.get_feature_names())

    return None


dict_demo()
           

注意觀察沒有加上sparse=False參數的結果

傳回的結果:
  (0, 1)    1.0
  (0, 3)    100.0
  (1, 0)    1.0
  (1, 3)    60.0
  (2, 2)    1.0
  (2, 3)    30.0
特征名字：
 ['city=上海', 'city=北京', 'city=深圳', 'temperature']
           

這個結果并不是我們想要看到的，是以加上參數，得到想要的結果：

傳回的結果:
 [[   0.    1.    0.  100.]
 [   1.    0.    0.   60.]
 [   0.    0.    1.   30.]]
特征名字：
 ['city=上海', 'city=北京', 'city=深圳', 'temperature']
           

之前在學習pandas中的離散化的時候，也實作了類似的效果。我們把這個處理資料的技巧叫做”one-hot“編碼

2.3 總結

對于特征當中存在類别資訊的我們都會做one-hot編碼處理

3 文本特征提取

作用：對文本資料進行特征值化

sklearn.feature_extraction.text.CountVectorizer(stop_words=[])

• 傳回詞頻矩陣
• CountVectorizer.fit_transform(X)
  • X:文本或者包含文本字元串的可疊代對象
  • 傳回值:傳回sparse矩陣
• CountVectorizer.get_feature_names() 傳回值:單詞清單

sklearn.feature_extraction.text.TfidfVectorizer

3.1 應用

我們對以下資料進行特征提取

["life is short,i like python",
"life is too long,i dislike python"]
           

3.2 流程分析

• 執行個體化類CountVectorizer
• 調用fit_transform方法輸入資料并轉換 （注意傳回格式，利用toarray()進行sparse矩陣轉換array數組）

from sklearn.feature_extraction.text import CountVectorizer

def text_count_demo():
    """
    對文本進行特征抽取，countvetorizer
    :return: None
    """
    data = ["life is short,i like like python", "life is too long,i dislike python"]
    # 1、執行個體化一個轉換器類
    # transfer = CountVectorizer(sparse=False) # 注意,沒有sparse這個參數
    transfer = CountVectorizer()
    # 2、調用fit_transform
    data = transfer.fit_transform(data)
    print("文本特征抽取的結果：\n", data.toarray())
    print("傳回特征名字：\n", transfer.get_feature_names())

    return None
           

傳回結果：

文本特征抽取的結果：
 [[0 1 1 2 0 1 1 0]
 [1 1 1 0 1 1 0 1]]
傳回特征名字：
 ['dislike', 'is', 'life', 'like', 'long', 'python', 'short', 'too']
           

問題:如果我們将資料替換成中文？

那麼最終得到的結果是

為什麼會得到這樣的結果呢，仔細分析之後會發現英文預設是以空格分開的。其實就達到了一個分詞的效果，是以我們要對中文進行分詞處理

3.3 jieba分詞處理

jieba.cut()

：傳回詞語組成的生成器

3.4 案例分析

對以下三句話進行特征值化

今天很殘酷，明天更殘酷，後天很美好，
但絕對大部分是死在明天晚上，是以每個人不要放棄今天。

我們看到的從很遠星系來的光是在幾百萬年之前發出的，
這樣當我們看到宇宙時，我們是在看它的過去。

如果隻用一種方式了解某樣事物，你就不會真正了解它。
了解事物真正含義的秘密取決于如何将其與我們所了解的事物相聯系。
           

分析

• 準備句子，利用jieba.cut進行分詞
• 執行個體化CountVectorizer
• 将分詞結果變成字元串當作fit_transform的輸入值

from sklearn.feature_extraction.text import CountVectorizer
import jieba

def cut_word(text):
    """
    對中文進行分詞
    "我愛北京天安門"————>"我 愛 北京 天安門"
    :param text:
    :return: text
    """
    # 用結巴對中文字元串進行分詞
    text = " ".join(list(jieba.cut(text)))

    return text

def text_chinese_count_demo2():
    """
    對中文進行特征抽取
    :return: None
    """
    data = ["一種還是一種今天很殘酷，明天更殘酷，後天很美好，但絕對大部分是死在明天晚上，是以每個人不要放棄今天。",
            "我們看到的從很遠星系來的光是在幾百萬年之前發出的，這樣當我們看到宇宙時，我們是在看它的過去。",
            "如果隻用一種方式了解某樣事物，你就不會真正了解它。了解事物真正含義的秘密取決于如何将其與我們所了解的事物相聯系。"]
    # 将原始資料轉換成分好詞的形式
    text_list = []
    for sent in data:
        text_list.append(cut_word(sent))
    print(text_list)

    # 1、執行個體化一個轉換器類
    # transfer = CountVectorizer(sparse=False)
    transfer = CountVectorizer()
    # 2、調用fit_transform
    data = transfer.fit_transform(text_list)
    print("文本特征抽取的結果：\n", data.toarray())
    print("傳回特征名字：\n", transfer.get_feature_names())

    return None
           

傳回結果：

Building prefix dict from the default dictionary ...
Dumping model to file cache /var/folders/mz/tzf2l3sx4rgg6qpglfb035_r0000gn/T/jieba.cache
Loading model cost 1.032 seconds.
['一種 還是 一種 今天 很 殘酷 ， 明天 更 殘酷 ， 後天 很 美好 ， 但 絕對 大部分 是 死 在 明天 晚上 ， 是以 每個 人 不要 放棄 今天 。', '我們 看到 的 從 很 遠 星系 來 的 光是在 幾百萬年 之前 發出 的 ， 這樣 當 我們 看到 宇宙 時 ， 我們 是 在 看 它 的 過去 。', '如果 隻用 一種 方式 了解 某樣 事物 ， 你 就 不會 真正 了解 它 。 了解 事物 真正 含義 的 秘密 取決于 如何 将 其 與 我們 所 了解 的 事物 相 聯系 。']
Prefix dict has been built succesfully.
文本特征抽取的結果：
 [[2 0 1 0 0 0 2 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 2 0 1 0 2 1 0 0 0 1 1 0 0 1 0]
 [0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 3 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 1]
 [1 1 0 0 4 3 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 2 1 0 0 1 0 0 0]]
傳回特征名字：
 ['一種', '不會', '不要', '之前', '了解', '事物', '今天', '光是在', '幾百萬年', '發出', '取決于', '隻用', '後天', '含義', '大部分', '如何', '如果', '宇宙', '我們', '是以', '放棄', '方式', '明天', '星系', '晚上', '某樣', '殘酷', '每個', '看到', '真正', '秘密', '絕對', '美好', '聯系', '過去', '還是', '這樣']
           

但如果把這樣的詞語特征用于分類，會出現什麼問題？

請看問題：

該如何處理某個詞或短語在多篇文章中出現的次數高這種情況

3.5 Tf-idf文本特征提取

• TF-IDF的主要思想是：如果某個詞或短語在一篇文章中出現的機率高，并且在其他文章中很少出現， 則認為此詞或者短語具有很好的類别區分能力，适合用來分類。
• TF-IDF作用：用以評估一字詞對于一個檔案集或一個語料庫中的其中一份檔案的重要程度。

3.5.1 公式

• 詞頻（term frequency，tf）指的是某一個給定的詞語在該檔案中出現的頻率

• 逆向文檔頻率（inverse document frequency，idf）是一個詞語普遍重要性的度量。某一特定詞語的idf，可以由總檔案數目除以包含該詞語之檔案的數目，再将得到的商取以10為底的對數得到

  t f i d f i , j = t f i , j × i d f i tfidf_{i,j} = tf_{i,j} \times idf_i tfidfi,j​=tfi,j​×idfi​

  最終得出結果可以了解為重要程度。

舉例：
假如一篇文章的總詞語數是100個，而詞語"非常"出現了5次，那麼"非常"一詞在該檔案中的詞頻就是5/100=0.05。
而計算檔案頻率（IDF）的方法是以檔案集的檔案總數，除以出現"非常"一詞的檔案數。
是以，如果"非常"一詞在1,0000份檔案出現過，而檔案總數是10,000,000份的話，
其逆向檔案頻率就是lg（10,000,000 / 1,0000）=3。
最後"非常"對于這篇文檔的tf-idf的分數為0.05 * 3=0.15
           

3.5.2 案例

from sklearn.feature_extraction.text import TfidfVectorizer
import jieba

def cut_word(text):
    """
    對中文進行分詞
    "我愛北京天安門"————>"我 愛 北京 天安門"
    :param text:
    :return: text
    """
    # 用結巴對中文字元串進行分詞
    text = " ".join(list(jieba.cut(text)))

    return text

def text_chinese_tfidf_demo():
    """
    對中文進行特征抽取
    :return: None
    """
    data = ["一種還是一種今天很殘酷，明天更殘酷，後天很美好，但絕對大部分是死在明天晚上，是以每個人不要放棄今天。",
            "我們看到的從很遠星系來的光是在幾百萬年之前發出的，這樣當我們看到宇宙時，我們是在看它的過去。",
            "如果隻用一種方式了解某樣事物，你就不會真正了解它。了解事物真正含義的秘密取決于如何将其與我們所了解的事物相聯系。"]
    # 将原始資料轉換成分好詞的形式
    text_list = []
    for sent in data:
        text_list.append(cut_word(sent))
    print(text_list)

    # 1、執行個體化一個轉換器類
    # transfer = CountVectorizer(sparse=False)
    transfer = TfidfVectorizer(stop_words=['一種', '不會', '不要'])
    # 2、調用fit_transform
    data = transfer.fit_transform(text_list)
    print("文本特征抽取的結果：\n", data.toarray())
    print("傳回特征名字：\n", transfer.get_feature_names())

    return None
           

傳回結果：

Building prefix dict from the default dictionary ...
Loading model from cache /var/folders/mz/tzf2l3sx4rgg6qpglfb035_r0000gn/T/jieba.cache
Loading model cost 0.856 seconds.
Prefix dict has been built succesfully.
['一種 還是 一種 今天 很 殘酷 ， 明天 更 殘酷 ， 後天 很 美好 ， 但 絕對 大部分 是 死 在 明天 晚上 ， 是以 每個 人 不要 放棄 今天 。', '我們 看到 的 從 很 遠 星系 來 的 光是在 幾百萬年 之前 發出 的 ， 這樣 當 我們 看到 宇宙 時 ， 我們 是 在 看 它 的 過去 。', '如果 隻用 一種 方式 了解 某樣 事物 ， 你 就 不會 真正 了解 它 。 了解 事物 真正 含義 的 秘密 取決于 如何 将 其 與 我們 所 了解 的 事物 相 聯系 。']
文本特征抽取的結果：
 [[ 0.          0.          0.          0.43643578  0.          0.          0.
   0.          0.          0.21821789  0.          0.21821789  0.          0.
   0.          0.          0.21821789  0.21821789  0.          0.43643578
   0.          0.21821789  0.          0.43643578  0.21821789  0.          0.
   0.          0.21821789  0.21821789  0.          0.          0.21821789
   0.        ]
 [ 0.2410822   0.          0.          0.          0.2410822   0.2410822
   0.2410822   0.          0.          0.          0.          0.          0.
   0.          0.2410822   0.55004769  0.          0.          0.          0.
   0.2410822   0.          0.          0.          0.          0.48216441
   0.          0.          0.          0.          0.          0.2410822
   0.          0.2410822 ]
 [ 0.          0.644003    0.48300225  0.          0.          0.          0.
   0.16100075  0.16100075  0.          0.16100075  0.          0.16100075
   0.16100075  0.          0.12244522  0.          0.          0.16100075
   0.          0.          0.          0.16100075  0.          0.          0.
   0.3220015   0.16100075  0.          0.          0.16100075  0.          0.
   0.        ]]
傳回特征名字：
 ['之前', '了解', '事物', '今天', '光是在', '幾百萬年', '發出', '取決于', '隻用', '後天', '含義', '大部分', '如何', '如果', '宇宙', '我們', '是以', '放棄', '方式', '明天', '星系', '晚上', '某樣', '殘酷', '每個', '看到', '真正', '秘密', '絕對', '美好', '聯系', '過去', '還是', '這樣']
           

3.6 Tf-idf的重要性

分類機器學習算法進行文章分類中前期資料處理方式

五、決策樹算法api

class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)

• criterion
  • 特征選擇标準
  • “gini"或者"entropy”，前者代表基尼系數，後者代表資訊增益。一預設"gini"，即CART算法。
• min_samples_split
  • 内部節點再劃分所需最小樣本數
  • 這個值限制了子樹繼續劃分的條件，如果某節點的樣本數少于min_samples_split，則不會繼續再嘗試選擇最優特征來進行劃分。 預設是2，如果樣本量不大，不需要管這個值。如果樣本量數量級非常大，則推薦增大這個值。比如一個項目案例，有大概10萬樣本，建立決策樹時，選擇了min_samples_split=10。可以作為參考。
• min_samples_leaf
  • 葉子節點最少樣本數
  • 這個值限制了葉子節點最少的樣本數，如果某葉子節點數目小于樣本數，則會和兄弟節點一起被剪枝。 預設是1，可以輸入最少的樣本數的整數，或者最少樣本數占樣本總數的百分比。如果樣本量不大，不需要管這個值。如果樣本量數量級非常大，則推薦增大這個值。之前的10萬樣本項目使用min_samples_leaf的值為5，僅供參考。
• max_depth
  • 決策樹最大深度
  • 決策樹的最大深度，預設可以不輸入，如果不輸入的話，決策樹在建立子樹的時候不會限制子樹的深度。一般來說，資料少或者特征少的時候可以不管這個值。如果模型樣本量多，特征也多的情況下，推薦限制這個最大深度，具體的取值取決于資料的分布。常用的可以取值10-100之間
• random_state
  • 随機數種子

六、案例：泰坦尼克号乘客生存預測

1 案例背景

泰坦尼克号沉沒是曆史上最臭名昭着的沉船之一。1912年4月15日，在她的處女航中，泰坦尼克号在與冰山相撞後沉沒，在2224名乘客和機組人員中造成1502人死亡。這場聳人聽聞的悲劇震驚了國際社會，并為船舶制定了更好的安全規定。 造成海難失事的原因之一是乘客和機組人員沒有足夠的救生艇。盡管幸存下沉有一些運氣因素，但有些人比其他人更容易生存，例如婦女，兒童和上流社會。 在這個案例中，我們要求您完成對哪些人可能存活的分析。特别是，我們要求您運用機器學習工具來預測哪些乘客幸免于悲劇。

案例：https://www.kaggle.com/c/titanic/overview

經過觀察資料得到:

• 1 乘坐班是指乘客班（1，2，3），是社會經濟階層的代表。
• 2 其中age資料存在缺失。

2 步驟分析

1. 擷取資料

2. 資料基本處理

   2.1 确定特征值,目标值

   2.2 缺失值處理

   2.3 資料集劃分

3. 特征工程(字典特征抽取)
4. 機器學習(決策樹)
5. 模型評估

3 代碼實作

導入需要的子產品

import pandas as pd
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_graphviz
           

擷取資料

# 1、擷取資料
titanic= pd.read_csv("./data/train.csv")
           

資料基本處理

# 2.資料基本處理
# 2.1 确定特征值,目标值
x = titanic[["Pclass","Age","Sex"]]
y = titanic["Survived"]

# 2.2 缺失值處理
# 缺失值需要處理，将特征當中有類别的這些特征進行字典特征抽取
x["Age"].fillna(x["Age"].mean(), inplace=True)

# 2.3 資料集劃分
x_train,x_test,y_train,y_test = train_test_split(x,y,test_size=0.2,random_state=22)
           

特征工程(字典特征抽取)

# 3.特征工程(字典特征抽取)
# 對于x轉換成字典資料x.to_dict(orient="records")
# [{"pclass": "1st", "age": 29.00, "sex": "female"}, {}]

transfer = DictVectorizer(sparse=False)

x_train = transfer.fit_transform(x_train.to_dict(orient="records"))
x_test = transfer.transform(x_test.to_dict(orient="records"))
           

決策樹模型訓練和模型評估

# 4.機器學習(決策樹)
estimator = DecisionTreeClassifier(criterion="entropy", max_depth=5)
estimator.fit(x_train,y_train)

# 5.模型評估
estimator.score(x_test,y_test)

estimator.predict(x_test)
           

決策樹的結構是可以直接顯示

4 決策樹可視化

4.1 儲存樹的結構到dot檔案

sklearn.tree.export_graphviz() 該函數能夠導出DOT格式

• tree.export_graphviz(estimator,out_file='tree.dot’,feature_names=[‘’,’’])

# 6.決策樹可視化
export_graphviz(estimator, out_file="./data/tree.dot", feature_names=['Age','Pclass','Sex','Survived'])
           

dot檔案當中的内容如下

digraph Tree {
node [shape=box] ;
0 [label="Survived <= 0.5\nentropy = 0.96\nsamples = 712\nvalue = [439, 273]"] ;
1 [label="Pclass <= 2.5\nentropy = 0.802\nsamples = 250\nvalue = [61, 189]"] ;
0 -> 1 [labeldistance=2.5, labelangle=45, headlabel="True"] ;
2 [label="Age <= 27.5\nentropy = 0.264\nsamples = 134\nvalue = [6, 128]"] ;
1 -> 2 ;
3 [label="Age <= 23.5\nentropy = 0.496\nsamples = 46\nvalue = [5, 41]"] ;
2 -> 3 ;
4 [label="Age <= 2.5\nentropy = 0.206\nsamples = 31\nvalue = [1, 30]"] ;
3 -> 4 ;
5 [label="entropy = 1.0\nsamples = 2\nvalue = [1, 1]"] ;
4 -> 5 ;
6 [label="entropy = 0.0\nsamples = 29\nvalue = [0, 29]"] ;
4 -> 6 ;
7 [label="Age <= 24.5\nentropy = 0.837\nsamples = 15\nvalue = [4, 11]"] ;
3 -> 7 ;
8 [label="entropy = 0.592\nsamples = 7\nvalue = [1, 6]"] ;
7 -> 8 ;
9 [label="entropy = 0.954\nsamples = 8\nvalue = [3, 5]"] ;
7 -> 9 ;
10 [label="Age <= 56.5\nentropy = 0.09\nsamples = 88\nvalue = [1, 87]"] ;
2 -> 10 ;
11 [label="entropy = 0.0\nsamples = 82\nvalue = [0, 82]"] ;
10 -> 11 ;
12 [label="Pclass <= 1.5\nentropy = 0.65\nsamples = 6\nvalue = [1, 5]"] ;
10 -> 12 ;
13 [label="entropy = 0.0\nsamples = 5\nvalue = [0, 5]"] ;
12 -> 13 ;
14 [label="entropy = 0.0\nsamples = 1\nvalue = [1, 0]"] ;
12 -> 14 ;
15 [label="Age <= 38.5\nentropy = 0.998\nsamples = 116\nvalue = [55, 61]"] ;
1 -> 15 ;
16 [label="Age <= 1.5\nentropy = 0.988\nsamples = 108\nvalue = [47, 61]"] ;
15 -> 16 ;
17 [label="entropy = 0.0\nsamples = 4\nvalue = [0, 4]"] ;
16 -> 17 ;
18 [label="Age <= 32.5\nentropy = 0.993\nsamples = 104\nvalue = [47, 57]"] ;
16 -> 18 ;
19 [label="entropy = 0.997\nsamples = 100\nvalue = [47, 53]"] ;
18 -> 19 ;
20 [label="entropy = 0.0\nsamples = 4\nvalue = [0, 4]"] ;
18 -> 20 ;
21 [label="entropy = 0.0\nsamples = 8\nvalue = [8, 0]"] ;
15 -> 21 ;
22 [label="Age <= 13.0\nentropy = 0.684\nsamples = 462\nvalue = [378, 84]"] ;
0 -> 22 [labeldistance=2.5, labelangle=-45, headlabel="False"] ;
23 [label="Pclass <= 2.5\nentropy = 0.948\nsamples = 30\nvalue = [11, 19]"] ;
22 -> 23 ;
24 [label="entropy = 0.0\nsamples = 11\nvalue = [0, 11]"] ;
23 -> 24 ;
25 [label="Age <= 0.71\nentropy = 0.982\nsamples = 19\nvalue = [11, 8]"] ;
23 -> 25 ;
26 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1]"] ;
25 -> 26 ;
27 [label="Age <= 11.5\nentropy = 0.964\nsamples = 18\nvalue = [11, 7]"] ;
25 -> 27 ;
28 [label="entropy = 0.937\nsamples = 17\nvalue = [11, 6]"] ;
27 -> 28 ;
29 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1]"] ;
27 -> 29 ;
30 [label="Pclass <= 1.5\nentropy = 0.611\nsamples = 432\nvalue = [367, 65]"] ;
22 -> 30 ;
31 [label="Age <= 60.5\nentropy = 0.888\nsamples = 95\nvalue = [66, 29]"] ;
30 -> 31 ;
32 [label="Age <= 47.5\nentropy = 0.922\nsamples = 83\nvalue = [55, 28]"] ;
31 -> 32 ;
33 [label="entropy = 0.874\nsamples = 68\nvalue = [48, 20]"] ;
32 -> 33 ;
34 [label="entropy = 0.997\nsamples = 15\nvalue = [7, 8]"] ;
32 -> 34 ;
35 [label="Age <= 75.5\nentropy = 0.414\nsamples = 12\nvalue = [11, 1]"] ;
31 -> 35 ;
36 [label="entropy = 0.0\nsamples = 11\nvalue = [11, 0]"] ;
35 -> 36 ;
37 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1]"] ;
35 -> 37 ;
38 [label="Age <= 32.25\nentropy = 0.49\nsamples = 337\nvalue = [301, 36]"] ;
30 -> 38 ;
39 [label="Age <= 30.75\nentropy = 0.535\nsamples = 254\nvalue = [223, 31]"] ;
38 -> 39 ;
40 [label="entropy = 0.483\nsamples = 239\nvalue = [214, 25]"] ;
39 -> 40 ;
41 [label="entropy = 0.971\nsamples = 15\nvalue = [9, 6]"] ;
39 -> 41 ;
42 [label="Age <= 41.5\nentropy = 0.328\nsamples = 83\nvalue = [78, 5]"] ;
38 -> 42 ;
43 [label="entropy = 0.156\nsamples = 44\nvalue = [43, 1]"] ;
42 -> 43 ;
44 [label="entropy = 0.477\nsamples = 39\nvalue = [35, 4]"] ;
42 -> 44 ;
}
           

那麼這個結構不能看清結構，是以可以在一個網站上顯示

4.2 網站顯示結構

網站：點我

将上述dot代碼複制進去，就可以看到樹木的圖像了

5 決策樹總結

• 優點：

  簡單的了解和解釋，樹木可視化。

• 缺點：

  決策樹學習者可以建立不能很好地推廣資料的過于複雜的樹,容易發生過拟合。

• 改進：

  減枝cart算法

  随機森林（內建學習的一種）

• 注：企業重要決策，由于決策樹很好的分析能力，在決策過程應用較多， 可以選擇特征

七、回歸決策樹

前面已經講到，關于資料類型，我們主要可以把其分為兩類，連續型資料和離散型資料。在面對不同資料時，決策樹也可以分為兩大類型：

• 分類決策樹和回歸決策樹。
• 前者主要用于處理離散型資料，後者主要用于處理連續型資料。

1.原理概述

不管是回歸決策樹還是分類決策樹，都會存在兩個核心問題：

• 如何選擇劃分點？
• 如何決定葉節點的輸出值？

一個回歸樹對應着輸入空間（即特征空間）的一個劃分以及在劃分單元上的輸出值。分類樹中，我們采用資訊論中的方法，通過計算選擇最佳劃分點。

而在回歸樹中，采用的是啟發式的方法。假如我們有n個特征，每個特征有 s i ( i ∈ ( 1 , n ) ) s_i (i\in (1,n)) si​(i∈(1,n)) 個取值，那我們周遊所有特征，嘗試該特征所有取值，對空間進行劃分，直到取到特征 j 的取值 s，使得損失函數最小，這樣就得到了一個劃分點。 描述該過程的公式如下

假設将輸入空間劃分為M個單元： R 1 , R 2 , . . . , R m R_1,R_2,...,R_m R1​,R2​,...,Rm​ 那麼每個區域的輸出值就是： c m = a v g ( y i ∣ x i ∈ R m ) c_m=avg(y_i|x_i\in R_m) cm​=avg(yi​∣xi​∈Rm​) 也就是該區域内所有點y值的平均數。

舉例：

如下圖，假如我們想要對樓内居民的年齡進行回歸，将樓劃分為3個區域 R 1 , R 2 , R 3 R_1,R_2,R_3 R1​,R2​,R3​（紅線）

那麼 R 1 R_1 R1​ 的輸出就是第一列四個居民年齡的平均值，

R 2 R_2 R2​的輸出就是第二列四個居民年齡的平均值，

R 3 R_3 R3​的輸出就是第三、四列八個居民年齡的平均值。

2.算法描述

3.簡單執行個體

為了易于了解，接下來通過一個簡單執行個體加深對回歸決策樹的了解。

訓練資料見下表，目标是得到一棵最小二乘回歸樹。

x	1	2	3	4	5	6	7	8	9	10
y	5.56	5.7	5.91	6.4	6.8	7.05	8.9	8.7	9	9.05

3.1 執行個體計算過程

（1）選擇最優的切分特征 j 與最優切分點 s

• 确定第一個問題：選擇最優切分特征：
  • 在本資料集中，隻有一個特征，是以最優切分特征自然是x。
• 确定第二個問題：我們考慮9個切分點 [1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5]
  • 損失函數定義為平方損失函數 L o s s ( y , f ( x ) ) = ( f ( x ) − y ) 2 Loss(y,f(x))=(f(x)-y)^2 Loss(y,f(x))=(f(x)−y)2，将上述9個切分點依此代入公式，其中 c m = a v g ( y i ∣ x i ∈ R m ) c_m=avg(yi|xi\in R_m) cm​=avg(yi∣xi∈Rm​)

a、計算子區域輸出值：

例如，取 s = 1.5 s=1.5 s=1.5。此時 R 1 = 1 ， R 2 = 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 R1={1}，R2={2,3,4,5,6,7,8,9,10} R1=1，R2=2,3,4,5,6,7,8,9,10，這兩個區域的輸出值分别為：

• c 1 = 5.56 c1=5.56 c1=5.56
• c 2 = ( 5.7 + 5.91 + 6.4 + 6.8 + 7.05 + 8.9 + 8.7 + 9 + 9.05 ) / 9 = 7.50 c2=(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)/9=7.50 c2=(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)/9=7.50

同理，得到其他各切分點的子區域輸出值，如下表：

s	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5
m(s)	15.72	12.07	8.36	5.78	3.91	1.93	8.01	11.73	15.74

顯然取 s = 6.5 s=6.5 s=6.5 時， m ( s ) m(s) m(s) 最小。是以，第一個劃分變量 【 j = x , s = 6.5 】 【j=x,s=6.5】 【j=x,s=6.5】

（2）用標明的(j,s)劃分區域，并決定輸出值

• 兩個區域分别是： R 1 = { 1 , 2 , 3 , 4 , 5 , 6 } ， R 2 = { 7 , 8 , 9 , 10 } R1=\{1,2,3,4,5,6\}，R2=\{7,8,9,10\} R1={1,2,3,4,5,6}，R2={7,8,9,10}
• 輸出值 c m = a v g ( y i ∣ x i ∈ R m ) , c 1 = 6.24 , c 2 = 8.91 c_m=avg(yi|xi\in Rm),c1=6.24,c2=8.91 cm​=avg(yi∣xi∈Rm),c1=6.24,c2=8.91

（3）調用步驟 (1)、(2)，繼續劃分

對 R 1 R1 R1 繼續進行劃分：

x	1	2	3	4	5	6
y	5.56	5.7	5.91	6.4	6.8	7.05

取切分點[1.5,2.5,3.5,4.5,5.5]，則各區域的輸出值c如下表

s	1.5	2.5	3.5	4.5	5.5
c1	5.56	5.63	5.72	5.89	6.07
c2	6.37	6.54	6.75	6.93	7.05

計算損失函數值m(s)：

s	1.5	2.5	3.5	4.5	5.5
m(s)	1.3087	0.754	0.2771	0.4368	1.0644

s = 3.5 s=3.5 s=3.5時， m ( s ) m(s) m(s)最小。

（4）生成回歸樹

3.2 回歸決策樹和線性回歸對比

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
from sklearn import linear_model

# 生成資料
x = np.array(list(range(1, 11))).reshape(-1, 1)
y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])

# 訓練模型
model1 = DecisionTreeRegressor(max_depth=1)
model2 = DecisionTreeRegressor(max_depth=3)
model3 = linear_model.LinearRegression()
model1.fit(x, y)
model2.fit(x, y)
model3.fit(x, y)

# 模型預測
X_test = np.arange(0.0, 10.0, 0.01).reshape(-1, 1)  # 生成1000個數,用于預測模型
X_test.shape
y_1 = model1.predict(X_test)
y_2 = model2.predict(X_test)
y_3 = model3.predict(X_test)

# 結果可視化
plt.figure(figsize=(10, 6), dpi=100)
plt.scatter(x, y, label="data")
plt.plot(X_test, y_1,label="max_depth=1")
plt.plot(X_test, y_2, label="max_depth=3")
plt.plot(X_test, y_3, label='liner regression')

plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()

plt.show()
           

結果展示：

上一篇：機器學習： 邏輯回歸

下一篇：機器學習： 內建學習