【正文】 ?開始時，所有的訓(xùn)練樣本都在根節(jié)點 ?遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） – 樹剪枝 ?許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝 ? 決策樹的使用：對未知樣本進行分類 – 通過將樣本的屬性值與決策樹相比較 決策樹分類任務(wù) A p p l y M o d elI n d u c t i o nD e d u c t i o nL ea r n M o d elM o d e lTid A t t r i b 1 A t t r i b 2 A t t r i b 3 C l a s s 1 Yes L a rg e 125K No 2 No Me d iu m 100K No 3 No S m a ll 70K No 4 Yes Me d iu m 120K No 5 No L a rg e 95K Yes 6 No Me d iu m 60K No 7 Yes L a rg e 220K No 8 No S m a ll 85K Yes 9 No Me d iu m 75K No 10 No S m a ll 90K Yes 10 T i d A t t r i b 1 A t t r i b 2 A t t r i b 3 Class 11 No S m a ll 55K ? 12 Y e s Me d iu m 80K ? 13 Y e s L a rg e 110K ? 14 No S m a ll 95K ? 15 No L a rg e 67K ? 10 T e s t S e tT r e eI n d u c t i o na l g o r i t h mT r a i n i n g S e tDecision Tree 一個決策樹的例子 Tid Re f und Marital Stat u s Taxable In e Che a t 1 Yes Single 125K No 2 No Marr i ed 100K No 3 No Single 70K No 4 Yes Marr i ed 120K No 5 No Divor ce d 95K Yes 6 No Marr i ed 60K No 7 Yes Divor ce d 220K No 8 No Single 85K Yes 9 No Marr i ed 75K No 10 No Singl e 90K Yes 10 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Splitting Attributes 訓(xùn)練數(shù)據(jù) 模型 : 決策樹 應(yīng)用決策樹進行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Ref un d Ma ri tal S tatu s Taxa bl e I nco m e Chea t No Ma rri ed 80K ? 10 測試數(shù)據(jù) Start from the root of tree. 應(yīng)用決策樹進行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Ref un d Ma ri tal S tatu s Taxa bl e I nco m e Chea t No Ma rri ed 80K ? 10 測試數(shù)據(jù) 應(yīng)用決策樹進行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Ref un d Ma ri tal S tatu s Taxa bl e I nco m e Chea t No Ma rri ed 80K ? 10 測試數(shù)據(jù) 應(yīng)用決策樹進行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Ref un d Ma ri tal S tatu s Taxa bl e I nco m e Chea t No Ma rri ed 80K ? 10 測試數(shù)據(jù) 應(yīng)用決策樹進行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Ref un d Ma ri tal S tatu s Taxa bl e I nco m e Chea t No Ma rri ed 80K ? 10 測試數(shù)據(jù) 應(yīng)用決策樹進行分類 Refund MarSt TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K Ref un d Ma ri tal S tatu s Taxa bl e I nco m e Chea t No Ma rri ed 80K ? 10 測試數(shù)據(jù) Assign Cheat to “No” 決策樹分類 A p p l y M o d elI n d u c t i o nD e d u c t i o nL ea r n M o d elM o d e lTid A t t r i b 1 A t t r i b 2 A t t r i b 3 C l a s s 1 Yes L a rg e 125K No 2 No Me d iu m 100K No 3 No S m a ll 70K No 4 Yes Me d iu m 120K No 5 No L a rg e 95K Yes 6 No Me d iu m 60K No 7 Yes L a rg e 220K No 8 No S m a ll 85K Yes 9 No Me d iu m 75K No 10 No S m a ll 90K Yes 10 T i d A t t r i b 1 A t t r i b 2 A t t r i b 3 Class 11 No S m a ll 55K ? 12 Y e s Me d iu m 80K ? 13 Y e s L a rg e 110K ? 14 No S m a ll 95K ? 15 No L a rg e 67K ? 10 T e s t S e tT r e eI n d u c t i o na l g o r i t h mT r a i n i n g S e tDecision Tree 決策樹 ? 有許多決策樹算法 : ? Hunt算法 ? 信息增益 ——Information gain （ ID3） ? 增益比率 ——Gain ration（ ） ? 基尼指數(shù) ——Gini index (SLIQ， SPRINT) Hunt 算法 ? 設(shè) Dt 是與結(jié)點 t相關(guān)聯(lián)的訓(xùn)練記錄集 ? 算法步驟 : – 如果 Dt 中所有記錄都屬于同一個類 yt, 則 t是葉結(jié)點，用 yt標(biāo)記 – 如果 Dt 中包含屬于多個類的記錄，則 選擇一個屬性測試條件 ，將記錄劃分成較小的子集。 c )。 ?訓(xùn)練集中的單個元組稱為 訓(xùn)練樣本 ,每個訓(xùn)練樣本有一個類別標(biāo)記。數(shù)據(jù)挖掘 分類：基本概念、決策樹與模型評價 第 4章 分類：基本概念、決策樹與模型評價 ? 分類的是利用一個分類函數(shù)（分類模型、分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)影射到給定類別中的一個。 分類 A p p l y M o d elI n d u c t i o nD e d u c t i o nL ea r n M o d elM o d e lTid A t t r