決策樹說通俗點就是一棵能夠替我們做決策的樹，或者說是我們人類在要做決策時腦回路的一種表現形式。

本實訓項目的主要內容是基于 python 語言搭建出決策樹模型對數據分類，并使用 sklearn 的決策時模型對鳶尾花數據進行分類。

第1關：什么是決策樹

• 任務描述
• 相關知識
  • 引例
  • 決策樹的相關概念
• 編程要求
• 測試說明

---

任務描述

本關任務：根據本節課所學知識完成本關所設置的選擇題。

相關知識

為了完成本關任務，你需要掌握決策樹的相關基礎知識。

引例

在炎熱的夏天，沒有什么比冰鎮后的西瓜更能令人感到心曠神怡的了。現在我要去水果店買西瓜，但什么樣的西瓜能入我法眼呢？那根據我的個人習慣，在挑西瓜時可能就有這樣的腦回路。

假設現在水果店里有3個西瓜，它們的屬性如下：

編號瓤是否夠紅夠不夠冰是否便宜是否有籽

1	是	否	是	否
2	是	是	否	是
3	否	是	是	否

那么根據我的腦回路我會買1和2號西瓜。

其實我的腦回路可以看成一棵樹，并且這棵樹能夠幫助我對買不買西瓜這件事做決策，所以它就是一棵決策樹。

決策樹的相關概念

決策樹是一種可以用于分類與回歸的機器學習算法，但主要用于分類。用于分類的決策樹是一種描述對實例進行分類的樹形結構。決策樹由結點和邊組成，其中結點分為內部結點和葉子結點，內部結點表示一個特征或者屬性，葉子結點表示標簽（腦回路圖中黃色的是內部結點，藍色的是葉子結點）。

從代碼角度來看，決策樹其實可以看成是一堆if-else語句的集合，例如引例中的決策樹完全可以看成是如下代碼：

if isRed:

if isCold:

if hasSeed:

print("buy")

else:

print("don't buy")

else:

if isCheap:

print("buy")

else:

print("don't buy")

else:

print("don't buy")

因此決策樹的一個非常大的優勢就是模型的可理解性非常高，甚至可以用來挖掘數據中比較重要的信息。

那么如何構造出一棵好的決策樹呢？其實構造決策樹時會遵循一個指標，有的是按照信息增益來構建，如ID3算法；有的是信息增益率來構建，如C4.5算法；有的是按照基尼系數來構建的，如CART算法。但不管是使用哪種構建算法，決策樹的構建過程通常都是一個遞歸選擇最優特征，并根據特征對訓練集進行分割，使得對各個子數據集有一個最好的分類的過程。

這一過程對應著對特征空間的劃分，也對應著決策樹的構建。一開始，構建決策樹的根結點，將所有訓練數據都放在根結點。選擇一個最優特征，并按照這一特征將訓練數據集分割成子集，使得各個子集有一個在當前條件下最好的分類。如果這些子集已經能夠被基本正確分類，那么構建葉子結點，并將這些子集分到所對應的葉結點中去；如果還有子集不能被基本正確分類，那么就對這些子集選擇新的最優特征，繼續對其進行分割，并構建相應的結點。如此遞歸進行下去，直至所有訓練數據子集被基本正確分類，或者沒有合適的特征為止。最后每個子集都被分到葉子結點上，即都有了明確的類別。這就構建出了一棵決策樹。

編程要求

根據本關所學習到的知識，完成所有選擇題。

測試說明

平臺會對你的選項進行判斷，如果實際輸出結果與預期結果相同，則通關；反之，則 GameOver。

---

開始你的任務吧，祝你成功！

• 1、下列說法正確的是？（AB）

  A、

  訓練決策樹的過程就是構建決策樹的過程

  B、

  ID3算法是根據信息增益來構建決策樹

  C、

  C4.5算法是根據基尼系數來構建決策樹

  D、

  決策樹模型的可理解性不高

• 2、下列說法錯誤的是？（B）

  A、

  從樹的根節點開始，根據特征的值一步一步走到葉子節點的過程是決策樹做決策的過程

  B、

  決策樹只能是一棵二叉樹

  C、

  根節點所代表的特征是最優特征

第2關：信息熵與信息增益

• 任務描述
• 相關知識
  • 信息熵
  • 條件熵
  • 信息增益
• 編程要求
• 測試說明

---

任務描述

本關任務：掌握什么是信息增益，完成計算信息增益的程序設計。

相關知識

為了完成本關任務，你需要掌握：

• 信息熵；

• 條件熵；

• 信息增益。

信息熵

信息是個很抽象的概念。人們常常說信息很多，或者信息較少，但卻很難說清楚信息到底有多少。比如一本五十萬字的中文書到底有多少信息量。

直到1948年，香農提出了“信息熵”的概念，才解決了對信息的量化度量問題。信息熵這個詞是香農從熱力學中借用過來的。熱力學中的熱熵是表示分子狀態混亂程度的物理量。香農用信息熵的概念來描述信源的不確定度。信源的不確定性越大，信息熵也越大。

從機器學習的角度來看，信息熵表示的是信息量的期望值。如果數據集中的數據需要被分成多個類別，則信息量I(xi?)的定義如下(其中xi?表示多個類別中的第i個類別，p(xi?)數據集中類別為xi?的數據在數據集中出現的概率表示)：

I(Xi?)=?log2?p(xi?)

