【正文】 樹結(jié)構(gòu)越復(fù)雜，則 過渡擬合發(fā)生的可能性越大。（訓(xùn)練誤差低，泛化誤差高，稱為過渡擬合） 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 模型過渡擬合的潛在因素 （ 1）噪聲導(dǎo)致的過渡擬合； 錯(cuò)誤的類別值 /類標(biāo)簽，屬性值等 （ 2）缺乏代表性樣本所導(dǎo)致的過渡擬合 根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過渡擬合的 影響。 過度擬合：給定一個(gè)假設(shè)空間 H，一個(gè)假設(shè) h∈ H，如果存在其 它的假設(shè) h1 ∈ H ,使得在訓(xùn)練樣例上 h的錯(cuò)誤率比 h1小，但在整個(gè)實(shí) 例發(fā)布上 h1的錯(cuò)誤率比 h小，則稱假設(shè) h過度擬合訓(xùn)練數(shù)據(jù) 過度擬合產(chǎn)生的原因：噪聲，訓(xùn)練樣例太小等 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 對(duì)學(xué)習(xí)算法是否成功的真正測試是看它對(duì)于訓(xùn)練中未見到的 數(shù)據(jù)的執(zhí)行性能。 表 2 轉(zhuǎn)化后的客戶信息表 年齡 學(xué)歷 職業(yè) 繳費(fèi)方式 開戶時(shí)間 費(fèi)用變化率 客戶流失 N3 W3 Z1 T1 H2 F1 NO N2 W2 Z2 T2 H2 F2 NO N1 W3 Z1 T3 H1 F2 YES N1 W3 Z1 T2 H1 F1 NO N1 W1 Z2 T2 H1 F1 NO N2 W2 Z3 T3 H1 F3 YES N3 W1 Z3 T1 H2 F1 NO 第 6章 決策樹 決策樹算法 ID3算法實(shí)際應(yīng)用 在電信行業(yè)應(yīng)用實(shí)例（ 5） YES NO 年 齡 職 業(yè) YES 繳費(fèi)方式 YES YES NO YSES NO NO 在網(wǎng)時(shí)長 NO F1 F2 F3 N1 N2 N3 T1 T2 T3 Z1 Z2 Z3 H1 H2 費(fèi)用變化率 第 6章 決策樹 決策樹算法 ID3算法實(shí)際應(yīng)用 在電信行業(yè)應(yīng)用實(shí)例（ 6） 在圖中， NO表示客戶不流失， YES表示客戶流失。 該公司經(jīng)過多年的電腦化管理，已有大量的客戶個(gè)人基本信息 (文中簡稱為客戶信息表 )。三、 指客戶自然流失和被動(dòng)流失。 （ Binary Split）。 。 在決策樹分類中，假設(shè) S是訓(xùn)練樣本集合， |S|是訓(xùn)練樣本數(shù)，樣本 劃分為 n個(gè)不同的類 C1,C2,….Cn ，這些類的大小分別標(biāo)記為 |C1|， |C2|， …..,|Cn| 。 （ 1） D中包含有 50%的正例和 50%的負(fù)例。 （ a） （ b） 第 6章 決策樹 決策樹算法 Age？ young middle old No:3 Yes:2 No:2 Yes:3 No:1 Yes:4 Own_house？ true false No:0 Yes:6 No:6 Yes:3 （ a） （ b） 選擇 (b)時(shí)，當(dāng) Own_house=true時(shí)，每個(gè)樣例都分配到 yse類中。 當(dāng)獲取信息時(shí)，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信 息伴著不確定性。 6 轉(zhuǎn)步驟 2, 對(duì)每個(gè)子集遞歸調(diào)用 CLS。它是許多決策樹學(xué)習(xí)算法 的基礎(chǔ)。 CLS, ID3， ， CART 第 6章 決策樹 決策樹算法 計(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ù)據(jù)，那么對(duì)于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？ 即：你能預(yù)測這位客人是屬于“買”計(jì)算機(jī)的那一類，還是屬于“不買”計(jì)算機(jī)的那一類？ 又：你需要多少有關(guān)這位客人的信息才能回答這個(gè)問題？ 決策樹的用途 第 6章 決策樹 計(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) 買 誰在買計(jì)算機(jī)？ 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹的用途 決策樹算法 第 6章 決策樹 計(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) 買 誰在買計(jì)算機(jī)？ 年齡？ 學(xué)生？ 信譽(yù)？ 買 青 中 老 否 是 優(yōu) 良 不買 買 買 不買 決策樹的用途 決策樹算法 第 6章 決策樹 決策樹算法 決策樹的表示 決策樹的基本組成部分：決策結(jié)點(diǎn)、分支和葉子。 定義 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例中很 好地逼近目標(biāo)函數(shù)，則它也能在未見實(shí)例中很好地逼近目標(biāo)函數(shù)。 例如 有 150個(gè)數(shù)據(jù)，分 3類，每類 50個(gè)數(shù)據(jù)。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 2） 從這些不同的變形中選擇最佳的假設(shè)（或者說權(quán)值集合）。 第 6章 決策樹 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 1） 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問題； 從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理。歸納學(xué)習(xí)存在一個(gè)基本的假設(shè)： 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則它也能在未見樣本中很好地逼近目標(biāo)函數(shù)。歸納推理從若干個(gè)事實(shí)中表 征出的特征、特性和屬性中，通過比較、總結(jié)、概括而得出一 個(gè)規(guī)律性的結(jié)論。但其合理性和收斂性沒有理論的保證。 協(xié)同訓(xùn)練利用分類器之間的相互訓(xùn)練來提高分類性能。半監(jiān)督學(xué)習(xí)致力于 利用未標(biāo)記樣本來提高學(xué)習(xí)性能。因此，訓(xùn)練算法的主要目標(biāo)就是要建立具有很好的泛化 能力模型，即建立能夠準(zhǔn)確地預(yù)測未知樣本類標(biāo)號(hào)的模型。用元組 (X,y)表示，其中， X 是屬性集合， y是一個(gè) 特殊的屬性，指出樣例的類標(biāo)號(hào)（也稱為分類屬性或者目標(biāo)屬性） 第 6章 決策樹 決策樹基本概念 關(guān)于分類問題 名稱 體溫 表皮覆蓋 胎生 水生動(dòng)物 飛行動(dòng)物 有腿 冬眠 類標(biāo)號(hào) 人類 恒溫 毛發(fā) 是 否 否 是 否 哺乳動(dòng)物 海龜 冷血 鱗片 否 半 否 是 否 爬行類 鴿子 恒溫 羽毛 否 否 是 是 否 鳥類 鯨 恒溫 毛發(fā) 是 是 否 否 否 哺乳類 X y 分類與回歸 分類目標(biāo)屬性 y是離散的，回歸目標(biāo)屬性 y是連續(xù)的 第 6章 決策樹 決策樹基本概念 解決分類問題的一般方法 分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。 新數(shù)據(jù)使用訓(xùn)練數(shù)據(jù)集中得到的規(guī)則進(jìn)行分類。但要求分類器對(duì)未標(biāo)識(shí)數(shù)據(jù)具有較高的分類精度。 第 6章 決策樹 半監(jiān)督學(xué)習(xí)（ semisupervised learning ） CoEM算法及特點(diǎn) CoEM算法是協(xié)同訓(xùn)練的改進(jìn)形式，它不是直接利用當(dāng) 前分類器對(duì)未標(biāo)識(shí)樣本的分類，而利用分類后的后驗(yàn)概率進(jìn) 行分類。 第 6章 決策樹 決策樹基本概念 決策樹的優(yōu)點(diǎn) 推理過程容易理解，決策推理過程可以表示成 If Then形式； 推理過程完全依賴于屬性變量的取值特點(diǎn)； 可自動(dòng)忽略目標(biāo)變量沒有貢獻(xiàn)的屬性變量，也為判斷屬性 變量的重要性，減少變量的數(shù)目提供參考。 第 6章 決策樹 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (2) 歸納學(xué)習(xí)的過程就是尋找一般化描述的過程。將描述逐步一般化。例如， y=ax+b。多數(shù)情況下，為了高效地搜索，可以 利用假設(shè)空間中一種自然形成的結(jié)構(gòu)，即一般到特殊的偏序關(guān)系。 H中每個(gè)假設(shè) h表 示 X上定義的布爾函數(shù)。 1988年， Utgoff 在 ID4基礎(chǔ)上提出了 ID5學(xué)習(xí)算法，進(jìn)一步提高了效率。 每個(gè)葉結(jié)點(diǎn)代表一種可能的分類結(jié)果 在沿著決策樹從上到下的遍歷過程中，在每個(gè)結(jié)點(diǎn)都有一個(gè) 測試。 2 若訓(xùn)練樣本集 T 中所有的樣本都屬于同一類 , 則生成結(jié)點(diǎn) T , 并終止學(xué)習(xí)算法 。 第 6章 決策樹 ID3 決策樹算法 ID3算法主要針對(duì)屬性選擇問題。對(duì)于 每個(gè)分支，列出該分支上每個(gè)類（ Yes或 No）的訓(xùn)練數(shù)據(jù)的數(shù)目。事件 ai的信息量 I（ ai ）可 如下度量： 其中 p(ai)表示事件 ai發(fā)生的概率。當(dāng) D 中所有數(shù)據(jù)都只屬于一個(gè)類時(shí)，熵得到最小值。 分別計(jì)算不同屬性的信息增益。 在應(yīng)用連續(xù)屬性值時(shí)，在一個(gè)樹結(jié)點(diǎn)可以將屬性 Ai的值 劃分為幾個(gè)區(qū)間。 第 6章 決策樹 決策樹算法 ID3算法實(shí)際應(yīng)用 在電信行業(yè)應(yīng)用實(shí)例（ 1） 通過 ID3算法來實(shí)現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的 特征，以幫助電信公司有針對(duì)性地改善客戶關(guān)系，避免客戶流失 利用決策樹方法進(jìn)行數(shù)據(jù)挖掘，一般有如下步驟： 數(shù)據(jù)預(yù)處 理、決策樹挖掘操作 ，模式評(píng)估和應(yīng)用。 第 6章 決策樹 決策樹算法 ID3算法實(shí)際應(yīng)用 在電信行業(yè)應(yīng)用實(shí)例（ 2） 數(shù)據(jù)預(yù)處理 數(shù)據(jù)挖掘的處理對(duì)象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲(chǔ)在數(shù) 據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲(chǔ)在其 CRM中），是長期積累的 結(jié)果。文化程度分為 3類： W1初中以下 (含初中 )， W2高中 (含 中專 )， W3大學(xué) (專科、本科及以上 )；職業(yè)類別：按工作性質(zhì)來分 共分 3類： Z1一 Z3； 繳費(fèi)方式：托收： T1,營業(yè)廳繳費(fèi)： T2,充值卡： T3。 第 6章 決策樹 關(guān)于過渡擬合 上述的決策樹算法增長樹的每一個(gè)分支的深度，直到恰好能 對(duì)訓(xùn)練樣例比較完美地分類。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 一般可以將分類模型的誤差分為： 訓(xùn)練誤差（ Training Error）； 泛化誤差（ Generalization Error） 決策樹研究問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 訓(xùn)練誤差是在訓(xùn)練記錄上誤分類樣本比例； 泛化誤差是模型在未知記錄上的期望誤差； 一個(gè)好的模型不僅要能夠很好地?cái)M合訓(xùn)練數(shù)據(jù)，而且對(duì)未知 樣本也要能夠準(zhǔn)確地分類。 該例清楚表明，當(dāng)決策樹的葉節(jié) 點(diǎn)沒有足夠的代表性時(shí)，可能會(huì) 預(yù)測錯(cuò)誤。 決策樹研究 問題 。人和大象都不是 哺乳動(dòng)物。如果驗(yàn)證結(jié)果差，則需要考慮采用不同的結(jié)構(gòu)重 新進(jìn)行訓(xùn)練，例如使用更大的樣本集，或者改變從連續(xù)值到離散 值得數(shù)據(jù)轉(zhuǎn)換等。 然而，洪家榮等人已經(jīng)證明了要找到這種最優(yōu)的決策樹是 NP難