【正文】
?開始時,所有的訓練樣本都在根節(jié)點 ?遞歸的通過選定的屬性,來劃分樣本 (必須是離散值) – 樹剪枝 ?許多分枝反映的是訓練數(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 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 訓練數(shù)據(jù) 模型 : 決策樹 應用決策樹進行分類 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. 應用決策樹進行分類 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ù) 應用決策樹進行分類 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ù) 應用決策樹進行分類 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ù) 應用決策樹進行分類 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ù) 應用決策樹進行分類 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 算法 ? 設 Dt 是與結(jié)點 t相關聯(lián)的訓練記錄集 ? 算法步驟 : – 如果 Dt 中所有記錄都屬于同一個類 yt, 則 t是葉結(jié)點,用 yt標記 – 如果 Dt 中包含屬于多個類的記錄,則 選擇一個屬性測試條件 ,將記錄劃分成較小的子集。 c )。 ?訓練集中的單個元組稱為 訓練樣本 ,每個訓練樣本有一個類別標記。數(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