由于信息熵是信息量的期望值，所以信息熵H(X)的定義如下(其中n為數據集中類別的數量)：

H(X)=?sumi=1n?p(xi?)log2?p(xi?)

從這個公式也可以看出，如果概率是0或者是1的時候，熵就是0（因為這種情況下隨機變量的不確定性是最低的）。那如果概率是0.5，也就是五五開的時候，此時熵達到最大，也就是1。（就像扔硬幣，你永遠都猜不透你下次扔到的是正面還是反面，所以它的不確定性非常高）。所以呢，熵越大，不確定性就越高。

條件熵

在實際的場景中，我們可能需要研究數據集中某個特征等于某個值時的信息熵等于多少，這個時候就需要用到條件熵。條件熵H(Y|X)表示特征X為某個值的條件下，類別為Y的熵。條件熵的計算公式如下：

H(Y∣X)=sumi=1n?pi?H(Y∣X=xi?)

當然條件熵的性質也和熵的性質一樣，概率越確定，條件熵就越小，概率越五五開，條件熵就越大。

信息增益

現在已經知道了什么是熵，什么是條件熵。接下來就可以看看什么是信息增益了。所謂的信息增益就是表示我已知條件X后能得到信息Y的不確定性的減少程度。

就好比，我在玩讀心術。你心里想一件東西，我來猜。我已開始什么都沒問你，我要猜的話，肯定是瞎猜。這個時候我的熵就非常高。然后我接下來我會去試著問你是非題，當我問了是非題之后，我就能減小猜測你心中想到的東西的范圍，這樣其實就是減小了我的熵。那么我熵的減小程度就是我的信息增益。

所以信息增益如果套上機器學習的話就是，如果把特征A對訓練集D的信息增益記為g(D, A)的話，那么g(D, A)的計算公式就是：

$$g(D,A)=H(D)?H(D,A)$$

為了更好的解釋熵，條件熵，信息增益的計算過程，下面通過示例來描述。假設我現在有這一個數據集，第一列是編號，第二列是性別，第三列是活躍度，第四列是客戶是否流失的標簽（0表示未流失，1表示流失）。

編號性別活躍度是否流失

1	男	高	0
2	女	中	0
3	男	低	1
4	女	高	0
5	男	高	0
6	男	中	0
7	男	中	1
8	女	中	0
9	女	低	1
10	女	中	0
11	女	高	0
12	男	低	1
13	女	低	1
14	男	高	0
15	男	高	0

假如要算性別和活躍度這兩個特征的信息增益的話，首先要先算總的熵和條件熵。總的熵其實非常好算，就是把標簽作為隨機變量X。上表中標簽只有兩種（0和1）因此隨機變量X的取值只有0或者1。所以要計算熵就需要先分別計算標簽為0的概率和標簽為1的概率。從表中能看出標簽為0的數據有10條，所以標簽為0的概率等于2/3。標簽為1的概率為1/3。所以熵為：

$$?(1/3)?log(1/3)?(2/3)?log(2/3)=0.9182$$

接下來就是條件熵的計算，以性別為男的熵為例。表格中性別為男的數據有8條，這8條數據中有3條數據的標簽為1，有5條數據的標簽為0。所以根據條件熵的計算公式能夠得出該條件熵為：

$$?(3/8)?log(3/8)?(5/8)?log(5/8)=0.9543$$

根據上述的計算方法可知，總熵為：

$$?(5/15)?log(5/15)?(10/15)?log(10/15)=0.9182$$

性別為男的熵為：

$$?(3/8)?log(3/8)?(5/8)?log(5/8)=0.9543$$

性別為女的熵為：

$$?(2/7)?log(2/7)?(5/7)?log(5/7)=0.8631$$

活躍度為低的熵為：

$$?(4/4)?log(4/4)?0=0$$

活躍度為中的熵為：

$$?(1/5)?log(1/5)?(4/5)?log(4/5)=0.7219$$

活躍度為高的熵為：

$$?0?(6/6)?log(6/6)=0$$

現在有了總的熵和條件熵之后就能算出性別和活躍度這兩個特征的信息增益了。

性別的信息增益=總的熵-(8/15)*性別為男的熵-(7/15)*性別為女的熵=0.0064

*活躍度的信息增益=總的熵-(6/15)活躍度為高的熵-(5/15)*活躍度為中的熵-(4/15)*活躍度為低的熵=0.6776

那信息增益算出來之后有什么意義呢？回到讀心術的問題，為了我能更加準確的猜出你心中所想，我肯定是問的問題越好就能猜得越準！換句話來說我肯定是要想出一個信息增益最大（減少不確定性程度最高）的問題來問你。其實ID3算法也是這么想的。ID3算法的思想是從訓練集D中計算每個特征的信息增益，然后看哪個最大就選哪個作為當前結點。然后繼續重復剛剛的步驟來構建決策樹。

編程要求

根據提示，在右側編輯器補充代碼，完成calcInfoGain函數實現計算信息增益。

calcInfoGain函數中的參數:

• feature：測試用例中字典里的feature，類型為ndarray；

• label：測試用例中字典里的label，類型為ndarray；

• index：測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。

測試說明

平臺會對你編寫的代碼進行測試，期望您的代碼根據輸入來輸出正確的信息增益，以下為其中一個測試用例：

測試輸入： {'feature':[[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]], 'label':[0, 1, 0, 0, 1], 'index': 0}

預期輸出： 0.419973

