《教材配套教學——基本數(shù)據(jù)挖掘技術(shù)ppt課件》由會員分享，可在線閱讀，更多相關(guān)《教材配套教學——基本數(shù)據(jù)挖掘技術(shù)ppt課件（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,第,*,頁，共,27,頁,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第,2,章 基本數(shù)據(jù)挖掘技術(shù),之一,決策樹,第2章 基本數(shù)據(jù)挖掘技術(shù) 之一決策樹,本章目標,決策樹,了解決策樹的概念；,了解,C4.5,決策樹建立過程、關(guān)鍵技術(shù)、和決策樹規(guī)則；,了解其他決策樹算法。,關(guān)聯(lián)規(guī)則,了解關(guān)聯(lián)規(guī)則；,掌握,Apriori,關(guān)聯(lián)分析過程。,聚類分析,掌握,K-,均值算法。,了解數(shù)據(jù)挖掘技術(shù)的選擇考慮。,20 十一月 2024,第,2,頁，共,28,頁,本章目

2、標決策樹07 十月 2023第2頁，共28頁,2.1,決策樹,2.1 決策樹,決策樹學習,從數(shù)據(jù)產(chǎn)生決策樹的機器學習技術(shù)稱為決策樹學習，簡稱決策樹（,Decision Tree,）。,決策樹是數(shù)據(jù)挖掘中最常用的一種分類和預測技術(shù)，使用其可建立分類和預測模型。,決策樹模型是一個樹狀結(jié)構(gòu)，樹中每個節(jié)點表示分析對象的某個屬性，每個分支表示這個屬性的某個可能的取值，每個葉節(jié)點表示經(jīng)歷從根節(jié)點到該葉節(jié)點這條路徑上的對象的值。模型通過樹中的各個分支對對象進行分類，葉節(jié)點表示的對象值表達了決策樹分類的結(jié)果。決策樹僅有一個輸出，若需要有多個輸出，可以建立多棵獨立的決策樹以處理不同輸出。,20 十一月 2024

3、,第,4,頁，共,28,頁,決策樹學習從數(shù)據(jù)產(chǎn)生決策樹的機器學習技術(shù)稱為決策樹學習，簡稱,2.1.1,決策樹算法的一般過程,（,C4.5,）,（,1,）給定一個表示為“屬性,-,值”格式的數(shù)據(jù)集,T,。數(shù)據(jù)集由多個具有多個輸入屬性和一個輸出屬性的實例組成。,（,2,）選擇一個最能區(qū)別,T,中實例的輸入屬性，,C4.5,使用增益率來選擇該屬性。,（,3,）使用該屬性創(chuàng)建一個樹節(jié)點，同時創(chuàng)建該節(jié)點的分支，每個分支為該節(jié)點的所有可能取值。,（,4,）使用這些分支，將數(shù)據(jù)集中的實例進行分類，成為細分的子類。,（,5,）將當前子類的實例集合設為,T,，對數(shù)據(jù)集中的剩余屬性重復（,2,）（,3,）步，直到

4、滿足以下兩個條件之一時，該過程終止，創(chuàng)建一個葉子節(jié)點，該節(jié)點為沿此分支所表達的分類類別，其值為輸出屬性的值。,該子類中的實例滿足預定義的標準，如全部分到一個輸出類中，分到一個輸出類中的實例達到某個比例；,沒有剩余屬性。,20 十一月 2024,第,5,頁，共,28,頁,2.1.1 決策樹算法的一般過程（C4.5）（1）給定一個表,【例,2.1,】,給定如表,2.1,所示的數(shù)據(jù)集,T,，建立一棵決策樹，用于預測某個學生是否決定去打籃球。,【例2.1】給定如表2.1所示的數(shù)據(jù)集T，建立一棵決策樹，用,表,2.1,一個假想的打籃球數(shù)據(jù)集,20 十一月 2024,第,7,頁，共,28,頁,序號,Wea

5、ther,Temperature/,C,Courses,Partner,Play,1,Sunny,2030,4,Yes,Yes,2,Sunny,2030,4,No,Yes,3,Rain,100,1,Yes,Yes,4,Sunny,3040,5,Yes,Yes,5,Rain,2030,8,No,No,6,Sunny,-100,5,Yes,Yes,7,Sunny,-100,7,No,No,8,Rain,2030,2,Yes,Yes,9,Rain,2030,6,Yes,No,10,Sunny,1020,6,Yes,No,11,Rain,1020,3,No,No,12,Rain,1020,1,Yes,

