商務(wù)智能-Chapter04-Data Mining-Clasification學(xué)習(xí)課件

ZhangjunWu（伍章俊）InstituteofBusinessIntelligence,FacultyofElectronicCommerce,ManagementSchool第五章分類分析2025/2/27?TheInstituteofBusinessIntelligence,HFUT1/1002025/2/27?TheInstituteofBusinessIntelligence,HFUT2/100課程回顧BI基本概念數(shù)據(jù)倉(cāng)庫(kù)OLAP操作2025/2/27?TheInstituteofBusinessIntelligence,HFUT3/100數(shù)據(jù)挖掘分類分析聚類分析關(guān)聯(lián)分析分類分析什么是分類？K-近鄰分類算法決策樹分類算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT4/1002025/2/27?TheInstituteofBusinessIntelligence,HFUT5/1002025/2/27?TheInstituteofBusinessIntelligence,HFUT6/1002025/2/27?TheInstituteofBusinessIntelligence,HFUT7/1002025/2/27?TheInstituteofBusinessIntelligence,HFUT8/100分類分析什么是分類？K-近鄰算法分類決策樹分類2025/2/27?TheInstituteofBusinessIntelligence,HFUT9/100是否會(huì)買計(jì)算機(jī)？ageincomestudentcreditbuys_computer<=30highnofairno<=30highnoexcellentno30…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes

………

…

…

假定公司擁有如上表所示的消費(fèi)者數(shù)據(jù)，那么對(duì)于一個(gè)潛在消費(fèi)者，該消費(fèi)者會(huì)不會(huì)購(gòu)買計(jì)算機(jī)？ageincomestudentcreditbuys_computer<=30lowyesfair?2025/2/27?TheInstituteofBusinessIntelligence,HFUT10/100是否保險(xiǎn)欺詐?目前有一個(gè)索賠申請(qǐng)，索賠人的資料如下年齡性別申請(qǐng)金額罰單數(shù)已有申請(qǐng)擔(dān)保人欺詐52Male200001張三OK38Male180000NoneOK21Female560012王五Fraudulent36Female380001NoneOK19Male60022李四OK41Male420012王五Fraudulent38Male270000NoneOK33Female250001NoneFraudulent18Female130000NoneOK26Male260020NoneOK年齡性別申請(qǐng)金額罰單數(shù)已有申請(qǐng)擔(dān)保人欺詐35Male600010王五？2025/2/27?TheInstituteofBusinessIntelligence,HFUT11/100分類的應(yīng)用信譽(yù)評(píng)估滿意度預(yù)測(cè)2025/2/27?TheInstituteofBusinessIntelligence,HFUT12/100分類的定義分類是基于已有的類別數(shù)據(jù)構(gòu)造一個(gè)分類函數(shù)或分類規(guī)則集合（分類器），該分類器能把潛在的數(shù)據(jù)項(xiàng)映射到某一個(gè)給定類別給定數(shù)據(jù)表D＝｛t1,t2,…,tn｝，元組ti

D，類的集合C＝｛C1,……,Cm｝，分類問(wèn)題定義為從數(shù)據(jù)表到類集合的映射f：D

C，即數(shù)據(jù)庫(kù)中的元組ti分配到某個(gè)類Cj中，有Cj＝｛ti|f(ti)=Cj，1≤i≤n，且ti∈D｝2025/2/27?TheInstituteofBusinessIntelligence,HFUT13/100是否會(huì)買計(jì)算機(jī)？ageincomestudentcreditbuys_computer<=30highnofairno<=30highnoexcellentno30…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes

………

…

…

ageincomestudentcreditbuys_computer<=30lowyesfair?分類器buys=f(age,income,student,credit)2025/2/27?TheInstituteofBusinessIntelligence,HFUT14/100簡(jiǎn)單例子姓名統(tǒng)率武力智力政治槍兵戟兵呂玲綺81893718通精凌統(tǒng)77895540通神馬雲(yún)錄78885346精疏関索74885247通精王雙64881922通精鄧艾94878981神精孟獲76874245通神張苞75874846神精董卓74876919疏疏陳武74874340精神曹仁89865646精神高順85865546精通関興76866258精神孫尚香72866763精通等級(jí)★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★周倉(cāng)62844233疏精？2025/2/27?TheInstituteofBusinessIntelligence,HFUT15/100監(jiān)督學(xué)習(xí)與非監(jiān)督學(xué)習(xí)監(jiān)督學(xué)習(xí)(有導(dǎo)師學(xué)習(xí))-Supervisedlearning數(shù)據(jù)的類標(biāo)志是已知的由訓(xùn)練數(shù)據(jù)集得到模型，用于新的對(duì)象classification非監(jiān)督的學(xué)習(xí)(無(wú)導(dǎo)師學(xué)習(xí))-Unsupervisedlearning數(shù)據(jù)的類標(biāo)志是未知的根據(jù)對(duì)象之間的距離或相似性進(jìn)行劃分clustering2025/2/27?TheInstituteofBusinessIntelligence,HFUT16/100簡(jiǎn)單例子分類兩歲寶寶，給他看幾個(gè)水果，并告訴他：紅的圓的是蘋果，橘黃的圓的是橘子（建立模型）拿一個(gè)水果問(wèn)寶寶：這個(gè)水果，紅的圓的，是什么？（使用模型）聚類三歲寶寶，給他一堆水果，告訴他：根據(jù)顏色分成兩堆。寶寶會(huì)將紅的蘋果分成一堆，橘黃的橘子分成一堆。2025/2/27?TheInstituteofBusinessIntelligence,HFUT17/100分類與預(yù)測(cè)類別屬性是離散值，通常稱為分類類別屬性是連續(xù)值，通常稱為預(yù)測(cè)ageincomestudentcreditbuys_computer<=30highnofairno<=30highnoexcellentno30…40highnofairyes>40mediumnofairyes>40lowyesfairyes>40lowyesexcellentno31…40lowyesexcellentyes

