決策樹

DecisionTree精選ppt決策樹算法是一種歸納分類算法,它通過對訓練集的學習,挖掘出有用的規則,用于對新集進行預測。有監督的學習。

非參數學習算法。對每個輸入使用由該區域的訓練數據計算得到的對應的局部模型。

決策樹歸納的基本算法是貪心算法，自頂向下遞歸方式構造決策樹。貪心算法：在每一步選擇中都采取在當前狀態下最好/優的選擇。在其生成過程中，分割方法即屬性選擇度量是關鍵。通過屬性選擇度量，選擇出最好的將樣本分類的屬性。

簡介精選ppt決策樹的結構

決策樹算法以樹狀結構表示數據分類的結果。每個決策點實現一個具有離散輸出的測試函數，記為分支。根節點非葉子節點（決策點）葉子節點分支精選ppt

決策樹的結構4根部節點(rootnode)非葉子節點(non-leafnode)(代表測試的條件，對數據屬性的測試)分支(branches)(代表測試的結果)葉節點(leafnode)(代表分類后所獲得的分類標記)2023/4/17精選ppt單變量樹

每個內部節點中的測試只使用一個輸入維。如果使用的輸入維是離散的，取n個可能的值之一，則該節點檢測的值，并取相應的分支，實現一個n路劃分。決策點具有離散分支，而數值輸入應當離散化。如果是數值的（有序的），則測試函數是比較：其中是適當選擇閾值。該決策節點將輸入空間一份為二：和，稱為一個二元劃分。決策樹根據所選取的屬性是數值型還是離散型，每次將數據劃分成兩個或n個子集。然后使用對應的子集遞歸地進行劃分，直到不需要劃分，此時，創建一個樹葉節點標記它。精選ppt決策樹分類訓練階段

從給定的訓練數據集DB，構造出一棵決策樹

NB=DecisionTree(data,class)分類階段

從根開始，按照決策樹的分類屬性逐層往下劃分，直到葉節點，獲得概念（決策、分類）結果。y=DecisionTree(NB,x)精選pptExampleofaDecisionTree

精選pptAnotherExampleofDecisionTree

精選pptApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KTestDataStartfromtherootoftree.精選pptApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KTestData精選pptApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KTestData精選pptApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80KTestData精選pptApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80KTestData精選pptApplyModeltoTestDataRefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80KTestDataAssignCheatto“No”精選ppt決策樹原理基本算法（貪心算法）自上而下分而治之的方法開始時，所有的數據都在根節點屬性都是離散值字段(如果是連續的，將其離散化)所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發式規則或者一個統計的度量(如,informationgain)停止分割的條件一個節點上的數據都是屬于同一個類別沒有屬性可以再用于對數據進行分割精選ppt

算法：Generate_decision_tree由給定的訓練數據產生一棵決策樹輸入：訓練數據集samples，用離散值屬性表示；候選屬性的集合attribute_list。輸出：一棵決策樹方法：（1）創建結點N；（2）ifsamples都在同一個類Cthen（3）返回N作為葉結點，用類C標記；（4）ifattribute_list為空then（5）返回N作為葉結點，標記samples中最普通的類； //多數表決（6）選擇attribute_list中的最優分類屬性test_attribute；//用信息增益作為屬性選擇度量（7）標記結點N為test_attribute；（8）foreachtest_attribute中的已知值ai//劃分samples（9）由結點N生長出一個條件為test_attribute＝ai的分枝；（10）設si為samples中test_attribute＝ai的樣本集合； //一個劃分（11）ifsi為空then（12）加上一個葉結點，標記為標記samples中最普通的類； //多數表決（13）else加上一個由Generate_decision_tree（si,attribute_list-test_attribute）返回的結點；精選ppt例子：算法過程RefundYesNo1.samples={1,2,3,4,5,6,7,8,9,10}

attribute_list={Refund,MarSt,TaxInc}假設選擇Refund為最優分割屬性：2.samples={1,4,7}