提示： 計算log可以使用NumPy中的log2函數

---

開始你的任務吧，祝你成功！

import numpy as npdef calcInfoGain(feature, label, index):'''計算信息增益:param feature:測試用例中字典里的feature，類型為ndarray:param label:測試用例中字典里的label，類型為ndarray:param index:測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。:return:信息增益，類型float'''#*********** Begin ***********## 計算熵def calcInfoEntropy(feature, label):'''計算信息熵:param feature:數據集中的特征，類型為ndarray:param label:數據集中的標簽，類型為ndarray:return:信息熵，類型float'''label_set = set(label)result = 0for l in label_set:count = 0for j in range(len(label)):if label[j] == l:count += 1# 計算標簽在數據集中出現的概率p = count / len(label)# 計算熵result -= p * np.log2(p)return result# 計算條件熵def calcHDA(feature, label, index, value):'''計算信息熵:param feature:數據集中的特征，類型為ndarray:param label:數據集中的標簽，類型為ndarray:param index:需要使用的特征列索引，類型為int:param value:index所表示的特征列中需要考察的特征值，類型為int:return:信息熵，類型float'''count = 0# sub_feature和sub_label表示根據特征列和特征值分割出的子數據集中的特征和標簽sub_feature = []sub_label = []for i in range(len(feature)):if feature[i][index] == value:count += 1sub_feature.append(feature[i])sub_label.append(label[i])pHA = count / len(feature)e = calcInfoEntropy(sub_feature, sub_label)return pHA * ebase_e = calcInfoEntropy(feature, label)f = np.array(feature)# 得到指定特征列的值的集合f_set = set(f[:, index])sum_HDA = 0# 計算條件熵for value in f_set:sum_HDA += calcHDA(feature, label, index, value)# 計算信息增益return base_e - sum_HDA#*********** End *************#

第3關：使用ID3算法構建決策樹

• 任務描述
• 相關知識
  • ID3算法
  • 使用決策樹進行預測
• 編程要求
• 測試說明

---

任務描述

本關任務：補充python代碼，完成DecisionTree類中的fit和predict函數。

相關知識

為了完成本關任務，你需要掌握：

• ID3算法構造決策樹的流程；

• 如何使用構造好的決策樹進行預測。

ID3算法

ID3算法其實就是依據特征的信息增益來構建樹的。其大致步驟就是從根結點開始，對結點計算所有可能的特征的信息增益，然后選擇信息增益最大的特征作為結點的特征，由該特征的不同取值建立子結點，然后對子結點遞歸執行上述的步驟直到信息增益很小或者沒有特征可以繼續選擇為止。

因此，ID3算法偽代碼如下：

#假設數據集為D，標簽集為A，需要構造的決策樹為tree

def ID3(D, A):

if D中所有的標簽都相同:

return 標簽

if 樣本中只有一個特征或者所有樣本的特征都一樣:

對D中所有的標簽進行計數

return 計數最高的標簽

計算所有特征的信息增益

選出增益最大的特征作為最佳特征(best_feature)

將best_feature作為tree的根結點

得到best_feature在數據集中所有出現過的值的集合(value_set)

for value in value_set:

從D中篩選出best_feature=value的子數據集(sub_feature)

從A中篩選出best_feature=value的子標簽集(sub_label)

#遞歸構造tree

tree[best_feature][value] = ID3(sub_feature, sub_label)

return tree

使用決策樹進行預測

決策樹的預測思想非常簡單，假設現在已經構建出了一棵用來決策是否買西瓜的決策樹。

并假設現在在水果店里有這樣一個西瓜，其屬性如下：

瓤是否夠紅夠不夠冰是否便宜是否有籽

是	否	是	否

那買不買這個西瓜呢？只需把西瓜的屬性代入決策樹即可。決策樹的根結點是瓤是否夠紅，所以就看西瓜的屬性，經查看發現夠紅，因此接下來就看夠不夠冰。而西瓜不夠冰，那么看是否便宜。發現西瓜是便宜的，所以這個西瓜是可以買的。

因此使用決策樹進行預測的偽代碼也比較簡單，偽代碼如下：

#tree表示決策樹，feature表示測試數據

def predict(tree, feature):

if tree是葉子結點:

return tree

根據feature中的特征值走入tree中對應的分支

if 分支依然是課樹:

result = predict(分支, feature)

return result

編程要求

填寫fit(self, feature, label)函數，實現ID3算法，要求決策樹保存在self.tree中。其中：

• feature：訓練集數據，類型為ndarray，數值全為整數；

• label：訓練集標簽，類型為ndarray，數值全為整數。

填寫predict(self, feature)函數，實現預測功能，并將標簽返回，其中：

• feature：測試集數據，類型為ndarray，數值全為整數。（PS：feature中有多條數據）

測試說明

只需完成fit與predict函數即可，程序內部會調用您所完成的fit函數構建模型并調用predict函數來對數據進行預測。預測的準確率高于0.92視為過關。(PS:若self.tree is None則會打印決策樹構建失敗)

---

開始你的任務吧，祝你成功！

