第4講數(shù)據(jù)分類-決策樹和科學(xué)決策與信息分析

第4講數(shù)據(jù)分類-決策樹目錄基本概念決策樹ID3算法決策樹C4.5算法2本周學(xué)習(xí)目標(biāo)1.掌握數(shù)據(jù)分類的基本原理和評(píng)價(jià)指標(biāo)2.了解兩種決策樹算法34PartI數(shù)據(jù)分類的基本概念定義數(shù)據(jù)分類是指把數(shù)據(jù)樣本映射到一個(gè)事先定義的類中的學(xué)習(xí)過(guò)程即給定一組輸入的屬性向量及其對(duì)應(yīng)的類，用基于歸納的學(xué)習(xí)算法得出分類分類問(wèn)題是數(shù)據(jù)挖掘領(lǐng)域中研究和應(yīng)用最為廣泛的技術(shù)之一，如何更精確、更有效地分類一直是人們追求的目標(biāo)數(shù)據(jù)分類的任務(wù)通過(guò)學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)f，把每個(gè)屬性集x映射到一個(gè)預(yù)先定義的類標(biāo)號(hào)y5分類的示例兩類分類示例銀行業(yè)：區(qū)分高端信用卡和低端信用卡醫(yī)療診斷：區(qū)分正常細(xì)胞和癌細(xì)胞互聯(lián)網(wǎng)：區(qū)分正常郵件和垃圾郵件多類分類示例油氣傳輸：區(qū)分行人走過(guò)、汽車碾過(guò)、鎬刨、電鉆等行為文字識(shí)別：區(qū)分不同的字符（其中漢字識(shí)別是一個(gè)大類別問(wèn)題）社會(huì)網(wǎng)絡(luò)：區(qū)分中心用戶、活躍用戶、不活躍用戶、馬甲用戶等6示例數(shù)據(jù)集數(shù)據(jù)集包含多個(gè)描述屬性和一個(gè)類別屬性一般來(lái)說(shuō)描述屬性：連續(xù)值或離散值類別屬性：只能是離散值（目標(biāo)屬性連續(xù)對(duì)應(yīng)回歸問(wèn)題）7AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1..................分類問(wèn)題的形式化描述8分類的過(guò)程9獲取數(shù)據(jù)預(yù)處理分類決策分類器設(shè)計(jì)獲取數(shù)據(jù)數(shù)值型數(shù)據(jù)病例中的各種化驗(yàn)數(shù)據(jù)空氣質(zhì)量監(jiān)測(cè)數(shù)據(jù)描述性數(shù)據(jù)人事部門檔案資料圖片型數(shù)據(jù)指紋、掌紋自然場(chǎng)景圖片很多情況下，需要將上述數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為數(shù)值型數(shù)據(jù)序列，即形成特征向量（特征提?。?0預(yù)處理為了提高分類的準(zhǔn)確性和有效性，需要對(duì)分類所用的數(shù)據(jù)進(jìn)行預(yù)處理去除噪聲數(shù)據(jù)對(duì)空缺值進(jìn)行處理數(shù)據(jù)降維（特征選擇）--（PCA、LDA）11分類器設(shè)計(jì)1-劃分?jǐn)?shù)據(jù)集給定帶有類標(biāo)號(hào)的數(shù)據(jù)集，并且將數(shù)據(jù)集劃分為兩個(gè)部分訓(xùn)練集（trainingset）測(cè)試集（testingset）劃分策略隨機(jī)抽取法2/1<訓(xùn)練集/測(cè)試集<8/1十交叉驗(yàn)證法（10-foldvalidation）將數(shù)據(jù)集隨機(jī)地劃分為10組之后執(zhí)行10次循環(huán)，在第i次循環(huán)中，將第i組數(shù)據(jù)樣本作為測(cè)試集，其余的9組數(shù)據(jù)樣本作為訓(xùn)練集12分類器設(shè)計(jì)2-分類器構(gòu)造利用訓(xùn)練集構(gòu)造分類器（分類模型）通過(guò)分析由屬性描述的每類樣本的數(shù)據(jù)信息，從中總結(jié)出分類的規(guī)律性，建立判別公式或判別規(guī)則在分類器構(gòu)造過(guò)程中，由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號(hào)，這一步也稱作監(jiān)督學(xué)習(xí)（supervisedlearning）13分類器設(shè)計(jì)3-分類器測(cè)試?yán)脺y(cè)試集對(duì)分類器的分類性能進(jìn)行評(píng)估，具體方式是首先，利用分類器對(duì)測(cè)試集中的每一個(gè)樣本進(jìn)行分類其次，將分類得到的類標(biāo)號(hào)和測(cè)試集中數(shù)據(jù)樣本的原始類標(biāo)號(hào)進(jìn)行對(duì)比由上述過(guò)程得到分類器的分類性能（如何評(píng)價(jià)？）14分類決策在構(gòu)造成功分類器之后（通過(guò)測(cè)試），則可以利用該分類器實(shí)際執(zhí)行分類15分類的評(píng)價(jià)準(zhǔn)則-約定和假設(shè)16分類的評(píng)價(jià)準(zhǔn)則-指標(biāo)1精確度（accuracy）是最常用的評(píng)價(jià)準(zhǔn)則代表測(cè)試集中被正確分類的數(shù)據(jù)樣本所占的比例反映了分類器對(duì)于數(shù)據(jù)集的整體分類性能17分類的評(píng)價(jià)準(zhǔn)則-指標(biāo)2查全率（recall）第j個(gè)類別的查全率（召回率）表示在本類樣本中，被正確分類的樣本占的比例代表該類別的分類精度18分類的評(píng)價(jià)準(zhǔn)則-指標(biāo)3查準(zhǔn)率（precision）第j個(gè)類別的查準(zhǔn)率表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例代表該類別的分類純度19分類的評(píng)價(jià)準(zhǔn)則-指標(biāo)4F-measure可以比較合理地評(píng)價(jià)分類器對(duì)每一類樣本的分類性能它是查全率和查準(zhǔn)率的組合表達(dá)式其中參數(shù)β是可以調(diào)節(jié)的，通常取值為120分類的評(píng)價(jià)準(zhǔn)則-指標(biāo)5幾何均值（G-mean）它能合理地評(píng)價(jià)數(shù)據(jù)集的整體分類性能是各個(gè)類別查全率的平方根，當(dāng)各個(gè)類別的查全率都大時(shí)才增大同時(shí)兼顧了各個(gè)類別的分類精度21延伸閱讀Jin-MaoWei,Xiao-JieYuan,etal.Anovelmeasureforevaluatingclassifiers,ExpertSystemswithApplications,37(2023):3799-380922關(guān)于數(shù)據(jù)分類的小結(jié)所謂分類即是使用某種分類模型，以對(duì)象的若干維描述屬性為輸入，經(jīng)過(guò)計(jì)算輸出該對(duì)象所屬類別的過(guò)程數(shù)據(jù)分類的兩個(gè)關(guān)鍵步驟是分類器訓(xùn)練：選定合適的分類模型及參數(shù)分類器測(cè)試：利用合適的指標(biāo)檢驗(yàn)分類器有效性目前已有一些成熟的分類器可供使用決策樹支持向量機(jī)最近鄰/k-近鄰2324PartII決策樹ID3算法決策樹是一種以給定的數(shù)據(jù)樣本為基礎(chǔ)的歸納學(xué)習(xí)方法在給定已知類標(biāo)號(hào)的數(shù)據(jù)集的情況下，采用自頂向下的遞歸方式來(lái)產(chǎn)生一個(gè)類似于流程圖的樹結(jié)構(gòu)樹的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)最底層節(jié)點(diǎn)是葉節(jié)點(diǎn)：代表樣本的類別根節(jié)點(diǎn)和葉節(jié)點(diǎn)之間的節(jié)點(diǎn)是內(nèi)部節(jié)點(diǎn)決策樹方法在根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)上根據(jù)給定的度量標(biāo)準(zhǔn)來(lái)選擇最適合的描述屬性作為分支屬性并根據(jù)該屬性的不同取值向下建立分支25決策樹示例-購(gòu)買保險(xiǎn)26A1-公司職員A2-年齡A3-收入A4-信譽(yù)度C-買保險(xiǎn)否<=40高良c2否<=40高優(yōu)c2否41~50高良c1否>50中良c1是>50低良c1是>50低優(yōu)c2是41~50低優(yōu)c1否<=40中良c2是<=40低良c1是>50中良c1是<=40中優(yōu)c1否41~50中優(yōu)c1是41~50高良c1否>50中優(yōu)c2保險(xiǎn)決策樹解決了哪類人更傾向于購(gòu)買保險(xiǎn)的問(wèn)題27年齡信譽(yù)度公司職員c1c1c2c1c2<=4041~50>50是否良優(yōu)決策樹向程序語(yǔ)言的轉(zhuǎn)化if(年齡<=40&&是公司職員)

