決策樹培訓(xùn)講義(ppt50頁)(已修改)
2025-01-21 19:35 本頁面
【正文】 決策樹 上 武承羲 內(nèi)容 決策樹基礎(chǔ) 經(jīng)典決策樹 剪枝 決策樹 決策 樹： 用來表示 決策 和相應(yīng)的 決策結(jié)果 對應(yīng)關(guān)系的樹。 樹中每一 個非葉節(jié) 點表示一個決策，該決策的值導(dǎo)致不同的決策結(jié) 果 (葉節(jié)點 )或 者影響后面的決策選擇。 示例： 天氣 風(fēng) 陽光 不玩 玩 不玩 玩 玩 雨 晴 陰 強 弱 強 弱 決策樹 決策樹類型 分類樹：葉節(jié)點對應(yīng)于一 類別 回歸樹：葉節(jié)點對應(yīng)于 一連續(xù)值 ID3, and ( Ross Quinlan ) CART ( ， ， ) 思想：空間劃分！ 比如，用 變量 y表示因變量（分類變量），用 x1, x2, x3,...,xm表示自變量。通過遞歸的方式把關(guān) 于自變量的 m維空間劃分為不重疊的矩形 。 圖 示： 決策樹 ID3== ID3/信息 熵 1948年，香農(nóng)提出了“信息熵”的概念，解決了對系統(tǒng)信息的量化度量問題。 香 農(nóng)認(rèn)為信息的準(zhǔn)確信息量可以用下面 的信息熵公 式計算： 一個 系 統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越亂，信息熵就越高。所以，信息熵也可以說是系統(tǒng)有序化程度的一個衡量。 21( ) l og ( )C=CiiiiiEn tr opy S p pi??? ?其 中 ， S 表 示 樣 本 集 ，C 表 示 樣 本 集 合 中 類 別 個 數(shù) ( 只 含 有 正 負(fù) 樣 本 ， 則 2) ，p 表 示 第 個 類 的 概 率 ，（ p 可 由 類 別 i 中 含 有 樣 本 的 個 數(shù) 除 以 總 樣 本 數(shù) 得 到 ）? 信息增益（ information gain） 是指期望信息或者信息熵的有效減少量。 2122112211( , ) ( ) ( )l og ( ) ( ) ( )l og ( ) ( ) { l og ( ) }l og ( ) ( ) l og ( )FCi i vi v V ofFCCi i v j v ji v V ofF jCCi i v j v ji v V ofF jG ain S F En tr opy S Ex pe c te dE ntr opy Sp p p v En tr opy Sp p p v p pppSv p pFpV??? ? ?? ? ???? ? ?? ? ? ??? ? ???? ? ?? ? ?說 明 ： 設(shè) 樣 本 集 按 離 散 屬 性 的 個 不 同 的 取 值 劃 分1 , ...Vv j vS S Vp S j為 ， 共 個 子 集其 中 ， 表 示 中 第 類 的 概 率? 信息增 益率（ information gain ratio） 由劃分個數(shù)引起的偏置問題（劃分越多 =引起每個劃分內(nèi)部數(shù)據(jù)純度的變化，分塊越小，數(shù)據(jù)純度可能越高 =進(jìn)而引起偏置問題）： 設(shè)樣本集 S按離散屬性 F的 V個不同的取值劃分為， 共 V個子集 定義 Split(S, F)： 則用 F對 S進(jìn)行劃分的信息增益率為： 2| | | |( , ) * l og ( )| | | |vvvVSSSplit S F??? ?1,.., VSS ( , )( , )( , )G ain S FG ainR ati o S FSplit S F?21 12( , ) l og ( lo) ) )( g(CvCiiv V ofFvjjijpG ai pv pn S F p p? ??? ? ??? ?ID3 1986年由 Quilan提出的 ID3算法 選 擇具有最 高信息增 益的屬性作為測試屬性 。 ID3(DataSet, featureList)： 創(chuàng)建根節(jié)點 R 如果當(dāng)前 DataSet中的數(shù)據(jù)都屬于同一類，則標(biāo) 記 R的類別為該 類 如 果當(dāng) 前 featureList 集 合為空，則標(biāo)記 R的類別為當(dāng)前 DataSet中樣本最多的類別 遞 歸情況： 從 featureList中選擇屬性 F（選擇 Gain(DataSet, F)最大的屬性） 根 據(jù) F的每一個值 v，將 DataSet劃分為不同的子集 DS，對于每一個 DS： 創(chuàng)建節(jié)點 C 如果 DS為空，節(jié)點 C標(biāo)記為 DataSet中樣本最多的類別 如果 DS不為空，節(jié)點 C=ID3(DS, featureList F) 將節(jié)點 C添加為 R的子節(jié)點 ? C源碼： Day Outlook Temperature Humidity Wind Play ball D1 Sunny Hot High Weak No D2 Sunny Hot High Strong No D3 Overcast Hot High Weak Yes D4 Rain Mild High Weak Yes D5 Rain Cool Normal Weak Yes D6 Rain Cool Normal Strong No D7 Overcast Cool Normal Strong Yes D8 Sunny Mild High Weak No D9 Sunny Cool Normal Weak Yes D10 Rain
化學(xué)相關(guān)推薦
鄂ICP備17016276號-1