………

…

…

Amount(￥)2003005001000350560780…ageincomestudentcreditbuys_computer<=30lowyesfair?Amount(￥)?2025/2/27?TheInstituteofBusinessIntelligence,HFUT18/100Decisiontrees

決策樹RoughSet粗糙集BayesClassifier

貝葉斯分類AssociativeClassification關(guān)聯(lián)分類……分類技術(shù)各八顯仙神過(guò)通海2025/2/27?TheInstituteofBusinessIntelligence,HFUT19/100分類的三個(gè)階段構(gòu)建模型:描述一組已知的類訓(xùn)練數(shù)據(jù)集:(trainingset)基于分類規(guī)則、決策樹等構(gòu)建分類模型分類模型的剪枝，得到簡(jiǎn)潔、分類能力強(qiáng)的分類器測(cè)試模型：檢測(cè)模型的準(zhǔn)確度測(cè)試數(shù)據(jù)集(testset)用模型推導(dǎo)出來(lái)的類標(biāo)志與已知的類標(biāo)志比較，如果相同，則稱結(jié)果是正確的準(zhǔn)確度等于測(cè)試數(shù)據(jù)集中由模型得到正確結(jié)果的比例應(yīng)用模型：利用分類模型，預(yù)測(cè)在類別未知的情況下樣本所屬的類

別(unclassifiedsample)2025/2/27?TheInstituteofBusinessIntelligence,HFUT20/100一個(gè)完整的分類過(guò)程數(shù)據(jù)訓(xùn)練集測(cè)試集分類模型評(píng)估準(zhǔn)確性新數(shù)據(jù)分類模型預(yù)測(cè)類別

（1）（2）（3）模型構(gòu)造模型測(cè)試模型應(yīng)用2025/2/27?TheInstituteofBusinessIntelligence,HFUT21/100分類任務(wù)(Jeff,Professor,4)2025/2/27?TheInstituteofBusinessIntelligence,HFUT22/100數(shù)據(jù)劃分TrainingsetTestset2025/2/27?TheInstituteofBusinessIntelligence,HFUT23/100模型構(gòu)造訓(xùn)練數(shù)據(jù)分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類器2025/2/27?TheInstituteofBusinessIntelligence,HFUT24/100模型測(cè)試/應(yīng)用分類器測(cè)試數(shù)據(jù)新數(shù)據(jù)(Jeff,Professor,4)Tenured?2025/2/27?TheInstituteofBusinessIntelligence,HFUT25/100分類分析什么是分類？K-近鄰算法分類決策樹分類2025/2/27?TheInstituteofBusinessIntelligence,HFUT26/100基于距離的分類算法定義4-2

給定一個(gè)對(duì)象(個(gè)體)t和一組類C={C1，…，Cm}。假定t包括一些數(shù)值型的屬性值：t={t1，t2，…，tk}，每個(gè)類也包含數(shù)值型屬性值：Cj={Cj1，Cj2，…，Cjk}，則分類問(wèn)題是要分配t到滿足如下條件的類Cj：sim(t，Cj)>=sim(t，Ci)，

