決策樹信息論c45算法-wenkub.com
2025-01-12 19:41 本頁面
【正文】 解決方法：引入“閾值”。所以 ID3產(chǎn)生了偏向性。 極限情況下，每個子集內(nèi)如只有一個單元（表格中的行），則它的信息增益必然最高（對不確定性的消除達(dá)到最大）。 Dichotomiser（二分器） ? ID3算出的決策樹的“類別”只有“是”、“否” ? 如“流感”決策樹 W=F(X,Y,Z) X Y Z W ID3算法 :主算法 1) 從訓(xùn)練集中隨機(jī)選擇一個既含正例 (Y)又含反例 (N)的子集（稱為“窗口”）； 2) 用“建樹算法”對當(dāng)前窗口形成一棵決策樹； 3) 對訓(xùn)練集（窗口除外）中例子用所得決策樹進(jìn)行類別判定，找出錯判的例子； 4) 若存在錯判的例子，把它們插入窗口，重復(fù)步驟（ 2），否則結(jié)束。 ID3算法 知識結(jié)構(gòu) 決策樹基礎(chǔ) 信息論基礎(chǔ) 決策樹基礎(chǔ) ? 女孩家長 安排相親 ? 女孩 不厭其煩 ? 女孩 提出決策樹 ? 父母篩選 候選男士 決策樹基礎(chǔ) 有向無環(huán) 二叉 /多叉樹 ?父節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn) ?內(nèi)部節(jié)點(diǎn)：有父節(jié)點(diǎn)、子節(jié)點(diǎn)的節(jié)點(diǎn) ?葉節(jié)點(diǎn)：有父節(jié)點(diǎn)沒有子節(jié)點(diǎn)的節(jié)點(diǎn) 父節(jié)點(diǎn) 內(nèi)部節(jié)點(diǎn) 葉節(jié)點(diǎn) 分割屬性 +判斷規(guī)則 類別標(biāo)識 決策樹基礎(chǔ) 父節(jié)點(diǎn) 內(nèi)部節(jié)點(diǎn) 葉節(jié)點(diǎn) （類別標(biāo)識） （分割屬性 +判斷規(guī)則） 決策樹基礎(chǔ) 訓(xùn)練集： 數(shù)據(jù)的集合，用于生成樹（模型） 測試集： 用于測試樹（模型）的性能 決策樹作用： ?通過訓(xùn)練集 ?算法指導(dǎo)下 ?生成決策樹 ?新數(shù)據(jù)進(jìn)行劃分 ?否則是 “三拍” 決策 訓(xùn)練集 算法 決策樹 新數(shù)據(jù) 決策 決策樹基礎(chǔ) 實(shí)例 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) N(1) 7 是 (1) 否 (0) 高 (1) Y(1) 決策樹怎么做？誰是父節(jié)點(diǎn)？ 誰是下一層子節(jié)點(diǎn)？為什么是它？ ?頭 肌肉 體溫 ?頭 體溫 肌肉 ?肌肉 頭 體溫 ?肌肉 體溫 頭 ?體溫 頭 肌肉 ?體溫 肌肉 頭 33 3! 6P ??三 拍 決 策 決策樹基礎(chǔ) …… ）￥ —— JK)I*^Fkl9*^%*UIDOFGJ No. 天氣 氣溫 濕度 風(fēng) 類別 1 晴 熱 高 無 N 2 晴 熱 高 有 N 3 多云 熱 高 無 P 4 雨 適中 高 無 P 5 雨 冷 正常 無 P 6 雨 冷 正常 有 N 7 多云 冷 正常 有 P No. 天氣 氣溫 濕度 風(fēng) 類別 8 晴 適中 高 無 N 9 晴 冷 正常 無 P 10 雨 適中 正常 無 P 11 晴 適中 正常 有 P 12 多云 適中 高 有 P 13 多云 熱 正常 無 P 14 雨 適中 高 有 N 怎么生成好的？ 哪個好？ 種決策樹方案 決策樹基礎(chǔ) N個分割屬性的訓(xùn)練集 ( ! )nnPn? 決策樹基礎(chǔ) 好的決策樹 ： （ MDL準(zhǔn)則下為例） Minimum Description Length ?訓(xùn)練集中大多數(shù)數(shù)據(jù)符合這棵樹 ?例外的數(shù)據(jù)單獨(dú)編碼 描述決策樹用的 bit 描述例外數(shù)據(jù)用 bit M in哪個好？ 決策樹基礎(chǔ)（選擇掌握） ? 如何描述決策樹 體溫 頭痛 很高 正常 高 Y N Y N 否 是 流感決策樹 ?深度優(yōu)先遍歷決策樹 ?用 1標(biāo)注父子節(jié)點(diǎn) ?用 0標(biāo)注葉節(jié)點(diǎn) ?記錄分割屬性 ?1,體溫 ,0,Y,1,頭疼 ,0,Y,0,N,0,N 層次少 +分枝少 ?占用存儲空間小 ?決策計(jì)算時間快 決策樹基礎(chǔ) ID3算法 決策樹基礎(chǔ) 信息論基礎(chǔ) 選哪個？？ 怎么生成好的？ Next One! 信息論基礎(chǔ) 2I ( x ) = l og P ( x )ii辨析 ? 先驗(yàn)概率 ? 信息量 P(x )i 信息論基礎(chǔ) — 先驗(yàn)概率 P ( x )Xxii 先 驗(yàn) 概 率事 件 發(fā) 生 前 ， 猜 測 結(jié) 果 為 的 可 能 性? 對事件 X的某一結(jié)果進(jìn)行討論： 例：在沒有任何幫助的情況下，奧 /羅誰贏的概率 P（ x1=奧） = P（ x2=羅） 信息論基礎(chǔ) — 信息量 I ( ) I ( ) I ( )習(xí) 近 平 奧 巴 馬 薄 熙 來主 席 總 統(tǒng) 主 席2X x P ( x )X I ( x )I ( x ) = l og P ( x )iiiiii事 件 的 可 能 結(jié) 果 出 現(xiàn) 的 概 率則 可 能 結(jié) 果 的 信 息 量 為 信息論基礎(chǔ) 2I ( x ) = l og P ( x )ii2=1H ( X ) = P ( x ) l og P ( x )Niii?P(x )i辨析 ? 先驗(yàn)概率 ? 信息量 ? 先驗(yàn)熵 信息論基礎(chǔ) ? 先驗(yàn)熵 —— 自信息量 —— 熵 H（ X） 原意：熱力學(xué)中形容失序現(xiàn)象和復(fù)雜程度 現(xiàn)意：一個事件 X的平均信息量 ? 熵越大，不確定性就越大，正確估計(jì)其值的可
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1