【正文】 題。比如客戶信息表 中的用戶標(biāo)識(shí)、身份證號(hào)碼等，它們的取值太多應(yīng)將其刪除，得 到表 1。他們會(huì)正常支付服務(wù)費(fèi)用，并容易 對(duì)市場(chǎng)活動(dòng)有所響應(yīng)。 ID3算法的基本思想是，以信息熵為度量，用于決策樹(shù)節(jié) 點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值 變?yōu)樽钚〉膶傩?，以?gòu)造一顆熵值下降最快的決策樹(shù)，到葉子節(jié) 點(diǎn)處的熵值為 0。 整理后的數(shù)據(jù)表 決策樹(shù)的數(shù)據(jù)準(zhǔn)備 ? Data cleaning 刪除 /減少 noise， 補(bǔ)填 missing values ? Data transformation 數(shù)據(jù)標(biāo)準(zhǔn)化（ data normalization） 數(shù)據(jù)歸納（ generalize data to higherlevel concepts using concept hierarchies） 例如：年齡歸納為老、中、青三類 控制每個(gè)屬性的可能值不超過(guò)七種 （最好不超過(guò)五種） ? Relevance analysis 對(duì)于與問(wèn)題無(wú)關(guān)的屬性：刪 對(duì)于屬性的可能值大于七種 又不能歸納的屬性：刪 決策樹(shù)算法 第 6章 決策樹(shù) 決策樹(shù)的數(shù)據(jù)準(zhǔn)備 決策樹(shù)算法 處理連續(xù)屬性值 決策樹(shù)算法比較適合處理離散數(shù)值的屬性。該屬性分 兩類：買 /不買 S1(買 )=641 S2（不買） = 383 S=S1+S2=1024 P1=641/1024= P2=383/1024= I(S1,S2)=I(641,383) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹(shù)算法 第 6章 決策樹(shù) 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 2步計(jì)算條件屬性的熵 條件屬性共有 4個(gè)。 Entropy(D)=1*log210*log20=0 從上述的結(jié)果可以看到一個(gè)趨勢(shì)，當(dāng)數(shù)據(jù)變得越來(lái)越純凈時(shí)，熵的值變得 越來(lái)越小。 說(shuō)明，節(jié)點(diǎn)的選擇對(duì)結(jié)果是有影響的。 如何度量信息量的大??？ 第 6章 決策樹(shù) 決策樹(shù)算法 ID Age Hasjob Own_house Credit_rating Class 1 Young False False Fair No 2 Young False False Good No 3 Young True False Good Yes 4 Young True True Fair Yes 5 Young False False Fair No 6 Middle False False Fair No 7 Middle False False Good No 8 Middle True True Good Yes 9 Middle False True Excellent Yes 10 Middle False True Excellent Yes 11 Old False True Excellent Yes 12 Old False True Good Yes 13 Old True False Good Yes 14 Old True False Excellent Yes 15 Old False False fair no 例申請(qǐng)貸款 的數(shù)據(jù)集合 第 6章 決策樹(shù) 決策樹(shù)算法 上例可能的兩種根節(jié)點(diǎn) Age？ young middle old No:3 Yes:2 No:2 Yes:3 No:4 Yes:1 Own_house？ true false No:0 Yes:6 No:6 Yes:3 上例若采用 Age或 Own_house作為根節(jié)點(diǎn)。實(shí)踐表明，測(cè)試屬性集的組成以及測(cè)試屬性的先后對(duì)決策樹(shù)的學(xué)習(xí)具有舉足輕重的影響。根據(jù)該屬性的值的 不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子 集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對(duì)應(yīng) 于決策樹(shù)的內(nèi)部結(jié)點(diǎn)，即測(cè)試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性 對(duì)該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類。每個(gè)分支是一 個(gè)新的決策結(jié)點(diǎn)，或者是樹(shù)的葉子。 1979年 , . Quinlan 給出 ID3算法，并在 1983年和 1986年對(duì) ID3 進(jìn)行了總結(jié)和簡(jiǎn)化，使其成為決策樹(shù)學(xué)習(xí)算法的典型。 歸納學(xué)習(xí)假設(shè) 機(jī)器學(xué)習(xí)的任務(wù)是在整個(gè)實(shí)例集合 X上確定與目標(biāo)概念 c相同 的假設(shè) 。概念學(xué)習(xí)也可以看作是一 個(gè)搜索問(wèn)題的過(guò)程。 F的每一個(gè)逼近都 叫做一個(gè)假設(shè)。歸納可分為自 頂向下，自底向上和雙向搜索三種方式。 歸納對(duì)于認(rèn)識(shí)的發(fā)展和完善具有重要的意義。 基于圖的方法（ graphbased methods） . 第 6章 決策樹(shù) 決策樹(shù)基本概念 決策樹(shù) 決策樹(shù)是一種典型的分類方法，首先對(duì)數(shù)據(jù)進(jìn)行處理，利用 歸納算法生成可讀的規(guī)則和決策樹(shù)，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行 分析。協(xié)同訓(xùn)練結(jié)果一般要優(yōu)于自訓(xùn) 練。如此循環(huán)多次后，輸出得到的 分類器及其分類結(jié)果。 預(yù)測(cè)應(yīng)用（推論） 根據(jù)建立的分類模型，對(duì)測(cè)試集合進(jìn)行測(cè)試。第 6 章 決策樹(shù) 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)研究問(wèn)題 主要參考文獻(xiàn) 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)研究問(wèn)題 主要參考文獻(xiàn) 第 6章 決策樹(shù) 決策樹(shù)基本概念 關(guān)于分類問(wèn)題 分類（ Classification）任務(wù)就是通過(guò)學(xué)習(xí)獲得一個(gè)目標(biāo)函數(shù) （ Target Function） f, 將每個(gè)屬性集 x映射到一個(gè)預(yù)先定義好的類 標(biāo)號(hào) y。 第 6章 決策樹(shù) 決策樹(shù)基本概念 解決分類問(wèn)題的一般方法 通過(guò)以上對(duì)分類問(wèn)題一般方法的描述，可以看出分類問(wèn)題 一般包括兩個(gè)步驟： 模型構(gòu)建（歸納） 通過(guò)對(duì)訓(xùn)練集合的歸納，建立分類模型。將分類臵信度 較高的未標(biāo)識(shí)數(shù)據(jù)作為新的訓(xùn)練樣本，添加到原訓(xùn)練 集中對(duì)模型進(jìn)行更新。最終結(jié)果 綜合了兩個(gè)分類器的結(jié)果得到。 最大化分離（ maximizing separation） 。即從特殊事實(shí)到普遍性規(guī)律的結(jié)論。 第 6章 決策樹(shù) 決策樹(shù)基本概念 關(guān)于歸納學(xué)習(xí) (3) 第 6章 決策樹(shù) 決策樹(shù)基本概念 關(guān)于歸納學(xué)習(xí) (4) 歸納過(guò)程就是在描述空間中進(jìn)行搜索的過(guò)程。 學(xué)習(xí)過(guò)程將產(chǎn)生對(duì)目標(biāo)函數(shù) f的不同逼近。 ??????amplestraininge xbVtrainbbVbVtrainE)(,2^ ))()(( 學(xué)習(xí)是在假設(shè)空間上的一個(gè)搜索。其分類精度為 .43/ 上例的數(shù)據(jù)來(lái)自 UCI Machine Learning Repository中的 German Credit Dataset 可以免費(fèi)獲取。 })1,0{:( ?xhh第 6章 決策樹(shù) 決策樹(shù)基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問(wèn)題（ 4） 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)研究問(wèn)題 主要參考文獻(xiàn) 第 6章 決策樹(shù) 決策樹(shù)算法 與決策樹(shù)相關(guān)的重要算法 Hunt,Marin和 Stone 于 1966年研制的 CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個(gè)概 念。 是整個(gè)決策樹(shù)的開(kāi)始。該測(cè)試屬性對(duì)應(yīng)決策樹(shù)中的決策結(jié)點(diǎn)。沒(méi)有規(guī)定采用何種測(cè)試屬性。 如果某件事情是“百年一見(jiàn)”則肯定比“習(xí)以為?！钡氖录? 信息量大。 選擇 (a)時(shí)，如果我們選擇按照多數(shù)服從少數(shù)的方法，則會(huì)產(chǎn)生 5個(gè)錯(cuò)誤的分類。 Entropy(D)=**= （ 3） D中包含有 100%的正例和 0%的負(fù)例。 第 6章 決策樹(shù) ID3 –信息量大小的度量 決策樹(shù)算法 Gain（ S， A）是屬性 A在集合 S上的信息增益 Gain（ S， A） = Entropy（ S） Entropy（ S， A） 公式 3 Gain（ S， A）越大，說(shuō)明選擇測(cè)試屬性對(duì)分類提供的信息越多 第 6章 決策樹(shù) 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 決策樹(shù)算法 第 6章 決策樹(shù) 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 132 老 中 是 良 買 64 青 中 是 優(yōu) 買 32 中 中 否 優(yōu) 買 32 中 高 是 良 買 63 老 中 否 優(yōu) 不買 1 老 中 否 優(yōu) 買 第 1步計(jì)算決策屬性的熵 決策屬性“買計(jì)算機(jī)？”。 原始表 決策樹(shù)算法 第 6章 決策樹(shù) 計(jì)數(shù) 年齡 收入 學(xué)生 信譽(yù) 歸類：買計(jì)算機(jī)？ 64 青 高 否 良 不買 64 青 高 否 優(yōu) 不買 128 中 高 否 良 買 60 老 中 否 良 買 64 老 低 是 良 買 64 老 低 是 優(yōu) 不買 64 中 低 是 優(yōu) 買 128 青 中 否 良 不買 64 青 低 是 良 買 。 參考 Top 10 algorithms in data mining Knowledge Information System 2023 14:1–37 第 6章 決策樹(shù) 決策樹(shù)算法 ID3算法小結(jié) ID3算法是一種經(jīng)典的決策樹(shù)學(xué)習(xí)算法，由 Quinlan于 1979年 提出。 客戶流失可以相應(yīng)分為四種類型：其中非財(cái)務(wù)原因主動(dòng)流失 的客戶往往是高價(jià)值的客戶。 第 6章 決策樹(shù) 決策樹(shù)算法 ID3算法實(shí)際應(yīng)用 在電信行業(yè)應(yīng)用實(shí)例（ 3） 屬性刪除：將有大量不同取值且無(wú)概化操作符的屬性或者可用其 它屬性來(lái)代替它的較高層概念的那些屬性刪除。 主要內(nèi)容 決策樹(shù)基本概念 決策樹(shù)算法 決策樹(shù)研究問(wèn)題 主要參考文獻(xiàn) 第 6章 決策樹(shù) 決策樹(shù)研究問(wèn)題 理想的決策樹(shù)有三種： (1)葉子結(jié)點(diǎn)數(shù)最少； (2)葉子結(jié)點(diǎn)深度最?。? (3)葉子結(jié)點(diǎn)數(shù)最少且葉子結(jié)點(diǎn)深度最小。驗(yàn)證樣本用于測(cè)試 訓(xùn)練后的性能。 決策樹(shù)研究 問(wèn)題 關(guān)于過(guò)渡擬合 第 6章 決策樹(shù) 模型過(guò)渡擬合的潛在因素