【正文】 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 決策樹 ? Hunt算法采用貪心策略構建決策樹 . – 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構造決策樹 . ? 決策樹歸納的設計問題 – 如何分裂訓練記錄 ?怎樣為不同類型的屬性指定測試條件 ? ?怎樣評估每種測試條件 ? – 如何停止分裂過程 決策樹 ? Hunt算法采用貪心策略構建決策樹 . – 在選擇劃分數(shù)據(jù)的屬性時，采取一系列局部最優(yōu)決策來構造決策樹 . ? 決策樹歸納的設計問題 – 如何分裂訓練記錄 ?怎樣為不同類型的屬性指定測試條件 ? ?怎樣評估每種測試條件 ? – 如何停止分裂過程 怎樣為不同類型的屬性指定測試條件 ? ? 依賴于屬性的類型 – 標稱 – 序數(shù) – 連續(xù) ? 依賴于劃分的路數(shù) – 2路劃分 – 多路劃分 基于標稱屬性的分裂 ? 多路劃分 : 劃分數(shù)（輸出數(shù)）取決于該屬性不同屬性值的個數(shù) . ? 二元劃分 : 劃分數(shù)為 2，這種劃分要考慮創(chuàng)建 k個屬性值的二元劃分的所有 2k11種方法 . CarType Family Sports Luxury CarType {Family, Luxury} {Sports} CarType {Sports, Luxury} {Family} OR CarType {Family, Sports} {Luxury} ? 多路劃分 : 劃分數(shù)（輸出數(shù)）取決于該屬性不同屬性值的個數(shù) . ? 二元劃分 : 劃分數(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) ? 二元劃分 : (A v) or (A ? v) – 考慮所有的劃分點，選擇一個最佳劃分點 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決策樹 ? 決策樹歸納的設計問題 – 如何分裂訓練記錄 ?怎樣為不同類型的屬性指定測試條件 ? ?怎樣評估每種測試條件 ? – 如何停止分裂過程 怎樣選擇最佳劃分？ 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 個記錄 class 0, 10 個記錄 class 1 怎樣選擇最佳劃分？ ? 選擇最佳劃分的度量通常是根據(jù)劃分后子結點不純性的程度。 ?測試集：用于評估分類模型的準確率 數(shù)據(jù)分類 ——一個兩步過程 (1) ? 第一步，建立一個模型，描述預定數(shù)據(jù)類集和概念集 – 假定每個元組屬于一個預定義的類，由一個類標號屬性確定 – 學習模型可以用分類規(guī)則、決策樹或數(shù)學公式的形式提供 數(shù)據(jù)分類 ——一個兩步過程 (2) ? 第二步，使用模型，對將來的或未知的對象進行分類 – 首先評估模型的預測準確率 ?對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較 ?模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比 ?測試集要獨立于訓練樣本集，否則會出現(xiàn)“過分適應數(shù)據(jù)”的情況 ? 如果準確性能被接受，則分類規(guī)則就可用來對新數(shù)據(jù)進行分類 有監(jiān)督的學習 VS. 無監(jiān)督的學習 ? 有監(jiān)督的學習（用于分類） – 模型的學習在被告知每個訓練樣本屬于哪個類的“監(jiān)督”下進行 – 新數(shù)據(jù)使用訓練數(shù)據(jù)集中得到的規(guī)則進行分類 ? 無監(jiān)督的學習（用于聚類） – 每個訓練樣本的類編號是未知的，要學習的類集合或數(shù)量也可能是事先未知的 – 通過一系列的度量、觀察來建立數(shù)據(jù)中的類編號或進行聚類 分類模型的構造方法 ? ： ? 決策樹法 ? 規(guī)則歸納 ? ： 知識表示是判別函數(shù)和原型事例 ? 貝葉斯法 ? 非參數(shù)法 (近鄰學習或基于事例的學習 ) ? ： ? BP算法 ,模型表示是前向反饋神經網絡模型 ? (rough set)知識表示是產生式規(guī)則 一個決策樹的例子 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ù) 模型 : 決策樹 決策樹的另一個例子 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 用決策樹歸納分類 ? 什么是決策樹？ – 類似于流程圖的樹結構 – 每個內部節(jié)點表示在一個屬性上的測試 – 每個分枝代表一個測試輸出 – 每個樹葉節(jié)點代表類或類分布 ? 決策樹的生成由兩個階段組成 – 決策樹構建