第一章概論西華大學機器學習第六章決策樹XXX學校XXX2022目錄Contents模型介紹魚類和非魚類判定貸款權限判定

知識引入3

本章知識圖譜4模型介紹一1.1決策樹概述6

決策樹是一種基本的分類和回歸方法。決策樹呈樹形結構，在分類問題中，表示基于特征對實例進行分類的過程。它可以認為是if-then規則的集合，也可以認為是定義在特征空間和類空間上的條件概率分布。學習時，利用訓練數據，根據損失函數最小化的原則建立決策樹模型。預測時，對新的數據，利用決策樹模型進行分類。決策樹學習通常包括三個步驟：特征選擇、決策樹的生成和決策樹的剪枝。決策樹可以看作為一個條件概率模型，因此決策樹的深度就代表了模型的復雜度，決策樹的生成代表了尋找局部最優模型，決策樹的剪枝代表了尋找全局最優模型。1.決策樹定義

分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點(node)和有向邊(directededge)組成。結點有兩種類型：內部結點(internalnode)和葉結點(leafnode)。內部結點表示一個特征或屬性(features)，葉結點表示一個類(labels)。1.1決策樹概述72.決策樹應用場景

游戲應用，參與游戲的一方在腦海中想某個事物，其他參與者向他提問，只允許提20個問題，問題的答案也只能用對或錯回答。提問的人通過推斷分解，逐步縮小待猜測事物的范圍，最后得到游戲的答案。3.決策樹結構1.1決策樹概述8

決策樹算法的學習通常是一個遞歸選擇最優特征，并根據該特征對訓練數據進行分割，使得各個子數據集有一個最好的分類的過程。這一過程對應著對特征空間的劃分，也對應著決策樹的構建。構建決策樹的具體過程如下：(1)構建根節點，將所有數據放在根節點，選擇一個最優的特征，按照這一特征將訓練數據集劃分為多個子集。(2)判斷，如果一個子集中的所有實例均為一類，即通過根節點所選的特征值已經能夠將此部分數據正確分類，那么就構建葉節點。(3)判斷，如果一個子集中的實例不能夠被正確分類，那么遞歸地對這些子集進行選擇最優特征，并進行分類，構建相應節點，不斷遞歸下去，直到所劃分的子集能夠被正確分類并構建出葉子節點為止。4.決策樹的構建1.1決策樹概述95.決策樹的剪枝后剪枝：對生成的數據進行剪枝，去掉過于細分的葉節點，使其退回到父節點，甚至更高的節點，并將父節點或更高的節點作為葉節點。預剪枝：若輸入的訓練數據集特征較多，也可以挑選出對數據分類影響最大的幾類特征作為分類特征，從而減小決策樹的復雜度。1.1決策樹概述105.決策樹的剪枝常用預剪枝方法：(1)定義一個高度，當決策樹達到該高度時就停止決策樹的生長。(2)達到某個結點的實例具有相同的特征向量，即使這些實例不屬于同一類，也可以停止決策樹的生長。這個方法對于處理數據的沖突問題比較有效。(3)定義一個閾值，當達到某個結點的實例個數小于閾值時就可以停止決策樹的生長。(4)定義一個閾值，通過計算每次擴張對系統性能的增益，并比較增益值與該閾值大小來決定是否停止決策樹的生長。1.1決策樹概述115.決策樹的剪枝常用后剪枝方法：(1)Reduced-ErrorPruning(REP,錯誤率降低剪枝)，該剪枝方法考慮將樹上的每個節點作為修剪的候選對象，決定是否修剪這個結點由如下步驟組成： a.刪除以此結點為根的子樹，使其成為葉子結點； b.

賦予該結點關聯的訓練數據的最常見分類； c.

當修剪后的樹對于驗證集合的性能不會比原來的樹差時，才真正刪除該結點。1.1決策樹概述125.決策樹的剪枝常用后剪枝方法：(2)Pesimistic-ErrorPruning(PEP,悲觀錯誤剪枝)。悲觀錯誤剪枝法是根據剪枝前后的錯誤率來判定子樹的修剪，先計算規則在它應用的訓練樣例上的精度，然后假定此估計精度為二項式分布，并計算它的標準差。對于給定的置信區間，采用下界估計作為規則性能的度量。1.1決策樹概述135.決策樹的剪枝

1.1決策樹概述145.決策樹的剪枝常用后剪枝方法：(4)Error-BasedPruning(EBP基于錯誤的剪枝)。這種剪枝方法的步驟如下： a.計算葉節點的錯分樣本率估計的置信區間上限U。 b.計算葉節點的預測錯分樣本數。葉節點的預測錯分樣本數=到達該葉節點的樣本數×該葉節點的預測錯分樣本率U。 c.判斷是否剪枝及如何剪枝。此步驟需要分別計算三種預測錯分樣本數：計算子樹t的所有葉節點預測錯分樣本數之和，記為E1。計算子樹t被剪枝以葉節點代替時的預測錯分樣本數，記為E2。計算子樹t的最大分枝的預測錯分樣本數，記為E3。

