決策樹資料專業(yè)知識講座

主要內容決策樹基本概念決策樹算法決策樹研究問題主要參照文獻第1頁第6章決策樹決策樹算法計數(shù)年紀收入學生信譽歸類：買計算機？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ù)，那么對于任意給定客人（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預測這位客人是屬于“買”計算機那一類，還是屬于“不買”計算機那一類？又：你需要多少有關這位客人信息才能回答這個問題？決策樹用途第2頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買誰在買計算機？年紀？學生？信譽？買青中老否是優(yōu)良不買買買不買決策樹用途決策樹算法第3頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買誰在買計算機？年紀？學生？信譽？買青中老否是優(yōu)良不買買買不買決策樹用途決策樹算法第4頁第6章決策樹決策樹算法決策樹表達決策樹基本組成部分：決策結點、分支和葉子。年紀？學生？信譽？買青中老否是優(yōu)良不買買買不買決策樹中最上面結點稱為根結點。是整個決策樹開始。每個分支是一個新決策結點，或者是樹葉子。每個決策結點代表一種問題或者決策.一般對應待分類對象屬性。每個葉結點代表一種也許分類成果在沿著決策樹從上到下遍歷過程中，在每個結點都有一種測試。對每個結點上問題不一樣測試輸出造成不一樣分枝，最后會達成一種葉子結點。這一過程就是利用決策樹進行分類過程，利用若干個變量來判斷屬性類別第5頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買決策樹算法第6頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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步計算決策屬性熵決策屬性“買計算機？”。該屬性分兩類：買/不買S1(買)=641S2（不買）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537決策樹算法第7頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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步計算條件屬性熵條件屬性共有4個。分別是年紀、收入、學生、信譽。分別計算不一樣屬性信息增益。決策樹算法第8頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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-1步計算年紀熵年紀共分三個組：青年、中年、老年青年買與不買百分比為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183決策樹算法第9頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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-2步計算年紀熵年紀共分三個組：青年、中年、老年中年買與不買百分比為256/0S1(買)=256S2（不買）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0決策樹算法第10頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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-3步計算年紀熵年紀共分三個組：青年、中年、老年老年買與不買百分比為257/127S1(買)=257S2（不買）=127S=S1+S2=384P1=257/384P2=127/384I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157決策樹算法第11頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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-4步計算年紀熵年紀共分三個組：青年、中年、老年所占百分比青年組384/1024=0.375中年組256/1024=0.25老年組384/1024=0.375計算年紀平均信息盼望E（年紀）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年紀信息增益）=0.9537-0.6877=0.2660（1）決策樹算法第12頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買第3步計算收入熵收入共分三個組：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)決策樹算法第13頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買第4步計算學生熵學生共分二個組：學生、非學生E（學生）=0.7811年紀信息增益=0.9537-0.7811=0.1726（3）決策樹算法第14頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買第5步計算信譽熵信譽分二個組：良好，優(yōu)秀E（信譽）=0.9048信譽信息增益=0.9537-0.9048=0.0453（4）決策樹算法第15頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買第6步計算選擇節(jié)點年紀信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年紀信息增益=0.9537-0.7811=0.1726（3）信譽信息增益=0.9537-0.9048=0.0453（4）決策樹算法第16頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年紀青年中年老年買/不買買買/不買葉子決策樹算法第17頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買青年買與不買百分比為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183決策樹算法第18頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買假如選擇收入作為節(jié)點分高、中、低條件熵就是E： E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591Gain就是計算信息增益I(0,128)=0百分比:128/384=0.3333I(64,128)=0.9183百分比:192/384=0.5I(64,0)=0百分比:64/384=0.1667注意決策樹算法第19頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？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)買年紀青年中年老年學生買信譽葉子否是優(yōu)良買不買買/不買買葉子葉子葉子決策樹算法第20頁第6章決策樹ID3決策樹建立算法1決定分類屬性；2對目前數(shù)據(jù)表，建立一種節(jié)點N3假如數(shù)據(jù)庫中數(shù)據(jù)都屬于同一種類，N就是樹葉，在樹葉上標出所屬類4假如數(shù)據(jù)表中沒有其他屬性能夠考慮，則N也是樹葉，按照少數(shù)服從多數(shù)標準在樹葉上標出所屬類別5不然，根據(jù)平均信息盼望值E或GAIN值選出一種最佳屬性作為節(jié)點N測試屬性6節(jié)點屬性選定后，對于該屬性中每個值：從N生成一種分支，并將數(shù)據(jù)表中與該分支有關數(shù)據(jù)搜集形成份支節(jié)點數(shù)據(jù)表，在表中刪除節(jié)點屬性那一欄假如分支數(shù)據(jù)表非空，則利用以上算法從該節(jié)點建立子樹。決策樹算法第21頁第6章決策樹決策樹數(shù)據(jù)準備姓名年紀收入學生信譽電話地址郵編買計算機張三234000是良281-322-03282714Ave.M77388買李四342800否優(yōu)713-239-78305606HollyCr78766買王二701900否優(yōu)281-242-32222023BellBlvd.70244不買趙五18900是良281-550-0544100MainStreet70244買劉蘭342500否優(yōu)713-239-7430606HollyCt78566買楊俊278900否優(yōu)281-355-7990233RiceBlvd.70388不買張毅389500否優(yōu)281-556-0544399SugarRd.78244買。。。。。。。。原始表決策樹算法第22頁第6章決策樹計數(shù)年紀收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買。。。整頓后數(shù)據(jù)表決策樹數(shù)據(jù)準備Datacleaning 刪除/減少noise，補填missingvaluesDatatransformation 數(shù)據(jù)標準化（datanormalization） 數(shù)據(jù)歸納（generalizedatatohigher-levelconceptsusingconcepthierarchies） 例如：年紀歸納為老、中、青三類 控制每個屬性也許值不超出七種（最佳不超出五種）Relevanceanalysis 對于與問題無關屬性：刪 對于屬性也許值大于七種又不能歸納屬性：刪決策樹算法第23頁第6章決策樹決策樹數(shù)據(jù)準備決策樹算法處理連續(xù)屬性值決策樹算法比較適合處理離散數(shù)值屬性。實際應用中屬性是連續(xù)或者離散情況都比較常見。在應用連續(xù)屬性值時，在一種樹結點能夠將屬性Ai值劃分為幾個區(qū)間。然后信息增益計算就能夠采取和離散值處理同樣辦法。標準上能夠將Ai屬性劃分為任意數(shù)目標空間。C4.5中采取是二元分割（BinarySplit）。需要找出一種合適分割閾值。參照C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem202314:1–37第24頁第6章決策樹決策樹算法ID3算法小結ID3算法是一種典型決策樹學習算法，由Quinlan于1979年提出。ID3算法基本思想是，以信息熵為度量，用于決策樹節(jié)點屬性選擇，每次優(yōu)先選用信息量最多屬性，亦即能使熵值變?yōu)樽钚傩裕詷嬙煲活w熵值下降最快決策樹，到葉子節(jié)點處熵值為0。此時，每個葉子節(jié)點對應實例集中實例屬于同一類。第25頁第6章決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（1）通過ID3算法來實現(xiàn)客戶流失預警分析，找出客戶流失特性，以幫助電信公司有針對性地改善客戶關系，避免客戶流失利用決策樹辦法進行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預處理、決策樹挖掘操作，模式評定和應用。電信運行商客戶流失有三方面含義：一是指客戶從一種電信運行商轉網(wǎng)到其他電信運行商，這是流失分析重點。二是指客戶月平均消費量減少，從高價值客戶成為低價值客戶。三、指客戶自然流失和被動流失。在客戶流失分析中有兩個關鍵變量：財務原因／非財務原因、積極流失／被動流失?？蛻袅魇軌驅譃樗姆N類型：其中非財務原因積極流失客戶往往是高價值客戶。他們會正常支付服務費用，并容易對市場活動有所響應。這種客戶是電信公司真正需要保住客戶。第26頁第6章決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（2）數(shù)據(jù)預處理數(shù)據(jù)挖掘處理對象是大量數(shù)據(jù)，這些數(shù)據(jù)一般存放在數(shù)據(jù)庫系統(tǒng)中（該顧客有關數(shù)據(jù)存放在其CRM中），是長期積累成果。但往往不適合直接挖掘，需要做數(shù)據(jù)預處理工作，一般包括數(shù)據(jù)選擇(選擇有關數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉換、歸約等。數(shù)據(jù)預處理工作準備是否充足，對于挖掘算法效率乃至正確性都有關鍵性影響。該公司通過數(shù)年電腦化管理，已有大量客戶個人基本信息(文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名顧客號碼、顧客標識、顧客身份證號碼(轉化為年紀)、在網(wǎng)時間（完工時間）、地址、職業(yè)、顧客類別、客戶流失（顧客狀態(tài)）等等，數(shù)據(jù)準備時必須除掉表中某些無須要屬性，一般可采取面向屬性歸納等辦法去掉不有關或弱有關屬性。第27頁第6章決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（3）屬性刪除：將有大量不一樣取值且無概化操作符屬性或者可用其它屬性來替代它較高層概念那些屬性刪除。例如客戶信息表中顧客標識、身份證號碼等，它們取值太多且無法在該取值域內找到概化操作符，應將其刪除，得到表1。

表1客戶信息表年紀學歷職業(yè)繳費方式在網(wǎng)時長費用變化率客戶流失58大學公務員托收1310%NO47高中工人營業(yè)廳繳費942%NO26碩士公務員充值卡263%YES28大學公務員營業(yè)廳繳費52.91%NO32初中工人營業(yè)廳繳費32.3%NO42高中無業(yè)人員充值卡2100%YES68初中無業(yè)人員營業(yè)廳繳費92.3%NO第28頁第6章決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（4）屬性概化：用屬性概化閾值控制技術沿屬性概念分層上卷或下鉆進行概化。文化程度分為3類：W1初中下列(含初中)，W2高中(含中專)，W3大學(專科、本科及以上)；職業(yè)類別：按工作性質來分共分3類：Z1一Z3；繳費方式：托收：T1,營業(yè)廳繳費：T2,充值卡：T3。連續(xù)型屬性概化為區(qū)間值：表中年紀、費用變化率和在網(wǎng)時間為連續(xù)型數(shù)據(jù)，由于建立決策樹時，用離散型數(shù)據(jù)進行處理速度最快，因此對連續(xù)型數(shù)據(jù)進行離散化處理，根據(jù)專家經(jīng)驗和實際計算信息增益，在“在網(wǎng)時長”屬性中，通過檢測每個劃分，得到在閾值為5年時信息增益最大，從而確定最佳劃分是在5年處，則這個屬性范圍就變?yōu)椋?lt;=5,>5：H1,H2｝。而在“年紀”屬性中，信息增益有兩個鋒值，分別在40和50處，因而該屬性范圍變?yōu)閧<=40,>40-<=50,>50}即變?yōu)閧青年，中年，老年：N1,N2,N3}；費用變化率：指（（當月話費－近3個月平均話費）/近3個月平均話費）×％>0，F(xiàn)1:<＝30%，F(xiàn)2：30%-99%,F3:＝100%變?yōu)椋鸉1,F2,F3｝。