Ci∈C，Ci≠Cj，其中sim(t，Cj)被稱為相似性。在實(shí)際的計(jì)算中往往用距離來(lái)表征，距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。距離的計(jì)算方法有多種，最常用的是通過(guò)計(jì)算每個(gè)類的中心來(lái)完成。2025/2/27?TheInstituteofBusinessIntelligence,HFUT27/100基于距離分類算法的一般性描述算法4-1通過(guò)對(duì)每個(gè)元組和各個(gè)類的中心來(lái)比較，從而可以找出其最近的類中心，得到確定的類別標(biāo)記。算法4-1基于距離的分類算法輸入：每個(gè)類的中心C1，…，Cm；待分類的元組t。輸出：輸出類別c。（1）dist=∞；//距離初始化（2）FORi:=1tomDO（3） IFdis(ci，t)<distTHENBEGIN（4） c←i；（5） dist←dist(ci，t)；（6） END2025/2/27?TheInstituteofBusinessIntelligence,HFUT28/100基于距離的分類方法的直觀解釋例：有A，B，C三個(gè)類；有18個(gè)待分類的樣例；通過(guò)計(jì)算每個(gè)類代表區(qū)域的中心來(lái)確定每個(gè)類的分類中心CA，CB，CC；通過(guò)計(jì)算待分類的樣例到每個(gè)分類中心的距離就可以找出最相似的類。（a）類定義（b）待分類樣例（c）分類結(jié)果2025/2/27?TheInstituteofBusinessIntelligence,HFUT29/100k-近鄰分類算法思想k-近鄰分類算法（kNearestNeighbors，簡(jiǎn)稱kNN）計(jì)算新樣本與訓(xùn)練樣本之間的距離，找到距離最近的K個(gè)鄰居;根據(jù)這些鄰居所屬的類別來(lái)判定新樣本的類別，如果屬于同一個(gè)類別，那么新樣本也屬于這個(gè)類；否則，對(duì)每個(gè)候選類別進(jìn)行評(píng)分，按照某種規(guī)則確定新樣本的類別。2025/2/27?TheInstituteofBusinessIntelligence,HFUT30/100K-近鄰算法描述：輸入：訓(xùn)練數(shù)據(jù)集D={(Xi,Yi),1≤i≤N}，其中Xi是第i個(gè)樣本的條件屬性，Yi是類別，新樣本X，距離函數(shù)d。輸出：X的類別Y。

fori=1toNdo計(jì)算X和Xi之間的距離d(Xi,X)；

endfor對(duì)距離排序，得到d(X,Xi1)，d(X,Xi2)，...，d(X,XiN)；選擇前K個(gè)樣本：S={(Xi1,Yi1),...,(Xik,Yik)}；統(tǒng)計(jì)S中每個(gè)類別出現(xiàn)的次數(shù)，確定X的類別Y。2025/2/27?TheInstituteofBusinessIntelligence,HFUT31/100kNN的例子姓名性別身高(米)類別姓名性別身高(米)類別Kristina女1.6矮Worth男2.2高Jim男2高Steven男2.1高M(jìn)aggie女1.9中等Debbie女1.8中等Martha女1.83中等Todd男1.95中等Stephanie女1.7矮Kim女1.9中等Bob男1.85中等Amy女1.8中等Kathy女1.6矮Wynette女1.75中等Dave男1.7矮使用下表中的樣本數(shù)據(jù)，對(duì)<Pat,女,1.6>進(jìn)行分類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT32/100kNN的例子姓名性別身高(米)類別Kristina女1.6矮Dave男1.7矮Kathy女1.6矮Wynette女1.75中等Stephanie女1.7矮在這五項(xiàng)中，四個(gè)屬于矮個(gè)、一個(gè)屬于中等。最終kNN方法認(rèn)為Pat為矮個(gè)。2025/2/27?TheInstituteofBusinessIntelligence,HFUT33/100K-近鄰算法的幾個(gè)問(wèn)題確定距離函數(shù)

距離函數(shù)決定了哪些樣本是待分樣本的K個(gè)最近鄰居，它的選擇取決于實(shí)際的數(shù)據(jù)和決策問(wèn)題。如果樣本是空間中的點(diǎn)，最常用是歐幾里德距離。其它常用的距離函數(shù)有：絕對(duì)距離、平方差或標(biāo)準(zhǔn)差等。決定K的取值

鄰居的個(gè)數(shù)對(duì)分類的結(jié)果有一定的影響，一般先確定一個(gè)初始值，再進(jìn)行調(diào)整，直到找到合適的值為止。綜合K個(gè)鄰居的類別

多數(shù)法是最簡(jiǎn)單一種綜合方法。從鄰居中選擇一個(gè)出現(xiàn)頻率最高的類別作為最后的結(jié)果，如果頻率最高的類別不止一個(gè)，就選擇最近鄰居的類別。權(quán)重法是較復(fù)雜的一種方法，對(duì)K個(gè)最近鄰居設(shè)置權(quán)重，距離越大，權(quán)重就越小。在統(tǒng)計(jì)類別時(shí)，計(jì)算每個(gè)類別的權(quán)重和，最大的那個(gè)就是新樣本的類別。2025/2/27?TheInstituteofBusinessIntelligence,HFUT34/100分類分析什么是分類？K-近鄰算法分類決策樹分類2025/2/27?TheInstituteofBusinessIntelligence,HFUT35/100決策樹基本概念決策樹是一種典型的分類方法，將分類器表示成樹狀結(jié)構(gòu)，然后使用決策樹對(duì)新數(shù)據(jù)進(jìn)行分類。年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買不買2025/2/27?TheInstituteofBusinessIntelligence,HFUT36/100決策樹計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？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)買2025/2/27?TheInstituteofBusinessIntelligence,HFUT37/100內(nèi)部節(jié)點(diǎn)：數(shù)據(jù)集的一個(gè)屬性分枝：對(duì)應(yīng)屬性的一個(gè)分割葉子節(jié)點(diǎn)：表示一個(gè)類年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買買買誰(shuí)在買計(jì)算機(jī)？他/她會(huì)買計(jì)算機(jī)嗎？類似情況學(xué)習(xí)<3535-60>602025/2/27?TheInstituteofBusinessIntelligence,HFUT38/100決策樹不買決策樹決策樹算法在數(shù)據(jù)處理過(guò)程中，將數(shù)據(jù)按樹狀結(jié)構(gòu)分成若干分枝形成決策樹，從根到樹葉的每條路徑創(chuàng)建一個(gè)規(guī)則。年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買不買買買If(年齡＝中)then