attribute_list={MarSt,TaxInc}3.samples={2,3,5,6,8,9,10}

attribute_list={MarSt,TaxInc}精選ppt例子：算法過程RefundYesNosamples中所有樣本屬于同一個類Cheat=No2.samples={1,4,7}

attribute_list={MarSt,TaxInc}NO精選ppt例子：算法過程RefundYesNo假設選擇MarSt為最優分割屬性：3.samples={2,3,5,6,8,9,10}

attribute_list={MarSt,TaxInc}NOMarStSingleMarriedDivorced4.samples={3,8,10},attribute_list={TaxInc}5.samples={5,7},attribute_list={TaxInc}6.samples={2,9},attribute_list={TaxInc}精選ppt例子：算法過程RefundYesNo選擇TaxInc為最優分割屬性：4.samples={3,8,10}

attribute_list={TaxInc}NOMarStSingleMarriedDivorcedTaxInc<80K>=80KYESNO精選ppt問題1：分類從哪個屬性開始？

——選擇分裂變量的標準問題2：為什么工資以80為界限？

——找到被選擇的變量的分裂點的標準（連續變量情況）精選ppt分類劃分的優劣用不純性度量來分析。如果對于所有分支，劃分后選擇相同分支的所有實例都屬于相同的類，則這個劃分是純的。對于節點m，令為到達節點m的訓練實例數，個實例中個屬于類，而。如果一個實例到節點m，則它屬于類的概率估計為：節點m是純的，如果對于所有i，為0或1。當到達節點m的所有實例都不屬于類時，為0，當到達節點m的所有實例都屬于類時，為1。一種度量不純性的可能函數是熵函數（entropy)。精選pptFatherofinformationtheory證明熵與信息內容的不確定程度有等價關系