6、No,13,Sunny,1020,8,Yes,No,14,Sunny,010,3,Yes,Yes,15,Rain,010,2,Yes,No,表2.1 一個假想的打籃球數(shù)據(jù)集07 十月 2023第7頁，,決策樹,使用,15,個實例進行有訓練，其中,Weather,、,Temperature,、,Courses,和,Partner,作為輸入屬性，,Play,作為輸出屬性。,20 十一月 2024,第,8,頁，共,28,頁,圖,2.1,打籃球決策樹,決策樹使用15個實例進行有訓練，其中Weather、Temp,2.1.2,決策樹算法的關(guān)鍵技術(shù),三項關(guān)鍵技術(shù),（,1,）選擇最能區(qū)別數(shù)據(jù)集中實例屬性的方

7、法,（,2,）剪枝方法,（,3,）檢驗方法,20 十一月 2024,第,9,頁，共,28,頁,2.1.2 決策樹算法的關(guān)鍵技術(shù)三項關(guān)鍵技術(shù)07 十月 20,1,、,選擇最能區(qū)別數(shù)據(jù)集中實例屬性的方法,C4.5,使用了信息論（,Information Theory,）的方法，即使用增益率（,Gain Ratio,）的概念來選擇屬性,；,目的是使樹的層次和節(jié)點數(shù)最小，使數(shù)據(jù)的概化程度最大化。,C4.5,選擇的基本思想,選擇具有最大增益率的屬性作為分支節(jié)點來分類實例數(shù)據(jù)。,20 十一月 2024,第,10,頁，共,28,頁,1、選擇最能區(qū)別數(shù)據(jù)集中實例屬性的方法C4.5使用了信息論,1,）信息熵,1

8、948,年，克勞德香農(nóng)（,Claude Shannon,）提出,“,信息熵,”,（,InformationEntropy,）的概念,信息變化的平均信息量稱為“信息熵”,（,信息量化,）,在信息論中，信息熵是信息的不確定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大,，,能傳輸?shù)男畔⒕驮蕉唷?20 十一月 2024,第,11,頁，共,28,頁,1）信息熵1948年，克勞德香農(nóng)（Claude Shann,2,）信息增益（,InformationGain,）,信息增益表示當,x,取屬性,x,i,值時，其對降低,x,的熵的貢獻大小。,信息增益值越大，越適于對,x,進行分類。,C4.5,使

9、用信息量和信息增益的概念計算所有屬性的增益，并計算所有屬性的增益率，選擇值最大的屬性來劃分數(shù)據(jù)實例。,20 十一月 2024,第,12,頁，共,28,頁,計算屬性,A,的增益率的公式,其中，對于一組,I,實例，計算,Gain(A),2）信息增益（InformationGain）信息增益表,2,）信息增益（,InformationGain,）,Info(,I,),為當前數(shù)據(jù)集所有實例所表達的信息量,20 十一月 2024,第,13,頁，共,28,頁,Info(I,A),為根據(jù)屬性,A,的,k,個可能取值分類,I,中實例之后所表達,的信息量,SplitsInfo(A),是對,A,屬性的增益值的標準