買計(jì)算機(jī)If(年齡＝老and

信譽(yù)＝優(yōu))then

買計(jì)算機(jī)If(年齡＝青and

學(xué)生＝是)then

買計(jì)算機(jī)If(年齡＝老and

信譽(yù)＝良)then

不買計(jì)算機(jī)If(年齡＝青and

學(xué)生＝否)

then

不買計(jì)算機(jī)規(guī)則表示年齡收入學(xué)生信譽(yù)老中否優(yōu)問(wèn)題？？2025/2/27?TheInstituteofBusinessIntelligence,HFUT39/100決策樹的構(gòu)造樹的生成從根結(jié)點(diǎn)開始、從上到下的遞歸過(guò)程樹的剪枝對(duì)樹結(jié)構(gòu)進(jìn)行修剪，刪除多余分支目標(biāo)構(gòu)建一棵內(nèi)部節(jié)點(diǎn)盡可能少、層次盡可能淺、分枝盡可能少,而分類精度盡可能大的樹2025/2/27?TheInstituteofBusinessIntelligence,HFUT40/100反例一棵很糟糕的決策樹收入？學(xué)生？青中否是高低中信譽(yù)？良優(yōu)年齡？不買買買不買年齡？學(xué)生？信譽(yù)？買青中老否是優(yōu)良不買不買買買2025/2/27?TheInstituteofBusinessIntelligence,HFUT41/100決策樹算法思想基本算法自上而下分而治之的方法開始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)根據(jù)特定的啟發(fā)式規(guī)則選擇某一屬性對(duì)樣本數(shù)據(jù)遞歸地進(jìn)行分割結(jié)束條件內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)的所有樣本屬于同一類沒(méi)有屬性可以繼續(xù)分割再繼續(xù)分割的意義不大2025/2/27?TheInstituteofBusinessIntelligence,HFUT42/100決策樹生成算法FunctionTree=Decision_Tree_Create(T,A,Y)輸入：訓(xùn)練集T，條件屬性集A，類別Y輸出：決策樹Tree步驟：

Tree=Create_Node(T);//生成結(jié)點(diǎn)Tree

IfT的所有樣本的類別相同，Then用該類別標(biāo)識(shí)結(jié)點(diǎn)，returnTree;

If

沒(méi)有可分的屬性，Then用T中頻率最高的類別標(biāo)識(shí)結(jié)點(diǎn)，returnTree;

(X,Values)=Attribute_Selection(T,A,Y);//選擇最佳屬性X和分裂點(diǎn)Values

foreachVinValuesdo

//根據(jù)測(cè)試(X,Values)劃分樣本集，生成子結(jié)點(diǎn)

SubT=滿足X的測(cè)試條件V的樣本子集;

Node=Decision_Tree_Create(SubT,A-{X},Y);//對(duì)子結(jié)點(diǎn)進(jìn)行遞

歸操作，通常X在子樹的生成中不再作為分裂屬性

Create_Branch(Tree,Node);//生成T的一個(gè)分支

endfor

returnTree;2025/2/27?TheInstituteofBusinessIntelligence,HFUT43/100決策樹生成過(guò)程⑴在條件屬性集中選擇最有分類能力的屬性作為決策樹當(dāng)前節(jié)點(diǎn)。實(shí)例顏色體形毛型類別1黑大卷毛危險(xiǎn)2棕大光滑危險(xiǎn)3棕中卷毛不危險(xiǎn)4黑小卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)6黑大光滑危險(xiǎn)7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)9棕大卷毛危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)體形2025/2/27?TheInstituteofBusinessIntelligence,HFUT44/100為什么要選擇最有分類能力的屬性作為決策樹當(dāng)前節(jié)點(diǎn)？實(shí)例顏色體形毛型類別1黑大卷毛危險(xiǎn)2棕大光滑危險(xiǎn)3棕中卷毛不危險(xiǎn)4黑小卷毛不危險(xiǎn)5棕中光滑不危險(xiǎn)6黑大光滑危險(xiǎn)7棕小卷毛不危險(xiǎn)8棕小光滑不危險(xiǎn)9棕大卷毛危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)體形大中小危險(xiǎn)不危險(xiǎn)不危險(xiǎn)決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT45/100如何選擇最有分類能力的屬性作為決策樹當(dāng)前節(jié)點(diǎn)？

