【正文】 higherlevel concepts using concept hierarchies） 例如：年齡歸納為老、中、青三類 控制每個屬性的可能值不超過七種 （最好不超過五種） ? Relevance analysis 對于與問題無關(guān)的屬性：刪 對于屬性的可能值大于七種 又不能歸納的屬性：刪 決策樹算法 第 6章 決策樹 決策樹的數(shù)據(jù)準(zhǔn)備 決策樹算法 處理連續(xù)屬性值 決策樹算法比較適合處理離散數(shù)值的屬性。實際應(yīng)用中 屬性是連續(xù)的或者離散的情況都比較常見。 在應(yīng)用連續(xù)屬性值時，在一個樹結(jié)點可以將屬性 Ai的值 劃分為幾個區(qū)間。然后信息增益的計算就可以采用和離散值 處理一樣的方法。原則上可以將 Ai的屬性劃分為任意數(shù)目的 空間。 （ Binary Split）。需要找出 一個合適的分割閾值。 參考 Top 10 algorithms in data mining Knowledge Information System 2023 14:1–37 第 6章 決策樹 決策樹算法 ID3算法小結(jié) ID3算法是一種經(jīng)典的決策樹學(xué)習(xí)算法，由 Quinlan于 1979年 提出。 ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié) 點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值 變?yōu)樽钚〉膶傩?，以?gòu)造一顆熵值下降最快的決策樹，到葉子節(jié) 點處的熵值為 0。此時，每個葉子節(jié)點對應(yīng)的實例集中的實例屬于 同一類。 第 6章 決策樹 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例（ 1） 通過 ID3算法來實現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的 特征，以幫助電信公司有針對性地改善客戶關(guān)系，避免客戶流失 利用決策樹方法進(jìn)行數(shù)據(jù)挖掘，一般有如下步驟： 數(shù)據(jù)預(yù)處 理、決策樹挖掘操作 ，模式評估和應(yīng)用。 電信運營商的客戶流失有三方面的含義：一是指客戶從一個 電信運營商轉(zhuǎn)網(wǎng)到其他電信運營商，這是流失分析的重點。二是 指客戶月平均消費量降低，從高價值客戶成為低價值客戶。三、 指客戶自然流失和被動流失。 在客戶流失分析中有兩個核心變量：財務(wù)原因／非財務(wù)原因、 主動流失／被動流失。 客戶流失可以相應(yīng)分為四種類型：其中非財務(wù)原因主動流失 的客戶往往是高價值的客戶。他們會正常支付服務(wù)費用，并容易 對市場活動有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。 第 6章 決策樹 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例（ 2） 數(shù)據(jù)預(yù)處理 數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲在數(shù) 據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲在其 CRM中），是長期積累的 結(jié)果。但往往不適合直接挖掘，需要做數(shù)據(jù)的預(yù)處理工作，一般 包括數(shù)據(jù)的選擇 (選擇相關(guān)的數(shù)據(jù) )、凈化 (消除冗余數(shù)據(jù) )、轉(zhuǎn)換、 歸約等。數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充分，對于挖掘算法的效率乃 至正確性都有關(guān)鍵性的影響。 該公司經(jīng)過多年的電腦化管理，已有大量的客戶個人基本信息 (文中簡稱為客戶信息表 )。在客戶信息表中，有很多屬性，如姓名 用戶號碼、用戶標(biāo)識、用戶身份證號碼 (轉(zhuǎn)化為年齡 )、在網(wǎng)時間 （竣工時間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)） 等等，數(shù)據(jù)準(zhǔn)備時必須除掉表中一些不必要的屬性，一般可采用面 向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性。 第 6章 決策樹 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例（ 3） 屬性刪除：將有大量不同取值且無概化操作符的屬性或者可用其 它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表 中的用戶標(biāo)識、身份證號碼等，它們的取值太多應(yīng)將其刪除，得 到表 1。 表 1 客戶信息表 年齡 學(xué)歷 職業(yè) 繳費方式 在網(wǎng)時長 費用變化率 客戶流失 58 大學(xué) 公務(wù)員 托收 13 10% NO 47 高中 工人 營業(yè)廳繳費 9 42% NO 26 研究生 公務(wù)員 充值卡 2 63% YES 28 大學(xué) 公務(wù)員 營業(yè)廳繳費 5 % NO 32 初中 工人 營業(yè)廳繳費 3 % NO 42 高中 無業(yè)人員 充值卡 2 100% YES 68 初中 無業(yè)人員 營業(yè)廳繳費 9 % NO 第 6章 決策樹 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例（ 4） 屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆 進(jìn)行概化。文化程度分為 3類： W1初中以下 (含初中 )， W2高中 (含 中專 )， W3大學(xué) (?？?、本科及以上 )；職業(yè)類別：按工作性質(zhì)來分 共分 3類： Z1一 Z3； 繳費方式：托收： T1,營業(yè)廳繳費： T2,充值卡： T3。 連續(xù)型屬性概化為區(qū)間值：表中年齡、費用變化率和在網(wǎng)時間為 連續(xù)型數(shù)據(jù)，由于建立決策樹時，用離散型數(shù)據(jù)進(jìn)行處理速度最 快，因此對連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，根據(jù)專家經(jīng)驗和實際計 算信息增益，在“在網(wǎng)時長”屬性中，通過檢測每個劃分，得到在 閾值為 5年時信息增益最大，從而確定最好的劃分是在 5年處，則 這個屬性的范圍就變?yōu)椋?=5,5： H1,H2｝。而在“年齡”屬性中， 信息增益有兩個鋒值，分別在 40和 50處，因而該屬性的范圍變?yōu)? {=40,40=50,50}即變?yōu)?{青年，中年，老年： N1,N2,N3}；費 用變化率：指（（當(dāng)月話費－近 3個月的平均話費） /近 3個月的平 均話費） ％ 0， F1:＝ 30%， F2： 30%99%, F3:＝ 100%變?yōu)? ｛ F1,F2,F3｝。 表 2 轉(zhuǎn)化后的客戶信息表 年齡 學(xué)歷 職業(yè) 繳費方式 開戶時間 費用變化率 客戶流失 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算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例（ 5） YES NO 年 齡 職 業(yè) YES 繳費方式 YES YES NO YSES NO NO 在網(wǎng)時長 NO F1 F2 F3 N1 N2 N3 T1 T2 T3 Z1 Z2 Z3 H1 H2 費用變化率 第 6章 決策樹 決策樹算法 ID3算法實際應(yīng)用 在電信行業(yè)應(yīng)用實例（ 6） 在圖中， NO表示客戶不流失， YES表示客戶流失。從圖可以看出，客戶費用變化率 為 100%的客戶肯定已經(jīng)流失；而費用變化率低于 30%的客戶；即每月資費相對穩(wěn)定的客 戶一般不會流失，費用變化率在 30%～ 99%的客戶有可能流失，其中年齡在 40～ 50歲之間 的客戶流失的可能性非常大，而年齡低于 40歲的客戶，用充值卡繳費的客戶和在網(wǎng)時間較 短的客戶容易流失；年齡較大的客戶，則工人容易流失。 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻(xiàn) 第 6章 決策樹 決策樹研究問題 理想的決策樹有三種： (1)葉子結(jié)點數(shù)最少； (2)葉子結(jié)點深度最小； (3)葉子結(jié)點數(shù)最少且葉子結(jié)點深度最小。 然而，洪家榮等人已經(jīng)證明了要找到這種最優(yōu)的決策樹是 NP難 題。因此，決策樹優(yōu)化的目的就是要找到盡可能趨向于最優(yōu)的 決策樹。 第 6章 決策樹 關(guān)于過渡擬合 上述的決策樹算法增長樹的每一個分支的深度，直到恰好能 對訓(xùn)練樣例比較完美地分類。實際應(yīng)用中，當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練 樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時，該 策略可能會遇到困難。 在以上情況發(fā)生時，這個簡單的算法產(chǎn)生的樹會過渡擬合訓(xùn)練 樣例（過渡擬合： Over Fitting） . 決策樹研究問題 關(guān)于過渡擬合 第 6章 決策樹 對于一個假設(shè)，當(dāng)存在其它的假設(shè)對訓(xùn)練樣例的擬合比它差， 但事實上在實例的整個分布上（包含訓(xùn)練集合以外的實例）表現(xiàn)得 卻更好時，則稱該假設(shè)過度擬合訓(xùn)練樣例。 過度擬合：給定一個假設(shè)空間 H，一個假設(shè) h∈ H，如果存在其 它的假設(shè) h1 ∈ H ,使得在訓(xùn)練樣例上 h的錯誤率比 h1小，但在整個實 例發(fā)布上 h1的錯誤率比 h小，則稱假設(shè) h過度擬合訓(xùn)練數(shù)據(jù) 過度擬合產(chǎn)生的原因：噪聲，訓(xùn)練樣例太小等 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 對學(xué)習(xí)算法是否成功的真正測試是看它對于訓(xùn)練中未見到的 數(shù)據(jù)的執(zhí)行性能。 訓(xùn)練過程應(yīng)該包含訓(xùn)練樣本和驗證樣本。驗證樣本用于測試 訓(xùn)練后的性能。如果驗證結(jié)果差，則需要考慮采用不同的結(jié)構(gòu)重 新進(jìn)行訓(xùn)練，例如使用更大的樣本集，或者改變從連續(xù)值到離散 值得數(shù)據(jù)轉(zhuǎn)換等。 通常應(yīng)該建立一個驗證過程，在訓(xùn)練最終完成后用來檢測訓(xùn) 練結(jié)果的泛化能力。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 一般可以將分類模型的誤差分為： 訓(xùn)練誤差（ Training Error）； 泛化誤差（ Generalization Error） 決策樹研究問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 訓(xùn)練誤差是在訓(xùn)練記錄上誤分類樣本比例； 泛化誤差是模型在未知記錄上的期望誤差； 一個好的模型不僅要能夠很好地擬合訓(xùn)練數(shù)據(jù)，而且對未知 樣本也要能夠準(zhǔn)確地分類。 一個好的分類模型必須具有低的訓(xùn)練誤差和泛化誤差。因為 一個具有低訓(xùn)練誤差的模型，其泛化誤差可能比具有較高訓(xùn)練誤 差的模型高。（訓(xùn)練誤差低，泛化誤差高，稱為過渡擬合） 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 模型過渡擬合的潛在因素 （ 1）噪聲導(dǎo)致的過渡擬合； 錯誤的類別值 /類標(biāo)簽，屬性值等 （ 2）缺乏代表性樣本所導(dǎo)致的過渡擬合 根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過渡擬合的 影響。由于訓(xùn)練樣本缺乏代表性的樣本，在沒有多少訓(xùn)練 記錄的情況下，學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型就會導(dǎo)致過渡 擬合。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 模型過渡擬合的潛在因素 名稱 體溫 胎生 4條腿 冬眠 哺乳動物 蠑螈 冷血 N Y Y N 虹鳉 冷血 Y N N N 鷹 恒溫 N N N N 弱夜鷹 恒溫 N N Y N 鴨嘴獸 恒溫 Y Y Y Y 哺乳動物分類的訓(xùn)練樣例 體溫 恒溫 冷血 冬眠 N Y N N 4條腿 Y N N Y 名稱 體溫 胎生 4條腿 冬眠 哺乳動物 人 恒溫 Y N N Y 大象 恒溫 Y Y N Y 鴿子 恒溫 N N N N 哺乳動物分類的訓(xùn)練樣例 按照訓(xùn)練模型。人和大象都不是 哺乳動物。決策樹作出這樣的判 斷是因為只有一個訓(xùn)練樣例具有 這些特點（鷹，恒溫，不冬眠） 被劃分為非哺乳動物。 該例清楚表明，當(dāng)決策樹的葉節(jié) 點沒有足夠的代表性時，可能會 預(yù)測錯誤。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 解決過度擬合的手段： 1 及早停止樹增長； 2 后修剪法。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 1 及早停止樹增長 由于決策樹學(xué)習(xí)要從候選集合眾選擇滿足給定標(biāo)準(zhǔn)的 最大化屬性，并且不回溯，也就是我們常說的爬山策略，其 選擇往往會是局部最優(yōu)而不是全局最優(yōu)。樹結(jié)構(gòu)越復(fù)雜，則 過渡擬合發(fā)生的可能性越大。因此，要選擇簡單的模型。 Occan法則（又稱 Occan剃刀 Occan Razor） :具有相同 泛化誤差的兩個模型，較簡單的模型比復(fù)雜的模型更可取。 決策樹研究 問題