【正文】 只要沿著樹(shù)根向下一直走到葉，沿途的分裂條件就能夠唯一確定一條分類的謂詞。 例子 ? 氣象數(shù)據(jù)集，都是標(biāo)稱屬性 什么因素影響是否去 打網(wǎng)球？ 溫度 的劃分 濕度 的劃分 有風(fēng) 的劃分 構(gòu)造樹(shù) ? 訓(xùn)練樣本的信息值 ? 第一棵樹(shù)，屬性，各葉節(jié)點(diǎn)的信息值 ? 第一棵樹(shù)，屬性，導(dǎo)致的信息增益 ? 依次，計(jì)算每棵樹(shù)導(dǎo)致的信息增益 ? 選擇獲得最大信息增益的屬性進(jìn)行劃分 ? 以此類推，遞歸，繼續(xù)劃分 ? 當(dāng)所有葉節(jié)點(diǎn)都是純的，劃分過(guò)程終止 ? （ 1）訓(xùn)練樣本的信息值 (基于類的比例） ? 訓(xùn)練樣本（用來(lái)創(chuàng)建樹(shù)的數(shù)據(jù)集）在包含 9個(gè) yes和 5個(gè) no的根節(jié)點(diǎn)上，對(duì)應(yīng)于信息值 info([9,5])= → 總的信息 ? （ 2） 第一棵樹(shù)，屬性，各葉節(jié)點(diǎn)的信息值 ? 基于天氣 (outlook)的劃分，在葉節(jié)點(diǎn)的yes和 no類的個(gè)數(shù)分別是 [2,3]， [4,0]，和[3,2]，而這些節(jié)點(diǎn)的信息值分別是： ? info([2,3])= → sunny ? info([4,0])=0. 0位 → overcast ? info([3,2])= → rain ? （ 3）第一棵樹(shù)，屬性，導(dǎo)致的信息增益 ? 計(jì)算平均信息值。 0:)( mjm wxxf ?0mw ? ?0 | mjm wxxL ?? 決策樹(shù)分類 1. 訓(xùn)練階段 從給定的訓(xùn)練數(shù)據(jù)集 DB，構(gòu)造出一棵決策樹(shù) class = DecisionTree( DB ) 2. 分類階段 從根開(kāi)始，按照決策樹(shù)的分類屬性逐層往下劃分，直到葉節(jié)點(diǎn)，獲得概念（決策、分類）結(jié)果。 有監(jiān)督的學(xué)習(xí)。該決策節(jié)點(diǎn)將輸入空間一份為二： 和 ，稱為一個(gè)二元?jiǎng)澐帧? ? 如果一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)的類值對(duì)于所有數(shù)據(jù)都相同，則熵最小。 ? 用系數(shù) F修正增益參數(shù) F=數(shù)據(jù)庫(kù)中一個(gè)給出的屬性值具有已知值的樣本數(shù)量 /數(shù)據(jù)集中樣本數(shù)量總和 未知屬性值問(wèn)題 新的增益標(biāo)準(zhǔn)： Gain(X) = F*(info(T) – infox(T)) 同時(shí)， 通過(guò)把具有未知值的樣本看作分區(qū)的一個(gè) 附加組 來(lái)修改Split_Info (X)。 缺點(diǎn)： (1) 缺乏伸縮性：由于進(jìn)行深度優(yōu)先搜索，所以算法受內(nèi)存大小限制，難于處理大訓(xùn)練集。 ? （ 6）以此類推，遞歸，繼續(xù)劃分 ? 遞歸繼續(xù)選擇 ? 當(dāng)天氣為晴時(shí)，所達(dá)到的節(jié)點(diǎn)上的可 能的深一層的分支 ? 除天氣外，其他屬性產(chǎn)生的信息增益 分別為： gain(temperature)= gain(humidity)= gain(windy)= ? 繼續(xù)再選擇濕度 (humidity)作為劃分屬性 天氣，晴分支 純子節(jié)點(diǎn) ? （ 6）以此類推，遞歸，繼續(xù)劃分 ? 天氣，晴分支，氣溫， gain(temperature)=位 ? 天氣，晴分支，濕度， gain(humidity)= (純的子女節(jié)點(diǎn)） ? 天氣，晴分支，有風(fēng)， gain(windy)= ? 天氣，雨分支，氣溫， gain(temperature)=位 ? 天氣，雨分支，濕度， gain(humidity)= ? 天氣，雨分支，有風(fēng)， gain(windy)= （純的子女節(jié)點(diǎn)） 天氣 雨分支 有風(fēng) 純的子節(jié)點(diǎn) （ 7） 當(dāng)所有葉節(jié)點(diǎn)都是純的，劃分過(guò)程終止 ? 理想情況下，當(dāng)所有葉節(jié)點(diǎn)都是純的而使過(guò)程終止時(shí)，即當(dāng)它們包含的實(shí)例都具有相同類時(shí)該過(guò)程終止。如果對(duì)于所有分支，劃分后選擇相同分支的所有實(shí)例都屬于相同的類，則這個(gè)劃分是純的。 決策樹(shù)歸納的基本算法是貪心算法，自頂向下遞歸方式構(gòu)造決策樹(shù)。如果使用的輸入維 是離散的，取 n個(gè)可能的值之一，則該節(jié)點(diǎn)檢測(cè) 的值，并取相應(yīng)的分支，實(shí)現(xiàn)一個(gè) n路劃分。 ? 構(gòu)造決策樹(shù)，熵定義為無(wú)序性度量 。 ?缺失數(shù)據(jù)的考慮：在構(gòu)建決策樹(shù)時(shí) ， 可以簡(jiǎn)單地忽略缺失數(shù)據(jù) ， 即在計(jì)算增益時(shí) ， 僅考慮具有屬性值的記錄 。用以前的方法是顯然不行的。 最終的決策樹(shù) ? Weather數(shù)據(jù) overcast high normal false true sunny rain No No Yes Yes Yes Outlook Humidity Windy ? ID3如何選擇具有最高信息增益的屬性 ： ? pi 是 D中任意元組屬于類 Ci 的概率，用 |Ci,D|/|D| 估計(jì) ? D中的元組分類所需的期望信息 Expected information (entropy)： ? Information needed (after using A to split D into v partitions) to classify D: ? Information gained by branching on attribute A )(log)( 21imii ppDIn