1、第2章 基本數據挖掘技術 之一決策樹本章目標決策樹了解決策樹的概念；了解C4.5決策樹建立過程、關鍵技術、和決策樹規則；了解其他決策樹算法。關聯規則了解關聯規則；掌握Apriori關聯分析過程。聚類分析掌握K-均值算法。了解數據挖掘技術的選擇考慮。21 七月 2022第2頁，共28頁2.1 決策樹決策樹學習從數據產生決策樹的機器學習技術稱為決策樹學習，簡稱決策樹（Decision Tree）。決策樹是數據挖掘中最常用的一種分類和預測技術，使用其可建立分類和預測模型。決策樹模型是一個樹狀結構，樹中每個節點表示分析對象的某個屬性，每個分支表示這個屬性的某個可能的取值，每個葉節點表示經歷從根節點到該

2、葉節點這條路徑上的對象的值。模型通過樹中的各個分支對對象進行分類，葉節點表示的對象值表達了決策樹分類的結果。決策樹僅有一個輸出，若需要有多個輸出，可以建立多棵獨立的決策樹以處理不同輸出。21 七月 2022第4頁，共28頁2.1.1 決策樹算法的一般過程（C4.5）（1）給定一個表示為“屬性-值”格式的數據集T。數據集由多個具有多個輸入屬性和一個輸出屬性的實例組成。（2）選擇一個最能區別T中實例的輸入屬性，C4.5使用增益率來選擇該屬性。（3）使用該屬性創建一個樹節點，同時創建該節點的分支，每個分支為該節點的所有可能取值。（4）使用這些分支，將數據集中的實例進行分類，成為細分的子類。（5）將當

3、前子類的實例集合設為T，對數據集中的剩余屬性重復（2）（3）步，直到滿足以下兩個條件之一時，該過程終止，創建一個葉子節點，該節點為沿此分支所表達的分類類別，其值為輸出屬性的值。該子類中的實例滿足預定義的標準，如全部分到一個輸出類中，分到一個輸出類中的實例達到某個比例；沒有剩余屬性。21 七月 2022第5頁，共28頁【例2.1】給定如表2.1所示的數據集T，建立一棵決策樹，用于預測某個學生是否決定去打籃球。表2.1 一個假想的打籃球數據集21 七月 2022第7頁，共28頁序號WeatherTemperature/CCoursesPartnerPlay1Sunny20304YesYes2Sun

4、ny20304NoYes3Rain1001YesYes4Sunny30405YesYes5Rain20308NoNo6Sunny-1005YesYes7Sunny-1007NoNo8Rain20302YesYes9Rain20306YesNo10Sunny10206YesNo11Rain10203NoNo12Rain10201YesNo13Sunny10208YesNo14Sunny0103YesYes15Rain0102YesNo決策樹使用15個實例進行有訓練，其中Weather、Temperature、Courses和Partner作為輸入屬性，Play作為輸出屬性。21 七月 2022第

5、8頁，共28頁圖2.1 打籃球決策樹2.1.2 決策樹算法的關鍵技術三項關鍵技術（1）選擇最能區別數據集中實例屬性的方法（2）剪枝方法（3）檢驗方法21 七月 2022第9頁，共28頁1、 選擇最能區別數據集中實例屬性的方法C4.5使用了信息論（Information Theory）的方法，即使用增益率（Gain Ratio）的概念來選擇屬性；目的是使樹的層次和節點數最小，使數據的概化程度最大化。C4.5選擇的基本思想選擇具有最大增益率的屬性作為分支節點來分類實例數據。21 七月 2022第10頁，共28頁1）信息熵1948年，克勞德香農（Claude Shannon）提出“信息熵”（Info

6、rmationEntropy）的概念信息變化的平均信息量稱為“信息熵”（信息量化）在信息論中，信息熵是信息的不確定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大，能傳輸的信息就越多。21 七月 2022第11頁，共28頁2）信息增益（InformationGain）信息增益表示當x取屬性xi值時，其對降低x的熵的貢獻大小。信息增益值越大，越適于對x進行分類。C4.5使用信息量和信息增益的概念計算所有屬性的增益，并計算所有屬性的增益率，選擇值最大的屬性來劃分數據實例。21 七月 2022第12頁，共28頁計算屬性A的增益率的公式其中，對于一組 I 實例，計算Gain(A) 2）信息