第29頁表2轉化后客戶信息表年紀學歷職業(yè)繳費方式開戶時間費用變化率客戶流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NO第6章決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（5）第30頁YESNO年齡職業(yè)YES繳費方式YESYESNOYSESNONO在網(wǎng)時長NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2費用變化率第6章決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（6）在圖中，NO表達客戶不流失，YES表達客戶流失。從圖能夠看出，客戶費用變化率為100%客戶肯定已經(jīng)流失；而費用變化率低于30%客戶；即每個月資費相對穩(wěn)定客戶一般不會流失，費用變化率在30%～99%客戶有也許流失，其中年紀在40～50歲之間客戶流失也許性非常大，而年紀低于40歲客戶，用充值卡繳費客戶和在網(wǎng)時間較短客戶容易流失；年紀較大客戶，則工人容易流失。第31頁主要內容決策樹基本概念決策樹算法決策樹研究問題主要參照文獻第32頁第6章決策樹決策樹研究問題抱負決策樹有三種：(1)葉子結點數(shù)最少；(2)葉子結點深度最??；(3)葉子結點數(shù)最少且葉子結點深度最小。

然而，洪家榮等人已經(jīng)證明了要找到這種最優(yōu)決策樹是NP難題。因此，決策樹優(yōu)化目標就是要找到盡也許趨向于最優(yōu)決策樹。第33頁第6章決策樹有關過渡擬合上述決策樹算法增加樹每一種分支深度，直到正好能對訓練樣例比較完美地分類。實際應用中，當數(shù)據(jù)中有噪聲或訓練樣例數(shù)量太少以至于不能產(chǎn)生目標函數(shù)有代表性采樣時，該策略也許會遇到困難。在以上情況發(fā)生時，這個簡單算法產(chǎn)生樹會過渡擬合訓練樣例（過渡擬合：OverFitting）.決策樹研究問題第34頁有關過渡擬合第6章決策樹對于一種假設，當存在其他假設對訓練樣例擬合比它差，但事實上在實例整個分布上（包括訓練集合以外實例）體現(xiàn)得卻更加好時，則稱該假設過度擬合訓練樣例。過度擬合：給定一種假設空間H，一種假設h∈H，假如存在其它假設h1∈H,使得在訓練樣例上h錯誤率比h1小，但在整個實例公布上h1錯誤率比h小，則稱假設h過度擬合訓練數(shù)據(jù)過度擬合產(chǎn)生原因：噪聲，訓練樣例太小等決策樹研究問題第35頁有關過渡擬合第6章決策樹對學習算法是否成功真正測試是看它對于訓練中未見到數(shù)據(jù)執(zhí)行性能。訓練過程應當包括訓練樣本和驗證樣本。驗證樣本用于測試訓練后性能。假如驗證成果差，則需要考慮采取不一樣構造重新進行訓練，例如使用更大樣本集，或者變化從連續(xù)值到離散值得數(shù)據(jù)轉換等。一般應當建立一種驗證過程，在訓練最后完成后用來檢測訓練成果泛化能力。決策樹研究問題第36頁有關過渡擬合第6章決策樹分類模型誤差一般能夠將分類模型誤差分為：