信息增益、增益指標(biāo)、GINI指標(biāo)、…實(shí)例顏色體形毛型類別1黑大卷毛危險(xiǎn)2棕大光滑危險(xiǎn)3棕中卷毛不危險(xiǎn)4黑小卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)6黑大光滑危險(xiǎn)7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)9棕大卷毛危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT46/100⑵根據(jù)當(dāng)前決策屬性取值不同，將訓(xùn)練樣本數(shù)據(jù)集劃分為若干子集。實(shí)例序號(hào)顏色體形毛型類別1黑大卷毛危險(xiǎn)2棕大光滑危險(xiǎn)6黑大光滑危險(xiǎn)9棕大卷毛危險(xiǎn)體形大中小實(shí)例序號(hào)顏色體形毛型類別3棕中卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)實(shí)例序號(hào)顏色體形毛型類別4黑小卷毛不危險(xiǎn)7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT47/100⑶針對(duì)上一步得到每一個(gè)子集，重復(fù)上述過(guò)程，直到子集中所有元組都屬于同一類，不能再進(jìn)一步劃分為止。實(shí)例序號(hào)顏色體形毛型類別3棕中卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)體形大中小危險(xiǎn)？？顏色序號(hào)顏色體形毛型類別3棕中卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)序號(hào)顏色體形毛型類別10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)棕黑決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT48/100體形大中小危險(xiǎn)顏色？不危險(xiǎn)黑？棕實(shí)例顏色體形毛型類別4黑小卷毛不危險(xiǎn)7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)顏色實(shí)例顏色體形毛型類別4黑小卷毛不危險(xiǎn)12黑小光滑不危險(xiǎn)實(shí)例顏色體形毛型類別7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)黑棕決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT49/100體形大中小危險(xiǎn)顏色顏色不危險(xiǎn)黑？棕不危險(xiǎn)？黑棕實(shí)例序號(hào)顏色體形毛型類別3棕中卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)毛型實(shí)例序號(hào)顏色體形毛型類別3棕中卷毛不危險(xiǎn)實(shí)例序號(hào)顏色體形毛型類別5棕中光滑危險(xiǎn)卷毛光滑實(shí)例序號(hào)顏色體形毛型類別7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)毛型實(shí)例序號(hào)顏色體形毛型類別3棕小卷毛危險(xiǎn)實(shí)例序號(hào)顏色體形毛型類別5棕小光滑不危險(xiǎn)卷毛光滑決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT50/100最終生成的決策樹體形大中小危險(xiǎn)顏色顏色不危險(xiǎn)黑毛型棕不危險(xiǎn)毛型黑棕不危險(xiǎn)危險(xiǎn)不危險(xiǎn)危險(xiǎn)卷毛光滑卷毛光滑決策樹生成過(guò)程2025/2/27?TheInstituteofBusinessIntelligence,HFUT51/100示例1：

訓(xùn)練集2025/2/27?TheInstituteofBusinessIntelligence,HFUT52/100天氣風(fēng)況有無(wú)晴雨多云溫度適中涼爽熱2025/2/27?TheInstituteofBusinessIntelligence,HFUT53/100示例1：

訓(xùn)練集不適合適合不適合適合不適合適合決策樹建立的關(guān)鍵屬性？屬性？屬性？屬性？建立一個(gè)好的決策樹的關(guān)鍵是決定內(nèi)部節(jié)點(diǎn)的屬性實(shí)例顏色體形毛型類別1黑大卷毛危險(xiǎn)2棕大光滑危險(xiǎn)3棕中卷毛不危險(xiǎn)4黑小卷毛不危險(xiǎn)5棕中光滑危險(xiǎn)6黑大光滑危險(xiǎn)7棕小卷毛危險(xiǎn)8棕小光滑不危險(xiǎn)9棕大卷毛危險(xiǎn)10黑中卷毛不危險(xiǎn)11黑中光滑不危險(xiǎn)12黑小光滑不危險(xiǎn)2025/2/27?TheInstituteofBusinessIntelligence,HFUT54/100決策樹分類算法－ID3分類算法決策樹的每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)一個(gè)非類別屬性每條邊對(duì)應(yīng)該屬性的每個(gè)可能值以信息增益作為選取測(cè)試屬性的標(biāo)準(zhǔn)，即所選的測(cè)試屬性是從根到當(dāng)前節(jié)點(diǎn)的路徑上尚未被考慮的具有最高信息增益的屬性。2025/2/27?TheInstituteofBusinessIntelligence,HFUT55/100ID3學(xué)習(xí)算法熵

度量樣例的純度(度量標(biāo)準(zhǔn))

熵定義：設(shè)S是n個(gè)數(shù)據(jù)樣本的集合，將樣本劃分為c個(gè)不同的類，每個(gè)類含樣本數(shù)ni，則S劃分為c個(gè)類的熵為2025/2/27?TheInstituteofBusinessIntelligence,HFUT56/100類別危險(xiǎn)危險(xiǎn)不危險(xiǎn)不危險(xiǎn)危險(xiǎn)危險(xiǎn)危險(xiǎn)不危險(xiǎn)危險(xiǎn)不危險(xiǎn)不危險(xiǎn)不危險(xiǎn)分為兩類，“危險(xiǎn)”的類有6個(gè)，“不危險(xiǎn)”的類有6個(gè)，則劃分為兩類的信息熵為：ID3學(xué)習(xí)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT57/100

