決策樹(shù)和模型評(píng)估課件

DataMining

第四章分類：基本概念、決策樹(shù)和模型評(píng)估4.1預(yù)備知識(shí)

4.2解決分類問(wèn)題的一般方法分類例子預(yù)測(cè)癌細(xì)胞是良性還是惡性將信用卡交易分為合法和欺詐……分類：定義給定一個(gè)記錄集

每個(gè)記錄包含一個(gè)屬性集，通常最后一個(gè)屬性是該記錄的分類（class）屬性.目標(biāo)：找到一個(gè)模型（從其余屬性值到分類屬性的轉(zhuǎn)換函數(shù)），實(shí)現(xiàn)對(duì)未知分類的記錄進(jìn)行盡可能精確地分類。通常，將給定的數(shù)據(jù)集分為訓(xùn)練集（trainingset

）和檢驗(yàn)集（testset

）。訓(xùn)練集用來(lái)創(chuàng)建模型，檢驗(yàn)集用來(lái)驗(yàn)證模型的有效性。分類性能度量：預(yù)測(cè)的類類=1類=0實(shí)際

的數(shù)類=1f11f10類=0f01f00分類過(guò)程訓(xùn)練集檢驗(yàn)集學(xué)習(xí)模型學(xué)習(xí)模型學(xué)習(xí)算法模型分類技術(shù)基于決策樹(shù)的方法DecisionTreebasedMethods基于規(guī)則的方法Rule-basedMethods基于記憶的推理Memorybasedreasoning神經(jīng)網(wǎng)絡(luò)NeuralNetworks樸素貝葉斯和貝葉斯信念網(wǎng)絡(luò)Na?veBayesandBayesianBeliefNetworks支持向量機(jī)SupportVectorMachines決策樹(shù)定義決策樹(shù)是由結(jié)點(diǎn)和有向邊組成的層次結(jié)構(gòu)。樹(shù)中包含三種結(jié)點(diǎn)：根結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)葉結(jié)點(diǎn)非終結(jié)點(diǎn)。包含屬性測(cè)試條件，用于分開(kāi)不同特性的記錄每個(gè)葉結(jié)點(diǎn)都賦予一個(gè)類標(biāo)號(hào)決策樹(shù)例1二元屬性分類屬性連續(xù)屬性分類標(biāo)號(hào)有房產(chǎn)婚姻狀況收入YESNONONOYesNoMarried