import numpy as np class DecisionTree(object):def __init__(self):#決策樹模型self.tree = {}def calcInfoGain(self, feature, label, index):'''計算信息增益:param feature:測試用例中字典里的feature，類型為ndarray:param label:測試用例中字典里的label，類型為ndarray:param index:測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。:return:信息增益，類型float'''# 計算熵def calcInfoEntropy(label):'''計算信息熵:param label:數據集中的標簽，類型為ndarray:return:信息熵，類型float'''label_set = set(label)result = 0for l in label_set:count = 0for j in range(len(label)):if label[j] == l:count += 1# 計算標簽在數據集中出現的概率p = count / len(label)# 計算熵result -= p * np.log2(p)return result# 計算條件熵def calcHDA(feature, label, index, value):'''計算信息熵:param feature:數據集中的特征，類型為ndarray:param label:數據集中的標簽，類型為ndarray:param index:需要使用的特征列索引，類型為int:param value:index所表示的特征列中需要考察的特征值，類型為int:return:信息熵，類型float'''count = 0# sub_feature和sub_label表示根據特征列和特征值分割出的子數據集中的特征和標簽sub_feature = []sub_label = []for i in range(len(feature)):if feature[i][index] == value:count += 1sub_feature.append(feature[i])sub_label.append(label[i])pHA = count / len(feature)e = calcInfoEntropy(sub_label)return pHA * ebase_e = calcInfoEntropy(label)f = np.array(feature)# 得到指定特征列的值的集合f_set = set(f[:, index])sum_HDA = 0# 計算條件熵for value in f_set:sum_HDA += calcHDA(feature, label, index, value)# 計算信息增益return base_e - sum_HDA# 獲得信息增益最高的特征def getBestFeature(self, feature, label):max_infogain = 0best_feature = 0for i in range(len(feature[0])):infogain = self.calcInfoGain(feature, label, i)if infogain > max_infogain:max_infogain = infogainbest_feature = ireturn best_featuredef createTree(self, feature, label):# 樣本里都是同一個label沒必要繼續分叉了if len(set(label)) == 1:return label[0]# 樣本中只有一個特征或者所有樣本的特征都一樣的話就看哪個label的票數高if len(feature[0]) == 1 or len(np.unique(feature, axis=0)) == 1:vote = {}for l in label:if l in vote.keys():vote[l] += 1else:vote[l] = 1max_count = 0vote_label = Nonefor k, v in vote.items():if v > max_count:max_count = vvote_label = kreturn vote_label# 根據信息增益拿到特征的索引best_feature = self.getBestFeature(feature, label)tree = {best_feature: {}}f = np.array(feature)# 拿到bestfeature的所有特征值f_set = set(f[:, best_feature])# 構建對應特征值的子樣本集sub_feature, sub_labelfor v in f_set:sub_feature = []sub_label = []for i in range(len(feature)):if feature[i][best_feature] == v:sub_feature.append(feature[i])sub_label.append(label[i])# 遞歸構建決策樹tree[best_feature][v] = self.createTree(sub_feature, sub_label)return treedef fit(self, feature, label):''':param feature: 訓練集數據，類型為ndarray:param label:訓練集標簽，類型為ndarray:return: None'''#************* Begin ************#self.tree = self.createTree(feature, label)#************* End **************#def predict(self, feature):''':param feature:測試集數據，類型為ndarray:return:預測結果，如np.array([0, 1, 2, 2, 1, 0])'''#************* Begin ************#result = []def classify(tree, feature):if not isinstance(tree, dict):return treet_index, t_value = list(tree.items())[0]f_value = feature[t_index]if isinstance(t_value, dict):classLabel = classify(tree[t_index][f_value], feature)return classLabelelse:return t_valuefor f in feature:result.append(classify(self.tree, f))return np.array(result)#************* End **************#

第4關：信息增益率

• 任務描述
• 相關知識
  • 信息增益率
• 編程要求
• 測試說明

---

任務描述

本關任務：根據本關所學知識，完成calcInfoGainRatio函數。

相關知識

為了完成本關任務，你需要掌握：信息增益率

信息增益率

由于在使用信息增益這一指標進行劃分時，更喜歡可取值數量較多的特征。為了減少這種偏好可能帶來的不利影響，Ross Quinlan使用了信息增益率這一指標來選擇最優劃分屬性。

信息增益率的數學定義為如下，其中$D$表示數據集，$a$表示數據集中的某一列，$Gain(D,a)$表示$D$中$a$的信息增益，$V$表示$a$這一列中取值的集合，$v$表示$V$中的某種取值，$|D|$表示$D$中樣本的數量，∣Dv∣表示$D$中$a$這一列中值等于$v$的數量。

Gain_ratio(D,a)=?v=1∑V?∣D∣∣Dv∣?log2?∣D∣∣Dv∣?Gain(D,a)?

從公式可以看出，信息增益率很好算，只是用信息增益除以另一個分母，該分母通常稱為固有值。舉個例子，還是使用第二關中提到過的數據集，第一列是編號，第二列是性別，第三列是活躍度，第四列是客戶是否流失的標簽（0表示未流失，1表示流失）。

編號性別活躍度是否流失

1	男	高	0
2	女	中	0
3	男	低	1
4	女	高	0
5	男	高	0
6	男	中	0
7	男	中	1
8	女	中	0
9	女	低	1
10	女	中	0
11	女	高	0
12	男	低	1
13	女	低	1
14	男	高	0
15	男	高	0

根據第二關已經知道性別的信息增益為$0.0064$，設$a$為性別，則有$Gain(D,a)=0.0064$。由根據數據可知，$V=2$，假設當$v=1$時表示性別為男，$v=2$時表示性別為女，則有$|D|=15$，∣D1∣=8，∣D2∣=7。因此根據信息增益率的計算公式可知Gainr?atio(D,a)=0.0642。同理可以算出活躍度的信息增益率為$0.4328$。

