【正文】 Marital Status Don’t Cheat Cheat Single, Divorced Married Taxable Ine Don’t Cheat 80K = 80K Refund Don’t Cheat Yes No Marital Status Don’t Cheat Cheat Single, Divorced Married 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 決策樹(shù) ? Hunt算法采用貪心策略構(gòu)建決策樹(shù) . – 在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù) . ? 決策樹(shù)歸納的設(shè)計(jì)問(wèn)題 – 如何分裂訓(xùn)練記錄 ?怎樣為不同類型的屬性指定測(cè)試條件 ? ?怎樣評(píng)估每種測(cè)試條件 ? – 如何停止分裂過(guò)程 決策樹(shù) ? Hunt算法采用貪心策略構(gòu)建決策樹(shù) . – 在選擇劃分?jǐn)?shù)據(jù)的屬性時(shí)，采取一系列局部最優(yōu)決策來(lái)構(gòu)造決策樹(shù) . ? 決策樹(shù)歸納的設(shè)計(jì)問(wèn)題 – 如何分裂訓(xùn)練記錄 ?怎樣為不同類型的屬性指定測(cè)試條件 ? ?怎樣評(píng)估每種測(cè)試條件 ? – 如何停止分裂過(guò)程 怎樣為不同類型的屬性指定測(cè)試條件 ? ? 依賴于屬性的類型 – 標(biāo)稱 – 序數(shù) – 連續(xù) ? 依賴于劃分的路數(shù) – 2路劃分 – 多路劃分 基于標(biāo)稱屬性的分裂 ? 多路劃分 : 劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù) . ? 二元?jiǎng)澐?: 劃分?jǐn)?shù)為 2，這種劃分要考慮創(chuàng)建 k個(gè)屬性值的二元?jiǎng)澐值乃?2k11種方法 . CarType Family Sports Luxury CarType {Family, Luxury} {Sports} CarType {Sports, Luxury} {Family} OR CarType {Family, Sports} {Luxury} ? 多路劃分 : 劃分?jǐn)?shù)（輸出數(shù)）取決于該屬性不同屬性值的個(gè)數(shù) . ? 二元?jiǎng)澐?: 劃分?jǐn)?shù)為 2，需要保持序數(shù)屬性值的有序性 . 基于序數(shù)屬性的劃分 Size Small Medium Large Size {Medium, Large} {Small} Size {Small, Medium} {Large} OR Size {Small, Large} {Medium} 基于連續(xù)屬性的劃分 ? 多路劃分 :vi≤A＜ vi+1（ i=1,…,k) ? 二元?jiǎng)澐?: (A v) or (A ? v) – 考慮所有的劃分點(diǎn)，選擇一個(gè)最佳劃分點(diǎn) v 基于連續(xù)屬性的劃分 T a x a b l eI n c o m e 8 0 K ?Y e s N oT a x a b l eI n c o m e ?( i ) B i n a r y s p l i t ( i i ) M u l t i w a y s p l i t 1 0 K[ 1 0 K , 2 5 K ) [ 2 5 K , 5 0 K ) [ 5 0 K , 8 0 K ) 8 0 K決策樹(shù) ? 決策樹(shù)歸納的設(shè)計(jì)問(wèn)題 – 如何分裂訓(xùn)練記錄 ?怎樣為不同類型的屬性指定測(cè)試條件 ? ?怎樣評(píng)估每種測(cè)試條件 ? – 如何停止分裂過(guò)程 怎樣選擇最佳劃分？ s e x ?C 0 : 6C 1 : 4C 0 : 4C 1 : 6C 0 : 1C 1 : 3C 0 : 8C 1 : 0C 0 : 1C 1 : 7C a r T y p e ?C 0 : 1C 1 : 0C 0 : 1C 1 : 0C 0 : 0C 1 : 1c u s t o m I D ?. . .Y e sN oF a m i l yS p o r t sL u x u r y c1c1 0c2 0C 0 : 0C 1 : 1. . .c1 1在劃分前 : 10 個(gè)記錄 class 0, 10 個(gè)記錄 class 1 怎樣選擇最佳劃分？ ? 選擇最佳劃分的度量通常是根據(jù)劃分后子結(jié)點(diǎn)不純性的程度。 ?測(cè)試集：用于評(píng)估分類模型的準(zhǔn)確率 數(shù)據(jù)分類 ——一個(gè)兩步過(guò)程 (1) ? 第一步，建立一個(gè)模型，描述預(yù)定數(shù)據(jù)類集和概念集 – 假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)類標(biāo)號(hào)屬性確定 – 學(xué)習(xí)模型可以用分類規(guī)則、決策樹(shù)或數(shù)學(xué)公式的形式提供 數(shù)據(jù)分類 ——一個(gè)兩步過(guò)程 (2) ? 第二步，使用模型，對(duì)將來(lái)的或未知的對(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)“過(guò)分適應(yīng)數(shù)據(jù)”的情況 ? 如果準(zhǔn)確性能被接受，則分類規(guī)則就可用來(lái)對(duì)新數(shù)據(jù)進(jìn)行分類 有監(jiān)督的學(xué)習(xí) VS. 無(wú)監(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)行分類 ? 無(wú)監(jiān)督的學(xué)習(xí)（用于聚類） – 每個(gè)訓(xùn)練樣本的類編號(hào)是未知的，要學(xué)習(xí)的類集合或數(shù)量也可能是事先未知的 – 通過(guò)一系列的度量、觀察來(lái)建立數(shù)據(jù)中的類編號(hào)或進(jìn)行聚類 分類模型的構(gòu)造方法 ? ： ? 決策樹(shù)法 ? 規(guī)則歸納 ? ： 知識(shí)表示是判別函數(shù)和原型事例 ? 貝葉斯法 ? 非參數(shù)法 (近鄰學(xué)習(xí)或基于事例的學(xué)習(xí) ) ? ： ? BP算法 ,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型 ? (rough set)知識(shí)表示是產(chǎn)生式規(guī)則 一個(gè)決策樹(shù)的例子 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ù) 模型 : 決策樹(shù) 決策樹(shù)的另一個(gè)例子 Ti d Refun d M ar italS t atu sT ax ableIne Chea t1 Y es S i n gl e 12 5 K No2 No M arr i ed 10 0 K No3 No S i n gl e 70K No4 Y es M arr i ed 12 0 K No5 No Di v orc ed 95K Y es6 No M arr i ed 60K No7 Y es Di v orc ed 22 0 K No8 No S i n gl e 85K Y es9 No M arr i ed 75K No10 No S i n gl e 90K Y es10MarSt Refund TaxInc YES NO NO NO Yes No Married Single, Divorced 80K 80K 用決策樹(shù)歸納分類 ? 什么是決策樹(shù)？ – 類似于流程圖的樹(shù)結(jié)構(gòu) – 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 – 每個(gè)分枝代表一個(gè)測(cè)試輸出 – 每個(gè)樹(shù)葉節(jié)點(diǎn)代表類或類分布 ? 決策樹(shù)的生成由兩個(gè)階段組成 – 決策樹(shù)構(gòu)建