買保險(xiǎn)if(年齡<=40&&不是公司職員)

不買保險(xiǎn)if(年齡介于41~50之間)

買保險(xiǎn)if(年齡>50&&信譽(yù)度為良)

買保險(xiǎn)if(年齡>50&&信譽(yù)度為優(yōu))

不買保險(xiǎn)28ID3算法的原理核心思想在選擇根節(jié)點(diǎn)和各個(gè)內(nèi)部節(jié)點(diǎn)上的分支屬性時(shí)，采用信息增益（informationgain）作為度量標(biāo)準(zhǔn)特別說(shuō)明創(chuàng)建根節(jié)點(diǎn)時(shí)，X是最初給定的所有數(shù)據(jù)創(chuàng)建內(nèi)部節(jié)點(diǎn)時(shí)，X是上層節(jié)點(diǎn)的某個(gè)分支對(duì)應(yīng)的數(shù)據(jù)集29ID3算法的原理期望信息30什么情況下信息量更大？分布更平均？vs

分布更極端？分布更集中？VS分布更疏散？ID3算法的原理熵熵值E(Af)越小，表示屬性Af對(duì)數(shù)據(jù)集劃分的純度越高31ID3算法的原理信息增益32ID3算法原理選擇具有較高信息增益的描述屬性作為給定數(shù)據(jù)集X的分支屬性，從而創(chuàng)建決策樹中的一個(gè)節(jié)點(diǎn)根據(jù)該描述屬性的不同取值再創(chuàng)建分支之后對(duì)各個(gè)分支中的樣本子集遞歸調(diào)用上述方法建立下一級(jí)子節(jié)點(diǎn)當(dāng)某個(gè)分支上的所有數(shù)據(jù)樣本都屬于同一個(gè)類別時(shí)劃分停止，形成葉節(jié)點(diǎn)或者當(dāng)某個(gè)分支上的樣本不屬于同一個(gè)類別，但是又沒有剩余的描述屬性可以進(jìn)一步劃分?jǐn)?shù)據(jù)集時(shí)也形成葉節(jié)點(diǎn)，并且用多數(shù)樣本所屬的類別來(lái)標(biāo)記這個(gè)葉節(jié)點(diǎn)33ID3算法示例該樣本集中共包含4個(gè)描述屬性和1個(gè)類別屬性，空間容量為14目標(biāo)是利用ID3思想構(gòu)建一棵可用于新樣本分類的決策樹34A1-公司職員A2-年齡A3-收入A4-信譽(yù)度C-買保險(xiǎn)否<=40高良c2否<=40高優(yōu)c2否41~50高良c1否>50中良c1是>50低良c1是>50低優(yōu)c2是41~50低優(yōu)c1否<=40中良c2是<=40低良c1是>50中良c1是<=40中優(yōu)c1否41~50中優(yōu)c1是41~50高良c1否>50中優(yōu)c2第1步：計(jì)算對(duì)訓(xùn)練集分類所需的期望信息已知total=14c1(買保險(xiǎn))的樣本數(shù)量是n1=9c2(不買保險(xiǎn))的樣本數(shù)量是n2=5所以P(c1)=9/14P(c2)=5/14根據(jù)期望信息公式可得35第2步：計(jì)算A1（公司職員）的熵A1包含兩種取值：“是”和“否”利用A1可將X劃分為兩個(gè)子集X1和X2X1中的數(shù)據(jù)樣本都是公司職員（7個(gè)）標(biāo)號(hào)為c1的有6個(gè)，n11=6標(biāo)號(hào)為c2的有1個(gè)，n21=1則可得p11=6/7p21=1/736A1-公司職員C-買保險(xiǎn)否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2第2步：計(jì)算A1（公司職員）的熵利用A1可將X劃分為兩個(gè)子集X1和X2X2中的數(shù)據(jù)樣本都不是公司職員（7個(gè)）標(biāo)號(hào)為c1的有3個(gè)，n12=3標(biāo)號(hào)為c2的有4個(gè)，n22=4則可得p12=3/7p22=4/737A1-公司職員C-買保險(xiǎn)否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c2第2步：計(jì)算A1（公司職員）的熵則計(jì)算出A1劃分訓(xùn)練集所得的熵為38第3步：計(jì)算A1（公司職員）的信息增益39第4步：求出其他描述屬性的信息增益Gain(A2)=0.246Gain(A3)=0.029Gain(A4)=0.048經(jīng)比較可知Gain(A2)最大，所以選擇A2（年齡）作為決策樹的根節(jié)點(diǎn)進(jìn)一步將樹劃分為3個(gè)分支40第5步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集年齡<=40的子集在此子集內(nèi)繼續(xù)檢查Gain(A1)、Gain(A3)、Gain(A4)選取信息增益最大的描述屬性作為內(nèi)部節(jié)點(diǎn)41A1-公司職員A3-收入A4-信譽(yù)度C-買保險(xiǎn)否高良c2否高優(yōu)c2否中良c2是低良c1是中優(yōu)c1第5步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集年齡41~50的子集該子集中所有樣本的類別標(biāo)號(hào)都一樣，所以無(wú)需繼續(xù)劃分可將它標(biāo)注為一個(gè)葉節(jié)點(diǎn)，而且葉節(jié)點(diǎn)的類標(biāo)號(hào)為c142A1-公司職員A3-收入A4-信譽(yù)度C-買保險(xiǎn)否高良c1是低優(yōu)c1否中優(yōu)c1是高良c1第5步：根據(jù)根節(jié)點(diǎn)劃分?jǐn)?shù)據(jù)集年齡>50的子集在此子集內(nèi)繼續(xù)檢查Gain(A1)、Gain(A3)、Gain(A4)選取信息增益最大的描述屬性作為內(nèi)部節(jié)點(diǎn)43A1-公司職員A3-收入A4-信譽(yù)度C-買保險(xiǎn)否中良c1是低良c1是低優(yōu)c2是中良c1否中優(yōu)c2ID3算法小結(jié)使用ID3算法的基本思想是采用自頂向下的遞歸方式，將原始樣本空間劃分成若干更小的樣本空間再對(duì)他們單獨(dú)進(jìn)行處理其中，選擇哪一個(gè)描述屬性作為新建節(jié)點(diǎn)，依據(jù)是考察該描述屬性的信息增益是否最大4445PartIIIC4.5算法ID3的不足（1/2）使用信息增益作為屬性選擇依據(jù)帶有傾向性，傾向于選擇取值較多的屬性為什么？一種可能的解釋是：對(duì)于較難分類的集合，優(yōu)先將樣本分割到盡可能多的分支中將極大簡(jiǎn)化分類工作46ID3的不足（2/2）無(wú)法處理未知值的樣本對(duì)于個(gè)別樣本缺失了某項(xiàng)描述屬性的情況，無(wú)法處理無(wú)法處理連續(xù)值的樣本對(duì)于描述屬性是連續(xù)值的情況，無(wú)法處理47變化一：使用信息增益比48變化二：處理未知值的訓(xùn)練樣本（1/2）思想將未知值用最常用的值來(lái)替代（較容易）或，依據(jù)現(xiàn)有取值的概率分布來(lái)估計(jì)未知值（較真實(shí)）顯然：依據(jù)思想一，在已知樣本中年齡的三個(gè)區(qū)間分布是<=40，4人41~50，4人>50，5人則可以直接指定未知值為“>50”49A2-年齡C-買保險(xiǎn)<=40c2<=40c241~50c1>50c1>50c1>50c241~50c1<=40c2<=40c1>50c1？c141~50c141~50c1>50c2變化二：處理未知值的訓(xùn)練樣本（2/2）思想將未知值用最常用的值來(lái)替代（較容易）或，依據(jù)現(xiàn)有取值的概率分布來(lái)估計(jì)未知值（較真實(shí)）顯然：依據(jù)思想二，在已知樣本中年齡的三個(gè)區(qū)間分布是<=40，4人41~50，4人>50，5人考慮未知值樣本后，分布更新為<=40，4+4/13人41~50，4+4/13人>50，5+5/13人50A2-年齡C-買保險(xiǎn)<=40c2<=40c241~50c1>50c1>50c1>50c241~50c1<=40c2<=40c1>50c1？c141~50c141~50c1>50c2變化三：處理連續(xù)值的訓(xùn)練樣本（1/10）思想將所有數(shù)據(jù)樣本按照連續(xù)型描述屬性Ac的具體取值，由小到大進(jìn)行升序排列，得到的屬性值取值序列{A1c,A2c,...,Atotalc}在{A1c,A2c,...,Atotalc}中生成total-1個(gè)分割點(diǎn)，第i個(gè)分割點(diǎn)的取值設(shè)置為vi=(Aic+A(i+1)c)/2或者vi=Aic該分割點(diǎn)將數(shù)據(jù)集劃分為兩個(gè)子集，即描述屬性Ac的取值在區(qū)間[A1c,vi]的數(shù)據(jù)樣本和在區(qū)間(vi,Atotalc]的數(shù)據(jù)樣本，顯然劃分共有total-1種方式從total-1個(gè)分割點(diǎn)中選擇最佳分割點(diǎn)。對(duì)于每一個(gè)分割點(diǎn)劃分?jǐn)?shù)據(jù)集的方式，計(jì)算其信息增益比，從中選擇信息增益比最大的分割點(diǎn)來(lái)劃分?jǐn)?shù)據(jù)集51變化三：處理連續(xù)值的訓(xùn)練樣本（2/10）示例求利用C4.5算法在連續(xù)值描述屬性A上的最佳分割點(diǎn)解：第0步，將A的取值升序排列{65,70,70,70,75,78,80,80,80,85,90,90,95,96}第1步，計(jì)算vi=65時(shí)的信息增益比52AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（3/10）解：第1步，計(jì)算vi=65時(shí)的信息增益比53AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（4/10）解：第1步，計(jì)算vi=65時(shí)的信息增益比54AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（5/10）解：第2步，計(jì)算vi=70時(shí)的信息增益比55AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（6/10）解：第2步，計(jì)算vi=70時(shí)的信息增益比56AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（7/10）解：第2步，計(jì)算vi=70時(shí)的信息增益比57AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（8/10）解：第3步，計(jì)算vi=75時(shí)的信息增益比58AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（9/10）解：第3步，計(jì)算vi=75時(shí)的信息增益比59AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2變化三：處理連續(xù)值的訓(xùn)練樣本（10/10）解：第3步，計(jì)算vi=75時(shí)的信息增益比60AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c2本章結(jié)束第3章科學(xué)決策與信息分析主要內(nèi)容：信息分析在決策中的作用；各類型決策中的信息保障；信息分析的工作流程?；疽螅毫私飧黝悰Q策中信息利用的重要性；了解不同決策階段信息服務(wù)的特點(diǎn)；理解決策對(duì)信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在決策中的作用3.1.1決策活動(dòng)中的信息利用信息分析:是對(duì)情報(bào)進(jìn)行定向濃集和科學(xué)抽象的一種科學(xué)勞動(dòng).信息在軍事戰(zhàn)略制定中的作用；信息在制定地區(qū)經(jīng)濟(jì)發(fā)展規(guī)劃中的作用；信息在科學(xué)管理中的作用；信息在對(duì)外貿(mào)易中的作用；信息在制定生產(chǎn)計(jì)劃中的作用；信息在提高產(chǎn)品質(zhì)量、發(fā)展花色品種中的作用。3.1信息分析在決策中的作用決策階段信息服務(wù)的內(nèi)容與特點(diǎn)決策前（超前服務(wù)）促成決策及早完成（快）；有助于決策者掌握預(yù)測(cè)性信息（準(zhǔn)）；有助于決策者更新知識(shí)、增強(qiáng)判斷力（增）決策中（跟蹤服務(wù)）確立目標(biāo)階段；決策方案準(zhǔn)備階段；選定決策方案階段。決策后（反饋服務(wù)）跟蹤反饋；循環(huán)反饋；同步追蹤反饋。3.1.2不同決策階段的信息服務(wù)3.1信息分析在決策中的作用3.1.3決策對(duì)信息的基本要求可靠性（可信度）——信息的真實(shí)性和準(zhǔn)確性。信息源；信息獲取手段；信息獲取的條件。完整性（完全度）——包括決策對(duì)象全部的信息全面收集歷史的、現(xiàn)實(shí)的和未來(lái)的信息；兼顧反映正面的和反面問(wèn)題的信息。精確性（精確度）——反映事物特征的細(xì)微化程度。不同決策對(duì)信息的精確度要求不同；劃定范圍，確定上限和下限。3.2各類型決策中的信息保障3.2.1新產(chǎn)品研制的信息保障創(chuàng)意產(chǎn)生與篩選階段的信息保障創(chuàng)意產(chǎn)生于對(duì)信息的收集、吸收和理解；創(chuàng)意孕育著新產(chǎn)品，要盡可能多的收集；篩選是從多個(gè)創(chuàng)意中選擇出具有開發(fā)價(jià)值項(xiàng)目的過(guò)程，其要求是：新意；可行；實(shí)用；有效。3.2各類型決策中的信息保障3.2.1新產(chǎn)品研制的信息保障開發(fā)決策階段的信息保障主要任務(wù)是針對(duì)經(jīng)過(guò)初步篩選出的幾個(gè)創(chuàng)意中的每一個(gè)新產(chǎn)品開發(fā)構(gòu)想收集