編程要求

根據提示，在右側編輯器補充代碼，完成calcInfoGainRatio函數實現計算信息增益。

calcInfoGainRatio函數中的參數:

• feature：測試用例中字典里的feature，類型為ndarray；

• label：測試用例中字典里的label，類型為ndarray；

• index：測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益率。

測試說明

平臺會對你編寫的代碼進行測試，期望您的代碼根據輸入來輸出正確的信息增益，以下為其中一個測試用例：

測試輸入： {'feature':[[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]], 'label':[0, 1, 0, 0, 1], 'index': 0}

預期輸出： 0.432538

提示： 計算log可以使用NumPy中的log2函數

---

開始你的任務吧，祝你成功！

import numpy as npdef calcInfoGain(feature, label, index):'''計算信息增益:param feature:測試用例中字典里的feature，類型為ndarray:param label:測試用例中字典里的label，類型為ndarray:param index:測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。:return:信息增益，類型float'''# 計算熵def calcInfoEntropy(label):'''計算信息熵:param label:數據集中的標簽，類型為ndarray:return:信息熵，類型float'''label_set = set(label)result = 0for l in label_set:count = 0for j in range(len(label)):if label[j] == l:count += 1# 計算標簽在數據集中出現的概率p = count / len(label)# 計算熵result -= p * np.log2(p)return result# 計算條件熵def calcHDA(feature, label, index, value):'''計算信息熵:param feature:數據集中的特征，類型為ndarray:param label:數據集中的標簽，類型為ndarray:param index:需要使用的特征列索引，類型為int:param value:index所表示的特征列中需要考察的特征值，類型為int:return:信息熵，類型float'''count = 0# sub_feature和sub_label表示根據特征列和特征值分割出的子數據集中的特征和標簽sub_feature = []sub_label = []for i in range(len(feature)):if feature[i][index] == value:count += 1sub_feature.append(feature[i])sub_label.append(label[i])pHA = count / len(feature)e = calcInfoEntropy(sub_label)return pHA * ebase_e = calcInfoEntropy(label)f = np.array(feature)# 得到指定特征列的值的集合f_set = set(f[:, index])sum_HDA = 0# 計算條件熵for value in f_set:sum_HDA += calcHDA(feature, label, index, value)# 計算信息增益return base_e - sum_HDAdef calcInfoGainRatio(feature, label, index):'''計算信息增益率:param feature:測試用例中字典里的feature，類型為ndarray:param label:測試用例中字典里的label，類型為ndarray:param index:測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。:return:信息增益率，類型float'''#********* Begin *********#info_gain = calcInfoGain(feature, label, index)unique_value = list(set(feature[:, index]))IV = 0for value in unique_value:len_v = np.sum(feature[:, index] == value)IV -= (len_v/len(feature))*np.log2((len_v/len(feature)))return info_gain/IV#********* End *********#

第5關：基尼系數

• 任務描述
• 相關知識
  • 基尼系數
• 編程要求
• 測試說明

---

任務描述

本關任務：根據本關所學知識，完成calcGini函數。

相關知識

為了完成本關任務，你需要掌握：基尼系數。

基尼系數

在ID3算法中我們使用了信息增益來選擇特征，信息增益大的優先選擇。在C4.5算法中，采用了信息增益率來選擇特征，以減少信息增益容易選擇特征值多的特征的問題。但是無論是ID3還是C4.5,都是基于信息論的熵模型的，這里面會涉及大量的對數運算。能不能簡化模型同時也不至于完全丟失熵模型的優點呢？當然有！那就是基尼系數！

CART算法使用基尼系數來代替信息增益率，基尼系數代表了模型的不純度，基尼系數越小，則不純度越低，特征越好。這和信息增益與信息增益率是相反的(它們都是越大越好)。

基尼系數的數學定義為如下，其中$D$表示數據集，pk?表示D中第k個類別在D中所占比例。

Gini(D)=1?sumk=1∣y∣?pk2?

從公式可以看出，相比于信息增益和信息增益率，計算起來更加簡單。舉個例子，還是使用第二關中提到過的數據集，第一列是編號，第二列是性別，第三列是活躍度，第四列是客戶是否流失的標簽（0表示未流失，1表示流失）。

編號性別活躍度是否流失

1	男	高	0
2	女	中	0
3	男	低	1
4	女	高	0
5	男	高	0
6	男	中	0
7	男	中	1
8	女	中	0
9	女	低	1
10	女	中	0
11	女	高	0
12	男	低	1
13	女	低	1
14	男	高	0
15	男	高	0

從表格可以看出，$D$中總共有$2$個類別，設類別為$0$的比例為p1?，則有p1?=1510?。設類別為$1$的比例為p2?，則有p2?=155?。根據基尼系數的公式可知Gini(D)=1?(p12?+p22?)=0.4444。

上面是基于數據集D的基尼系數的計算方法，那么基于數據集D與特征a的基尼系數怎樣計算呢？其實和信息增益率的套路差不多。計算公式如下：

Gini(D,a)=sumv=1V?∣D∣∣Dv∣?Gini(Dv)

還是以用戶流失的數據為例，現在算一算性別的基尼系數。設性別男為$v=1$，性別女為$v=2$則有$|D|=15$，∣D1∣=8，∣D2∣=7，Gini(D1)=0.46875，Gini(D2)=0.40816。所以$Gini(D,a)=0.44048$。