信息增益（InformationGain）衡量屬性區(qū)分訓(xùn)練樣例的能力:一個(gè)屬性的信息增益就是由于使用這個(gè)屬性而導(dǎo)致的熵的降低屬性X相對(duì)樣例集合S的信息增益定義：ID3學(xué)習(xí)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT58/100決策樹建立的關(guān)鍵實(shí)例體形類別1大危險(xiǎn)2大危險(xiǎn)3中不危險(xiǎn)4小不危險(xiǎn)5中危險(xiǎn)6大危險(xiǎn)7小危險(xiǎn)8小不危險(xiǎn)9大危險(xiǎn)10中不危險(xiǎn)11中不危險(xiǎn)12小不危險(xiǎn)2025/2/27?TheInstituteofBusinessIntelligence,HFUT59/100ID3學(xué)習(xí)算法根據(jù)“體形”取值可分為3個(gè)子表，每個(gè)表劃分為2類，每個(gè)子表進(jìn)行劃分的信息熵為：實(shí)例序號(hào)體形類別1大危險(xiǎn)2大危險(xiǎn)6大危險(xiǎn)9大危險(xiǎn)2025/2/27?TheInstituteofBusinessIntelligence,HFUT60/100實(shí)例序號(hào)體形類別3中不危險(xiǎn)5中危險(xiǎn)10中不危險(xiǎn)11中不危險(xiǎn)ID3學(xué)習(xí)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT61/100實(shí)例序號(hào)體形類別4小不危險(xiǎn)7小危險(xiǎn)8小不危險(xiǎn)12小不危險(xiǎn)ID3學(xué)習(xí)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT62/100按屬性“體形”取值劃分的信息增益為：“顏色”、“毛型”劃分..選取信息增益值最大的屬性作為最佳屬性(體形)，進(jìn)行分類ID3學(xué)習(xí)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT63/100對(duì)當(dāng)前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn)N。如果數(shù)據(jù)表中的數(shù)據(jù)都屬于同一類，N就是樹葉，在樹葉上標(biāo)上所屬的那一類。如果數(shù)據(jù)表中沒(méi)有其他屬性可以考慮，N也是樹葉，按照少數(shù)服從多數(shù)的原則在樹葉上標(biāo)上所屬類別。否則，根據(jù)InformationGain值選出一個(gè)最佳屬性作為節(jié)點(diǎn)N的測(cè)試屬性A。節(jié)點(diǎn)屬性選定以后，對(duì)于該屬性的每一個(gè)值ai：從N生成一個(gè)A=ai的分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄。如果分支數(shù)據(jù)表非空，則運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹。遞歸上述過(guò)程

ID3學(xué)習(xí)算法2025/2/27?TheInstituteofBusinessIntelligence,HFUT64/100ID3算法舉例DayOutlookTemperatureHumidityWindPlayD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNoPlayTennis?2025/2/27?TheInstituteofBusinessIntelligence,HFUT65/100ID3算法舉例對(duì)樣本分類的信息熵為：以屬性“outlook”為例計(jì)算信息增益

屬性“outlook”有3個(gè)取值，分別為Sunny，Overcast，RainPlayNoNoYesYesYesNoYesNoYesYesYesYesYesNoOutlookSunnySunnyOvercastRainRainRainOvercastSunnySunnyRainSunnyOvercastOvercastRain2025/2/27?TheInstituteofBusinessIntelligence,HFUT66/100OutlookPlayRainYesRainYesRainNoRainYesRainNoOutlookPlayOvercastYesOvercastYesOvercastYesOvercastYesOutlookPlaySunnyNoSunnyNoSunnyNoSunnyYesSunnyYesID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT67/100屬性”O(jiān)utlook“的信息增益：同理通過(guò)計(jì)算，得Humidity，Temperature，Wind屬性的信息增益：

通過(guò)比較，選擇信息增益最大的屬性”O(jiān)utlook”作為根節(jié)點(diǎn)。

