分類和預(yù)測決策樹

第四章分類和預(yù)測主講教師：魏宏喜(博士，副教授)2第四章分類和預(yù)測4.1分類和預(yù)測的定義4.2數(shù)據(jù)分類方法決策樹神經(jīng)網(wǎng)絡(luò)SVM貝葉斯網(wǎng)絡(luò)4.3數(shù)據(jù)預(yù)測方法線性回歸非線性回歸3第四章分類和預(yù)測4.1分類和預(yù)測的定義4.2數(shù)據(jù)分類方法決策樹神經(jīng)網(wǎng)絡(luò)SVM貝葉斯網(wǎng)絡(luò)4.3數(shù)據(jù)預(yù)測方法線性回歸非線性回歸44.1分類和預(yù)測的定義分類（Classification）給定一個數(shù)據(jù)集D={t1,t2,…,tn}和一個類別集合C={C1,C2,…,Cm}，數(shù)據(jù)分類就是通過定義一個映射f:DC，為數(shù)據(jù)集D中的每條數(shù)據(jù)ti分配C中的一個類Cj。預(yù)測（Prediction）它是一種分類的泛化，當(dāng)分類的類別是一個連續(xù)值時（可看成無限多類），就是數(shù)據(jù)預(yù)測。54.1分類和預(yù)測的定義——示例分類銀行貸款員需要分析數(shù)據(jù)，來弄清哪些貸款申請者是安全的，哪些是有風(fēng)險的。構(gòu)造一個映射（模型）將申請者分為兩類：安全有風(fēng)險預(yù)測銀行貸款員需要分析數(shù)據(jù)，來預(yù)測貸給某個顧客多少錢是安全的。構(gòu)造一個映射（模型）來預(yù)測一個連續(xù)值。如何建立具體的映射（模型）？64.1分類和預(yù)測的定義數(shù)據(jù)分類和預(yù)測的步驟如下：第一步——建立模型第二步——使用模型下面以分類為例，詳細(xì)介紹這兩個步驟。74.1分類和預(yù)測的定義第一步——建立模型訓(xùn)練數(shù)據(jù)集：由若干數(shù)據(jù)（通常用n維屬性向量表示）和它們相對應(yīng)的類標(biāo)號組成。訓(xùn)練樣本：訓(xùn)練數(shù)據(jù)集中的單個數(shù)據(jù)及其類標(biāo)號。從訓(xùn)練數(shù)據(jù)集“學(xué)習(xí)”相關(guān)知識來構(gòu)造分類模型。分類模型可能會以分類規(guī)則、決策樹或數(shù)學(xué)公式等形式呈現(xiàn)出來。第二步——使用模型對未知類別的數(shù)據(jù)進行分類（分配類別標(biāo)號）。8第一步——建立模型訓(xùn)練數(shù)據(jù)集分類模型IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規(guī)則9第二步——使用模型分類規(guī)則測試數(shù)據(jù)集未知數(shù)據(jù)(Jeff,Professor,4)Tenured?10第四章分類和預(yù)測4.1分類和預(yù)測的定義4.2數(shù)據(jù)分類方法決策樹神經(jīng)網(wǎng)絡(luò)SVM貝葉斯網(wǎng)絡(luò)4.3數(shù)據(jù)預(yù)測方法線性回歸非線性回歸114.2數(shù)據(jù)據(jù)分分類類方方法法分類類過過程程的的數(shù)數(shù)據(jù)據(jù)預(yù)預(yù)處處理理分類類的的評評價價標(biāo)標(biāo)準(zhǔn)準(zhǔn)————性性能能度度量量12分類類過過程程的的數(shù)數(shù)據(jù)據(jù)預(yù)預(yù)處處理理在執(zhí)執(zhí)行行分分類類過過程程之之前前，，通通過過對對數(shù)數(shù)據(jù)據(jù)進進行行預(yù)預(yù)處處理理，，可可以以提提高高分分類類過過程程的的準(zhǔn)確確性性、有效效性性和可伸伸縮縮性性。常用的預(yù)處處理操作包包括：數(shù)據(jù)清理相關(guān)分析數(shù)據(jù)變換13分類過程的的數(shù)據(jù)預(yù)處處理在執(zhí)行分類類過程之前前，通過對對數(shù)據(jù)進行行預(yù)處理，，可以提高高分類過程程的準(zhǔn)確性、有效性和可伸縮性。常用的預(yù)處處理操作包包括：數(shù)據(jù)清理：消除或減減少噪聲，，處理空缺缺值，從而而減少學(xué)習(xí)習(xí)時的混亂亂。相關(guān)分析數(shù)據(jù)變換14分類過程的的數(shù)據(jù)預(yù)處處理在執(zhí)行分類類過程之前前，通過對對數(shù)據(jù)進行行預(yù)處理，，可以提高高分類過程程的準(zhǔn)確性、有效性和可伸縮性。常用的預(yù)處處理操作包包括：數(shù)據(jù)清理相關(guān)分析：數(shù)據(jù)中的的有些屬性性可能與當(dāng)當(dāng)前任務(wù)不不相關(guān)或者者是冗余的的，則可以以刪除這些些屬性以加加快學(xué)習(xí)過過程，并使使學(xué)習(xí)結(jié)果果更精確。。例如：主成成分分析（（PCA）數(shù)據(jù)變換15分類過程的的數(shù)據(jù)預(yù)處處理在執(zhí)行分類類過程之前前，通過對對數(shù)據(jù)進行行預(yù)處理，，可以提高高分類過程程的準(zhǔn)確性、有效性和可伸縮性。常用的預(yù)處處理操作包包括：數(shù)據(jù)清理相關(guān)分析數(shù)據(jù)變換：數(shù)據(jù)可以以通過規(guī)范范化，將給給定屬性的的所有值按按比例進行行縮放，使使其落入一一個較小的的指定區(qū)間間中。例如：[0.0,1.0]（神經(jīng)網(wǎng)絡(luò)絡(luò)中常用））。16分類過程的的數(shù)據(jù)預(yù)處處理在執(zhí)行分類類過程之前前，通過對對數(shù)據(jù)進行行預(yù)處理，，可以提高高分類過程程的準(zhǔn)確性、有效性和可伸縮性。常用的預(yù)處處理操作包包括：數(shù)據(jù)清理相關(guān)分析數(shù)據(jù)變換在模式識別別領(lǐng)域特征提取與與特征選擇17分類的評價價標(biāo)準(zhǔn)假設(shè)：給定定測試集Xtest={(xi,yi)|i=1,2,……,N}N表示測試集集中的樣本本個數(shù)；xi表示測試集集中第i個樣本；yi表示樣本xi的類標(biāo)號。。對于測試集集的第j個類別，分分類結(jié)果如如下：被正確分類類的樣本數(shù)數(shù)量為TPj；被錯誤分類類的樣本數(shù)數(shù)量為FNj；其他類別被被錯誤分類類為該類的的樣本數(shù)據(jù)據(jù)量為FPj。18分類的評價價標(biāo)準(zhǔn)精確度（正正確率）：表示測試試集中被正正確分類的的數(shù)據(jù)所占占的比例。。例如：在文文字識別中中，經(jīng)常統(tǒng)統(tǒng)計識別正確率率，以此來表表示識別系系統(tǒng)的性能能。19第四章分分類和預(yù)測測4.1分類和預(yù)測測的定義4.2數(shù)據(jù)分類方方法決策樹神經(jīng)網(wǎng)絡(luò)SVM貝葉斯網(wǎng)絡(luò)絡(luò)4.3數(shù)據(jù)預(yù)測方方法線性回歸非線性回歸歸20決策樹什么是決策策樹？由數(shù)據(jù)的不同屬性逐次劃分?jǐn)?shù)數(shù)據(jù)集，直直至得到的的數(shù)據(jù)子集只包含同一一類數(shù)據(jù)為為止，這樣樣可形成一一棵樹，稱稱為決策樹樹。結(jié)構(gòu)上類似似于程序流流程圖；每個內(nèi)部結(jié)結(jié)點表示在在一個屬性性上的測試；每個分枝代代表一個測測試的輸出；每個葉結(jié)點點存放一個個類標(biāo)號。由樹的根結(jié)結(jié)點到某個個葉結(jié)點的的屬性的合取可形成一條條分類規(guī)則則；所有規(guī)規(guī)則的析取可形成一整整套分類規(guī)規(guī)則。21決策樹生成目標(biāo)：根據(jù)據(jù)客戶的如如下屬性，，是否有貸款款、婚姻狀況、收入水平，來判斷客客戶是否存存在“金融融欺騙”行行為。如何從訓(xùn)練數(shù)據(jù)集生成相應(yīng)決策樹，是本節(jié)所關(guān)注的內(nèi)容。22決策樹———分類過程程23決策樹———分類過程程24決策樹———分類過程程25決策樹———分類過程程26決策樹———分類過程程27決策樹———分類過程程28決策樹———屬性選擇擇的次序問問題哪棵樹更好好？or哪種次序更更好？29決策樹決策樹關(guān)注注的主要問問題：決策樹的生生成算法ID3算法C4.5算法決策樹的剪剪枝策略：：許多分枝枝反映的是是訓(xùn)練數(shù)據(jù)據(jù)集中的噪噪聲和離群群點，剪枝枝試圖識別別并剪去這這種分枝，，以提高對對未知數(shù)據(jù)據(jù)分類的準(zhǔn)準(zhǔn)確性。先剪枝方法法后剪枝方法法30ID3算法法特點：在選選擇根結(jié)點點和各個內(nèi)內(nèi)部結(jié)點的的分枝屬性性時，采用用信息增益作為度量標(biāo)標(biāo)準(zhǔn)，因因此每次都都會選擇具具有最高信息增增益的屬性作為為分枝屬性性。ID3算法只能處處理屬性值值為離散型的數(shù)據(jù)集的的劃分。31ID3算法法給定數(shù)據(jù)集集X={(xi,yi)|i=1,2,……,total}。xi(i=1,2,...,total)用d維特征向量量xi=(xi1,xi2,...,xid)來表示，xi1,xi2,...,xid分別對應(yīng)d個屬性A1,A2,...,Ad的具體取值值；yi(i=1,2,...,total)表示樣本xi的類標(biāo)號，，假設(shè)要研研究的分類類問題有m個類別，則則yi∈{c1,c2,...,cm}。假設(shè)nj是數(shù)據(jù)集X中屬于類別別cj的樣本數(shù)量量，則各類類別的先驗概率為：對于數(shù)據(jù)集集X，將其分為為m類的期望信息為：32ID3算法法計算屬性Af劃分?jǐn)?shù)據(jù)集集X所得的熵：假設(shè)Af有q個不同取值值，可按q的不同取值值將X劃分為q個不同的子子集{X1,X2,…,Xs,…,Xq}；假設(shè)ns表示Xs中的樣本本數(shù)量，，njs表示Xs中屬于類類別cj的樣本數(shù)數(shù)量，則則由屬性性Af劃分?jǐn)?shù)據(jù)據(jù)集X的熵為：：其中：33ID3算算法計算屬性性Af劃分?jǐn)?shù)據(jù)據(jù)集時的的信息增益益：屬性的信信息增益益值越大大，表示示它的區(qū)區(qū)分度就就越高，，使用該該屬性進進行分類類的效果果就越好好。ID3算法是通通過選擇擇具有最高信息息增益的屬性作作為數(shù)據(jù)據(jù)集的劃劃分，從從而可創(chuàng)創(chuàng)建決策策樹中的的一個結(jié)結(jié)點，根根據(jù)該屬屬性的不不同取值值可形成成該結(jié)點點的不同同分枝。。再對各分分枝中的的數(shù)據(jù)子子集進行行遞歸劃分分，直至形形成葉結(jié)結(jié)點或者者某分枝枝上的所所有數(shù)據(jù)據(jù)不屬于于同一類類別，但但又沒有有剩余的的屬性可可以進一一步劃分分為止。。34ageincomestudentcredit_ratingbuy_computeryouthhighnofairnoyouthhighnoexcellentnomiddle_agedhighnofairyesseniormediumnofairyesseniorlowyesfairyesseniorlowyesexcellentnomiddle_agedlowyesexcellentyesyouthmediumnofairnoyouthlowyesfairyesseniormediumyesfairyesyouthmediumyesexcellentyesmiddle_agedmediumnoexcellentyesmiddle_agedhighyesfairyesseniormediumnoexcellentnoID3算法——示例（buy_computer）35ID3算法——示例（buy_computer）首先，計計算數(shù)據(jù)據(jù)集分類類所需的的期望信信息：在數(shù)據(jù)集集中，給給定的樣樣本數(shù)量量為14，類標(biāo)號號為Yes(表示購買買電腦)的樣本數(shù)數(shù)量為n1=9，類標(biāo)號號為No(表示不購購買電腦腦)的樣本數(shù)數(shù)量為n2=5，因此數(shù)數(shù)據(jù)集中中兩個類類別的先先驗概率率分別為為：p(Yes)=n1/total=9/14p(No)=n2/total=5/14對數(shù)據(jù)集集分類所所需的期期望信息息為：Info(n1,n2)=-p(Yes)*log(p(Yes))-p(No)*log(p(No))=-9/14*log(9/14)-5/14*log(5/14)≈0.9436ID3算法——示例（buy_computer）其次，計計算各屬屬性劃分分?jǐn)?shù)據(jù)集集時的信信息增益益：先計算屬屬性age的熵。由由于屬性性age有三個不不同取值值（youth，middle_aged，senior），因此此可將數(shù)數(shù)據(jù)集劃劃分成三三個子集集：X1,X2和X3。對于子集集X1(age=youth)，它的樣樣本數(shù)量量為n1=5，其中類類標(biāo)號為為Yes的數(shù)量n11=2，類標(biāo)號號為No的數(shù)量n12=3，則這兩兩類樣本本在子集集X1中所占的的比例分分別為：：p11=n11/n1=2/5=0.4p12=n12/n1=3/5=0.6這樣，子子集X1的期望信信息為：：Info(n11,n12)=-p11*log(p11)-p12*log(p12)=-0.4*log(0.4)-0.6*log(0.6)37ID3算法法———示例例（（buy_computer）其次次，，計計算算各各屬屬性性劃劃分分?jǐn)?shù)數(shù)據(jù)據(jù)集集時時的的信信息息增增益益：：先計計算算屬屬性性age的熵熵。。由由于于屬屬性性age有三三個個不不同同取取值值（（youth，middle_aged，senior），，因因此此可可將將數(shù)數(shù)據(jù)據(jù)集集劃劃分分成成三三個個子子集集：：X1,X2和X3。對于于子子集集X2(age=middle_aged)，它它的的樣樣本本數(shù)數(shù)量量為為n2=4，其其中中類類標(biāo)標(biāo)號號為為Yes的數(shù)數(shù)量量n12=4，類類標(biāo)標(biāo)號號為為No的數(shù)數(shù)量量n22=0，則則這這兩兩類類樣樣本本在在子子集集X2中所所占占的的比比例例分分別別為為：：p21=n12/n2=4/4=1p22=n22/n2=0/4=0這樣樣，，子子集集X2的期期望望信信息息為為：：Info(n12,n22)=-p12*log(p12)-p22*log(p22)=038ID3算法法———示例例（（buy_computer）其次次，，計計算算各各屬屬性性劃劃分分?jǐn)?shù)數(shù)據(jù)據(jù)集集時時的的信信息息增增益益：：先計計算算屬屬性性age的熵熵。。由由于于屬屬性性age有三三個個不不同同取取值值（（youth，middle_aged，senior），，因因此此可可將將數(shù)數(shù)據(jù)據(jù)集集劃劃分分成成三三個個子子集集：：X1,X2和X3。對于于子子集集X3(age=senior)，它它的的樣樣本本數(shù)數(shù)量量為為n3=5，其其中中類類標(biāo)標(biāo)號號為為Yes的數(shù)數(shù)量量n13=3，類類標(biāo)標(biāo)號號為為No的數(shù)數(shù)量量n23=2，則則這這兩兩類類樣樣本本在在子子集集X3中所占的的比例分分別為：：p13=n13/n3=3/5=0.6p23=n23/n3=2/5=0.4這樣，子子集X3的期望信信息為：：Info(n13,n23)=-p13*log(p13)-p23*log(p23)=-0.6*log(0.6)-0.4*log(0.4)39ID3算法——示例（buy_computer）其次，計計算各屬屬性劃分分?jǐn)?shù)據(jù)集集時的信信息增益益：先計算屬屬性age的熵。由由于屬性性age有三個不不同取值值（youth，middle_aged，senior），因此此可將數(shù)數(shù)據(jù)集劃劃分成三三個子集集：X1,X2和X3。由于子集集X1,X2和X3各自的期期望信息息分別為為Info(n11,n12)，Info(n12,n22)和Info(n13,n23)，因此，，屬性age劃分?jǐn)?shù)據(jù)據(jù)集的熵熵為：E(age)=5/14*Info(n11,n12)+4/14*Info(n12,n22)+5/14*Info(n13,n23)≈0.694計算屬性性age的信息增增益為：：Gain(age)=Info(Yes,No)––E(age)=0.94–0.694=0.24640ID3算法——示例（buy_computer）其次，計計算各屬屬性劃分分?jǐn)?shù)據(jù)集集時的信信息增益益：按上述方方式，可可依次計計算其他他屬性的的信息增增益分別別為：Gain(income)=0.029Gain(student)=0.151Gain(credit_rating)=0.048在4個屬性中中，age的信息增增益最大大(0.246)，因此先先以該屬屬性來劃劃分?jǐn)?shù)據(jù)據(jù)集。41ID3算法——示例（buy_computer）42ID3算算法ID3算法的優(yōu)點：ID3算法通常常只需要要測試一一部分屬屬性就可可完成對對訓(xùn)練數(shù)數(shù)據(jù)集的的分類。。從ID3算法構(gòu)建建的決策策樹中，，很容易易獲得相相應(yīng)的決決策規(guī)則則。43ID3算算法ID3算法的缺點：ID3算法在選選擇根節(jié)節(jié)點和內(nèi)內(nèi)部結(jié)點點的屬性性時，使使用信息息增益作作為評價價標(biāo)準(zhǔn)。。信息增益益更傾向向于選擇擇取值種種類較多多的屬性性進行劃劃分，而而不一定定是最優(yōu)屬性性進行劃分分。ID3算法只能能對屬性性值為離離散型的的數(shù)據(jù)集集進行劃劃分（構(gòu)構(gòu)建決策策樹），，不能處處理屬性性值為連連續(xù)型的的數(shù)據(jù)集集。44C4.5算法C4.5算法使用用信息增益益比來確定分分枝屬性性，能夠夠克服ID3算法使用用信息增增益時偏偏向于取取值類型型較多屬屬性的不不足。屬性Af的信息增益益比的定義為為：其中：當(dāng)q的值較大時，就會降低信息增益比。45C4.5算法C4.5算法既可可以處理理離散型型描述屬屬性，也也可以處處理連續(xù)續(xù)型描述述屬性。。當(dāng)處理離離散型屬屬性時，，C4.5算法與ID3算法相同同；當(dāng)處理連連續(xù)型屬屬性時，，C4.5算法需要要先將連連續(xù)型屬屬性轉(zhuǎn)換換成離散散型屬性性。46C4.5算法C4.5算法既可可以處理理離散型型描述屬屬性，也也可以處處理連續(xù)續(xù)型描述述屬性。。當(dāng)處理離離散型屬屬性時，，C4.5算法與ID3算法相同同；當(dāng)處理連連續(xù)型屬屬性時，，C4.5算法需要要先將連連續(xù)型屬屬性轉(zhuǎn)換換成離散散型屬性性。對于連續(xù)續(xù)值屬性性Ac，假設(shè)在在某個結(jié)結(jié)點上的的樣本數(shù)數(shù)量為total，則C4.5算法將進進行如下下操作：：(1)將該結(jié)點點上的所所有樣本本按照屬屬性的取取值由小到大大排序，得得到排序序結(jié)果{A1c,A2c,...,Atotalc}；47C4.5算法C4.5算法既可可以處理理離散型型描述屬屬性，也也可以處處理連續(xù)續(xù)型描述述屬性。。當(dāng)處理離離散型屬屬性時，，C4.5算法與ID3算法相同同；當(dāng)處理連連續(xù)型屬屬性時，，C4.5算法需要要先將連連續(xù)型屬屬性轉(zhuǎn)換換成離散散型屬性性。對于連續(xù)續(xù)值屬性性Ac，假設(shè)在在某個結(jié)結(jié)點上的的樣本數(shù)數(shù)量為total，則C4.5算法將進進行如下下操作：：(2)在{A1c,A2c,...,Atotalc}中生成total-1個分割點點其中：第第i個(1≤i≤total-1)分割點的的取值設(shè)設(shè)置為vi=(Aic+A(i+1)c)/2。48C4.5算法C4.5算法既可可以處理理離散型型描述屬屬性，也也可以處處理連續(xù)續(xù)型描述述屬性。。當(dāng)處理離離散型屬屬性時，，C4.5算法與ID3算法相同同；當(dāng)處理連連續(xù)型屬屬性時，，C4.5算法需要要先將連連續(xù)型屬屬性轉(zhuǎn)換換成離散散型屬性性。對于連續(xù)續(xù)值屬性性Ac，假設(shè)在在某個結(jié)結(jié)點上的的樣本數(shù)數(shù)量為total，則C4.5算法將進進行如下下操作：：(3)從total-1個分割點點中選擇擇最佳分分割點。。其中：最最佳分割割點具有有最大信息息增益比比。49C4.5算法———離散散化示例例將“buy_computer””中的屬性性age的取值由由{youth,middle_aged,senior}改為具體體年齡{32,25,46,56,60,52,42,36,23,51,38,43,41,65}，C4.5算法離散散化的具具體過程程。(1)對年齡序序列由小小到大排排序，新新的序列列為{23,25,32,36,38,41,42,43,46,51,52,56,60,65}；(2)對新的年年齡序列列生成分分割點：：由于樣樣本數(shù)量量為14，因此可可生成13個分割點點。例如：第第一個分分割點為為(23+25)/2=24，它可將將數(shù)據(jù)集集劃分為為年齡在在區(qū)間[23,24]的樣本和和在