系統科學領域三大論之一C.Shannon的信息論信息熵熵(entropy)描述物質系統狀態:該狀態可能出現的程度。平均信息量若一個系統中存在多個事件E1,E2,…En每個事件出現的概率是p1,p2,…pn則這個系統的平均信息量是指的是系統的混亂的程度!(bits)精選ppt系統越無序、越混亂，熵就越大。構造決策樹，熵定義為無序性度量。選擇一個屬性劃分數據，使得子女節點上數據的類值（例中“yes”或“no”）大部分都相同（低無序性）。如果一個節點上的數據類值在可能的類值上均勻分布，則稱節點的熵（無序性）最大。如果一個節點上的數據的類值對于所有數據都相同，則熵最小。通過分裂，得到盡可能純的節點。這相當于降低系統的熵。精選ppt例子氣象數據集，都是標稱屬性什么因素影響是否去打網球？OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNo精選ppt1.基于天氣的劃分2.基于溫度的劃分3.基于濕度的劃分4.基于有風的劃分精選ppt構造樹訓練樣本的信息值第一棵樹，屬性，各葉節點的信息值第一棵樹，屬性，導致的信息增益依次，計算每棵樹導致的信息增益選擇獲得最大信息增益的屬性進行劃分以此類推，遞歸，繼續劃分當所有葉節點都是純的，劃分過程終止精選ppt（1）訓練樣本的信息值(基于類的比例）訓練樣本（用來創建樹的數據集）在包含9個yes和5個no的根節點上，對應于信息值info([9,5])=0.940位→總的信息精選ppt（2）第一棵樹，屬性，各葉節點的信息值基于天氣(outlook)的劃分，在葉節點的yes和no類的個數分別是[2,3]，[4,0]，和[3,2]，而這些節點的信息值分別是：info([2,3])=0.971位→sunnyinfo([4,0])=0.0位→overcastinfo([3,2])=0.971位→rainYESNo合計sunny235overcast404rain325合計95精選ppt（3）第一棵樹，屬性，導致的信息增益計算平均信息值。根據天氣的樹導致的信息增益為：基于類比例原來信息需求-基于天氣屬性劃分之后得到的信息需求gain(outlook)=info([9,5])-info([2,3],[4,0],[3,2])=0.940-0.693=0.247位精選ppt（4）依次，計算每棵樹導致的信息增益為每個屬性計算信息增益gain(outlook)=0.247位gain(temperature)=0.029位gain(humidity)=0.152位gain(windy)=0.048位精選ppt（5）選擇獲得最大信息增益的屬性進行劃分最大信息增益：gain(outlook)=0.247位選擇天氣作為樹的根節點的劃分屬性，其中一個子女節點是最純的，并且這使它明顯優于其他屬性。濕度是次佳選擇，它產生了一個幾乎完全純的較大的子女節點。精選ppt（6）以此類推，遞歸，繼續劃分遞歸繼續選擇當天氣為晴時，所達到的節點上的可能的深一層的分支除天氣外，其他屬性產生的信息增益分別為：gain(temperature)=0.571位gain(humidity)=0.971位gain(windy)=0.020位繼續再選擇濕度(humidity)作為劃分屬性精選ppt天氣，晴分支純子節點精選ppt（6）以此類推，遞歸，繼續劃分天氣，晴分支，氣溫，gain(temperature)=0.571位天氣，晴分支，濕度，gain(humidity)=0.971位(純的子女節點）天氣，晴分支，有風，gain(windy)=0.020位天氣，雨分支，氣溫，gain(temperature)=0.020位天氣，雨分支，濕度，gain(humidity)=0.020位天氣，雨分支，有風，gain(windy)=0.971位（純的子女節點）精選ppt天氣雨分支有風純的子節點精選ppt（7）當所有葉節點都是純的，劃分過程終止理想情況下，當所有葉節點都是純的而使過程終止時，即當它們包含的實例都具有相同類時該過程終止。可能無法達到這種結果，因為無法避免訓練集包含兩個具有相同屬性集，但具有不同類的實例。當數據不能進一步劃分時，停止劃分過程。精選ppt最終的決策樹Weather數據OutlookTemperatureHumidityWindyPlay?sunnyhothighfalseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNoovercasthighnormalfalsetruesunnyrainNoNoYesYesYesOutlookHumidityWindy精選pptID3如何選擇具有最高信息增益的屬性：pi

是D中任意元組屬于類Ci的概率，用|Ci,D|/|D|

估計D中的元組分類所需的期望信息Expectedinformation(entropy)：Informationneeded(afterusingAtosplitDintovpartitions)toclassifyD:InformationgainedbybranchingonattributeA使用屬性A得到準確分類所需信息精選ppt思考：如果考慮充當唯一識別的屬性，如product_ID。對product_ID的分裂結果？Infoproduct_ID(D)=0Gain(product_ID)最大有無實際意義？標識屬性被選為分裂屬性，但標識屬性的分支對預測未知實例的類別并無任何幫助精選pptC4.5C4.5如何選擇具有最高信息增益的屬性：使用“分裂信息（splitinformation）”值將gain規范化表示屬性A第j個劃分的權重。信息率精選pptC4.5算法概述

C4.5算法是ID3算法的擴展能夠處理連續型的屬性。首先將連續型屬性離散化，把連續型屬性的值分成不同的區間，依據是比較各個分裂點Gian值的大小。缺失數據的考慮：在構建決策樹時，可以簡單地忽略缺失數據，即在計算增益時，僅考慮具有屬性值的記錄。精選ppt連續值的處理選取(連續值的)哪個分界點？貪婪算法！1.排序607075859095100120125220若進行“二分”，則可能有9個分界點。例子：607075859095100120125220607075859095100120125220分割成TaxIn<=80和TaxIn>80分割成TaxIn<=97.5和TaxIn>97.5實際上,這就是“離散化”過程精選ppt連續值的處理2.對每個候選的分界點，分別計算熵

例子:測試以80分界的情形(1).TaxIn<=80(2).TaxIn>80(3).加權平均同理,測試以95分界的情形,Info(TaxIn|95)=0.600bits3.比較取