ID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT68/100初步生成的決策樹：Outlook??yesSunnyOvercastRainID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT69/100OutlookDayTemperatureHumidityWindPlayD1HotHighWeakNoD2HotHighStrongNoD8MildHighWeakNoD9CoolNormalWeakYesD11MildNormalStrongYesDayTemperatureHumidityWindPlayD4MildHighWeakYesD5CoolNormalWeakYesD6CoolNormalStrongNoD10MildNormalWeakYesD14MildHighStrongNoyesSunnyOvercastRainID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT70/100以outlook=“sunny”對(duì)應(yīng)的節(jié)點(diǎn)為例繼續(xù)劃分。對(duì)樣本劃分的信息熵：TemperatureHumidityWindPlayHotHighWeakNoHotHighStrongNoMildHighWeakNoCoolNormalWeakYesMildNormalStrongYesID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT71/100以屬性”temperature”為例計(jì)算信息增益，有3個(gè)屬性值hot，mild，cool。TemperaturePlayHotNoHotNoTemperaturePlayCoolYesTemperaturePlayMildNoMildYesID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT72/100屬性“temperature”的信息增益同理通過(guò)計(jì)算，得Humidity，Wind屬性的信息增益：通過(guò)比較，選擇信息增益最大的屬性”Humidity”作為當(dāng)前節(jié)點(diǎn)。ID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT73/100OutlookHumidity?yesSunnyOvercastRain進(jìn)一步生成的決策樹：yesNoNormalHighHumidityPlayHighNoHighNoHighNoNormalYesNormalYesID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT74/100以“outlook=‘Rain’”對(duì)應(yīng)的節(jié)點(diǎn)為例繼續(xù)劃分。對(duì)樣本劃分的信息熵：TemperatureHumidityWindPlayMildHighWeakYesCoolNormalWeakYesCoolNormalStrongNoMildNormalWeakYesMildHighStrongNoID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT75/100以屬性“temperature”為例計(jì)算信息增益，有2個(gè)屬性值mild，cool。TemperaturePlayMildYesMildYesMildNoTemperaturePlayCoolYesCoolNoID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT76/100屬性“temperature”的信息增益同理通過(guò)計(jì)算，得Humidity，Wind屬性的信息增益：通過(guò)比較，選擇信息增益最大的屬性”Wind”作為當(dāng)前節(jié)點(diǎn)。ID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT77/100最終生成的決策樹OutlookHumidityWindyesSunnyOvercastRainyesNoNormalHighyesNoweakstrongWindPlayWeakYesWeakYesStrongNoWeakYesStrongNoID3算法舉例2025/2/27?TheInstituteofBusinessIntelligence,HFUT78/100屬性選擇方法測(cè)試所有的屬性，對(duì)每個(gè)屬性分裂的好壞做出量化評(píng)價(jià)，選擇一個(gè)最好的分裂方式特征選擇策略：量化指標(biāo)，依賴于對(duì)集合不純度（impurity）的度量方法信息增益（informationgain）信息增益比率（gainratio）基尼系數(shù)（Giniindex）距離度量（distancemeasure）J-measureG統(tǒng)計(jì)

2統(tǒng)計(jì)證據(jù)權(quán)重（weightofevidence）最小描述長(zhǎng)度（MLP）正交法（orthogonalitymeasure）相關(guān)度（relevance）2025/2/27?TheInstituteofBusinessIntelligence,HFUT79/100信息增益與增益比率原理：選擇信息增益（比率）最大的屬性假設(shè)訓(xùn)練集T包含n個(gè)樣本，這些樣本分別屬于m個(gè)類，其中第i個(gè)類在T中出現(xiàn)的比例為pi，T的信息量:假設(shè)屬性A把集合T劃分成V個(gè)子集{T1,T2,…,Tv}，其中Ti所包含的樣本數(shù)為ni，那么劃分后的熵(entropy):信息增益（ID3）