然后按照如下規則比較E1，E2，E3：E1最小時，不剪枝。E2最小時，進行剪枝，以一個葉節點代替t。E3最小時，采用“嫁接”(grafting)策略，即用這個最大分枝代替t。1.1決策樹概述155.決策樹的剪枝常用后剪枝方法：(4)Error-BasedPruning(EBP基于錯誤的剪枝)。這種剪枝方法的步驟如下：c.判斷是否剪枝及如何剪枝。此步驟需要分別計算三種預測錯分樣本數：計算子樹t的所有葉節點預測錯分樣本數之和，記為E1。計算子樹t被剪枝以葉節點代替時的預測錯分樣本數，記為E2。計算子樹t的最大分枝的預測錯分樣本數，記為E3。

然后按照如下規則比較E1，E2，E3：E1最小時，不剪枝。E2最小時，進行剪枝，以一個葉節點代替t。E3最小時，采用“嫁接”(grafting)策略，即用這個最大分枝代替t。1.1決策樹概述166.決策樹算法的特點決策樹的優點：(1)其結構能方便地進行可視化，便于理解和解釋。(2)能處理數值型數據和非數值型數據，對缺失值也不敏感，能處理不相關的特征，因此對預處理的要求不高，數據準備工作相對簡單。(3)訓練需要的數據量少，計算量小，效率相對較高。決策樹的缺點：(1)適用范圍有限，擅長對人、地點、事物的一系列不同特征、品質、特性進行評估，但對連續性特征較難預測，當類別太多時，錯誤可能增加較快。(2)容易出現過擬合。(3)忽略了屬性之間的相關性，在處理特征關聯性比較強的數據時表現得不是太好。1.1決策樹概述177.Python中包含決策樹的常用庫classsklearn.tree.DecisionTreeClassifier(criterion='gini',splitter='best',max_depth=None,min_samples_split=2,min_samples_leaf=1,min_weight_fraction_leaf=0.0,max_features=None,random_state=None,max_leaf_nodes=None,min_impurity_decrease=0.0,class_weight=None,ccp_alpha=0.0)

決策樹的構建可以通過sklearn庫中的DecisionTreeClassifier類來構建，在最新的1.0.2版本的sklearn庫中，該類的構造函數定義為：1.1決策樹概述18函數參數描述參數描述criterion用于測量拆分質量的函數splitter用于在每個節點上選擇拆分的策略max_depth表示樹的最大深度，即樹的層數，整型變量min_samples_split表示內部節點再劃分所需最小樣本數，整型或浮點型min_samples_leaf表示葉節點上所需要的最小樣本數，整型或浮點型min_weight_fraction_leaf葉子節點最小的樣本權重和，整型或浮點型max_features劃分時考慮的最大特征數，默認是Nonerandom_state隨機數種子，其取值可以是整型、RandomState實例或Nonemax_leaf_nodes最大葉子節點數，整型，默認是Nonemin_impurity_decrease節點劃分最小不純度減少值，浮點型class_weight類別權重，默認是None，也可以字典、字典列表或balancedccp_alpha用于最小成本-復雜性修剪的復雜度參數，非負浮點數1.2決策樹數學基礎

191.信息熵

香農借鑒了熱力學的概念，把信息中排除了冗余后的平均信息量稱為“信息熵”。信息熵(entropy)具有以下三個性質：(1)單調性，發生概率越高的事件，其攜帶的信息量越低。(2)非負性，信息熵可以看作為一種廣度量，非負性是一種合理的必然。(3)累加性，即多隨機事件同時發生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和，這也是廣度量的一種體現。1.2決策樹數學基礎

201.信息熵

1.2決策樹數學基礎

212.條件熵

1.2決策樹數學基礎

223.信息增益

劃分數據集的大原則是將無序數據變得更加有序，在劃分數據集前后信息發生的變化稱為信息增益(InformationGain)。簡單來說信息增益就是熵和特征條件熵的差。

1.2決策樹數學基礎

234.信息增益比

1.2決策樹數學基礎

245.基尼系數

1.3決策樹算法

25三種決策樹算法的應用領域及所使用的準則：1.3決策樹算法

26決策樹算法分類表決策樹算法算法描述ID3算法其核心是在決策樹的各級節點上，使用信息增益方法作為屬性的選擇標準，來幫助確定生成每個節點時所應采用的合適屬性C4.5算法C4.5決策樹生成算法相對于ID3算法的重要改進是使用信息增益率來選擇節點屬性。該方法可以克服ID3存在的不足：ID3只適用于離散的屬性，而C4.5既能處理離散的屬性，也能處理連續的屬性CART算法CART決策樹是一種十分有效的非參數分類和回歸方法，通過構建樹、修剪樹、評估樹來構建一個二叉樹。當終節點是連續變量時，該樹為回歸樹；當終節點是離散變量時，該樹為分類樹1.3決策樹算法

27ID3算法：

