數(shù)據(jù)分類-決策樹(ppt71頁)(編輯修改稿)
2025-03-27 11:30 本頁面
【文章內(nèi)容簡介】 t y e s3 1 …4 0 h i g h y e s f a i r y e sage? =30 40 30..40 age i n co m e st u d e n t cr e d i t _ r a t i n g b u y s_ co m p u t e r 4 0 m e d i u m no f a i r y e s 4 0 lo w y e s f a i r y e s 4 0 m e d i u m y e s f a i r y e s 4 0 lo w y e s e x ce lle n t no 4 0 m e d i u m no e x ce lle n t no增益率 (Gain Ratio) ? (ID3的后繼算法 ) 應(yīng)用增益率克服信息增益的偏斜性 (信息增益的規(guī)范化 ) ? Ex. ? GainRatio(ine) = ? 具有最大增益率的屬性選為劃分屬性 21( ) l og ( )v jjAjnnSpli tIn fo Dnn?? ? ?? )14 4(log14 4)14 6(log14 6)14 4(log14 4)( 222 ????????DSp litIn fo A()()()G ain AG ainR ati o ASplit I nfo A?信息增益缺點 : 傾向于選擇分割數(shù)目多的屬性。 Gini指數(shù) ? Gini指數(shù) :節(jié)點屬性 A劃分樣本的不純度，設(shè)樣本集為 D (NOTE: p( j | D) 類 j 在樣本 D中的概率 ). ? 當所有樣本均勻分布在不同類時，最大為 (1 1/nc), 表示最小興趣信息 ? 當所有的樣本屬于一類時，最小 為 ()，表示最大興趣信息 2( ) 1 [ ( | ) ]iG ini D p i D?? ?C1 0C2 6Gini= 0. 000C1 2C2 4Gini= 0. 444C1 3C2 3Gini= 0. 500C1 1C2 5Gini= 0. 278Gini例子 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 2( ) 1 [ ( | ) ]jG I NI D p j D?? ?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 = C1 33Gini= 0. 500基于 Gini指數(shù)的劃分 ? 用于 CART算法 ? 在節(jié)點 A，將訓(xùn)練集 D劃分為 k個子集 (子節(jié)點 Di )，則以劃分的不純度加權(quán)和度量其優(yōu)劣 ni = 子樹 的訓(xùn)練樣本個數(shù) i, n = 節(jié)點 p處訓(xùn)練樣本個數(shù) . 1( ) ( )k iAiinG ini D G ini Dn?? ?二值屬性的 Gini指數(shù) ?劃分為兩個子集 ?帶權(quán)劃分的效果 : Gini指數(shù)越小越好 ? 尋求更大和更純的劃分 B? Yes No Node N1 Node N2 Pare nt B C1 6 C2 6 Gini = 0 .5 00 D 1 D 2 C1 5 1 C2 2 4 Gin i=0. 204 Gini(D1) = 1 – (5/7)2 – (2/7)2 = Gini(D2) = 1 – (1/5)2 – (4/5)2 = Gini(Children) = 7/12 * + 5/12 * = 決策樹歸納算法 ? 算法種類多 ? Hunt’s Algorithm (one of the earliest) ? CART ? ID3, ? SLIQ,SPRINT ID3算法原理 ?選擇具有較高信息增益的描述屬性作為給定數(shù)據(jù)集 X的分支屬性，從而創(chuàng)建決策樹中的一個節(jié)點 ?根據(jù)該描述屬性的不同取值再創(chuàng)建分支 ?之后對各個分支中的樣本子集遞歸調(diào)用上述方法建立下一級子節(jié)點 ?當某個分支上的所有數(shù)據(jù)樣本都屬于同一個類別時劃分停止，形成葉節(jié)點 ?或者當某個分支上的樣本不屬于同一個類別，但是又沒有剩余的描述屬性可以進一步劃分數(shù)據(jù)集時也形成葉節(jié)點，并且用多數(shù)樣本所屬的類別來標記這個葉節(jié)點 41 ID3算法示例 該樣本集中共 包含 4個描述 屬性和 1個類別 屬性，空間容量 為 14 目標是利用 ID3 思想構(gòu)建一棵 可用于新樣本 分類的決策樹 42 A1公司職員 A2年齡 A3收入 A4信譽度 C買保險 否 =40 高 良 c2 否 =40 高 優(yōu) c2 否 41~50 高 良 c1 否 50 中 良 c1 是 50 低 良 c1 是 50 低 優(yōu) c2 是 41~50 低 優(yōu) c1 否 =40 中 良 c2 是 =40 低 良 c1 是 50 中 良 c1 是 =40 中 優(yōu) c1 否 41~50 中 優(yōu) c1 是 41~50 高 良 c1 否 50 中 優(yōu) c2 第 1步：計算對訓(xùn)練集分類所需的期望信息 ?已知 ? total=14 ? c1(買保險 )的樣本數(shù)量是 n1=9 ? c2(不買保險 )的樣本數(shù)量是 n2=5 ?所以 ? P(c1)=9/14 ? P(c2)=5/14 ?根據(jù)期望信息公式可得 43 ))145(log145)149(log149())((log)(),(2221221?????? ??jjjcPcPnnI第 2步：計算 A1（公司職員）的熵 ? A1包含兩種取值：“是”和“否” ?利用 A1可將 X劃分為兩個子集 X1和 X2 ? X1中的數(shù)據(jù)樣本都是公司職員（ 7個） ? 標號為 c1的有 6個， n11=6 ? 標號為 c2的有 1個， n21=1 ? 則可得 ? p11=6/7 ? p21=1/7 44 A1公司職員 C買保險 否 c2 否 c2 否 c1 否 c1 是 c1 是 c2 是 c1 否 c2 是 c1 是 c1 是 c1 否 c1 是 c1 否 c2 ))71(log71)76(log76()(log),(22211212111?????? ??jjj ppnnI第 2步：計算 A1（公司職員）的熵 ?利用 A1可將 X劃分為兩個子集 X1和 X2 ? X2中的數(shù)據(jù)樣本都不是公司職員（ 7個） ? 標號為 c1的有 3個， n12=3 ? 標號為 c2的有 4個， n22=4 ? 則可得 ? p12=3/7 ? p22=4/7 45 A1公司職員 C買保險 否
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1