Gain(A)=I(T)-E(A)增益比率（C4.5） GR(A)=Gain(A)/I(T)2025/2/27?TheInstituteofBusinessIntelligence,HFUT80/100基尼系數(shù)IBMIntelligentMiner如果T包含n類元素,第j類的元素出現(xiàn)的概率為pj，giniindex：假設(shè)屬性A把集合T劃分成V個(gè)子集{T1,T2,…,Tv}，其中Ti的樣本個(gè)數(shù)為ni，則Gini(A)：選擇Gini(A)最小的屬性，對(duì)結(jié)點(diǎn)進(jìn)行分割(測(cè)試每個(gè)屬性所有可能的分割方法)2025/2/27?TheInstituteofBusinessIntelligence,HFUT81/100基尼系數(shù)示例按照“天氣”分裂，得到三個(gè)子集{T1,T2,T3}OutlookPlayRainYesRainYesRainNoRainYesRainNoOutlookPlayOvercastYesOvercastYesOvercastYesOvercastYesOutlookPlaySunnyNoSunnyNoSunnyNoSunnyYesSunnyYes342.0)(145)(144)(145)(321=++=TGiniTGiniTGiniGini天氣2025/2/27?TheInstituteofBusinessIntelligence,HFUT82/100按照“溫度”分裂，得到三個(gè)子集{T1,T2,T3}DayOutlookTemperatureHumidityWindPlayD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo2025/2/27?TheInstituteofBusinessIntelligence,HFUT83/100基尼系數(shù)示例基尼系數(shù)示例（續(xù)）按照“濕度”分裂，得到兩個(gè)子集{T1,T2}按照“風(fēng)況”分裂，得到兩個(gè)子集{T1,T2}Gini(天氣)<Gini(濕度)<Gini(風(fēng)況)<Gini(溫度)，因此“天氣”是基于GiniIndex選擇策略的最佳分裂特征2025/2/27?TheInstituteofBusinessIntelligence,HFUT84/100決策樹的“過(guò)度擬合”問(wèn)題決策樹的過(guò)度擬合現(xiàn)象(overfitting)-過(guò)學(xué)習(xí)分支過(guò)多完全擬合的決策樹對(duì)新數(shù)據(jù)的預(yù)測(cè)性能較低產(chǎn)生原因訓(xùn)練集存在噪聲，為了與訓(xùn)練數(shù)據(jù)相一致，必然生成一些反映噪聲的分支，這些分支不僅會(huì)在新的決策問(wèn)題中導(dǎo)致錯(cuò)誤的預(yù)測(cè)，而且增加了模型的復(fù)雜性決策樹越小就越容易理解，存儲(chǔ)與傳輸?shù)拇鷥r(jià)也較小，但結(jié)點(diǎn)過(guò)少會(huì)造成準(zhǔn)確度下降，因此需在樹的規(guī)模與準(zhǔn)確度之間權(quán)衡2025/2/27?TheInstituteofBusinessIntelligence,HFUT85/100避免過(guò)度的兩種方法前剪枝提前終止樹的生長(zhǎng)后剪枝先構(gòu)造決策樹，再刪除多余分支2025/2/27?TheInstituteofBusinessIntelligence,HFUT86/100前剪枝(prepruning)由于決策樹學(xué)習(xí)要從候選集合中選擇滿足給定標(biāo)準(zhǔn)的最大化屬性，并且不回溯，也就是我們常說(shuō)的爬山策略，其選擇往往會(huì)是局部最優(yōu)而不是全局最優(yōu)。樹結(jié)構(gòu)越復(fù)雜，則過(guò)渡擬合發(fā)生的可能性越大。因此，要選擇簡(jiǎn)單的模型。Occam法則（又稱Occam剃刀OccamRazor）:具有相同泛化誤差的兩個(gè)模型，簡(jiǎn)單的模型比復(fù)雜的模型更可取。2025/2/27?TheInstituteofBusinessIntelligence,HFUT87/100前剪枝(prepruning)在生成決策樹的過(guò)程中，利用某些測(cè)試條件，決定是否繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分參數(shù)控制法：利用某些參數(shù)(結(jié)點(diǎn)的大小、樹的深度、頻率最高的類別樣本比例等)限制樹的增長(zhǎng)分裂閾值法：設(shè)定一個(gè)分裂閾值，只有分裂后的信息增益不小于該閾值，才保留分支，否則停止分裂2025/2/27?TheInstituteofBusinessIntelligence,HFUT88/100后剪枝(postpruning)生成完全擬合的決策樹，自下而上地逐層開始剪枝。如果刪除某個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)后，決策樹的準(zhǔn)確度（或其它評(píng)價(jià)指標(biāo)）并沒(méi)有(顯著)降低，那么就將該結(jié)點(diǎn)變?yōu)槿~結(jié)點(diǎn).2025/2/27?TheInstituteofBusinessIntelligence,HFUT89/100后剪枝法舉例AB負(fù)C正正負(fù)YYYNNN

一棵通過(guò)訓(xùn)練集合學(xué)好的決策樹2025/2/27?TheInstituteofBusinessIntelligence,HFUT90/100AB負(fù)C正正負(fù)YYYNNN實(shí)例ABC類別錯(cuò)分類1YYY+2YYY+3YYY+4YYY+5YYY+6YYN-*7YYN-*8YYN-*9YNY+10YNY+11YNY+12YNY+13YNN+*14YNN+*15YNN-16YNN-17YNN-18NNN-19NYN-20NYY-對(duì)以上的決策樹通過(guò)右側(cè)的驗(yàn)證集合進(jìn)行測(cè)試，發(fā)現(xiàn)其有5個(gè)錯(cuò)分類。2025/2/27?TheInstituteofBusinessIntelligence,HFUT91/100AB負(fù)C正正負(fù)YYYNNN{18，19，20}{1，2，3，45，6，7，8}{9，10，11，12}{13，14，15，16，17}錯(cuò)分類5個(gè)，6，7，8，13，142025/2/27?TheInstituteofBusinessIntelligence,HFUT92/100第1步將決策樹規(guī)則化規(guī)則1IFA=YANDB=Y

THEN+規(guī)則2IFA=YANDB=NANDC=Y

THEN+規(guī)則3IFA=YANDB=NANDC=N

THEN–規(guī)則4IFA=N

THEN-

AB負(fù)C正正負(fù)YYYNNN2025/2/27?TheInstituteofBusinessIntelligence,HFUT93/100規(guī)則1IF

A=YANDB=Y

THEN+規(guī)則2IFA=YANDB=NANDC=Y

THEN+規(guī)則3IFA=YANDB=NANDC=N

THEN–規(guī)則4IFA=N

THEN-

規(guī)則分類正確的數(shù)目分類錯(cuò)誤的數(shù)目精度1535/82404/43323/54303/3第2步規(guī)則精度的計(jì)算2025/2/27?TheInstituteofBusinessIntelligence,HFUT94/100規(guī)則2與規(guī)則4精度為100%，保留規(guī)則分類正確的數(shù)目分類錯(cuò)誤的數(shù)目精度1535/82404