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