教材配套教學(xué)——基本數(shù)據(jù)挖掘技術(shù)ppt課件

,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第,*,頁(yè)，共,27,頁(yè),清華大學(xué)出版社,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),第,2,章 基本數(shù)據(jù)挖掘技術(shù),之一,決策樹(shù),第2章 基本數(shù)據(jù)挖掘技術(shù) 之一決策樹(shù),本章目標(biāo),決策樹(shù),了解決策樹(shù)的概念；,了解,C4.5,決策樹(shù)建立過(guò)程、關(guān)鍵技術(shù)、和決策樹(shù)規(guī)則；,了解其他決策樹(shù)算法。,關(guān)聯(lián)規(guī)則,了解關(guān)聯(lián)規(guī)則；,掌握,Apriori,關(guān)聯(lián)分析過(guò)程。,聚類(lèi)分析,掌握,K-,均值算法。,了解數(shù)據(jù)挖掘技術(shù)的選擇考慮。,20 十一月 2024,第,2,頁(yè)，共,28,頁(yè),本章目標(biāo)決策樹(shù)07 十月 2023第2頁(yè)，共28頁(yè),2.1,決策樹(shù),2.1 決策樹(shù),決策樹(shù)學(xué)習(xí),從數(shù)據(jù)產(chǎn)生決策樹(shù)的機(jī)器學(xué)習(xí)技術(shù)稱(chēng)為決策樹(shù)學(xué)習(xí)，簡(jiǎn)稱(chēng)決策樹(shù)（,Decision Tree,）。,決策樹(shù)是數(shù)據(jù)挖掘中最常用的一種分類(lèi)和預(yù)測(cè)技術(shù)，使用其可建立分類(lèi)和預(yù)測(cè)模型。,決策樹(shù)模型是一個(gè)樹(shù)狀結(jié)構(gòu)，樹(shù)中每個(gè)節(jié)點(diǎn)表示分析對(duì)象的某個(gè)屬性，每個(gè)分支表示這個(gè)屬性的某個(gè)可能的取值，每個(gè)葉節(jié)點(diǎn)表示經(jīng)歷從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)這條路徑上的對(duì)象的值。模型通過(guò)樹(shù)中的各個(gè)分支對(duì)對(duì)象進(jìn)行分類(lèi)，葉節(jié)點(diǎn)表示的對(duì)象值表達(dá)了決策樹(shù)分類(lèi)的結(jié)果。決策樹(shù)僅有一個(gè)輸出，若需要有多個(gè)輸出，可以建立多棵獨(dú)立的決策樹(shù)以處理不同輸出。,20 十一月 2024,第,4,頁(yè)，共,28,頁(yè),決策樹(shù)學(xué)習(xí)從數(shù)據(jù)產(chǎn)生決策樹(shù)的機(jī)器學(xué)習(xí)技術(shù)稱(chēng)為決策樹(shù)學(xué)習(xí)，簡(jiǎn)稱(chēng),2.1.1,決策樹(shù)算法的一般過(guò)程,（,C4.5,）,（,1,）給定一個(gè)表示為“屬性,-,值”格式的數(shù)據(jù)集,T,。數(shù)據(jù)集由多個(gè)具有多個(gè)輸入屬性和一個(gè)輸出屬性的實(shí)例組成。,（,2,）選擇一個(gè)最能區(qū)別,T,中實(shí)例的輸入屬性，,C4.5,使用增益率來(lái)選擇該屬性。,（,3,）使用該屬性創(chuàng)建一個(gè)樹(shù)節(jié)點(diǎn)，同時(shí)創(chuàng)建該節(jié)點(diǎn)的分支，每個(gè)分支為該節(jié)點(diǎn)的所有可能取值。,（,4,）使用這些分支，將數(shù)據(jù)集中的實(shí)例進(jìn)行分類(lèi)，成為細(xì)分的子類(lèi)。,（,5,）將當(dāng)前子類(lèi)的實(shí)例集合設(shè)為,T,，對(duì)數(shù)據(jù)集中的剩余屬性重復(fù)（,2,）（,3,）步，直到滿(mǎn)足以下兩個(gè)條件之一時(shí)，該過(guò)程終止，創(chuàng)建一個(gè)葉子節(jié)點(diǎn)，該節(jié)點(diǎn)為沿此分支所表達(dá)的分類(lèi)類(lèi)別，其值為輸出屬性的值。,該子類(lèi)中的實(shí)例滿(mǎn)足預(yù)定義的標(biāo)準(zhǔn)，如全部分到一個(gè)輸出類(lèi)中，分到一個(gè)輸出類(lèi)中的實(shí)例達(dá)到某個(gè)比例；,沒(méi)有剩余屬性。,20 十一月 2024,第,5,頁(yè)，共,28,頁(yè),2.1.1 決策樹(shù)算法的一般過(guò)程（C4.5）（1）給定一個(gè)表,【例,2.1,】,給定如表,2.1,所示的數(shù)據(jù)集,T,，建立一棵決策樹(shù)，用于預(yù)測(cè)某個(gè)學(xué)生是否決定去打籃球。,【例2.1】給定如表2.1所示的數(shù)據(jù)集T，建立一棵決策樹(shù)，用,表,2.1,一個(gè)假想的打籃球數(shù)據(jù)集,20 十一月 2024,第,7,頁(yè)，共,28,頁(yè),序號(hào),Weather,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,No,13,Sunny,1020,8,Yes,No,14,Sunny,010,3,Yes,Yes,15,Rain,010,2,Yes,No,表2.1 一個(gè)假想的打籃球數(shù)據(jù)集07 十月 2023第7頁(yè)，,決策樹(shù),使用,15,個(gè)實(shí)例進(jìn)行有訓(xùn)練，其中,Weather,、,Temperature,、,Courses,和,Partner,作為輸入屬性，,Play,作為輸出屬性。,20 十一月 2024,第,8,頁(yè)，共,28,頁(yè),圖,2.1,打籃球決策樹(shù),決策樹(shù)使用15個(gè)實(shí)例進(jìn)行有訓(xùn)練，其中Weather、Temp,2.1.2,決策樹(shù)算法的關(guān)鍵技術(shù),三項(xiàng)關(guān)鍵技術(shù),（,1,）選擇最能區(qū)別數(shù)據(jù)集中實(shí)例屬性的方法,（,2,）剪枝方法,（,3,）檢驗(yàn)方法,20 十一月 2024,第,9,頁(yè)，共,28,頁(yè),2.1.2 決策樹(shù)算法的關(guān)鍵技術(shù)三項(xiàng)關(guān)鍵技術(shù)07 十月 20,1,、,選擇最能區(qū)別數(shù)據(jù)集中實(shí)例屬性的方法,C4.5,使用了信息論（,Information Theory,）的方法，即使用增益率（,Gain Ratio,）的概念來(lái)選擇屬性,；,目的是使樹(shù)的層次和節(jié)點(diǎn)數(shù)最小，使數(shù)據(jù)的概化程度最大化。,C4.5,選擇的基本思想,選擇具有最大增益率的屬性作為分支節(jié)點(diǎn)來(lái)分類(lèi)實(shí)例數(shù)據(jù)。,20 十一月 2024,第,10,頁(yè)，共,28,頁(yè),1、選擇最能區(qū)別數(shù)據(jù)集中實(shí)例屬性的方法C4.5使用了信息論,1,）信息熵,1948,年，克勞德香農(nóng)（,Claude Shannon,）提出,“,信息熵,”,（,InformationEntropy,）的概念,信息變化的平均信息量稱(chēng)為“信息熵”,（,信息量化,）,在信息論中，信息熵是信息的不確定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大,，,能傳輸?shù)男畔⒕驮蕉唷?20 十一月 2024,第,11,頁(yè)，共,28,頁(yè),1）信息熵1948年，克勞德香農(nóng)（Claude Shann,2,）信息增益（,InformationGain,）,信息增益表示當(dāng),x,取屬性,x,i,值時(shí)，其對(duì)降低,x,的熵的貢獻(xiàn)大小。,信息增益值越大，越適于對(duì),x,進(jìn)行分類(lèi)。,C4.5,使用信息量和信息增益的概念計(jì)算所有屬性的增益，并計(jì)算所有屬性的增益率，選擇值最大的屬性來(lái)劃分?jǐn)?shù)據(jù)實(shí)例。,20 十一月 2024,第,12,頁(yè)，共,28,頁(yè),計(jì)算屬性,A,的增益率的公式,其中，對(duì)于一組,I,實(shí)例，計(jì)算,Gain(A),2）信息增益（InformationGain）信息增益表,2,）信息增益（,InformationGain,）,Info(,I,),為當(dāng)前數(shù)據(jù)集所有實(shí)例所表達(dá)的信息量,20 十一月 2024,第,13,頁(yè)，共,28,頁(yè),Info(I,A),為根據(jù)屬性,A,的,k,個(gè)可能取值分類(lèi),I,中實(shí)例之后所表達(dá),的信息量,SplitsInfo(A),是對(duì),A,屬性的增益值的標(biāo)準(zhǔn)化，目的是消除屬性選擇上的偏差（,Bias,），,2）信息增益（InformationGain）Info(,以,Weather,作為根節(jié)點(diǎn),（,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,）,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,頁(yè)，共,28,頁(yè),圖,2.2 Weather,作為根節(jié)點(diǎn)的局部決策樹(shù),以Weather作為根節(jié)點(diǎn)（1）Info(I)=(7/1,二元分裂點(diǎn)（,Binary Splits,）,數(shù)值型屬性,Courses,的增益值如何計(jì)算呢？,C4.5,算法對(duì)這些數(shù)值型數(shù)據(jù)進(jìn)行排序，計(jì)算每個(gè)可能的二元分裂點(diǎn)的增益率值來(lái)離散化這個(gè)屬性值。,20 十一月 2024,第,15,頁(yè)，共,28,頁(yè),表,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,二元分裂點(diǎn)（Binary Splits）數(shù)值型屬性Cours,Courses,屬性作為根節(jié)點(diǎn),計(jì)算,4,個(gè)屬性的增益率值后，發(fā)現(xiàn),Courses,屬性的,5,和,5,分裂點(diǎn)處具有最佳增益率值，為,0.4457,。,20 十一月 2024,第,16,頁(yè)，共,28,頁(yè),圖,2.3 Courses,作為根節(jié)點(diǎn)的局部決策樹(shù),Courses屬性作為根節(jié)點(diǎn)計(jì)算4個(gè)屬性的增益率值后，發(fā)現(xiàn)C,完,整,決策樹(shù),20 十一月 2024,第,17,頁(yè)，共,28,頁(yè),圖,2.4,Courses,作為根節(jié)點(diǎn)的完,整,決策樹(shù),完整決策樹(shù)07 十月 2023第17頁(yè)，共28頁(yè)圖2.4 C,【例,2.2,】,使用表,2.1,所示的數(shù)據(jù)集,T,，使用,Weka,軟件，應(yīng)用,C4.5,算法建立決策樹(shù)，用于預(yù)測(cè)某個(gè)學(xué)生是否決定去打籃球。,【例2.2】使用表2.1所示的數(shù)據(jù)集T，使用Weka軟件，應(yīng),實(shí)驗(yàn)結(jié)果,使用,Weka,軟件，選擇,C4.5,算法（名為,J48,）,20 十一月 2024,第,19,頁(yè)，共,28,頁(yè),圖,2.10 Weka J48,建立的打籃球決策樹(shù),實(shí)驗(yàn)結(jié)果使用Weka軟件，選擇C4.5算法（名為J48）07,2,、,決策樹(shù)剪枝,剪枝（,Pruning,）,為控制決策樹(shù)規(guī)模，優(yōu)化決策樹(shù)而采取的剪除部分分支的方法。,剪枝分為兩種,預(yù)剪枝（,Pre-Pruning,）,后剪枝（,Post-Pruning,）,20 十一月 2024,第,20,頁(yè)，共,28,頁(yè),2、決策樹(shù)剪枝剪枝（Pruning）07 十月 2023第2,【例,2.3,】,使用來(lái)自,UCI,的,Credit Screening Databases,數(shù)據(jù)集，應(yīng)用,Weka,的,J48,（,C4.5,）算法建立兩棵決策樹(shù)，分別為剪枝和未剪枝的。,【例2.3】使用來(lái)自UCI的 Credit Screenin,方法和結(jié)果,20 十一月 2024,第,22,頁(yè)，共,28,頁(yè),圖,2.11,設(shè)置“未剪枝的”,圖,2.12,經(jīng)過(guò)剪枝的決策樹(shù),2.13,未經(jīng)過(guò)剪枝的決策樹(shù),方法和結(jié)果07 十月 2023第22頁(yè)，共28頁(yè)圖2.11,3,、,決策樹(shù)檢驗(yàn),Weka,提供了,4,種檢驗(yàn)方法,（,1,）,use training set,：使用在訓(xùn)練集實(shí)例上的預(yù)測(cè)效果進(jìn)行檢驗(yàn)。,（,2,）,supplied test set,：使用另外提供的檢驗(yàn)集實(shí)例進(jìn)行檢驗(yàn)，此時(shí)需要單擊,Set,按鈕來(lái)選擇用來(lái)檢驗(yàn)的數(shù)據(jù)集文件。,（,3,）,cross-validation,：使用交叉驗(yàn)證（,Cross Validation,，,簡(jiǎn)稱(chēng),CV,）來(lái)檢驗(yàn)分類(lèi)器，所用的折數(shù)填在,Folds,文本框中。,（,4,）,percent split,：百分比檢驗(yàn)。從數(shù)據(jù)集中按一定百分比取出部分?jǐn)?shù)據(jù)作為檢驗(yàn)集實(shí)例用，根據(jù)分類(lèi)器在這些實(shí)例上的預(yù)測(cè)效果來(lái)檢驗(yàn)分類(lèi)器的質(zhì)量。取出的數(shù)據(jù)量由“,%,”欄中的值決定。,20 十一月 2024,第,23,頁(yè)，共,28,頁(yè),3、決策樹(shù)檢驗(yàn)Weka提供了4種檢驗(yàn)方法07 十月 2023,交叉檢驗(yàn),檢驗(yàn)分類(lèi)器性能的一種最為常用的統(tǒng)計(jì)分析方法，,基本思想,將數(shù)據(jù)集分為訓(xùn)練集和檢驗(yàn)集，劃分方法不同,有,不同,CV,檢驗(yàn)方法。,Hold-Out,方法,k-,折交叉檢驗(yàn)（,k-CV,）,Leave-One-Out,交叉檢驗(yàn)（,LOO-CV,）,20 十一月 2024,第,24,頁(yè)，共,28,頁(yè),交叉檢驗(yàn)檢驗(yàn)分類(lèi)器性能的一種最為常用的統(tǒng)計(jì)分析方法，07 十,2.1.3,決策