【正文】 確定性的大小來(lái)計(jì)量。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ID3算法 ? 當(dāng)前國(guó)際上最有影響的示例學(xué)習(xí)方法首推 ID3。 ? ID3引進(jìn)了信息論中的 互信息 ，他將其稱為 信息增益（ information gain） ， 作為特征判別能力的度量，并且將建樹(shù)的方法嵌在一個(gè)迭代的中。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 一、 ID3基本思想 某天早晨氣候描述為 : 天氣 ： 多云 氣溫 ： 冷 濕度 ： 正常 風(fēng) ： 無(wú)風(fēng) 在一實(shí)體世界中，每個(gè)實(shí)體用多個(gè)特征來(lái)描述。每個(gè)特征限于在一個(gè)離散集中取互斥的值。例如，設(shè)實(shí)體是某天早晨，分類任務(wù)是關(guān)于氣候的類型，特征為 : 天氣 取值為： 晴，多云，雨 氣溫 取值為： 冷 ，適中，熱 濕度 取值為： 高 ，正常 風(fēng) 取值為： 有風(fēng)， 無(wú)風(fēng) 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ? 它屬于哪類氣候呢 ? ? 每個(gè)實(shí)體屬于不同的類別，為簡(jiǎn)單起見(jiàn)，假定僅有兩個(gè)類別，分別為 P， N。 在這種兩個(gè)類別的歸納任務(wù)中， P類和 N類的實(shí)體分別稱為概念的正例和反例。 ? 將一些已知的正例和反例放在一起便得到訓(xùn)練集。 ? 下表給出一個(gè)訓(xùn)練集。由 ID3算法得出一棵正確分類訓(xùn)練集中每個(gè)實(shí)體的決策樹(shù)，見(jiàn)圖。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 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 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 天 氣 濕 度 風(fēng) 晴 雨 多云 高 正常 有風(fēng) 無(wú)風(fēng) P N N P P ID3決策樹(shù) 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ? 決策樹(shù)葉子為類別名，即 P 或者 N。 其它結(jié)點(diǎn)由實(shí)體的特征組成，每個(gè)特征的不同取值對(duì)應(yīng)一分枝。 ? 若要對(duì)一實(shí)體分類，從樹(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)記的類別。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ? 用圖來(lái)判本節(jié)開(kāi)始處的具體例子，得該實(shí)體的類別為P類。 ? ID3方法就是要從表的訓(xùn)練集構(gòu)造圖這樣的決策樹(shù)。 ? 實(shí)際上，能正確分類訓(xùn)練集的決策樹(shù)不止一棵。 ? Quinlan的 ID3算法能得出結(jié)點(diǎn)最少的決策樹(shù)。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 二、 ID3算法 （一）主算法 從訓(xùn)練集中隨機(jī)選擇一個(gè)既含正例又含反例的子集（稱為 窗口 ）； 用 “ 建樹(shù)算法 ” 對(duì)當(dāng)前窗口形成一棵決策樹(shù)； 對(duì)訓(xùn)練集（窗口除外）中例子用所得決策樹(shù)進(jìn)行類別判定，找出錯(cuò)判的例子； 若存在錯(cuò)判的例子，把它們插入窗口，轉(zhuǎn) 2，否則結(jié)束。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ? 主算法流程用下圖表示。其中 PE、 NE分別表示正例集和反例集，它們共同組成訓(xùn)練集。 ? PE’， PE’’和 NE’， NE’’分別表示正例集和反例集的子集。 ? 主算法中每迭代循環(huán)一次，生成的決策樹(shù)將會(huì)不相同。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 訓(xùn)練集 PE、 NE 取子集建窗口 窗口 PE`、 NE` 生成 決策樹(shù) 測(cè)試 PE、 NE 擴(kuò)展窗口 PE`=PE`+PE``NE`=NE`+NE`` 此決策樹(shù)為最后結(jié)果 存在錯(cuò)判的 PE``， NE``嗎 是 否 ID3主算法流程 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 （二）建樹(shù)算法 對(duì)當(dāng)前例子集合，計(jì)算各特征的互信息； 選擇互信息最大的特征 Ak； 把在 Ak處取值相同的例子歸于同一子集， Ak取幾個(gè)值就得幾個(gè)子集； 對(duì)既含正例又含反例的子集，遞歸調(diào)用建樹(shù)算法； 若子集僅含正例或反例，對(duì)應(yīng)分枝標(biāo)上 P或 N， 返回調(diào)用處。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 )logP(u)P(uH(U) ii i???|S||u|)P(u ii ? ID3方法應(yīng)用實(shí)例 對(duì)于氣候分類問(wèn)題進(jìn)行具體計(jì)算有： ⒈ 信息熵的計(jì)算 信息熵： 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(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） log（ 14/9） +（ 5/14） log（ 14/5）= 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ? ??? j jii jij vuPvuPvPVUH )/(l o g)/()()/(||||)/(jiji vuvuP ? 條件熵： ⒉ 條件熵計(jì)算 屬性 A1取值 vj時(shí) ， 類別 ui的條件概率： 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 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)) = 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ⒊ 互信息計(jì)算 對(duì) A1=天氣 處有： I（ 天氣） =H（ U） H（ U|V） = = bit 類似可得： I（ 氣溫） = bit I（ 濕度） = bit I（ 風(fēng)） = bit ⒋ 建決策樹(shù)的樹(shù)根和分枝 ID3算法將選擇互信息最大的特征天氣作為樹(shù)根，在 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)用建樹(shù)算法。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ⒌ 遞歸建樹(shù) 分別對(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。 這樣就得到圖的決策樹(shù) 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 ID3算法在數(shù)據(jù)挖掘中占有非常重要的地位。但是，在應(yīng)用中， ID3算法不能夠處理連續(xù)屬性、計(jì)算信息增益時(shí)偏向于選擇取值較多的屬性等不足。 ID3基礎(chǔ)上發(fā)展起來(lái)的決策樹(shù)生成算法，由 1993年提出。 ID3在應(yīng)用中存在的不足。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 （ 1） 用信息增益率來(lái)選擇屬性，它克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足； （ 2） 在樹(shù)構(gòu)造過(guò)程中或者構(gòu)造完成之后，進(jìn)行剪枝； （ 3） 能夠完成對(duì)連續(xù)屬性的離散化處理； （ 4） 能夠?qū)τ诓煌暾麛?shù)據(jù)的處理，例如未知的屬性值； （ 5） ，并最終可以形成產(chǎn)生式規(guī)則。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 Quinlan在 ID3中使用信息論中的信息增益 （ gain） 來(lái)選擇屬性 ， 而 （ gain ratio） 來(lái)選擇屬性 。 信息增益率 ID3改進(jìn)是用信息增益率來(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 ??決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 決策規(guī)則樹(shù)及應(yīng)用 IBLE方法： IBLE方法是利用信息論中信道容量來(lái)選擇屬性，比互信息更好。 IBLE方法建決策規(guī)則樹(shù)，每個(gè)結(jié)點(diǎn)由多個(gè)屬性取值組成，提高了屬性組合的識(shí)別效果。 IBLE比 ID3識(shí)別率提高了 10個(gè)百分點(diǎn)。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 數(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)策略。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 數(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)證、犯罪組織分析等工作。 決策支持系統(tǒng) 醫(yī)藥信息工程學(xué)院 . 數(shù) 據(jù) 倉(cāng)庫(kù)與數(shù) 據(jù) 挖 掘的 決 策支持 第 5 章 結(jié) 束