7、增益（InformationGain）Info(I) 為當前數據集所有實例所表達的信息量21 七月 2022第13頁，共28頁 Info(I,A) 為根據屬性 A 的 k 個可能取值分類 I 中實例之后所表達的信息量 SplitsInfo(A) 是對A屬性的增益值的標準化，目的是消除屬性選擇上的偏差（Bias），以Weather作為根節點（1）Info(I)= (7/15log2(7/15)-8/15log2(8/15)= 0.9968（2）Info(I,Weather)= 8/15Info(Sunny)+ 7/15Info(Rain)= 0.9118 其中：Info(Sunny)= (5/8

8、log2 (5/8) + 3/8log2 (3/8) = 0.9544 Info(Rain)= (2/7(log2 (2/7) + 5/7log2 (5/7) = 0.8631（3）SplitsInfo(Weather)= (8/15log2 (8/15) + 7/15log2 (7/15) = 0.9968（4）Gain(Weather) = Info(I)Info(I,Weather) =0.99680.9118 = -0.085（5）GainRatio(Weather) = Gain(Weather)/ SplitsInfo(Weather) = -0.085 / 0.9968 = -0

9、.08521 七月 2022第14頁，共28頁圖2.2 Weather作為根節點的局部決策樹二元分裂點（Binary Splits）數值型屬性Courses的增益值如何計算呢？C4.5算法對這些數值型數據進行排序，計算每個可能的二元分裂點的增益率值來離散化這個屬性值。21 七月 2022第15頁，共28頁表2.2 打籃球數據集中數值型屬性Courses的排序結果112233445566788YesNoYesNoNoYesYesYesYesYesNoNoNoNoNoCourses屬性作為根節點計算4個屬性的增益率值后，發現Courses屬性的 5 和 5 分裂點處具有最佳增益率值，為0.4457

10、。21 七月 2022第16頁，共28頁圖2.3 Courses作為根節點的局部決策樹完整決策樹21 七月 2022第17頁，共28頁圖2.4 Courses作為根節點的完整決策樹【例2.2】使用表2.1所示的數據集T，使用Weka軟件，應用C4.5算法建立決策樹，用于預測某個學生是否決定去打籃球。實驗結果使用Weka軟件，選擇C4.5算法（名為J48）21 七月 2022第19頁，共28頁圖2.10 Weka J48建立的打籃球決策樹2、決策樹剪枝剪枝（Pruning）為控制決策樹規模，優化決策樹而采取的剪除部分分支的方法。剪枝分為兩種預剪枝（Pre-Pruning）后剪枝（Post-Pru

11、ning）21 七月 2022第20頁，共28頁【例2.3】使用來自UCI的 Credit Screening Databases數據集，應用Weka的J48（C4.5）算法建立兩棵決策樹，分別為剪枝和未剪枝的。方法和結果21 七月 2022第22頁，共28頁圖2.11 設置“未剪枝的”圖2.12 經過剪枝的決策樹2.13 未經過剪枝的決策樹3、決策樹檢驗Weka提供了4種檢驗方法（1）use training set：使用在訓練集實例上的預測效果進行檢驗。（2）supplied test set：使用另外提供的檢驗集實例進行檢驗，此時需要單擊 Set按鈕來選擇用來檢驗的數據集文件。（3）cr

12、oss-validation：使用交叉驗證（Cross Validation，簡稱CV）來檢驗分類器，所用的折數填在Folds 文本框中。（4）percent split：百分比檢驗。從數據集中按一定百分比取出部分數據作為檢驗集實例用，根據分類器在這些實例上的預測效果來檢驗分類器的質量。取出的數據量由“%” 欄中的值決定。21 七月 2022第23頁，共28頁交叉檢驗檢驗分類器性能的一種最為常用的統計分析方法，基本思想將數據集分為訓練集和檢驗集，劃分方法不同有不同CV檢驗方法。 Hold-Out方法 k-折交叉檢驗（k-CV） Leave-One-Out交叉檢驗（LOO-CV）21 七月 20

13、22第24頁，共28頁2.1.3決策樹規則決策樹每一條路徑都可使用一條產生式規則來解釋，整個決策樹可以被映射為一組規則。Courses5| Weather = Sunny: Yes (5.0)| Weather = Rain: No (5.0/2.0)Courses 5: No (5.0) 將以上Weka產生的規則翻譯為三條產生式規則（1）IF Courses 5 and Weather = Sunny THEN Play = Yes 正確率：5/5 = 100% 覆蓋率：5/7 = 71.4%（2）IF Courses 5 THEN Play = No正確率：5/5 = 100% 覆蓋率：5

14、/8 = 62.5%21 七月 2022第25頁，共28頁簡化或淘汰規則例如，若出現如下一條規則：IF Courses 5 and Weather = Sunny and Temperature = 2030 THEN Play = Yes 正確率：2/2 = 100% 覆蓋率：2/7 = 28.6%可簡化為IF Courses 5 and Weather = Sunny THEN Play = Yes 正確率：5/5 = 100% 覆蓋率：5/7 = 71.4%21 七月 2022第26頁，共28頁2.1.4 其他決策樹算法ID3算法C4.5的前身J.羅斯昆蘭 1986年提出的。與C4.5最大的不同ID3使用信息增益來選擇分裂屬性。CART（Classification And Regression Tree，分類回歸樹）1984年雷奧布萊曼（Leo Breiman）等人提出的。CHAID決策樹算法戈登V.凱斯（Gordon V. Kass）于1980年提出的。CHAID與C4.5和CART不同，它要求所有屬性為分類類型，且使用x2顯著性檢驗來選擇分裂屬性。CHAID具有統計學特色，在SAS和SPSS等商業統計軟件中應用很好。21 七月 20