【正文】 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ù)庫中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集 。 ?一個具體樣本的形式可為 :( v1, v2, ..., vn。其中 vi表示屬性值 ,c表示類別。對于測試條件的每個輸出，創(chuàng)建一個子結(jié)點，并根據(jù)測試結(jié)果將 Dt中的記錄分布到子結(jié)點中。不純性的程度越低，類分布就越傾斜 ? 結(jié)點不純性的度量 : C0: 5C1: 5C0: 9C1: 1不純性大 不純性小 怎樣找到最佳劃分？ B? Yes No Node N3 Node N4 A? Yes No Node N1 Node N2 劃分前 : C0 N10 C1 N11 C0 N2 0 C1 N2 1 C0 N3 0 C1 N3 1 C0 N4 0 C1 N4 1 C0 N 0 0 C1 N0 1 M0 M1 M2 M3 M4 M12 M34 Gain = M0 – M12 vs M0 – M34 結(jié)點不純性的測量 ? Gini ? Entropy ? classification error 不純性的測量 : GINI ? 給定結(jié)點 t的 Gini值計算 : (p( j | t) 是在結(jié)點 t中，類 j發(fā)生的概率 ). – 當(dāng)類分布均衡時， Gini值達到最大值 (1 1/nc) – 相反當(dāng)只有一個類時， Gini值達到最小值 0 ???jtjptGINI 2)]|([1)(C1 0C2 6Gin i=0 .0 00C1 2C2 4Gin i=0 .4 44C1 3C2 3Gin i=0 .5 00C1 1C2 5Gin i=0 .2 78計算 GINI的例子 C1 0 C2 6 C1 2 C2 4 C1 1 C2 5 P(C1) = 0/6 = 0 P(C2) = 6/6 = 1 Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 = 0 ???jtjptGINI 2)]|([1)(P(C1) = 1/6 P(C2) = 5/6 Gini = 1 – (1/6)2 – (5/6)2 = P(C1) = 2/6 P(C2) = 4/6 Gini = 1 – (2/6)2 – (4/6)2 = 基于 GINI的劃分 ? 當(dāng)一個結(jié)點 p 分割成 k 個部分 (孩子 ), 劃分的質(zhì)量可由下面公式計算 ni = 孩子結(jié)點 i的記錄數(shù) , n = 父結(jié)點 p的記錄數(shù) . ???kiis p lit iGIN InnGIN I1)(二元屬性 : 計算 GINI ? 對于二元屬性，結(jié)點被劃分成兩個部分 ? 得到的 GINI值越小，這種劃分越可行 . B? Yes No Node N1 Node N2 Paren t C1 6 C2 6 Gin i = 0. 500 N1 N2 C1 5 1 C2 2 4 Gin i=0. 3 33 Gini(N1) = 1 – (5/6)2 – (2/6)2 = Gini(N2) = 1 – (1/6)2 – (4/6)2 = Gini split = 7/12 * + 5/12 * = 標稱屬性 :計算 Gini ? 多路劃分 ? 二元劃分 ? 一般多路劃分的 Gini值比二元劃分小，這一結(jié)果并不奇怪，因為二元劃分實際上合并了多路劃分的某些輸出，自然降低了子集的純度 CarT yp e{Spo rts,Lux ury }{Fa mi ly }C1 3 1C2 2 4Gin i 0. 400CarT yp e{Spo rts}{ Fa mi ly ,Lux ury }C1 2 2C2 1 5Gin i 0. 419CarTy peFa mi ly Sports Lux uryC1 1 2 1C2 4 1 1Gini 0. 393Multiway split Twoway split (find best partition of values) 連續(xù)屬性 : 計算 Gini ? 使用二元劃分 ? 劃分點 v選擇 – N個記錄中所有屬性值作為劃分點 ? 對每個劃分進行類計數(shù) , A v and A ? v ? 計算每個候選點 v的 Gini指標，并從中選擇具有最小值的候選劃分點 ? 時間復(fù)雜度為 (n2) 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 TaxableIne 80K?Yes No連續(xù)屬性 : 計算 Gini... ? 降低計算復(fù)雜性的方法 , – 將記錄進行排序 – 從兩個相鄰的排過序的屬性值之間選擇中間值作為劃分點 – 計算每個候選點的 Gini值 – 時間復(fù)雜度為 nlogn Cheat No No No Yes Yes Yes No No No No Taxabl e Inc om e 60 70 75 85 90 95 100 120 125 220 55 65 72 80 87 92 97 110 122 172 230 = = = = = = = = = = = Yes 0 3 0 3 0 3 0 3 1 2 2 1 3 0 3 0 3 0 3 0 3 0 No 0 7 1 6 2 5 3 4 3 4 3 4 3 4 4 3 5 2 6 1 7 0 G ini 劃分點 排序后的值 ? 定義：給定一個概率空間 事件 { , , ( )}X q x?kx ?的自信息定義為 因 I ( ) l ogkkxq??[ 0 , 1 ]kq ? 故I( ) 0kx ?自信息反映了事件 發(fā)生所需要的信息量。反過來， 值越小，需要較少信息量就能確定 的發(fā)生，即事件 隨機性較小。 是對不確定性大小的一種刻畫 kxI( )kx kxk I( )kxkxI( )kx熵 定義 熵 定義 ? ：在概率空間