10、化，目的是消除屬性選擇上的偏差（,Bias,），,2）信息增益（InformationGain）Info(,以,Weather,作為根節(jié)點,（,1,）,Info(,I,)=,(7/15log,2,(7/15)-8/15log,2,(8/15)=0.9968,（,2,）,Info(,I,Weather)=8/15Info(Sunny)+7/15Info(Rain)=0.9118,其中：,Info(Sunny)=,(5/8log,2,(5/8)+3/8log,2,(3/8)=0.9544,Info(Rain)=,(2/7(log,2,(2/7)+5/7log,2,(5/7)=0.8631,（,3,

11、）,SplitsInfo(Weather)=(8/15log,2,(8/15)+7/15log,2,(7/15)=0.9968,（,4,）,Gain(Weather)=Info(,I,),Info(,I,Weather)=0.9968,0.9118=-0.085,（,5,）,GainRatio(Weather)=Gain(Weather)/SplitsInfo(Weather),=-0.085/0.9968=-0.085,20 十一月 2024,第,14,頁，共,28,頁,圖,2.2 Weather,作為根節(jié)點的局部決策樹,以Weather作為根節(jié)點（1）Info(I)=(7/1,二元分裂點（

12、,Binary Splits,）,數(shù)值型屬性,Courses,的增益值如何計算呢？,C4.5,算法對這些數(shù)值型數(shù)據(jù)進行排序，計算每個可能的二元分裂點的增益率值來離散化這個屬性值。,20 十一月 2024,第,15,頁，共,28,頁,表,2.2,打籃球數(shù)據(jù)集中數(shù)值型屬性,Courses,的排序結(jié)果,1,1,2,2,3,3,4,4,5,5,6,6,7,8,8,Yes,No,Yes,No,No,Yes,Yes,Yes,Yes,Yes,No,No,No,No,No,二元分裂點（Binary Splits）數(shù)值型屬性Cours,Courses,屬性作為根節(jié)點,計算,4,個屬性的增益率值后，發(fā)現(xiàn),Cour

13、ses,屬性的,5,和,5,分裂點處具有最佳增益率值，為,0.4457,。,20 十一月 2024,第,16,頁，共,28,頁,圖,2.3 Courses,作為根節(jié)點的局部決策樹,Courses屬性作為根節(jié)點計算4個屬性的增益率值后，發(fā)現(xiàn)C,完,整,決策樹,20 十一月 2024,第,17,頁，共,28,頁,圖,2.4,Courses,作為根節(jié)點的完,整,決策樹,完整決策樹07 十月 2023第17頁，共28頁圖2.4 C,【例,2.2,】,使用表,2.1,所示的數(shù)據(jù)集,T,，使用,Weka,軟件，應用,C4.5,算法建立決策樹，用于預測某個學生是否決定去打籃球。,【例2.2】使用表2.1所示

14、的數(shù)據(jù)集T，使用Weka軟件，應,實驗結(jié)果,使用,Weka,軟件，選擇,C4.5,算法（名為,J48,）,20 十一月 2024,第,19,頁，共,28,頁,圖,2.10 Weka J48,建立的打籃球決策樹,實驗結(jié)果使用Weka軟件，選擇C4.5算法（名為J48）07,2,、,決策樹剪枝,剪枝（,Pruning,）,為控制決策樹規(guī)模，優(yōu)化決策樹而采取的剪除部分分支的方法。,剪枝分為兩種,預剪枝（,Pre-Pruning,）,后剪枝（,Post-Pruning,）,20 十一月 2024,第,20,頁，共,28,頁,2、決策樹剪枝剪枝（Pruning）07 十月 2023第2,【例,2.3,】

15、,使用來自,UCI,的,Credit Screening Databases,數(shù)據(jù)集，應用,Weka,的,J48,（,C4.5,）算法建立兩棵決策樹，分別為剪枝和未剪枝的。,【例2.3】使用來自UCI的 Credit Screenin,方法和結(jié)果,20 十一月 2024,第,22,頁，共,28,頁,圖,2.11,設置“未剪枝的”,圖,2.12,經(jīng)過剪枝的決策樹,2.13,未經(jīng)過剪枝的決策樹,方法和結(jié)果07 十月 2023第22頁，共28頁圖2.11,3,、,決策樹檢驗,Weka,提供了,4,種檢驗方法,（,1,）,use training set,：使用在訓練集實例上的預測效果進行檢驗。,（,

16、2,）,supplied test set,：使用另外提供的檢驗集實例進行檢驗，此時需要單擊,Set,按鈕來選擇用來檢驗的數(shù)據(jù)集文件。,（,3,）,cross-validation,：使用交叉驗證（,Cross Validation,，,簡稱,CV,）來檢驗分類器，所用的折數(shù)填在,Folds,文本框中。,（,4,）,percent split,：百分比檢驗。從數(shù)據(jù)集中按一定百分比取出部分數(shù)據(jù)作為檢驗集實例用，根據(jù)分類器在這些實例上的預測效果來檢驗分類器的質(zhì)量。取出的數(shù)據(jù)量由“,%,”欄中的值決定。,20 十一月 2024,第,23,頁，共,28,頁,3、決策樹檢驗Weka提供了4種檢驗方法07 十月 2023,交叉檢驗,檢驗分類器性能的一種最為常用的統(tǒng)計分析方法，,基本思想,將數(shù)據(jù)集分為訓練集和檢驗集，劃分方法不同,有,不同,CV,檢驗方法。,Hold-Out,方法,k-,折交叉檢驗（,k-CV,）,Leave-One-Out,交叉檢驗（,LOO-CV,）,20 十一月 2024,第,24,頁，共,28,頁,交叉檢驗檢驗分類器性能的一種最為常用的統(tǒng)計分析方法，07 十,2.1.3,決策