【正文】 values ? Data transformation 數(shù)據(jù)標準化（ data normalization） 數(shù)據(jù)歸納（ generalize data to higherlevel concepts using concept hierarchies） 例如：年齡歸納為老、中、青三類 控制每個屬性的可能值不超過七種 （最好不超過五種） ? Relevance analysis 對于與問題無關(guān)的屬性：刪 對于屬性的可能值大于七種 又不能歸納的屬性：刪 決策樹算法 第 6章 決策樹 決策樹的數(shù)據(jù)準備 決策樹算法 處理連續(xù)屬性值 決策樹算法比較適合處理離散數(shù)值的屬性。 在應用連續(xù)屬性值時，在一個樹結(jié)點可以將屬性 Ai的值 劃分為幾個區(qū)間。原則上可以將 Ai的屬性劃分為任意數(shù)目的 空間。需要找出 一個合適的分割閾值。 ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié) 點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值 變?yōu)樽钚〉膶傩裕詷?gòu)造一顆熵值下降最快的決策樹，到葉子節(jié) 點處的熵值為 0。 第 6章 決策樹 決策樹算法 ID3算法實際應用 在電信行業(yè)應用實例（ 1） 通過 ID3算法來實現(xiàn)客戶流失的預警分析，找出客戶流失的 特征，以幫助電信公司有針對性地改善客戶關(guān)系，避免客戶流失 利用決策樹方法進行數(shù)據(jù)挖掘，一般有如下步驟： 數(shù)據(jù)預處 理、決策樹挖掘操作 ，模式評估和應用。二是 指客戶月平均消費量降低，從高價值客戶成為低價值客戶。 在客戶流失分析中有兩個核心變量：財務(wù)原因／非財務(wù)原因、 主動流失／被動流失。他們會正常支付服務(wù)費用，并容易 對市場活動有所響應。 第 6章 決策樹 決策樹算法 ID3算法實際應用 在電信行業(yè)應用實例（ 2） 數(shù)據(jù)預處理 數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲在數(shù) 據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲在其 CRM中），是長期積累的 結(jié)果。數(shù)據(jù)預處理工作準備是否充分，對于挖掘算法的效率乃 至正確性都有關(guān)鍵性的影響。在客戶信息表中，有很多屬性，如姓名 用戶號碼、用戶標識、用戶身份證號碼 (轉(zhuǎn)化為年齡 )、在網(wǎng)時間 （竣工時間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)） 等等，數(shù)據(jù)準備時必須除掉表中一些不必要的屬性，一般可采用面 向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性。比如客戶信息表 中的用戶標識、身份證號碼等，它們的取值太多且無法在該取值 域內(nèi)找到概化操作符，應將其刪除，得到表 1。文化程度分為 3類： W1初中以下 (含初中 )， W2高中 (含 中專 )， W3大學 (?？?、本科及以上 )；職業(yè)類別：按工作性質(zhì)來分 共分 3類： Z1一 Z3； 繳費方式：托收： T1,營業(yè)廳繳費： T2,充值卡： T3。而在“年齡”屬性中， 信息增益有兩個鋒值，分別在 40和 50處，因而該屬性的范圍變?yōu)? {=40,40=50,50}即變?yōu)?{青年，中年，老年： N1,N2,N3}；費 用變化率：指（（當月話費－近 3個月的平均話費） /近 3個月的平 均話費）％ 0， F1:＝ 30%， F2： 30%99%, F3:＝ 100%變?yōu)? ｛ F1,F2,F3｝。從圖可以看出，客戶費用變化率 為 100%的客戶肯定已經(jīng)流失；而費用變化率低于 30%的客戶；即每月資費相對穩(wěn)定的客 戶一般不會流失，費用變化率在 30%～ 99%的客戶有可能流失，其中年齡在 40～ 50歲之間 的客戶流失的可能性非常大，而年齡低于 40歲的客戶，用充值卡繳費的客戶和在網(wǎng)時間較 短的客戶容易流失；年齡較大的客戶，則工人容易流失。 然而，洪家榮等人已經(jīng)證明了要找到這種最優(yōu)的決策樹是 NP難 題。 第 6章 決策樹 關(guān)于過渡擬合 上述的決策樹算法增長樹的每一個分支的深度，直到恰好能 對訓練樣例比較完美地分類。 在以上情況發(fā)生時，這個簡單的算法產(chǎn)生的樹會過渡擬合訓練 樣例（過渡擬合： Over Fitting） . 決策樹研究問題 關(guān)于過渡擬合 第 6章 決策樹 對于一個假設(shè)，當存在其它的假設(shè)對訓練樣例的擬合比它差， 但事實上在實例的整個分布上（包含訓練集合以外的實例）表現(xiàn)得 卻更好時，則稱該假設(shè)過度擬合訓練樣例。 訓練過程應該包含訓練樣本和驗證樣本。如果驗證結(jié)果差，則需要考慮采用不同的結(jié)構(gòu)重 新進行訓練，例如使用更大的樣本集，或者改變從連續(xù)值到離散 值得數(shù)據(jù)轉(zhuǎn)換等。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 一般可以將分類模型的誤差分為： 訓練誤差（ Training Error）； 泛化誤差（ Generalization Error） 決策樹研究問題 關(guān)于過渡擬合 第 6章 決策樹 分類模型的誤差 訓練誤差是在訓練記錄上誤分類樣本比例； 泛化誤差是模型在未知記錄上的期望誤差； 一個好的模型不僅要能夠很好地擬合訓練數(shù)據(jù)，而且對未知 樣本也要能夠準確地分類。因為 一個具有低訓練誤差的模型，其泛化誤差可能比具有較高訓練誤 差的模型高。由于訓練樣本缺乏代表性的樣本，在沒有多少訓練 記錄的情況下，學習算法仍然繼續(xù)細化模型就會導致過渡 擬合。人和大象都不是 哺乳動物。 該例清楚表明，當決策樹的葉節(jié) 點沒有足夠的代表性時，可能會 預測錯誤。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 1 及早停止樹增長 由于決策樹學習要從候選集合眾選擇滿足給定標準的 最大化屬性，并且不回溯，也就是我們常說的爬山策略，其 選擇往往會是局部最優(yōu)而不是全局最優(yōu)。因此，要選擇簡單的模型。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法） 在訓練過程中允許對數(shù)據(jù)的過渡擬合，然后再對樹進行修剪 該方法稱為后剪枝法。 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 A B 負 C 正 正 負 Y Y Y N N N {18， 19， 20} {1， 2， 3， 4 5， 6， 7， 8} {9， 10， 11， 12} {13， 14， 15， 16， 17} 錯分類 5個， 6， 7， 8， 13， 14 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 第 1步 將決策樹規(guī)則化 規(guī)則 1 IF A=Y AND B=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF A=Y AND B=N AND C=N THEN – 規(guī)則 4 IF A=N THEN A B 負 C 正 正 負 Y Y Y N N N 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 規(guī)則 1 IF A=Y AND B=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF A=Y AND B=N AND C=N THEN – 規(guī)則 4 IF A=N THEN 規(guī)則 分類正確的數(shù)目 分類錯誤的數(shù)目 精度 1 5 3 5/8 2 4 0 4/4 3 3 2 3/5 4 3 0 3/3 第 2步 規(guī)則精度的計算 決策樹研究 問題 規(guī)則 2與規(guī)則 4精度為 100%，保留 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 規(guī)則 分類正確的數(shù)目 分類錯誤的數(shù)目 精度 1 5 3 5/8 2 4 0 4/4 3 3 2 3/5 4 3 0 3/3 第 3步 對規(guī)則進行修剪 規(guī)則 去掉 A 去掉 B 去掉 C 去掉 AB 去掉 BC 去掉 AC 選擇 1 5/10 11/17 去掉 B 3 4/6 6/8 3/9 8/10 4/10 6/17 去掉 AB 決策樹研究 問題 ? 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 第 3步 對規(guī)則進行修剪 最終規(guī)則集合為 規(guī)則 去掉 A 去掉 B 去掉 C 去掉 AB 去掉 BC 去掉 AC 選擇 1 5/10 11/17 去掉 B 3 4/6 6/8 3/9 8/10 4/10 6/17 去掉 AB 規(guī)則 1 IF A=Y AND B=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF A=Y AND B=N AND C=N THEN – 規(guī)則 4 IF A=N THEN 原始規(guī)則集合 規(guī)則 1 IF A=Y THEN + 規(guī)則 2 IF A=Y AND B=N AND C=Y THEN + 規(guī)則 3 IF C=N THEN – 規(guī)則 4 IF A=N THEN 最終規(guī)則集合 決策樹研究 問題 關(guān)于過渡擬合 第 6章 決策樹 后修剪法（后剪枝法）例 第 4步 根據(jù)精度和泛化能力對對規(guī)則進行排序 IF A=N THEN {18， 19， 20} IF A=Y AND B=N AND C=Y THEN + {9,10,11,12} IF C=N THEN – {6,7,8,13,14,15,16,17} IF A=Y THEN +{1,2,3,4,5} 盡管 {13， 14}仍然被錯分，但整個模型的精度提高了 決策樹研究 問題 主要內(nèi)容 決策樹基本概念 決策樹算法 決策樹研究問題 主要參考文獻 第 6章 決策樹 主要參考文獻 幾個數(shù)據(jù) 萬方數(shù)據(jù)庫中查詢涉及決策樹的學位論文； 時間跨度是 20232023； 查詢結(jié)果是 245篇（碩士論文居多） 按照以下三個領(lǐng)域分類： 1 利用決策樹解決實際問題； 2 利用決策樹與其它數(shù)據(jù)挖掘（機器學習）結(jié)合改進； 3 有關(guān)決策樹的改進方法。 約 600篇 約 400篇 非計算機領(lǐng)域占相當部分 計算機領(lǐng)域的主要期刊沒有 一篇 以研究與發(fā)展為例，前 100篇中有 4篇 初略估計 1000篇中有 40篇，平均每年 8篇，該期刊每年發(fā)表文章 360篇， 占比 8/360=%.研究與發(fā)展錄用率 約 810%。仍然 是碩士研究生可以加以研究的主要方向。特別是學?？蒲许椖慷鄶?shù)是研究項目，對海量數(shù)據(jù)集合的獲得 非常不容易。 像網(wǎng)絡(luò)日志、萬方數(shù)據(jù)、國外數(shù)據(jù)挖掘通用數(shù)據(jù)集合（一般都比較 ?。┑榷际俏覀兛梢岳玫臄?shù)據(jù)集合