1、訓練誤差（TrainingError）；2、泛化誤差（GeneralizationError）決策樹研究問題第37頁有關過渡擬合第6章決策樹分類模型誤差訓練誤差是在訓練統(tǒng)計上誤分類樣本百分比；泛化誤差是模型在未知統(tǒng)計上盼望誤差；一種好模型不但要能夠較好地擬合訓練數(shù)據(jù)，并且對未知樣本也要能夠精確地分類。一種好分類模型必須具有低訓練誤差和泛化誤差。由于一種具有低訓練誤差模型，其泛化誤差也許比具有較高訓練誤差模型高。（訓練誤差低，泛化誤差高，稱為過渡擬合）決策樹研究問題第38頁有關過渡擬合第6章決策樹模型過渡擬合潛在原因（1）噪聲造成過渡擬合；

錯誤類別值/類標簽，屬性值等（2）缺乏代表性樣本所造成過渡擬合

根據(jù)少許訓練統(tǒng)計作出分類決策模型容易受過渡擬合影響。由于訓練樣本缺乏代表性樣本，在沒有多少訓練統(tǒng)計情況下，學習算法仍然繼續(xù)細化模型就會造成過渡擬合。決策樹研究問題第39頁有關過渡擬合第6章決策樹模型過渡擬合潛在原因名稱體溫胎生4條腿冬眠哺乳動物蠑螈冷血NYYN虹鳉冷血YNNN鷹恒溫NNNN弱夜鷹恒溫NNYN鴨嘴獸恒溫YYYY哺乳動物分類訓練樣例體溫恒溫冷血冬眠NYNN4條腿YNNY名稱體溫胎生4條腿冬眠哺乳動物人恒溫YNNY大象恒溫YYNY鴿子恒溫NNNN哺乳動物分類訓練樣例按照訓練模型。人和大象都不是哺乳動物。決策樹作出這樣判斷是由于只有一種訓練樣例具有這些特點（鷹，恒溫，不冬眠）被劃分為非哺乳動物。該例清楚表白，當決策樹葉節(jié)點沒有足夠代表性時，也許會預測錯誤。決策樹研究問題第40頁有關過渡擬合第6章決策樹處理過度擬合伎倆：1及早停頓樹增加；2后修剪法。決策樹研究問題第41頁有關過渡擬合第6章決策樹1及早停頓樹增加

