第5章：數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘的決策支持(1)-資料下載頁(yè)
2025-08-16 00:24本頁(yè)面
【正文】 別力的屬性進(jìn)行劃分 ,一直進(jìn)行到所有子集僅包含同一類型的數(shù)據(jù)為止 . ? 最后得到一棵決策樹 ,可用它來(lái)對(duì)新的實(shí)例進(jìn)行分類 . 訓(xùn)練集 PE、 NE 取子集建窗口 窗口 PE`、 NE` 生成 決策樹 測(cè)試 PE、 NE 擴(kuò)展窗口 PE`=PE`+PE``NE`=NE`+NE`` 此決策樹為最后結(jié)果 存在錯(cuò)判的 PE``， NE``嗎 是 否 ID3主算法流程 （一）主算法 從訓(xùn)練集中隨機(jī)選擇一個(gè)既含 正例 又含 反例 的子集（稱為 窗口 ）； 用 “ 建樹算法 ” 對(duì)當(dāng)前窗口形成一棵 決策樹 ； 對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹進(jìn)行類別判定，找出錯(cuò)判 的例子； 若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn) 2，否則結(jié)束。 ?主算法中每迭代循環(huán)一次，生成的決策樹將會(huì)不相同。 （二）建樹算法 對(duì)當(dāng)前例子集合，計(jì)算各特征的 互 信息； 選擇互信息最大的特征 Ak； 把在 Ak處取值相同的例子歸于同一子集， Ak取幾個(gè)值就得幾個(gè)子集； 對(duì)既含正例又含反例的子集，遞歸調(diào)用建樹算法； 若子集僅含正例或反例，對(duì)應(yīng)分枝標(biāo)上 P或 N，返回調(diào)用處。 二、 ID3算法 在一實(shí)體世界中，每個(gè)實(shí)體用多個(gè)特征來(lái)描述。每個(gè)特征限于在一個(gè)離散集中取 互斥 的值。例如，設(shè)實(shí)體是某天早晨，分類任務(wù)是關(guān)于氣候的類型，特征為 : 天氣 取值為： 晴，多云，雨 氣溫 取值為： 冷 ，適中，熱 濕度 取值為： 高 ，正常 風(fēng) 取值為： 有風(fēng)， 無(wú)風(fēng) 某天早晨氣候描述為 : 天氣 ： 多云 氣溫 ： 冷 濕度 ： 正常 風(fēng) ： 無(wú)風(fēng) ID3方法應(yīng)用實(shí)例 ? 它屬于哪類氣候呢 ? ? 每個(gè)實(shí)體屬于不同的類別，為簡(jiǎn)單起見(jiàn)，假定僅有兩個(gè)類別，分別為 P， N。在這種兩個(gè)類別的歸納任務(wù)中， P類和 N類的實(shí)體分別稱為概念的正例和反例 ? 將一些已知的正例和反例放在一起便得到訓(xùn)練集。 ? 下表給出一個(gè)訓(xùn)練集。由 ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)實(shí)體的決策樹，見(jiàn)圖。 ID3方法應(yīng)用實(shí)例 NO. 屬性 類別 天氣 氣溫 濕度 風(fēng) 1 晴 熱 高 無(wú)風(fēng) N 2 晴 熱 高 有風(fēng) N 3 多云 熱 高 無(wú)風(fēng) P 4 雨 適中 高 無(wú)風(fēng) P 5 雨 冷 正常 無(wú)風(fēng) P 6 雨 冷 正常 有風(fēng) N 7 多云 冷 正常 有風(fēng) P 8 晴 適中 高 無(wú)風(fēng) N 9 晴 冷 正常 無(wú)風(fēng) P 10 雨 適中 正常 無(wú)風(fēng) P 11 晴 適中 正常 有風(fēng) P 12 多云 適中 高 有風(fēng) P 13 多云 熱 正常 無(wú)風(fēng) P 14 雨 適中 高 有風(fēng) N 天 氣 濕 度 風(fēng) 晴 雨 多云 高 正常 有風(fēng) 無(wú)風(fēng) P N N P P ID3決策樹 ? 決策樹葉子為類別名，即 P 或者 N。其它結(jié)點(diǎn)由實(shí)體的特征組成，每個(gè)特征的不同取值對(duì)應(yīng)一分枝。 ? 若要對(duì)一實(shí)體分類，從樹根開(kāi)始進(jìn)行測(cè)試，按特征的取值分枝向下進(jìn)入下層結(jié)點(diǎn)，對(duì)該結(jié)點(diǎn)進(jìn)行測(cè)試，過(guò)程一直進(jìn)行到葉結(jié)點(diǎn)，實(shí)體被判為屬于該葉結(jié)點(diǎn)所標(biāo)記的類別。 ? 能正確分類訓(xùn)練集的決策樹不止一棵。 Quinlan的 ID3算法能得出結(jié)點(diǎn)最少的決策樹。 ( ) ( ) l o g ( )iiiH U P u P u? ?||()||iiuPuS? ID3方法應(yīng)用實(shí)例 對(duì)于氣候分類問(wèn)題進(jìn)行具體計(jì)算有： ⒈ 信息熵的計(jì)算 信息熵： 類別出現(xiàn)概率： |S|表示例子集 S的總數(shù)， |ui|表示類別 ui的例子數(shù)。 對(duì) 9個(gè)正例和 5個(gè)反例有： P（ u1） =9/14 P（ u2） =5/14 H（ U） =（ 9/14） log2（ 14/9） +（ 5/14） log2（ 14/5） = ID3方法應(yīng)用實(shí)例 ( / ) ( ) ( / ) l o g ( / )j i j i jjiH U V P v P u v P u v?? ??||( / )||iijjuP u vv? 條件熵： ⒉ 條件熵計(jì)算 屬性 A1取值 vj時(shí) ， 類別 ui的條件概率： A1=天氣 取值 v1=晴 ， v2=多云 ， v3=雨 在 A1處 取值晴 的例子 5個(gè) ， 取值多云 的例子 4個(gè) ， 取值雨 的例子 5個(gè) ， 故 P（ v1） =5/14 P（ v2） =4/14 P（ v3） =5/14 取值為晴 的 5個(gè)例子中有 2個(gè)正例 、 3個(gè)反例 ， 故： P（ u1/v1） =2/5， P（ u2/v1） =3/5 同理有： P（ u1/v2） =4/4， P（ u2/v2） =0 P（ u1/v3） =2/5， P（ u2/v3） =3/5 H(U/V)=(5/14)((2/5)log(5/2)+(3/5)log(5/3))+ (4/14)((4/4)log(4/4)+0)+ (5/14)((2/5)log(5/2)+(3/5)log(5/3)) = ⒊ 互信息計(jì)算 對(duì) A1=天氣 處有： I（天氣） =H（ U） H（ U|V） = = bit 類似可得： I（氣溫） = bit I（濕度） = bit I（風(fēng)） = bit ⒋ 建決策樹的樹根和分枝 ID3算法將選擇 互信息最大的特征天氣作為樹根 ，在 14個(gè)例子中對(duì)天氣的 3個(gè)取值進(jìn)行分枝， 3 個(gè)分枝對(duì)應(yīng) 3 個(gè)子集，分別是 : F1={1， 2， 8， 9， 11}， F2={3， 7， 12， 13}， F3={4， 5， 6， 10， 14} 其中 F2中的例子全屬于 P類，因此對(duì)應(yīng)分枝標(biāo)記為 P，其余兩個(gè)子集既含有正例又含有反例，將遞歸調(diào)用 建樹算法 。 ⒌ 遞歸建樹 分別對(duì) F1和 F3子集利用 ID3算法，在每個(gè)子集中對(duì)各特征（仍為四個(gè)特征）求互信息 . （ 1） F1中的天氣全取晴值，則H（ U） =H（ U|V），有 I（ U|V） =0，在余下三個(gè)特征中求出 濕度 互信息 最大，以它為該分枝的根結(jié)點(diǎn)，再向下分枝。濕度取高的例子全為 N類，該分枝標(biāo)記N。取值正常的例子全為 P類，該分枝標(biāo)記 P。 （ 2） 在 F3中，對(duì)四個(gè)特征求互信息，得到 風(fēng) 特征 互信息 最大，則以它為該分枝根結(jié)點(diǎn)。再向下分枝，風(fēng)取有風(fēng)時(shí)全為 N類，該分枝標(biāo)記 N。取無(wú)風(fēng)時(shí)全為 P類，該分枝標(biāo)記 P。 天 氣 濕 度 風(fēng) 晴 雨 多云 高 正常 有風(fēng) 無(wú)風(fēng) P N N P P ID3決策樹 ID3算法在數(shù)據(jù)挖掘中占有非常重要的地位。但是，在應(yīng)用中， ID3算法不能夠處理 連續(xù)屬性 、計(jì)算信息增益時(shí)偏向于選擇取值 較多的屬性 等不足。 ID3基礎(chǔ)上發(fā)展起來(lái)的決策樹生成算法，由 1993年提出。 ID3在應(yīng)用中存在的不足。 （ 1） 用 信息增益率 來(lái)選擇屬性，它克服了用信息增益選擇屬性時(shí)偏向選擇 取值多 的屬性的不足； （ 2） 在樹構(gòu)造過(guò)程中或者構(gòu)造完成之后，進(jìn)行 剪枝 ； （ 3） 能夠完成對(duì) 連續(xù)屬性 的離散化處理； （ 4） 能夠?qū)?不完整 數(shù)據(jù)的處理，例如未知的屬性值； （ 5） ，并最終可以形成產(chǎn)生式規(guī)則。 Quinlan在 ID3中使用信息論中的信息增益 （ gain） 來(lái)選擇屬性 ， 而 （ gain ratio）來(lái)選擇屬性 。 信息增益率 理論和實(shí)驗(yàn)表明，采用 “ 信息增益率 ” （ ）比采用 “ 信息增益 ” （ ID3方法）更好， 主要是克服了ID3方法選擇偏向取值多的屬性。 )(_/)()(/),(_ Vi n f os p l i tVg a i nVHVCIr a t i og a i n ?? 決策規(guī)則樹及應(yīng)用 IBLE方法： IBLE方法是利用信息論中 信道容量 來(lái)選擇屬性，比互信息更好。 IBLE方法建決策規(guī)則樹，每個(gè)結(jié)點(diǎn)由 多個(gè)屬性取值組成，提高了屬性組合的識(shí)別效果。 ?屬性的選取通過(guò)計(jì)算各屬性信道容量進(jìn)行 . ?各屬性的正例標(biāo)準(zhǔn)值由譯碼函數(shù)決定 . ?結(jié)點(diǎn)中判別正反例的閾值 (wn,wp)是由實(shí)例中權(quán)值變化的規(guī)律來(lái)確定的 . IBLE比 ID3識(shí)別率提高了 10個(gè)百分點(diǎn)。 數(shù)據(jù)挖掘的決策支持應(yīng)用領(lǐng)域 金融 （ 1） “ 數(shù)據(jù)清理 ” 、金融市場(chǎng)分析和預(yù)測(cè) （ 2）帳戶分類、銀行擔(dān)保和信用評(píng)估。 醫(yī)療保健 任務(wù)是進(jìn)行數(shù)據(jù)清理，預(yù)測(cè)醫(yī)療保健費(fèi)用。 市場(chǎng)業(yè) 進(jìn)行市場(chǎng)定位和消費(fèi)者分析，輔助制定市場(chǎng)策略。 數(shù)據(jù)挖掘的決策支持應(yīng)用領(lǐng)域 零售業(yè) 目前主要應(yīng)用于銷售預(yù)測(cè)、庫(kù)存需求、零售點(diǎn)選擇和價(jià)格分析。 制造業(yè) 進(jìn)行零部件故障診斷、資源優(yōu)化、生產(chǎn)過(guò)程分析等。 司法 應(yīng)用在案件調(diào)查、詐騙監(jiān)測(cè)、洗錢認(rèn)證、犯罪組織分析等工作。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1