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

知識引入3

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

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

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

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

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

賦予該結點關聯(lián)的訓練數(shù)據(jù)的最常見分類； c.

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

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

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

然后按照如下規(guī)則比較E1，E2，E3：E1最小時，不剪枝。E2最小時，進行剪枝，以一個葉節(jié)點代替t。E3最小時，采用“嫁接”(grafting)策略，即用這個最大分枝代替t。1.1決策樹概述166.決策樹算法的特點決策樹的優(yōu)點：(1)其結構能方便地進行可視化，便于理解和解釋。(2)能處理數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)，對缺失值也不敏感，能處理不相關的特征，因此對預處理的要求不高，數(shù)據(jù)準備工作相對簡單。(3)訓練需要的數(shù)據(jù)量少，計算量小，效率相對較高。決策樹的缺點：(1)適用范圍有限，擅長對人、地點、事物的一系列不同特征、品質、特性進行評估，但對連續(xù)性特征較難預測，當類別太多時，錯誤可能增加較快。(2)容易出現(xiàn)過擬合。(3)忽略了屬性之間的相關性，在處理特征關聯(lián)性比較強的數(shù)據(jù)時表現(xiàn)得不是太好。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庫中，該類的構造函數(shù)定義為：1.1決策樹概述18函數(shù)參數(shù)描述參數(shù)描述criterion用于測量拆分質量的函數(shù)splitter用于在每個節(jié)點上選擇拆分的策略max_depth表示樹的最大深度，即樹的層數(shù)，整型變量min_samples_split表示內部節(jié)點再劃分所需最小樣本數(shù)，整型或浮點型min_samples_leaf表示葉節(jié)點上所需要的最小樣本數(shù)，整型或浮點型min_weight_fraction_leaf葉子節(jié)點最小的樣本權重和，整型或浮點型max_features劃分時考慮的最大特征數(shù)，默認是Nonerandom_state隨機數(shù)種子，其取值可以是整型、RandomState實例或Nonemax_leaf_nodes最大葉子節(jié)點數(shù)，整型，默認是Nonemin_impurity_decrease節(jié)點劃分最小不純度減少值，浮點型class_weight類別權重，默認是None，也可以字典、字典列表或balancedccp_alpha用于最小成本-復雜性修剪的復雜度參數(shù)，非負浮點數(shù)1.2決策樹數(shù)學基礎

191.信息熵

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

201.信息熵

1.2決策樹數(shù)學基礎

212.條件熵

1.2決策樹數(shù)學基礎

223.信息增益

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

1.2決策樹數(shù)學基礎

234.信息增益比

1.2決策樹數(shù)學基礎

245.基尼系數(shù)

1.3決策樹算法

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

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

27ID3算法：

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

28ID3算法：

1.3決策樹算法

29ID3算法：

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

生成數(shù)據(jù)集

將表6-2中“不浮出水面是否可以生存”和“是否有腳蹼”這兩列數(shù)據(jù)特征中的“是”用“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案例實現(xiàn)332.

計算給定數(shù)據(jù)集的香農(nóng)熵

遍歷給定數(shù)據(jù)集的最后一列數(shù)據(jù)，創(chuàng)建類別標簽計數(shù)字典，最后依據(jù)公式計算香農(nóng)熵。函數(shù)返回香農(nóng)熵。創(chuàng)建類目計數(shù)字典香農(nóng)熵計算2.2案例實現(xiàn)343.

劃分數(shù)據(jù)集

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

#判斷axis值是否等于value

#遍歷數(shù)據(jù)集，將axis上的數(shù)據(jù)和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

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

劃分數(shù)據(jù)集

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

選擇最好的數(shù)據(jù)集劃分方式的函數(shù)

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

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

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

依靠訓練數(shù)據(jù)構造了決策樹之后，我們可以將它用于實際數(shù)據(jù)的分類。在執(zhí)行數(shù)據(jù)分類時，需要決策樹以及用于決策樹的標簽向量。然后，程序比較測試數(shù)據(jù)與決策樹上的數(shù)值，遞歸執(zhí)行該過程直到進入葉子結點；最后將測試數(shù)據(jù)定義為葉子結點所屬的類型。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)

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

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案例實現(xiàn)406.測試算法：使用決策樹執(zhí)行分類

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