由于決策樹學習要從候選集合眾選擇滿足給定標準最大化屬性，并且不回溯，也就是我們常說爬山策略，其選擇往往會是局部最優(yōu)而不是全局最優(yōu)。樹構造越復雜，則過渡擬合發(fā)生也許性越大。因此，要選擇簡單模型。Occan法則（又稱Occan剃刀OccanRazor）:具有相同泛化誤差兩個模型，較簡單模型比復雜模型更可取。決策樹研究問題第42頁有關過渡擬合第6章決策樹后修剪法（后剪枝法）

在訓練過程中允許對數(shù)據(jù)過渡擬合，然后再對樹進行修剪該辦法稱為后剪枝法。決策樹研究問題第43頁有關過渡擬合第6章決策樹后修剪法（后剪枝法）例AB負C正正負YYYNNN一棵通過訓練集合學好決策樹決策樹研究問題第44頁有關過渡擬合第6章決策樹后修剪法（后剪枝法）例AB負C正正負YYYNNN實例ABC類別錯分類1YYY+2YYY+3YYY+4YYY+5YYY+6YYN-*7YYN-*8YYN-*9YNY+10YNY+11YNY+12YNY+13YNN+*14YNN+*15YNN-16YNN-17YNN-18NNN-19NYN-20NYY-對以上決策樹通過右側驗證集合進行測試，發(fā)覺其有5個錯分類。決策樹研究問題第45頁有關過渡擬合第6章決策樹后修剪法（后剪枝法）例AB負C正正負YYYNNN{18，19，20}{1，2，3，45，6，7，8}{9，10，11，12}{13，14，15，16，17}錯分類5個，6，7，8，13，14決策樹研究問題第46頁有關過渡擬合第6章決策樹后修剪法（后剪枝法）例第1步將決策樹規(guī)則化規(guī)則1IFA=YANDB=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

AB負C正正負YYYNNN決策樹研究問題第47頁有關過渡擬合第6章決策樹后修剪法（后剪枝法）例規(guī)則1IFA=YANDB=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

規(guī)則分類正確數(shù)目分類錯誤數(shù)目精度1535/82404/43323/54303/3第2步規(guī)則精度計算決策樹研究問題第48頁規(guī)則2與規(guī)則4精度為100%，保存有關過渡擬合第6章決策樹后修剪法（后剪枝法）例規(guī)則分類正確數(shù)目分類錯誤數(shù)目精度1535/82404/43323/54303