編程要求

根據提示，在右側編輯器補充代碼，完成calcGini函數實現計算信息增益。

calcGini函數中的參數:

• feature：測試用例中字典里的feature，類型為ndarray；

• label：測試用例中字典里的label，類型為ndarray；

• index：測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算基尼系數。

測試說明

平臺會對你編寫的代碼進行測試，期望您的代碼根據輸入來輸出正確的信息增益，以下為其中一個測試用例：

測試輸入： {'feature':[[0, 1], [1, 0], [1, 2], [0, 0], [1, 1]], 'label':[0, 1, 0, 0, 1], 'index': 0}

預期輸出： 0.266667

---

開始你的任務吧，祝你成功！

import numpy as np def calcGini(feature, label, index):'''計算基尼系數:param feature:測試用例中字典里的feature，類型為ndarray:param label:測試用例中字典里的label，類型為ndarray:param index:測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。:return:基尼系數，類型float'''#********* Begin *********#def _gini(label):unique_label = list(set(label))gini = 1for l in unique_label:p = np.sum(label == l)/len(label)gini -= p**2return giniunique_value = list(set(feature[:, index]))gini = 0for value in unique_value:len_v = np.sum(feature[:, index] == value)gini += (len_v/len(feature))*_gini(label[feature[:, index] == value])return gini#********* End *********#

第6關：預剪枝與后剪枝

• 任務描述
• 相關知識
  • 為什么需要剪枝
  • 預剪枝
  • 后剪枝
• 編程要求
• 測試說明

---

任務描述

本關任務：補充python代碼，完成DecisionTree類中的fit和predict函數。

相關知識

為了完成本關任務，你需要掌握：

• 為什么需要剪枝；

• 預剪枝；

• 后剪枝。

為什么需要剪枝

決策樹的生成是遞歸地去構建決策樹，直到不能繼續下去為止。這樣產生的樹往往對訓練數據有很高的分類準確率，但對未知的測試數據進行預測就沒有那么準確了，也就是所謂的過擬合。

決策樹容易過擬合的原因是在構建決策樹的過程時會過多地考慮如何提高對訓練集中的數據的分類準確率，從而會構建出非常復雜的決策樹（樹的寬度和深度都比較大）。在之前的實訓中已經提到過，模型的復雜度越高，模型就越容易出現過擬合的現象。所以簡化決策樹的復雜度能夠有效地緩解過擬合現象，而簡化決策樹最常用的方法就是剪枝。剪枝分為預剪枝與后剪枝。

預剪枝

預剪枝的核心思想是在決策樹生成過程中，對每個結點在劃分前先進行一個評估，若當前結點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當前結點標記為葉結點。

想要評估決策樹算法的泛化性能如何，方法很簡單。可以將訓練數據集中隨機取出一部分作為驗證數據集，然后在用訓練數據集對每個結點進行劃分之前用當前狀態的決策樹計算出在驗證數據集上的正確率。正確率越高說明決策樹的泛化性能越好，如果在劃分結點的時候發現泛化性能有所下降或者沒有提升時，說明應該停止劃分，并用投票計數的方式將當前結點標記成葉子結點。

舉個例子，假如上一關中所提到的用來決定是否買西瓜的決策樹模型已經出現過擬合的情況，模型如下：

假設當模型在劃分是否便宜這個結點前，模型在驗證數據集上的正確率為0.81。但在劃分后，模型在驗證數據集上的正確率降為0.67。此時就不應該劃分是否便宜這個結點。所以預剪枝后的模型如下：

從上圖可以看出，預剪枝能夠降低決策樹的復雜度。這種預剪枝處理屬于貪心思想，但是貪心有一定的缺陷，就是可能當前劃分會降低泛化性能，但在其基礎上進行的后續劃分卻有可能導致性能顯著提高。所以有可能會導致決策樹出現欠擬合的情況。

后剪枝

后剪枝是先從訓練集生成一棵完整的決策樹，然后自底向上地對非葉結點進行考察，若將該結點對應的子樹替換為葉結點能夠帶來決策樹泛化性能提升，則將該子樹替換為葉結點。

后剪枝的思路很直接，對于決策樹中的每一個非葉子結點的子樹，我們嘗試著把它替換成一個葉子結點，該葉子結點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產生了一個簡化決策樹，然后比較這兩個決策樹在測試數據集中的表現，如果簡化決策樹在驗證數據集中的準確率有所提高，那么該子樹就可以替換成葉子結點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數據集的表現得以改進時，算法就可以終止。

從后剪枝的流程可以看出，后剪枝是從全局的角度來看待要不要剪枝，所以造成欠擬合現象的可能性比較小。但由于后剪枝需要先生成完整的決策樹，然后再剪枝，所以后剪枝的訓練時間開銷更高。

編程要求

填寫fit(self, train_feature, train_label, val_featrue, val_label)函數，實現帶后剪枝的ID3算法，要求決策樹保存在self.tree中。其中：

• train_feature：訓練集數據，類型為ndarray，數值全為整數；

• train_label：訓練集標簽，類型為ndarray，數值全為整數；

• val_feature：驗證集數據，類型為ndarray，數值全為整數；

• val_label：驗證集標簽，類型為ndarray，數值全為整數。

填寫predict(self, feature)函數，實現預測功能，并將標簽返回，其中：

