【正文】 數(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 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 tL e a r n i n ga l g o r i t h mT r a i n i n g S e t?訓(xùn)練集：數(shù)據(jù)庫(kù)中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集 。 ?訓(xùn)練集中的單個(gè)元組稱為 訓(xùn)練樣本 ,每個(gè)訓(xùn)練樣本有一個(gè)類別標(biāo)記。 ?一個(gè)具體樣本的形式可為 :( v1, v2, ..., vn。 c )。其中 vi表示屬性值 ,c表示類別。 ?測(cè)試集：用于評(píng)估分類模型的準(zhǔn)確率 數(shù)據(jù)分類 ——一個(gè)兩步過程 (1) ? 第一步，建立一個(gè)模型，描述預(yù)定數(shù)據(jù)類集和概念集 – 假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)類標(biāo)號(hào)屬性確定 – 學(xué)習(xí)模型可以用分類規(guī)則、決策樹或數(shù)學(xué)公式的形式提供 數(shù)據(jù)分類 ——一個(gè)兩步過程 (2) ? 第二步，使用模型，對(duì)將來的或未知的對(duì)象進(jìn)行分類 – 首先評(píng)估模型的預(yù)測(cè)準(zhǔn)確率 ?對(duì)每個(gè)測(cè)試樣本，將已知的類標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類預(yù)測(cè)比較 ?模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本的百分比 ?測(cè)試集要獨(dú)立于訓(xùn)練樣本集，否則會(huì)出現(xiàn)“過分適應(yīng)數(shù)據(jù)”的情況 ? 如果準(zhǔn)確性能被接受，則分類規(guī)則就可用來對(duì)新數(shù)據(jù)進(jìn)行分類 有監(jiān)督的學(xué)習(xí) VS. 無監(jiān)督的學(xué)習(xí) ? 有監(jiān)督的學(xué)習(xí)（用于分類） – 模型的學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“監(jiān)督”下進(jìn)行 – 新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類 ? 無監(jiān)督的學(xué)習(xí)（用于聚類） – 每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的 – 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類 分類模型的構(gòu)造方法 ? ： ? 決策樹法 ? 規(guī)則歸納 ? ： 知識(shí)表示是判別函數(shù)和原型事例 ? 貝葉斯法 ? 非參數(shù)法 (近鄰學(xué)習(xí)或基于事例的學(xué)習(xí) ) ? ： ? BP算法 ,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型 ? (rough set)知識(shí)表示是產(chǎn)生式規(guī)則 一個(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ù) 模型 : 決策樹 決策樹的另一個(gè)例子 Ti d Re f un d M a r italS t a t usT a x a bleIne Chea t1 Y e s S i n g l e 1 2 5 K No2 No M a r r i e d 1 0 0 K No3 No S i n g l e 70K No4 Y e s M a r r i e d 1 2 0 K No5 No Di v o r c e d 95K Y e s6 No M a r r i e d 60K No7 Y e s Di v o r c e d 2 2 0 K No8 No S i n g l e 85K Y e s9 No M a r r i e d 75K No10 No S i n g l e 90K Y e s10MarSt Refund TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K 用決策樹歸納分類 ? 什么是決策樹？ – 類似于流程圖的樹結(jié)構(gòu) – 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 – 每個(gè)分枝代表一個(gè)測(cè)試輸出 – 每個(gè)樹葉節(jié)點(diǎn)代表類或類分布 ? 決策樹的生成由兩個(gè)階段組成 – 決策樹構(gòu)建 ?開始時(shí)，所有的訓(xùn)練樣本都在根節(jié)點(diǎn) ?遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） – 樹剪枝 ?許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn)，樹剪枝試圖檢測(cè)和剪去這種分枝 ? 決策樹的使用：對(duì)未知樣本進(jìn)行分類 – 通過將樣本的屬性值與決策樹相比較 決策樹分類任務(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 Si