Single,Divorced<80K>80K屬性劃分訓(xùn)練數(shù)據(jù)模型：決策樹(shù)決策樹(shù)例2MarStRefundTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K對(duì)于相同的數(shù)據(jù)，能構(gòu)造多種不同的決策樹(shù)決策樹(shù)應(yīng)用用過(guò)程：使使用模型測(cè)測(cè)試數(shù)據(jù)－－1RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K檢驗(yàn)數(shù)據(jù)從樹(shù)根開(kāi)始始使用模型測(cè)測(cè)試數(shù)據(jù)－－2RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KTestData使用模型測(cè)測(cè)試數(shù)據(jù)－－3RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80KTestData使用模型測(cè)測(cè)試數(shù)據(jù)－－4RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80KTestData使用模型測(cè)測(cè)試數(shù)據(jù)－－5RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80KTestData使用模型測(cè)測(cè)試數(shù)據(jù)－－6RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80KTestData將Cheat賦值為“No”決策樹(shù)構(gòu)造造算法多種算法:Hunt算法(最早方法之之一)CART（classificationandregressiontrees）ID3,C4.5SLIQ,SPRINTHunt算法結(jié)構(gòu)Hunt算法的思想想是將訓(xùn)練記錄錄相繼劃分分成“較純純”的子集集，以遞歸歸方式建立立決策樹(shù)。。假設(shè)t表示結(jié)點(diǎn)，，Dt表示與結(jié)點(diǎn)點(diǎn)t相關(guān)聯(lián)的訓(xùn)訓(xùn)練記錄集集，y={y1,y2,…,yc}是類標(biāo)號(hào)Hunt算法的遞歸歸定義:如果Dt中所有記錄錄都屬于同一個(gè)類yt,則t就是葉子子節(jié)點(diǎn)，，并用yt標(biāo)號(hào)如果Dt是一個(gè)空集，那么t就是葉子子節(jié)點(diǎn)，，其標(biāo)號(hào)號(hào)為其父父結(jié)點(diǎn)上上訓(xùn)練記記錄中的的多數(shù)類類Dt?如果Dt中包含屬屬于多個(gè)類的記錄，，則選擇擇一個(gè)屬性測(cè)試試條件，將記錄錄劃分成成若干個(gè)個(gè)子集。。并對(duì)每每個(gè)子集集進(jìn)行遞遞歸分類類。例P93～P95預(yù)測(cè)拖欠欠銀行貸貸款的貸貸款者如何生成成決策樹(shù)樹(shù)？貪婪策略略.每次選擇擇屬性劃劃分條件件時(shí)，選選擇劃分分?jǐn)?shù)據(jù)的的最優(yōu)標(biāo)準(zhǔn).決策樹(shù)歸歸納的設(shè)設(shè)計(jì)問(wèn)題題問(wèn)題1：如何分分裂記錄錄？1.1定義屬性性測(cè)試條條件——給不同類類型的屬屬性指定定測(cè)試條條件的方方法1.2找到最好好的劃分分方法——對(duì)每種測(cè)測(cè)試條件件進(jìn)行評(píng)評(píng)估測(cè)量量問(wèn)題2：何時(shí)停停止分裂裂過(guò)程？？決策樹(shù)歸歸納的設(shè)設(shè)計(jì)問(wèn)題題1：1.1定義屬性性測(cè)試條條件表示屬性性測(cè)試條條件的方方法根據(jù)屬性性類型標(biāo)稱型Nominal序數(shù)型Ordinal連續(xù)型Continuous按劃分路路數(shù)二元?jiǎng)澐址?-waysplit多路劃分分Multi-waysplit標(biāo)稱屬性性的劃分分方法：：(數(shù)據(jù)集見(jiàn)見(jiàn)P122習(xí)題2)多路劃分分法:劃分成幾幾個(gè)不同同的值——輸出數(shù)取取決于該該屬性不不同屬性性值的個(gè)個(gè)數(shù).二分法:劃分為兩兩個(gè)不同同的值.（需要找找到最佳佳的劃分分方法））CarTypeFamilySportsLuxuryCarType{Family,

Luxury}{Sports}CarType{Sports,Luxury}{Family}OR多路劃分分法二分法（分組必須須保留屬屬性值之之間的序序關(guān)系）注意：第第三種劃劃分方法法合理嗎嗎?序數(shù)屬性性的劃分分方法：：SizeSmallMediumLargeSize{Medium,

Large}{Small}Size{Small,Medium}{Large}ORSize{Small,Large}{Medium}連續(xù)屬性性的劃分分方法多路劃分分：離散化屬屬性值，，每個(gè)離離散化區(qū)區(qū)間賦予予一個(gè)新新的序數(shù)數(shù)值二分法：：(A<v)or(Av)需要從所所有可能能的劃分分點(diǎn)中選選擇產(chǎn)生生最佳劃劃分的點(diǎn)點(diǎn)決策樹(shù)歸歸納的設(shè)設(shè)計(jì)問(wèn)題題1：1.2找到最好好劃分方方法劃分前:數(shù)據(jù)集有有20個(gè)記錄，，標(biāo)號(hào)為為class0和class1的各有10個(gè)。哪個(gè)個(gè)劃分測(cè)測(cè)試條件件最佳？？為了度量量不同的的測(cè)試條條件，常常用劃分分前和劃劃分后記記錄的類分布定義：p(i|t)表示結(jié)點(diǎn)點(diǎn)t中，屬于于類i的記錄所所占的比比例，常常簡(jiǎn)記為為pi。在二元分分類問(wèn)題題中，任任意結(jié)點(diǎn)點(diǎn)的類分分布可以以記作(p0，p1)，其中p1=1-p0。選擇最佳佳劃分的的度量選擇最佳佳劃分的的度量通通常是根根據(jù)劃分分后子女結(jié)點(diǎn)點(diǎn)不純性性的程度度：不純的程程度越低低，類分分布就越越傾斜，，劃分就就越好。。不同類，具有有較高的不純純度同類，具有較較低的不純度度結(jié)點(diǎn)不純度的的度量方法：：熵Entropy基尼指數(shù)GiniIndex分類差錯(cuò)率Classificationerror計(jì)算不純性方方法1:熵結(jié)點(diǎn)t的熵:其中，c為結(jié)點(diǎn)t中不同類標(biāo)號(hào)號(hào)個(gè)數(shù)p(i|t)是給定結(jié)點(diǎn)t中屬于類i的記錄所占比比例，簡(jiǎn)記為為pi結(jié)點(diǎn)熵值的取取值范圍：當(dāng)記錄均勻分分布于各分類類時(shí)，將取得得最大值(lognc)當(dāng)所有記錄都都屬于同一分分類時(shí)，將取取得最小值(0)例：分別計(jì)算算3個(gè)結(jié)點(diǎn)的熵P(C0)=0/6=0P(C1)=6/6=1Entropy=––0·log0–1·log1=–0––0=0P(C0)=1/6P(C1)=5/6Entropy=––(1/6)·log2(1/6)–(5/6)·log2(5/6)=0.65P(C0)=2/6P(C1)=4/6Entropy=––(2/6)·log2(2/6)–(4/6)·log2(4/6)=0.92練習(xí)1已知：數(shù)據(jù)見(jiàn)見(jiàn)課本表4-7（P122題2），采用熵作作為結(jié)點(diǎn)的不不純度度量。。問(wèn)題：整個(gè)訓(xùn)練樣本本集的不純度度是多少？如果對(duì)數(shù)據(jù)按按車型屬性進(jìn)行多路路劃分，則（車型=運(yùn)動(dòng)）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？（車型=豪華）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？（車型=家用）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？計(jì)算不純性方方法2:基尼指數(shù)（gini）結(jié)點(diǎn)t的吉尼指數(shù):其中，c為結(jié)點(diǎn)t中不同類標(biāo)號(hào)號(hào)個(gè)數(shù)p(i|t)是給定結(jié)點(diǎn)t中屬于類i的記錄所占比比例，簡(jiǎn)記為為pi結(jié)點(diǎn)Gini指數(shù)的取值范范圍：當(dāng)記錄均勻分分布于各分類類時(shí)，將取得得最大值(1-1/nc)當(dāng)所有記錄都都屬于同一分分類時(shí)，將取取得最小值(0)例：分別計(jì)算算3個(gè)結(jié)點(diǎn)的Gini指數(shù)P(C0)=0/6=0P(C1)=6/6=1Gini=1–P(C0)2–P(C1)2=1–0–1=0P(C0)=1/6P(C1)=5/6Gini=1–(1/6)2–(5/6)2=0.278P(C0)=2/6P(C1)=4/6Gini=1–(2/6)2–(4/6)2=0.444練習(xí)2已知：數(shù)據(jù)見(jiàn)見(jiàn)課本表4-7（P122題2），采用Gini指數(shù)作為結(jié)點(diǎn)的不不純度度量。。問(wèn)題：整個(gè)訓(xùn)練樣本本集的不純度度是多少？如果對(duì)數(shù)據(jù)按按車型屬性進(jìn)行多路路劃分，則（車型=運(yùn)動(dòng)）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？（車型=豪華）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？（車型=家用）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？計(jì)算不純性方方法3:分類差錯(cuò)率節(jié)點(diǎn)t的分類差錯(cuò)率率:p(i|t)是給定結(jié)點(diǎn)t中屬于類i的記錄所占比比例，簡(jiǎn)記為為pi結(jié)點(diǎn)分類誤差差率指數(shù)的取取值范圍：當(dāng)記錄均勻分分布于各分類類時(shí)，將取得得最大值(1-1/nc)當(dāng)所有記錄都都屬于同一分分類時(shí)，將取取得最小值(0)例：分別計(jì)算算3個(gè)子女結(jié)點(diǎn)的的分類差錯(cuò)率率P(C0)=0/6=0P(C1)=6/6=1Error=1––max(0,1)=1–1=0P(C0)=1/6P(C1)=5/6Error=1––max(1/6,5/6)=1––5/6=1/6P(C0)=2/6P(C1)=4/6Error=1––max(2/6,4/6)=1––4/6=1/3練習(xí)3已知：數(shù)據(jù)見(jiàn)見(jiàn)課本表4-7（P122題2），采用分類誤差率作為結(jié)點(diǎn)的不不純度度量。。問(wèn)題：整個(gè)訓(xùn)練樣本本集的不純度度是多少？如果對(duì)數(shù)據(jù)按按車型屬性進(jìn)行多路路劃分，則（車型=運(yùn)動(dòng)）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？（車型=豪華）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？（車型=家用）的結(jié)點(diǎn)點(diǎn)的不純度是是多少？二元分類問(wèn)題題結(jié)點(diǎn)不純性性度量之間的的比較：利用不純性度度量，選擇最最佳劃分方法：分別比較父節(jié)節(jié)點(diǎn)（劃分前前）的不純程程度和子女結(jié)結(jié)點(diǎn)（劃分后后）的不純程程度，它們的的差值越大，，測(cè)試條件的的效果就越好好。用增益Δ來(lái)作為確定劃劃分效果的標(biāo)標(biāo)準(zhǔn)其中：I(.)是結(jié)點(diǎn)不純性性度量,N是父節(jié)點(diǎn)上的的記錄總數(shù)，，k是父節(jié)點(diǎn)的分分支數(shù)，N(vj)是子女結(jié)點(diǎn)vj的記錄個(gè)數(shù)。。決策樹(shù)歸納算算法，通常就就是選擇最大大化增益Δ的測(cè)試條件，，作為當(dāng)前節(jié)節(jié)點(diǎn)的屬性測(cè)測(cè)試條件。利用增益Δ來(lái)選擇最佳劃劃分示意：B?YesNoNodeN3NodeN4A?YesNoNodeN1NodeN2劃分前M父親Ma1Ma2Mb1Mb2MAMB比較增益:ΔA(M父親–MA)vs.ΔB(M父親–MB)計(jì)算不純性計(jì)算不純性計(jì)算不純性計(jì)算不純性加權(quán)平均加權(quán)平均練習(xí)4已知：數(shù)據(jù)見(jiàn)見(jiàn)課本表4-7（P122題2）。問(wèn)題(a)~(g)熵和Gini指數(shù)等不純度度趨向有利于于具有大量不不同值的屬性性產(chǎn)生大量輸出出測(cè)試條件，，從而導(dǎo)致與與每個(gè)劃分關(guān)關(guān)聯(lián)的記錄很很少。極端情況如：：以顧客ID進(jìn)行劃分，比比其他劃分方方法能得到更更“純”的派派生結(jié)點(diǎn)改進(jìn)方法信息增益（熵熵差）:ni=孩子節(jié)點(diǎn)i的記錄數(shù)n=節(jié)點(diǎn)p的記錄數(shù)用于ID3和C4.5算法增益率:將父節(jié)點(diǎn)p劃分為k部分n表示p的記錄數(shù)數(shù)ni表示第i部分（p的第i個(gè)節(jié)點(diǎn)））的記錄錄數(shù)調(diào)整信息息增益，，引入劃劃分信息息SplitInfo，把屬性性測(cè)試條條件產(chǎn)生生的輸出出數(shù)也考考慮進(jìn)去去。如果一個(gè)個(gè)屬性產(chǎn)產(chǎn)生了大大量的劃劃分，它它的劃分分信息SplitInfo將會(huì)很大大，從而而增益率率降低。。用于C4.5算法比較不同同類型的的屬性的的劃分（（以Gini指數(shù)為例例）二元屬性性標(biāo)稱屬性性離散屬性性基于GINI指數(shù)的二元屬性性劃分方法法劃分為兩兩部分B?YesNoNodeN1NodeN2Gini(N1)=1–(5/7)2–(2/7)2=0.194Gini(N2)=1–(1/5)2–(4/5)2=0.528Gini(Children)=7/12*0.194+5/12*0.528

