決策樹(shù)信息論c45算法(存儲(chǔ)版)
【正文】 ? I(X,Y)信息增益才是接收端獲得的信息量 我沒(méi)收到任何東西前，我不知道你發(fā)了是什么 我收到了一些東西后，才有機(jī)會(huì)猜你到底發(fā)了什么 H ( X ) ( X )( X ) H ( X ) 0I ( X , ) = ( X ) H ( X )YHHYY H Y??定 義 為 信 息 增 益 信息論基礎(chǔ) I ( X , ) = ( X ) H ( X )Y H Y互信息量 I(X,Y)的物理含義 ? H(X) 事件 X的結(jié)果的不確定性 ? H(X|Y) 事件 X在輔助條件 Y下的結(jié)果的不確定性 ? H(X) H(X|Y) 輔助條件 Y對(duì)事件 X的結(jié)果的不確定性的消除 —— 信息增益 ID3和 ID3算法 互信息量 I(X,Y)的物理含義 ? 輔助條件 Y消除了事件 X多少的不確定性 ID3算法 ? Iterative Dichotomiser 迭代二分器（為什么？） ? 使用互信息量作為度量標(biāo)準(zhǔn) ? 選擇當(dāng)前所有分割屬性中，互信息量最大的 作為內(nèi)部節(jié)點(diǎn) ID3算法 ID3算法 ? 使用互信息量作為度量標(biāo)準(zhǔn) ? 選擇當(dāng)前所有分割屬性中，互信息量最大的 ? 作為內(nèi)部節(jié)點(diǎn) —— 最能消除不確定性的分割屬性 生活工作中的決策 （做？不做？） ?總是優(yōu)先選取最具有決定性意義的 輔助條件進(jìn)行判定 如 — 打不打室外羽毛球？ ?刮風(fēng)是最具有決定意義的因素 ID3算法 ID3算法 互信息量最大 No. 頭痛 肌肉痛 體溫 患流感 1 是 (1) 是 (1) 正常 (0) N(0) 2 是 (1) 是 (1) 高 (1) Y(1) 3 是 (1) 是 (1) 很高 (2) Y(1) 4 否 (0) 是 (1) 正常 (0) N(0) 5 否 (0) 否 (0) 高 (1) N(0) 6 否 (0) 是 (1) 很高 (2) Y(1) 7 是 (1) 否 (0) 高 (1) Y(1) 決策樹(shù)怎么做？誰(shuí)是父節(jié)點(diǎn)？ 誰(shuí)是下一層子節(jié)點(diǎn)？為什么是它？ ?頭 肌肉 體溫 ?頭 體溫 肌肉 ?肌肉 頭 體溫 ?肌肉 體溫 頭 ?體溫 頭 肌肉 ?體溫 肌肉 頭 33 3! 6P ?? ? 例題中各數(shù)據(jù)的屬性及其取值分別為： – 類別（事件 X）： 是、否； —— x1， x2 – 分割屬性 Y1 頭痛 ：是、否； – 分割屬性 Y2 肌肉痛 ：是、否； – 分割屬性 Y3 體溫 ：很高、高、正常 ? 選擇全部數(shù)據(jù)記錄，求先驗(yàn)熵（對(duì) 類別 ）： – P(x1)=4/7， P(x2)=3/7 – H(X)= ∑i=1,2P(xi) log2 P(xi)= bit ? 后驗(yàn)熵（對(duì) Y1）： y1 =是， y2=否 – P(y1)=4/7， P(y2)=3/7 – P(x1 | y1)=3/4 ， P(x2 | y1)=1/4 – H(X |y1 )= ∑i=1,2P(xi | y1) log2P(xi | y1) = – 同理， H(X|y2 )= ID3算法 ? 條件熵（對(duì) Y1）： – H(X | Y1) = ∑j=1,2,3 P(yj) H(X | yj)= ? 互信息（對(duì) Y1）： – I (X,Y1)= H(X) H(X | Y1) = ? 同理，有： – I (X,Y2)=， I (X,Y3)= ? I (X,Y3)值最大，所以選擇“體溫”作為決策樹(shù)的根節(jié)點(diǎn)，將其三個(gè)取值分別作為三個(gè)分支，并劃分原數(shù)據(jù)集合為三個(gè)子集 ? 判斷子集中各記錄是否屬于同一類別，若是則在樹(shù)上作標(biāo)記，否則對(duì)子集重復(fù)上述步驟 ID3算法 ID3算法（選擇掌握） 興趣題 ~~ 使用 ID3算法構(gòu)建“天氣 外出”決策樹(shù) No. 天氣 氣溫 濕度 風(fēng) 類別 1 晴 熱 高 無(wú) N 2 晴 熱 高 有 N 3 多云 熱 高 無(wú) P 4 雨 適中 高 無(wú) P 5 雨 冷 正常 無(wú) P 6 雨 冷 正常 有 N 7 多云 冷 正常 有 P No. 天氣 氣溫 濕度 風(fēng) 類別 8 晴 適中 高 無(wú) N 9 晴 冷 正常 無(wú) P 10 雨 適中 正常 無(wú) P 11 晴 適中 正常 有 P 12 多云 適中 高 有 P 13 多云 熱 正常 無(wú) P 14 雨 適中 高 有 N ? 例題中各數(shù)據(jù)的屬性及其取值分別為： – 類別： P、 N； —— u u2 – 天氣 A1：晴、多云、雨； 氣溫 A2：冷、適中、熱； – 濕度 A3 ：高、正常； 風(fēng) A4 ：有、無(wú) ? 選擇全部數(shù)據(jù)記錄，求先驗(yàn)熵（對(duì) 類別 ）： – P(u1)=9/14， P(u2)=5/14 – H(U)= ∑i=1,2P(ui) log2 P(ui)= bit ? 后驗(yàn)熵（對(duì) A1）： v1 =晴， v2=多云， v3=雨 – P(v1)=5/14， P(v2)=4/14， P(v3)=5/14 – P(u1 | v1)=2/5 ， P(u2 | v1)=3/5 – H(U |v1 )= ∑i=1,2P(ui | v1) log2P(ui | v1) = – 同理， H(U|v2 )=0， H(U|v3 )= ID3算法（選擇掌握） ? 條件熵（對(duì) A1）： – H(U | V) = ∑j=1,2,3 P(vj) H(U | vj)= ? 互信息（對(duì) A1）： – I (A1)= H(U) H(U | V) = ? 同理，有： – I (A2)=， I (A3)=， I (A4)= ? I (A1)值最大，所以選擇“天氣”作為決策樹(shù)的根節(jié)點(diǎn)，將其三個(gè)取值分別作為三個(gè)分支，并劃分原數(shù)據(jù)集合為三個(gè)子集 ? 判斷子集中各記錄是否屬于同一類別，若是則在樹(shù)上作標(biāo)記
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1