• feature：測試集數據，類型為ndarray，數值全為整數。（PS：feature中有多條數據）

測試說明

只需完成fit與predict函數即可，程序內部會調用您所完成的fit函數構建模型并調用predict函數來對數據進行預測。預測的準確率高于0.935視為過關。(PS:若self.tree is None則會打印決策樹構建失敗)

import numpy as np from copy import deepcopyclass DecisionTree(object):def __init__(self):#決策樹模型self.tree = {}def calcInfoGain(self, feature, label, index):'''計算信息增益:param feature:測試用例中字典里的feature，類型為ndarray:param label:測試用例中字典里的label，類型為ndarray:param index:測試用例中字典里的index，即feature部分特征列的索引。該索引指的是feature中第幾個特征，如index:0表示使用第一個特征來計算信息增益。:return:信息增益，類型float'''# 計算熵def calcInfoEntropy(feature, label):'''計算信息熵:param feature:數據集中的特征，類型為ndarray:param label:數據集中的標簽，類型為ndarray:return:信息熵，類型float'''label_set = set(label)result = 0for l in label_set:count = 0for j in range(len(label)):if label[j] == l:count += 1# 計算標簽在數據集中出現的概率p = count / len(label)# 計算熵result -= p * np.log2(p)return result# 計算條件熵def calcHDA(feature, label, index, value):'''計算信息熵:param feature:數據集中的特征，類型為ndarray:param label:數據集中的標簽，類型為ndarray:param index:需要使用的特征列索引，類型為int:param value:index所表示的特征列中需要考察的特征值，類型為int:return:信息熵，類型float'''count = 0# sub_feature和sub_label表示根據特征列和特征值分割出的子數據集中的特征和標簽sub_feature = []sub_label = []for i in range(len(feature)):if feature[i][index] == value:count += 1sub_feature.append(feature[i])sub_label.append(label[i])pHA = count / len(feature)e = calcInfoEntropy(sub_feature, sub_label)return pHA * ebase_e = calcInfoEntropy(feature, label)f = np.array(feature)# 得到指定特征列的值的集合f_set = set(f[:, index])sum_HDA = 0# 計算條件熵for value in f_set:sum_HDA += calcHDA(feature, label, index, value)# 計算信息增益return base_e - sum_HDA# 獲得信息增益最高的特征def getBestFeature(self, feature, label):max_infogain = 0best_feature = 0for i in range(len(feature[0])):infogain = self.calcInfoGain(feature, label, i)if infogain > max_infogain:max_infogain = infogainbest_feature = ireturn best_feature# 計算驗證集準確率def calc_acc_val(self, the_tree, val_feature, val_label):result = []def classify(tree, feature):if not isinstance(tree, dict):return treet_index, t_value = list(tree.items())[0]f_value = feature[t_index]if isinstance(t_value, dict):classLabel = classify(tree[t_index][f_value], feature)return classLabelelse:return t_valuefor f in val_feature:result.append(classify(the_tree, f))result = np.array(result)return np.mean(result == val_label)def createTree(self, train_feature, train_label):# 樣本里都是同一個label沒必要繼續分叉了if len(set(train_label)) == 1:return train_label[0]# 樣本中只有一個特征或者所有樣本的特征都一樣的話就看哪個label的票數高if len(train_feature[0]) == 1 or len(np.unique(train_feature, axis=0)) == 1:vote = {}for l in train_label:if l in vote.keys():vote[l] += 1else:vote[l] = 1max_count = 0vote_label = Nonefor k, v in vote.items():if v > max_count:max_count = vvote_label = kreturn vote_label# 根據信息增益拿到特征的索引best_feature = self.getBestFeature(train_feature, train_label)tree = {best_feature: {}}f = np.array(train_feature)# 拿到bestfeature的所有特征值f_set = set(f[:, best_feature])# 構建對應特征值的子樣本集sub_feature, sub_labelfor v in f_set:sub_feature = []sub_label = []for i in range(len(train_feature)):if train_feature[i][best_feature] == v:sub_feature.append(train_feature[i])sub_label.append(train_label[i])# 遞歸構建決策樹tree[best_feature][v] = self.createTree(sub_feature, sub_label)return tree# 后剪枝def post_cut(self, val_feature, val_label):# 拿到非葉子節點的數量def get_non_leaf_node_count(tree):non_leaf_node_path = []def dfs(tree, path, all_path):for k in tree.keys():if isinstance(tree[k], dict):path.append(k)dfs(tree[k], path, all_path)if len(path) > 0:path.pop()else:all_path.append(path[:])dfs(tree, [], non_leaf_node_path)unique_non_leaf_node = []for path in non_leaf_node_path:isFind = Falsefor p in unique_non_leaf_node:if path == p:isFind = Truebreakif not isFind:unique_non_leaf_node.append(path)return len(unique_non_leaf_node)# 拿到樹中深度最深的從根節點到非葉子節點的路徑def get_the_most_deep_path(tree):non_leaf_node_path = []def dfs(tree, path, all_path):for k in tree.keys():if isinstance(tree[k], dict):path.append(k)dfs(tree[k], path, all_path)if len(path) > 0:path.pop()else:all_path.append(path[:])dfs(tree, [], non_leaf_node_path)max_depth = 0result = Nonefor path in non_leaf_node_path:if len(path) > max_depth:max_depth = len(path)result = pathreturn result# 剪枝def set_vote_label(tree, path, label):for i in range(len(path)-1):tree = tree[path[i]]tree[path[len(path)-1]] = vote_labelacc_before_cut = self.calc_acc_val(self.tree, val_feature, val_label)# 遍歷所有非葉子節點for _ in range(get_non_leaf_node_count(self.tree)):path = get_the_most_deep_path(self.tree)# 備份樹tree = deepcopy(self.tree)step = deepcopy(tree)# 跟著路徑走for k in path:step = step[k]# 葉子節點中票數最多的標簽vote_label = sorted(step.items(), key=lambda item: item[1], reverse=True)[0][0]# 在備份的樹上剪枝set_vote_label(tree, path, vote_label)acc_after_cut = self.calc_acc_val(tree, val_feature, val_label)# 驗證集準確率高于0.9才剪枝if acc_after_cut > acc_before_cut:set_vote_label(self.tree, path, vote_label)acc_before_cut = acc_after_cutdef fit(self, train_feature, train_label, val_feature, val_label):''':param train_feature:訓練集數據，類型為ndarray:param train_label:訓練集標簽，類型為ndarray:param val_feature:驗證集數據，類型為ndarray:param val_label:驗證集標簽，類型為ndarray:return: None'''#************* Begin ************#self.tree = self.createTree(train_feature, train_label)# 后剪枝self.post_cut(val_feature, val_label)#************* End **************#def predict(self, feature):''':param feature:測試集數據，類型為ndarray:return:預測結果，如np.array([0, 1, 2, 2, 1, 0])'''#************* Begin ************#result = []# 單個樣本分類def classify(tree, feature):if not isinstance(tree, dict):return treet_index, t_value = list(tree.items())[0]f_value = feature[t_index]if isinstance(t_value, dict):classLabel = classify(tree[t_index][f_value], feature)return classLabelelse:return t_valuefor f in feature:result.append(classify(self.tree, f))return np.array(result)#************* End **************#