=0.333基于GINI指數(shù)的標(biāo)稱屬性性劃分方法法用矩陣幫幫助選擇擇最佳劃劃分Multi-waysplitTwo-waysplit(findbestpartitionofvalues)基于GINI指數(shù)的連續(xù)屬性性劃分方法法問(wèn)題：需需要選擇擇候選劃劃分點(diǎn)方法1:窮舉法將記錄中中所有的的屬性值值作為候候選劃分分點(diǎn)，計(jì)計(jì)算每個(gè)個(gè)候選的的Gini指標(biāo)，并并從中選選擇具有有最小值值的候選選劃分點(diǎn)點(diǎn)。效率低計(jì)算代價(jià)價(jià)昂貴改進(jìn)方法法：根據(jù)劃分分屬性，，先對(duì)記記錄進(jìn)行行排序從兩個(gè)相相鄰的排排過(guò)序的的屬性值值中選擇中間間值作為為候選劃劃分點(diǎn)(55、65、72、80、……）。在計(jì)計(jì)算相鄰鄰結(jié)點(diǎn)時(shí)時(shí)值，部部分類分分布保持持不變，，減少計(jì)計(jì)算量。。進(jìn)一步優(yōu)優(yōu)化：僅僅考考慮位于于具有不不同類標(biāo)標(biāo)號(hào)的兩兩個(gè)相鄰鄰記錄之之間的候候選劃分分點(diǎn)（55、80、97），計(jì)算算其Gini指數(shù)。候選劃分點(diǎn)排序后的值決策樹(shù)歸歸納的設(shè)設(shè)計(jì)問(wèn)題題2：如何停止止分裂過(guò)過(guò)程？停止方法法：方法1：當(dāng)所有有記錄都都屬于同同一分類類時(shí)，停停止劃分分方法2：當(dāng)所有有記錄都都有相似似（相同同）屬性性值時(shí)，，停止劃劃分方法3：提前前終止止決策樹(shù)樹(shù)歸納納算法法算法輸輸入：：訓(xùn)練練記錄錄集E和屬性性集F。算法輸輸出：：構(gòu)造造的決決策樹(shù)樹(shù)主要函函數(shù)：：createNode()：建立立一個(gè)個(gè)新結(jié)結(jié)點(diǎn)。。結(jié)點(diǎn)要要么表表示一一個(gè)測(cè)測(cè)試條條件(node.test_cond),要么表表示一一個(gè)類類標(biāo)號(hào)號(hào)(node.label)find_best_split()：從剩剩余屬屬性中中挑選選一個(gè)個(gè)屬性性作為為結(jié)點(diǎn)點(diǎn)的測(cè)測(cè)試條條件。。Classify()：為葉葉子結(jié)結(jié)點(diǎn)確確定類類標(biāo)號(hào)號(hào)。多數(shù)情情況下下，left.label=stopping_cond()：測(cè)試試是否否應(yīng)該該決策策樹(shù)的的增長(zhǎng)長(zhǎng)TreeGrowth算法框框架（（P101）ifstopping_cond(E,F)=truethenleft=createNode()left.lable=Classify()returnleafelseroot=createNode()root.test_cond=find_best_split(E,F)令V={v|v是root.test_cond的一個(gè)個(gè)可能能輸出出}for每個(gè)v∈∈VdoEv={e|root.test_cond(e)=v并且e∈E}child=TreeGrowth(Ev,F)將child作為root派生結(jié)結(jié)點(diǎn)加加到樹(shù)樹(shù)中，，將邊邊(rootchild)記為vendforendifreturnroot案例學(xué)學(xué)習(xí)：：機(jī)器人人檢測(cè)測(cè)閱讀課課本例例子，，回答答下列列問(wèn)題題：什么是是Web使用挖挖掘？？Web使用挖挖掘的的數(shù)據(jù)據(jù)源是是什么么？這這些數(shù)數(shù)據(jù)是是如何何得到到的？？為什么么說(shuō)在在Web挖掘中中，區(qū)區(qū)分正正常用用戶訪訪問(wèn)和和Web機(jī)器人人訪問(wèn)問(wèn)時(shí)重重要的的？本例子子中，，決策策樹(shù)模模型是是如何何建立立起來(lái)來(lái)的？？請(qǐng)你你用1分鐘長(zhǎng)長(zhǎng)度的的時(shí)間間，敘敘述其其建立立的過(guò)過(guò)程。。根據(jù)課課本的的決策策樹(shù)模模型，，正常常用戶戶訪問(wèn)問(wèn)有何何特征征？決策樹(shù)樹(shù)歸納納的特特點(diǎn)是一種種構(gòu)建建分類類模型型的非非參數(shù)數(shù)方法法大多決決策樹(shù)樹(shù)算法法都采采用啟啟發(fā)式式的方方法來(lái)來(lái)簡(jiǎn)化化搜索索決策樹(shù)容易易構(gòu)建，對(duì)對(duì)未知樣本本的分類也也快決策樹(shù)相對(duì)對(duì)容易理解解對(duì)于噪聲的的干擾具有有相當(dāng)好的的魯棒性冗余屬性不不會(huì)對(duì)決策策樹(shù)的準(zhǔn)確確率造成不不利影響對(duì)于數(shù)據(jù)碎碎片問(wèn)題，，可以通過(guò)過(guò)規(guī)定閾值值來(lái)檢測(cè)和和解決