【正文】
?開始時(shí),所有的訓(xùn)練樣本都在根節(jié)點(diǎn) ?遞歸的通過(guò)選定的屬性,來(lái)劃分樣本 (必須是離散值) – 樹剪枝 ?許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn),樹剪枝試圖檢測(cè)和剪去這種分枝 ? 決策樹的使用:對(duì)未知樣本進(jìn)行分類 – 通過(guò)將樣本的屬性值與決策樹相比較 決策樹分類任務(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 一個(gè)決策樹的例子 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)用決策樹進(jìn)行分類 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 測(cè)試數(shù)據(jù) Start from the root of tree. 應(yīng)用決策樹進(jìn)行分類 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 測(cè)試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 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 測(cè)試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 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 測(cè)試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 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 測(cè)試數(shù)據(jù) 應(yīng)用決策樹進(jìn)行分類 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 測(cè)試數(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é)點(diǎn) t相關(guān)聯(lián)的訓(xùn)練記錄集 ? 算法步驟 : – 如果 Dt 中所有記錄都屬于同一個(gè)類 yt, 則 t是葉結(jié)點(diǎn),用 yt標(biāo)記 – 如果 Dt 中包含屬于多個(gè)類的記錄,則 選擇一個(gè)屬性測(cè)試條件 ,將記錄劃分成較小的子集。 c )。 ?訓(xùn)練集中的單個(gè)元組稱為 訓(xùn)練樣本 ,每個(gè)訓(xùn)練樣本有一個(gè)類別標(biāo)記。數(shù)據(jù)挖掘 分類:基本概念、決策樹與模型評(píng)價(jià) 第 4章 分類:基本概念、決策樹與模型評(píng)價(jià) ? 分類的是利用一個(gè)分類函數(shù)(分類模型、分類器),該模型能把數(shù)據(jù)庫(kù)中的數(shù)據(jù)影射到給定類別中的一個(gè)。 分類 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