第7關：鳶尾花識別

• 任務描述
• 相關知識
  • 數據簡介
  • DecisionTreeClassifier
• 編程要求
• 測試說明

---

任務描述

本關任務：使用sklearn完成鳶尾花分類任務。

相關知識

為了完成本關任務，你需要掌握如何使用sklearn提供的DecisionTreeClassifier。

數據簡介

鳶尾花數據集是一類多重變量分析的數據集。通過花萼長度，花萼寬度，花瓣長度，花瓣寬度4個屬性預測鳶尾花卉屬于(Setosa，Versicolour，Virginica)三個種類中的哪一類(其中分別用0，1，2代替)。

數據集中部分數據與標簽如下圖所示：

DecisionTreeClassifier

DecisionTreeClassifier的構造函數中有兩個常用的參數可以設置：

• criterion:劃分節點時用到的指標。有gini（基尼系數）,entropy(信息增益)。若不設置，默認為gini
• max_depth:決策樹的最大深度，如果發現模型已經出現過擬合，可以嘗試將該參數調小。若不設置，默認為None

和sklearn中其他分類器一樣，DecisionTreeClassifier類中的fit函數用于訓練模型，fit函數有兩個向量輸入：

• X：大小為[樣本數量,特征數量]的ndarray，存放訓練樣本；

• Y：值為整型，大小為[樣本數量]的ndarray，存放訓練樣本的分類標簽。

DecisionTreeClassifier類中的predict函數用于預測，返回預測標簽，predict函數有一個向量輸入：

• X：大小為[樣本數量,特征數量]的ndarray，存放預測樣本。

DecisionTreeClassifier的使用代碼如下：

from sklearn.tree import DecisionTreeClassifier

clf = tree.DecisionTreeClassifier()

clf.fit(X_train, Y_train)

result = clf.predict(X_test)

編程要求

補充python代碼，實現鳶尾花數據的分類任務，其中訓練集數據保存在./step7/train_data.csv中，訓練集標簽保存在。./step7/train_label.csv中，測試集數據保存在。./step7/test_data.csv中。請將對測試集的預測結果保存至。./step7/predict.csv中。這些csv文件可以使用pandas讀取與寫入。

注意：當使用pandas讀取完csv文件后，請將讀取到的DataFrame轉換成ndarray類型。這樣才能正常的使用fit和predict。

示例代碼：

import pandas as pd

# as_matrix()可以將DataFrame轉換成ndarray

# 此時train_df的類型為ndarray而不是DataFrame

train_df = pd.read_csv('train_data.csv').as_matrix()

數據文件格式如下圖所示:

標簽文件格式如下圖所示:

PS：predict.csv文件的格式必須與標簽文件格式一致。

測試說明

只需將結果保存至./step7/predict.csv即可，程序內部會檢測您的代碼，預測準確率高于0.95視為過關。

---

開始你的任務吧，祝你成功！

#********* Begin *********# import pandas as pd from sklearn.tree import DecisionTreeClassifiertrain_df = pd.read_csv('./step7/train_data.csv').as_matrix() train_label = pd.read_csv('./step7/train_label.csv').as_matrix() test_df = pd.read_csv('./step7/test_data.csv').as_matrix()dt = DecisionTreeClassifier() dt.fit(train_df, train_label) result = dt.predict(test_df)result = pd.DataFrame({'target':result}) result.to_csv('./step7/predict.csv', index=False)#********* End *********#

總結

以上是生活随笔為你收集整理的EduCoder 机器学习 决策树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。