決策樹分類器培訓(xùn)課件

2023/1/25Guilin1決策樹分類器朱曉峰2023/1/25Guilin2數(shù)據(jù)庫知識發(fā)現(xiàn)技術(shù)數(shù)據(jù)預(yù)處理：屬性約簡，缺失值填充…關(guān)聯(lián)規(guī)則分類或預(yù)測聚類可視化分析2023/1/25Guilin3什么叫分類？分類是一個古老的方法、現(xiàn)代熱門的課題已知數(shù)據(jù)的集合D：數(shù)據(jù)被標(biāo)記學(xué)習(xí)：從數(shù)據(jù)集合中歸納出規(guī)則、規(guī)律等，通常稱為分類器，或模型預(yù)測：用分類器預(yù)測新數(shù)據(jù)的類這種從有標(biāo)記的數(shù)據(jù)種歸納分類器的方法叫監(jiān)督學(xué)習(xí)決策樹、回歸是最常用的分類器分類任務(wù)圖例分類任務(wù)例子PredictingtumorcellsasbenignormalignantClassifyingcreditcardtransactions

aslegitimateorfraudulentClassifyingsecondarystructuresofprotein

asalpha-helix,beta-sheet,orrandom

coilCategorizingnewsstoriesasfinance,

weather,entertainment,sports,etc分類技術(shù)DecisionTreebasedMethodsRule-basedMethodsMemorybasedreasoningNeuralNetworksNa?veBayesandBayesianBeliefNetworksSupportVectorMachines2023/1/25Guilin7決策樹分類器/模型學(xué)習(xí)將已知數(shù)據(jù)集合分成訓(xùn)練數(shù)據(jù)集合測試集合學(xué)習(xí)：從一個訓(xùn)練數(shù)據(jù)集合歸納出一棵決策樹：從完全空間搜索一棵最佳樹的過程預(yù)測：用決策樹分類新數(shù)據(jù)決策樹是最常用的分類器之一不要求任何知識或參數(shù)設(shè)定它是一種監(jiān)督學(xué)習(xí)方法一棵決策樹可以表示成一組規(guī)則2023/1/25Guilin8決策樹的結(jié)構(gòu)決策樹是層次的樹結(jié)構(gòu)由一些節(jié)點(diǎn)和枝（邊）組成，一棵決策樹至少有一個節(jié)點(diǎn)枝的兩端是節(jié)點(diǎn)一棵決策樹通常是從左到右，或從上到下畫圖樹的第一個節(jié)點(diǎn)稱為根節(jié)點(diǎn)，“根-枝-節(jié)點(diǎn)-...–節(jié)點(diǎn)”的最后一個節(jié)點(diǎn)是葉節(jié)點(diǎn)，其它節(jié)點(diǎn)叫中間節(jié)點(diǎn)非葉節(jié)點(diǎn)至少有一條枝2023/1/25Guilin9決策樹分類器的解釋一棵決策樹是訓(xùn)練數(shù)據(jù)的一個劃分樹的一個非葉節(jié)點(diǎn)是對一個屬性上的測試一個屬性的一條枝是測試該屬性的一個結(jié)果一個葉節(jié)點(diǎn)是一個類標(biāo)記在每個非葉節(jié)點(diǎn)，一個屬性被選中，它將訓(xùn)練數(shù)據(jù)分裂成盡可能不同類的子集合（劃分）對于一個新數(shù)據(jù)，根據(jù)它的每個屬性值從根節(jié)點(diǎn)一直匹配到葉節(jié)點(diǎn)，這個葉節(jié)點(diǎn)的標(biāo)記就用來預(yù)測新數(shù)據(jù)的類2023/1/6Guilin10構(gòu)造決策樹樹分類器的的原則目標(biāo)：最大化預(yù)測測新數(shù)據(jù)的的精度（實(shí)現(xiàn)困難）通常將給定定的已知數(shù)據(jù)隨機(jī)分成訓(xùn)練集合和測試集合。訓(xùn)練數(shù)據(jù)用用于歸納分類器器，測試數(shù)據(jù)據(jù)用來評估分類器器訓(xùn)練分類器器時的目標(biāo)標(biāo)是最大化預(yù)測測測試數(shù)據(jù)的的精度，即，該分分類器基本本上體現(xiàn)兩個（訓(xùn)練和測測試）集合的共同同結(jié)構(gòu)過度擬合（overfitting）問題：擬擬合訓(xùn)練數(shù)數(shù)據(jù)的效果果很好，擬擬合測試數(shù)數(shù)據(jù)的效果果很差2023/1/6Guilin11舉例說明（（訓(xùn)練數(shù)據(jù)據(jù)）2023/1/6Guilin12舉例說明（（決策樹））2023/1/6Guilin13舉例說明（測測試數(shù)據(jù)）決策樹是用于于預(yù)測一個數(shù)數(shù)據(jù)的類問題：Alex,BuddyandCheery使用哪種交通通工具？2023/1/6Guilin14舉例說明（決決策樹的運(yùn)用用）從根節(jié)點(diǎn)Travelcostperkm開始如果TravelCost=expensive，Transportationmode=car如果TravelCost=standard，Transportationmode=train如果TravelCost=cheap，決策樹需要要檢查下一個個節(jié)點(diǎn)Gender如果Gender=male，Transportationmode=bus如果Gender=female，決策樹需要要檢查下一個個節(jié)點(diǎn)Carownership如果Carownership=0，Transportationmode=bus，否則Transportationmode=train2023/1/6Guilin15舉例說說明（（決策策樹））2023/1/6Guilin16舉例說說明（（決策策樹產(chǎn)產(chǎn)生的的規(guī)則則）每個葉葉節(jié)點(diǎn)點(diǎn)產(chǎn)生生一條條規(guī)則則Rule1：IfTravelcost=expensivethenMode=carRule2：IfTravelcost=standardthenMode=trainRule3：IfTravelcost=cheapGender=malethenMode=busRule4：IfTravelcost=cheapGender=femaleCarownership=0thenMode=busRule5：IfTravelcost=cheapGender=femaleCarownership=1thenMode=train2023/1/6Guilin17舉例說明明（預(yù)測測）根據(jù)上面面的決策策樹或者者規(guī)則，，回答前前面的問問題就很很簡單、、直接Alex：Travelcost=standard，所以，無無論其它屬屬性取什么么值，可以以預(yù)測他的的交通工具具是trainBuddy：Travelcost=cheap并且Gender=male，則可以預(yù)預(yù)測他的交交通工具是是busCherry：Travelcost=cheap并且Gender=female并且Carownership=1，則可以預(yù)預(yù)測他的交交通工具是是train2023/1/6Guilin18決策樹樹的缺缺點(diǎn)多數(shù)決決策樹樹算法法采用用貪心策策略：按照照設(shè)定定的啟啟發(fā)式式信息息搜索索最佳佳樹無回溯溯非窮近近搜索索，但可可能剪枝2023/1/6Guilin19如何建構(gòu)構(gòu)決策樹樹？決策樹很很簡單，，但實(shí)現(xiàn)現(xiàn)建構(gòu)一一棵好的的樹是很很困難的的在上面的的例子中中，屬性性Incomelevel沒有用于于交通工工具的分分類建構(gòu)一棵棵樹通常常的辦法法（啟發(fā)式信信息）是度量量數(shù)據(jù)集集的不純純度（impurity）EntropyGiniindexClassificationerror2023/1/6Guilin20不純度的定定義給定一個訓(xùn)訓(xùn)練數(shù)據(jù)集集（決策表），我們能能根據(jù)類屬性度度量它的同構(gòu)性（或異構(gòu)性heterogeneity）如果一個訓(xùn)訓(xùn)練數(shù)據(jù)集集的類屬性只取一個類值，它是純的的或者同構(gòu)構(gòu)的如果一個訓(xùn)訓(xùn)練數(shù)據(jù)集集的類屬性性取多個類值，它是不純純的或者異異構(gòu)的2023/1/6Guilin21如何度量不純度有多種量化化方法度量量不純度最常用的三三種方法如如下上面所有的度度量方法都含含有類j的概率pj2023/1/6Guilin22舉例說明（訓(xùn)訓(xùn)練數(shù)據(jù)）2023/1/6Guilin23舉例說明明（類的的頻率））在訓(xùn)練數(shù)數(shù)據(jù)集合合中，類類屬性Transportationmode有三個類類值Bus、Car和Train我們的例例子中，，每個值值出現(xiàn)的的次數(shù)如如下4buses3cars3trains簡單記為為4B,3C,3T總數(shù)據(jù)量量是10個標(biāo)記的的例子2023/1/6Guilin24舉例說明明（計(jì)算算概率））根據(jù)上面面的數(shù)據(jù)據(jù)，每個個類的概概率如下下：p(Bus)=4/10=0.4p(Car)=3/10=0.3p(Train)=3/10=0.3注意，在在上面的的概率計(jì)計(jì)算中，，我們只只考慮了了類屬性性Transportationmode，其它屬屬性都不不考慮有了每個個類的概概率，我我們就可可以用前前面的方方法計(jì)算算訓(xùn)練數(shù)數(shù)據(jù)集合合的不純純度2023/1/6Guilin25舉例說明明（用熵熵計(jì)算概概率）計(jì)算訓(xùn)練練數(shù)據(jù)集集合的不不純度的的一個方方法就是是采用熵熵（entropy）已知p(Bus)=0.4,p(Car)=0.3和p(Train)=0.3，熵的計(jì)計(jì)算如下下：Entropy=––0.4log(0.4)–0.3log(0.3)––0.3log(0.3)=1.571對數(shù)的底底是22023/1/6Guilin26熵的性性質(zhì)一個純純的訓(xùn)訓(xùn)練數(shù)數(shù)據(jù)集集合（（只有有一個個類））的熵熵是0，這是是因?yàn)闉楦怕事?的對數(shù)數(shù)log(1)=0在多個個類的的情況況下，，熵在在每個個類的的概率率相等等時達(dá)達(dá)到最最大值值下面的的圖描描出了了不同同的類類個數(shù)數(shù)n的熵的的最大大值，，這里里，p=1/n熵的最最大值值是-n*p*logp注意：：當(dāng)類類個數(shù)數(shù)n>2時，熵熵>12023/1/6Guilin27圖示熵熵的性性質(zhì)2023/1/6Guilin28舉例說明（（用Gini索引計(jì)算概率））計(jì)算訓(xùn)練數(shù)數(shù)據(jù)集合的的不純度的的第二個方方法是采用用Gini索引（Giniindex）已知p(Bus)=0.4,p(Car)=0.3和p(Train)=0.3，Gini索引值的計(jì)計(jì)算如下：：GiniIndex=1–(0.4^2+0.3^2+0.3^2)=0.6602023/1/6Guilin29Gini索引的性質(zhì)一個純的訓(xùn)訓(xùn)練數(shù)據(jù)集集合（只有有一個類））的Gini索引值是0，這是因?yàn)闉楦怕?的Gini索引值是1-(1)^2=0與熵一樣，，Gini索引在每個個類的概率率相等時達(dá)達(dá)到最大值值下面的圖描描出了不同同的類個數(shù)數(shù)n的Gini索引的最大大值，這里里，p=1/n注意：無論論有多少個個類值，Gini索引值總是是在0和1之間2023/1/6Guilin30圖示Gini索引的性質(zhì)2023/1/6Guilin31舉例說明（（用分類誤差計(jì)算概率））計(jì)算訓(xùn)練數(shù)數(shù)據(jù)集合的的不純度的的第三個方方法是采用用分類誤差差（classificationerror）已知p(Bus)=0.4,p(Car)=0.3和p(Train)=0.3，分類誤差差值的計(jì)算算如下：Classification_Error=1––Max{0.4,0.3,0.3}=1-0.4=0.602023/1/6Guilin32分類誤差差的性質(zhì)與熵和Gini索引一樣樣，一個個純的訓(xùn)訓(xùn)練數(shù)據(jù)據(jù)集合（（只有一一個類））的分類類誤差值值是0，這是因因?yàn)楦怕事?的分類誤誤差值是是1-max(1)=0分類誤差差值總是是在0和1之間對于給定定類的個個數(shù)，Gini索引的最最大值總總是與分分類誤差差的最大大值相等等設(shè)每個類類的概率率為p=1/n，Gini索引的最最大值是是1-n*(1/n)^2=1-1/n，而分類類誤差的的最大值值也是1-max{1/n}=1-1/n2023/1/6Guilin33決策樹算算法的運(yùn)運(yùn)行方式式這里解釋釋決策樹樹算法的的運(yùn)行方方式設(shè)一個訓(xùn)訓(xùn)練數(shù)據(jù)據(jù)集合D有多個屬屬性和一一個類屬屬性對于D，取出每每個屬性性和類屬屬性形成成一個子子集合如果有m個屬性，，我們就就從D構(gòu)造出m個子集合合設(shè)第i個屬性的的子集合合為Si這里，D是Si的父親2023/1/6Guilin34舉例說明明（訓(xùn)練練數(shù)據(jù)））2023/1/6Guilin35舉例說明明（訓(xùn)練練數(shù)據(jù)的的子集合合）S1S2S3S42023/1/6Guilin36取多值值的屬屬性對于屬屬性i的Si表（子子集合合），，我們們需要要分別別計(jì)算算每個個屬性性i的不純純度例如，，屬性性Travelcost有三個個值：：Cheap,Standard和Expensive它應(yīng)該該分成成三個個表（（子集集合））2023/1/6Guilin37屬性Travelcost與三個個表TravelCosts:CheapStandardExpensive2023/1/6Guilin38信息增益益（informationgain）選擇分裂裂數(shù)據(jù)集集D的屬性，，需要比比較D和各個子子集合Si之間的不不純度差差異數(shù)據(jù)集D和子集合合Si的不純度度之差異異被稱為為信息增增益（informationgain）所以，需需要計(jì)算算每個屬屬性的信信息增益益值2023/1/6Guilin39信息增益益計(jì)算方方法一個屬性性的信息息增益是是它產(chǎn)生生的子集集合的父父集合的的不純度度與該子子集合的的不純度度之差該子集合的的不純度是是它分解的的表的不純純度的加權(quán)權(quán)之和，權(quán)權(quán)值一般是是每個表所所占的比例例對于熵方法法，屬性i的信息增益益計(jì)算如下下Informationgain(i)=i的父集合的的熵–(ki/n*Si產(chǎn)生的表ki的熵)2023/1/6Guilin40屬性TravelCost的信息增益對于訓(xùn)練數(shù)據(jù)據(jù)集D，我們有三個個類4B、3C、3T，D的熵是1.571對于屬性TravelCost，它產(chǎn)生的子子集合可以分分成如下三個個表值Cheap有兩個個類4B,1T，它的的熵是是0.722值Standard有一個個類2T，它的的熵是是0值Expensive有一個個類，，它的的熵是是0屬性TravelCost的信息息增益益是1.571––(5/10*0.722+2/10*0+3/10*0)=1.2102023/1/6Guilin41屬性TravelCost按三種方方法計(jì)算算的信息息增益同樣，我我們也可可以用Gini索引和分分類誤差差計(jì)算屬屬性TravelCost的信息增益益采用三種種方法計(jì)計(jì)算出屬屬性TravelCost的信息增增益如下下Entropy:1.210GiniIndex:0.500ClassificationError:0.5002023/1/6Guilin42屬性Gender按三種方法計(jì)算的的信息增益益采用三種方方法計(jì)算出出屬性Gender的信息增益益如下Entropy:0.125GiniIndex:0.060ClassificationError:0.1002023/1/6Guilin43屬性采用三種方法法計(jì)算出屬性性CarOwnership的信息增益如如下Entropy:0.534GiniIndex: 0.207ClassificationError: 0.2002023/1/6Guilin44屬性IncomeLevel按三種種方法計(jì)計(jì)算的的信息息增益益采用三三種方方法計(jì)計(jì)算出出屬性性IncomeLevel的信息息增益益如下下Entropy:0.695GiniIndex:0.293ClassificationError:0.3002023/1/6Guilin45分裂屬屬性選選擇的的標(biāo)準(zhǔn)準(zhǔn)在決策策樹構(gòu)構(gòu)建中中，哪哪個屬屬性是是目前前最好好的？？產(chǎn)生最最小樹樹的屬屬性啟發(fā)式式:選擇產(chǎn)產(chǎn)生最最純的的屬性性常用的的度量量：信息增增益策略：：選擇信信息增增益最最大的的屬性性為分分裂數(shù)數(shù)據(jù)集集合的的屬性性2023/1/6Guilin46選擇第第一個個分裂裂屬性性有了所所有屬屬性的的信息息增益益后，，我們們就可可以找找出信信息增增益最最大的的那個個屬性性：i*=argmax{informationgainofattributei}在我們們的例例子中中，屬屬性TravelCost產(chǎn)生的的信息息增益益最大大該屬性性作為為決策策樹的的當(dāng)前前節(jié)點(diǎn)點(diǎn)因?yàn)樗堑诘谝粋€個節(jié)點(diǎn)點(diǎn)，它它就是是決策策樹的的根節(jié)節(jié)點(diǎn)一棵決決策樹樹可以以只有有一個個節(jié)點(diǎn)點(diǎn)2023/1/6Guilin47用屬性性TravelCost分裂訓(xùn)訓(xùn)練數(shù)數(shù)據(jù)集集一個分分裂屬屬性選選定后后，我我們可可以根根據(jù)該該屬性性將當(dāng)當(dāng)前的的數(shù)據(jù)據(jù)集合合分裂裂成多多個子子集合合在我們們的例例子中中，我我們根根據(jù)TravelCost的取值值分列列D訓(xùn)練數(shù)數(shù)據(jù)集集合D被分裂裂成三三個子子集合合2023/1/6Guilin48用屬性TravelCost分裂訓(xùn)練數(shù)數(shù)據(jù)集的結(jié)結(jié)果數(shù)據(jù)被分裂裂后，我們們有TravelCost=Expensive只有一個類類CarTravelCost=Standard只有一個類類TrainTravelCost=Cheap需要進(jìn)一步步分裂產(chǎn)生純類（（只含一個個類）的屬屬性值總是是作為決策策樹的葉節(jié)節(jié)點(diǎn)這樣就完完成了決決策樹構(gòu)構(gòu)造的第第一個循循環(huán)2023/1/6Guilin49訓(xùn)練數(shù)據(jù)集的的三個子集合合2023/1/6Guilin50用屬性TravelCost產(chǎn)生的樹樹2023/1/6Guilin51第二次循循環(huán)屬性值Expensive和Standard是純類，，不再需需要分裂裂當(dāng)TravelCost=Cheap，它有多多個類，，需要繼繼續(xù)分裂裂將相應(yīng)的的表中的的數(shù)據(jù)作作為待分分裂的數(shù)數(shù)據(jù)，開開始第二二次循環(huán)環(huán)2023/1/6Guilin52為第二次次循環(huán)產(chǎn)產(chǎn)生數(shù)據(jù)據(jù)集合2023/1/6Guilin53Cheap連接的的節(jié)點(diǎn)點(diǎn)的數(shù)數(shù)據(jù)集集合的的不純純度現(xiàn)在只只有三三個屬屬性Gender、carownership、IncomelevelCheap連接的的節(jié)點(diǎn)點(diǎn)的數(shù)數(shù)據(jù)集集合的的不純純度如如下2023/1/6Guilin54屬性Gender按三種方法計(jì)算的信信息增益采用三種方法法計(jì)算出屬性性Gender的信息增益益如下Entropy:0.322GiniIndex:0.120ClassificationError:0.0002023/1/6Guilin55其它屬屬性按按三種種方法法計(jì)算算的信信息增增益采用三三種方方法計(jì)計(jì)算出出屬性性CarOwnership的信息息增益益如下下Entropy:0.171GiniIndex:0.053ClassificationError:0.000采用三三種方方法計(jì)計(jì)算出出屬性性IncomeLevel的信息息增益益如下下Entropy:0.171GiniIndex:0.053ClassificationError:0.0002023/1/6Guilin56為第二二次循循環(huán)選選擇分分裂屬屬性通過比比較屬屬性Gender的信息息增益益最大大當(dāng)前的的數(shù)據(jù)據(jù)集合合將按按照屬屬性Gender的取值值分裂裂在我們們的例例子中中，屬屬性值值Male只有一一個類類Bus，屬性性值Female有多個個類，，需要要繼續(xù)續(xù)分裂裂2023/1/6Guilin57第二次次循環(huán)環(huán)的數(shù)數(shù)據(jù)集集合分分裂2023/1/6Guilin58第二次循環(huán)環(huán)產(chǎn)生的樹樹2023/1/6Guilin59用屬性Gender分裂子數(shù)據(jù)據(jù)集的結(jié)果果節(jié)點(diǎn)Gender有兩個值MaleFemale屬性值Male是純的類，，是葉節(jié)點(diǎn)點(diǎn)屬性值Female有多個類，，需要在下下一個循環(huán)環(huán)繼續(xù)分裂裂2023/1/6Guilin60第三次循循環(huán)第三次循循環(huán)的數(shù)數(shù)據(jù)是第第二次循循環(huán)留待待分的數(shù)數(shù)據(jù)集合合屬性值Female的數(shù)據(jù)剩下可以以考慮的的屬性只只有兩個個CarownershipIncomelevel2023/1/6Guilin61為第三三次循循環(huán)產(chǎn)產(chǎn)生數(shù)數(shù)據(jù)集集合2023/1/6Guilin62Female連接的的節(jié)點(diǎn)點(diǎn)的數(shù)數(shù)據(jù)集集合的的不純純度只有兩兩個記記錄兩個記記錄有有不同同的類類如果選選用屬屬性carownership作為分分裂屬屬性，，我們們將得得到兩兩個純純類的的子集集合同樣，如果選選用屬性incomelevel作為分裂屬性性，我們也將將得到兩個純純類的子集合合所以，任意選選一個即可，，不需要計(jì)算算信息增益值值假設(shè)我們選用用屬性carownership，我們得到一一顆決策樹，，循環(huán)結(jié)束2023/1/6Guilin63建立的決決策樹2023/1/6Guilin64評估技術(shù)術(shù)Holdout:訓(xùn)練集合合/測試集合合數(shù)據(jù)集合合很大時時較好k-fold交叉驗(yàn)證證:將數(shù)據(jù)集集合分成成k子集合在每次建建樹時，，使用一一個子集集合作為為測試集集合，其其它k-1子集合一一起作為為訓(xùn)練集集合用這k次結(jié)果的的均值作作為參照照它消除了了訓(xùn)練集集合/測試集合合方法的的隨機(jī)性2023/1/6Guilin6565交叉驗(yàn)驗(yàn)證圖圖解數(shù)據(jù)集集合分分成k段一個做做測試

重復(fù)到Testiteration2023/1/6Guilin66增益率增益率（Gainratio）：是信息增益的的一個改良良版，它可可以減少信信息增益偏偏好于取值值較多的屬屬性增益率考慮