它選擇當前樣本集中具有最大信息增益值的屬性作為測試屬性；樣本集的劃分則根據測試屬性的取值進行，測試屬性有多少不同取值，就將樣本集劃分為多少子樣本集，同時決策樹上與該樣本集相應的節點長出新的葉子節點。ID3算法根據信息論理論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標準，用信息增益值度量不確定性：信息增益值越大，不確定性越小。(1)ID3算法的具體方法為：a.從根結點開始，對結點計算所有可能的特征的信息增益，選擇信息增益最大的特征作為結點的特征。b.由該特征的不同取值建立子節點，再對子結點遞歸地調用以上方法，構建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止。1.3決策樹算法

28ID3算法：

1.3決策樹算法

29ID3算法：

案例：魚類和非魚類判定二2.1案例介紹31在此案例中，需要根據以下兩個特征，將動物分成兩類：魚類和非魚類。特征一：不浮出水面是否可以生存。特征一：是否有腳蹼。數據如下表：ID不浮出水面是否可以生存是否有腳蹼是否是魚1是是是2是是是3是否否4否是否5否是否2.2案例實現321.

生成數據集

將表6-2中“不浮出水面是否可以生存”和“是否有腳蹼”這兩列數據特征中的“是”用“1”、“否”用“0”代替。類別標簽“是否為魚類”中的“是”用“yes”、“否”用“no”代替。data_set=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]

labels=['nosurfacing','flippers']2.2案例實現332.

計算給定數據集的香農熵

遍歷給定數據集的最后一列數據，創建類別標簽計數字典，最后依據公式計算香農熵。函數返回香農熵。創建類目計數字典香農熵計算2.2案例實現343.

劃分數據集

這個函數的是作用是當我們按某個特征劃分數據集時，把劃分后剩下的元素抽取出來，形成一個新的子集，用于計算條件熵。

#判斷axis值是否等于value

#遍歷數據集，將axis上的數據和value值進行比對

ret_data_set=[]

forfeat_vecindata_set:

iffeat_vec[axis]==value:

reduce_feat_vec=feat_vec[:axis]

reduce_feat_vec.extend(feat_vec[axis+1:])

ret_data_set.append(reduce_feat_vec)

returnret_data_set

該函數通過遍歷dataSet數據集,求出index對應的column列的值為value的行，然后依據index列進行分類，如果index列的數據等于value的時候，就要將index劃分到創建的新數據集中。該函數的返回值為index列為value的數據集(該數據集需要排除axis列)。2.2案例實現353.

劃分數據集

代碼中extend和append的區別：music_media.append(object)向列表中添加一個對象objectmusic_media.extend(sequence)把一個序列seq的內容添加到列表中(跟+=在list運用類似，music_media+=sequence)1、使用append時是將object看作一個對象，整體打包添加到music_media對象中。2、使用extend時是將sequence看作一個序列，將這個序列和music_media序列合并，并放在其后面。ID參數名稱釋義1dataSet待劃分的數據集2axis表示每一行的index列，特征的坐標，等于0，第0個特征為0或者13value表示index列對應的value值需要返回的特征的值2.2案例實現364.

選擇最好的數據集劃分方式的函數

接下來將遍歷整個數據集，循環計算香農熵，找到最好的特征劃分方式，并劃分數據集。熵計算將會告訴我們如何劃分數據集是最好的數據組織方式。外循環（遍歷特征，計算每個特征的信息增益）內循環（累加計算條件熵）比較信息增益，更新最佳信息增益值與最佳特征索引值輸出最優特征索引，函數返回最優索引值2.2案例實現375.遞歸構建決策樹

1）majorityCnt()函數篩選出現次數最多的分類標簽名稱創建類目計數字典倒序排序，取出出現次數最多的結果2.2案例實現385.遞歸構建決策樹

2）創建createTree()函數，遞歸地創建決策樹。調用函數得出最佳特征索引值從特征類別列表取出特征值，創建根節點通過循環，遞歸地創建子樹2.2案例實現396.測試算法：使用決策樹執行分類

依靠訓練數據構造了決策樹之后，我們可以將它用于實際數據的分類。在執行數據分類時，需要決策樹以及用于決策樹的標簽向量。然后，程序比較測試數據與決策樹上的數值，遞歸執行該過程直到進入葉子結點；最后將測試數據定義為葉子結點所屬的類型。defclassify(input_tree,feat_labels,test_vec):

#獲取樹的第一特征屬性

first_str=list(input_tree.keys())[0]

#樹的分子，子集合Dict

second_dict=input_tree[first_str]

#獲取決策樹第一層在feat_labels中的位置

feat_index=feat_labels.index(first_str)

#測試數據,找到根節點對應的label位置,也就知道從輸入數據的第幾位來開始分類

forkeyinsecond_dict.keys():

iftest_vec[feat_index]==key:

#判斷分支是否結束

iftype(second_dict[key]).__name__=='dict':

class_label=classify(second_dict[key],feat_labels,test_vec)

else:

class_label=second_dict[key]

returnclass_label2.2案例實現406.測試算法：使用決策樹執行分類

ID參數名稱釋義1input_tree輸入的決策樹對象2feat_labels特征標簽3test_vec測試的數據函數參數說明如下表：