DM 數(shù)據(jù)挖掘 3-1 分類與預(yù)測 QBai 21-08-2006

分類與預(yù)測Dr.QingyuanBaiSchoolofComputerScienceFacultyofMathematicsandComputerScience,FuzhouUniversityEmail:baiqy@1

分類和預(yù)測是數(shù)據(jù)挖掘中最基本也是最具豐富內(nèi)容的技術(shù)。一般來說，數(shù)據(jù)挖掘除數(shù)據(jù)預(yù)處理之外，主要基本技術(shù)為關(guān)聯(lián)規(guī)則、分類與預(yù)測、聚類。分類是區(qū)分抽象事務(wù)和具體事物的方法和能力，分類也是一種知識表示方法。

有人認為分類是人類具有的最基本知識。分類與預(yù)測2

預(yù)測是構(gòu)造和使用模型評估無標號樣本類（預(yù)測出類），或評估給定樣本可能具有的屬性值或值區(qū)間。用預(yù)測法預(yù)測類標號也稱為分類，用預(yù)測法預(yù)測連續(xù)值為預(yù)測。分類和預(yù)測是應(yīng)用最廣泛的方法。它不僅在數(shù)據(jù)挖掘有大量應(yīng)用，在其他學科也同樣有較好的應(yīng)用。分類與預(yù)測3分類和預(yù)測分類方法和預(yù)測方法已被許多學科研究機器學習事例學習、歸納學習、神經(jīng)元網(wǎng)絡(luò)學習模式識別特征提取，模式分類。專家系統(tǒng)專家系統(tǒng)中有許多是分類問題。統(tǒng)計學統(tǒng)計理論是分類的基礎(chǔ)。神經(jīng)生物學生物信息學Web技術(shù)4

圖像的區(qū)分模式的識別

指紋識別，人臉識別

語音識別，圖像識別醫(yī)療診斷信貸評估故障診斷

金融走勢股票分析客戶的分類信用卡評級納稅人分析文本分類網(wǎng)頁分類分類與預(yù)測在許多實際問題有很好應(yīng)用：5分類與預(yù)測

概述分類方法1決策(判定)樹歸納2貝葉斯方法3神經(jīng)元網(wǎng)絡(luò)4基于距離的分類方法基于案例的分類方法遺傳算法粗糙集方法模糊集方法關(guān)聯(lián)規(guī)則方法預(yù)測方法

1滑動平均

2線性回歸

2非線性回歸6概述：1.什么是分類（1）分類：

是給一個樣本（對象、元組、實例）按照給定分類體系用一定方法將其歸于某類。分類體系可能是人為的，也可能是學習到的（如聚類的得到的）。

71.什么是分類（2）分類的定義：

從給定樣本組成的數(shù)據(jù)集

和類集

分類就是給出一個映射樣本被分配到一個類，精確包含了被映射到其中的所有樣本。即：映射就是分類模型，通過樣本集和類集學習分類模型，按模型對給的新樣本分類。8分類分為兩步：分類第一步：通過帶有類別標記的樣本集來學習ｆ(模型/映射/函數(shù)），由于樣本的標記是人給定的，故稱有指導(dǎo)的學習。這個樣本集稱訓(xùn)練樣本集。若訓(xùn)練樣本集的樣本，典型且量多,學到的模型就會好。分類第二步：

任意給定一個沒有標記樣本，用學到的模型對其進行分類，即給出其類標記。為了測試模型的準確性，可用一個測試樣本集。1.什么是分類（3）9

分類方法學習器（訓(xùn)練器）分類器類1類2類m未被分類的數(shù)據(jù)訓(xùn)練例訓(xùn)練例訓(xùn)練例學習（訓(xùn)練）過程分類過程模型………10

訓(xùn)練樣本（數(shù)據(jù)）集

選那個屬性為類屬性由關(guān)心的問題而定，可為buys_computer,也可為credit_rating1234567891011121314屬性11

構(gòu)造模型（學習過程）分類學習算法IFage=’31..40’andIncome=‘high’THENCredit_rate=‘excellent’

訓(xùn)練數(shù)據(jù)集

學習到的分類器/模型12

分類模型訓(xùn)練數(shù)據(jù)集(JohnHenri,31..40,high)Credit_rate?回答新樣本的類（Excellent）新數(shù)據(jù)對新樣本分類過程132.什么是預(yù)測

是構(gòu)造模型來評估給定樣本的類或值。

對于離散值用分類方法預(yù)測其類

對于連續(xù)值問題用回歸方法來預(yù)測其值或值的區(qū)間。一般預(yù)測類也歸為分類，只把預(yù)測連續(xù)值（如回歸方法）為預(yù)測。143.分類預(yù)測的數(shù)據(jù)準備數(shù)據(jù)清理去噪聲:

補缺值:相關(guān)分析去無關(guān)屬性（特征），去冗余屬性數(shù)據(jù)變換概念分層數(shù)據(jù)規(guī)范化數(shù)據(jù)離散化154.常用的分類方法

決策樹貝葉斯方法神經(jīng)元網(wǎng)絡(luò)

K-近鄰方法

基于案例方法遺傳算法粗糙集方法模糊集方法

關(guān)聯(lián)規(guī)則方法支持向量機165.常用的預(yù)測方法分類法是對數(shù)據(jù)預(yù)測其類標號，但預(yù)測法是預(yù)測連續(xù)值，預(yù)測方法有：線性回歸多元回歸非線性回歸17決策樹方法18決策樹方法決策樹（DecisionTree)是類似流程圖的樹結(jié)構(gòu)。它是一棵樹，樹中每個內(nèi)部結(jié)點都表示一個屬性的測試，結(jié)點的每個分枝代表一個測試的輸出，每個葉結(jié)點代表一個類或類分布。決策樹是一種逼近離散值函數(shù)的方法，對噪聲數(shù)據(jù)有很好的健壯性，且能夠?qū)W習析取表達式。決策樹是一個有效的有指導(dǎo)的機器學習方法。作為一種分類的方法，為數(shù)據(jù)挖掘系統(tǒng)廣泛采用。它是一種歸納學習方法。19決策樹方法的發(fā)展決策樹方法是分類中最典型且用得最多的方法。決策樹方法是在歸納學習中最有代表性的方法。一般認為歸納學有兩個代表性的方法，一個為決策樹，一個為規(guī)則歸納。決策樹最早方法是1966年Hunt提出的CLS學習算法。以后有很多方法出現(xiàn)，其中最有影響的是J.R.Quinlan的ID3,C4.5方法。這些方法由于其有效性，被廣泛使用和開發(fā)為商品。

20決策樹1決策樹方法概念2決策樹構(gòu)造3決策樹剪枝4基本決策樹的歸納加強5決策樹的伸縮性問題6決策樹新方向7決策樹應(yīng)用211決策樹方法概念數(shù)據(jù)集：由多個屬性和一個決策屬性組成的數(shù)據(jù)集。數(shù)據(jù)劃分：通過對數(shù)據(jù)集的屬性依次按取值將數(shù)據(jù)集進行劃分，取一個屬性按其取值就把數(shù)據(jù)集分成幾個小的數(shù)據(jù)集，一直下去，到?jīng)Q策屬性為止，或按一定規(guī)則停止。22決策樹方法概念決策樹：由屬性逐次劃分就形成一棵樹，就稱決策樹決策規(guī)則由樹的根結(jié)點到葉結(jié)點屬性的合取就形成一條規(guī)則，所有規(guī)則的析取就形成一套一套規(guī)則。23

決策樹構(gòu)造方法：（1）給定一組帶有標記的樣本；（2）通過學習得到一棵樹；（3）將決策樹從根結(jié)點到葉結(jié)點形成合取的規(guī)則,所有葉結(jié)點形成的規(guī)則為析取規(guī)則。決策樹的基本問題是：（1）如何劃分樹的分枝，屬性選擇。（2）決策樹很大時需要剪枝，怎樣剪枝。所以劃分和剪枝是決策樹兩個關(guān)鍵問題。最典型算法：

ID3,C4.5,C5.0;決策樹方法概念24例子：數(shù)據(jù)集“buys_computer”25例子：

“buys_computer”的決策樹age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..4026例子：

“buys_computer”由決策樹生成規(guī)則IF“age<=30”ANDstudent=“no”THENbuys_computer=“no”,ORIF“age<=30”ANDstudent=“yes”THENbuys_computer=“yes”,ORIF“age<=30…40”THENbuys_computer=“yes”,ORIF“age>40”ANDcredit_rating=“excellent”THENbuys_computer=“no”,ORIF“agee>40”ANDcredit_rating=“fair”THENbuys_computer=“yes”272決策樹構(gòu)造決策樹構(gòu)造思路：1.給一個帶有類標簽的數(shù)據(jù)集2.選擇信息量大的屬性作為根結(jié)點3.根據(jù)根結(jié)點屬性的取值對數(shù)據(jù)集進行劃分，形成一個二叉（或多叉）樹。4.根據(jù)分叉將數(shù)據(jù)又分成幾個數(shù)據(jù)集。5.再遞歸用其余屬性對幾個數(shù)據(jù)集進行劃分，直到分類屬性為止，或規(guī)定的層次（剪枝）。28決策樹構(gòu)造的基本算法算法：Generate_decision_tree;//由給定數(shù)據(jù)集產(chǎn)生一棵決策樹輸入：訓(xùn)練樣本Samples;屬性集合attibute_list;輸出：一棵決策樹方法：1）創(chuàng)建結(jié)點N;2)ifSamples都在同一類Cthen3)返回N作為葉結(jié)點，以C類作為標記；4）ifattibute_list為空then5)返回N作為葉結(jié)點,標記為Samples中最普通的類；//多數(shù)表決6）選擇attibute_list中具有最高信息的屬性test_attribute;7)標記結(jié)點N為test_attribute；298）foreachTest_attribute中的已知值ai劃分samples9）由結(jié)點N長出來一個條件為Test_attribute=ai的分枝10）設(shè)si是samples中test_attribute=ai的樣本的集合；

//一個劃分11）ifsi為空then12)加上一個樹葉，標記為samples中最普通的類；13）else加上一個由Generate_decision_tree

（si，attibute_list－

Test_attribute）返回結(jié)點；30決策樹分支---屬性選擇方法

為了產(chǎn)生樹的分支在樹的每個結(jié)點上進行各屬性測試，來決定用那個屬性作為分支屬性，這種屬性測試稱屬性選擇度量或分裂的優(yōu)良性度量。選擇具有信息量大的屬性有許多方法。我們用ID3方法，該方法以信息增益作為屬性測試。信息增益是數(shù)據(jù)集的整體期望信息與根據(jù)某屬性A劃分成子集的期望信息之差。31信息熵：RQuinlan用在ID3中用信息熵來判斷屬性。一個隨機事件x發(fā)生的概率為P(x),如果x的所有取值為x1,x2,…xn,那么每個取值的概率為p(xi),p(x1)+p(x2)+…+p(xn)=1這樣就形成一個值空間和取值概率空間

x1x2x3……xnp(x1)p(x2)p(x3)…p(xn)p(xi)大說明其發(fā)生可能性大，說明其不確定性小，如p(xi)=1，就是確定的，不確定性為0。信息論中用一個自信息來定義其不確定性：//x的信息量

1log2----=-log2P(x)P(x)自信息的信息期望（信息熵）用-P(x)log2P(x)表示。322個取值的信息熵如x取值為兩個值，則P(x1)+P(x2)=1前者用p，后者為（1-p）,兩個給出的信息熵為：-Plog2P–(1-P）log2（1-P）

P33m個取值的信息熵如整個樣本為S個，有m個取值為Si（

i=1,2…m)整個樣本的信息熵：34信息增益的計算期望信息（信息熵）……屬性A對數(shù)據(jù)劃分的信息增益：

Gain(A)=I(s1,s2,..sm)-E(A)樣本集D,有S個樣本,共有m個類，每個類分別有S1,S2,…Sm個樣本，類1有S1個樣本，類m有Sm個樣本，取任意樣本為i

類的概率為Pi,在有了數(shù)據(jù)樣本情況下，用這個樣本集算出估計值。Pi的估計值=，用上述公式就可算出這個數(shù)據(jù)集分類所需的期望信息（信息熵）。35根據(jù)A劃分成子集的期望信息（屬性A情況下的熵，條件熵）……根據(jù)A屬性有v個取值將數(shù)據(jù)集劃分為v個子集s1,s2,…sv，第j個子集有樣本sj個，sj樣本也有m個類，各有樣本數(shù)為：S1j,S2j…Smj屬性第j個取值的期望信息為

I(S1j,S2j…Smj)=由于第j個屬性取值有樣本Sj個，占整個樣本S的Sj/S,所以為Sj樣本的信息熵為

Sj/S×I(S1j,S2j…Smj)sj36一個A屬性劃分之后的信息增益信息增益，就是熵的變化

Gain(A)=I(s1,s2,..sm)-E(A)37例子：

一個小孩根據(jù)天氣情況決定選擇在家學習

還是出去打網(wǎng)球的決策例子給出過去根據(jù)天氣情況的決定學習還是打球的情況表—決策表。2.根據(jù)決策表來學習決策樹。3.由決策樹來形成一套決策規(guī)則。4.給定當時的天氣情況。由決策樹判定是學習還是打球。38決策表（數(shù)據(jù)集）決策表有4個屬性，一個結(jié)論屬性，各屬性有2，3個取值。結(jié)論為Study或Play39樣本集整體的期望信息I(Study，play)=I(9,5)=914log2log2914514)(()514在例子中，分為2類，Study和Play，類Study9個，類Play5個，集合整體樣本為14個=0.940340屬性選擇根據(jù)各個屬性outlook，Temperature,Humidity,Windy,

來計算劃分后的信息熵41屬性選擇E(outlook)=對于outlook屬性，取值為sunny5Overcast4Rain5sunny5中類

study2類play3,Overcast4中類study4類play0，Rain5中類

study3

類play2。

2+314

4+014

3+214I(2,3）I(3,2）+I(4,0）+=0.694I(2,3）=0.971,I(4,0）=0,I(3,2）=0.97142屬性選擇

同樣可計算出：

E(Temperature),E(Humidity),E(Windy)

Gain(Temperature)=0.029Gain(Humidity)=0.151Gain(Wind)=0.0048這樣屬性outlook就作為第一分裂屬性。由outlook作為根結(jié)點，將數(shù)據(jù)分三部分。然后這三部分，還是按上述原則進行劃分。Gain(outlook)=I(study,play)-E(outlook)=0.940-0.694=0.24643信息增益計算：Log102=0.301,Log103=0.477,Log105=0.699,Log107=0.845;Log23=1.585,Log25=2.322.

第一次迭代時每個屬性的取值及在某個取值下的樣本子集的類別分布//P117.Outlookplay=‘y’play=‘n’I(C1,C2)子集份額E(A)--sunny13I4(1,3)=0.8113

4/14--overcast50I5(5,0)=05/14--rain32I5(3,2)=0.9715/14E=0.5786Temperatureplay=‘y’play=‘n’--hot22I4(2,2)=14/14--mild42I6(4,2)=0.91836/14--cold31I4(3,1)=0.81136/14E=0.9111Humidityplay=‘y’play=‘n’--normal34I7(3,4)=0.98527/14--humidity61I7(6,1)=0.59177/14E=0.775Windyplay=‘y’play=‘n’--false62I8(6,2)=0.81138/14--true33I6(3,3)=16/14E=0.892244outlookHumiditystudyWindysunny

OvercastRain按照分出的子集，再進行信息熵的計算再進行劃分。一直到葉結(jié)點或到規(guī)定層。生成決策樹45outlooksunny

OvercastRain再計算humidity再計算windy46由決策表生成的決策樹47決策樹形成規(guī)則IF(outlook=sunny∧Humidity=Normal）∨（outlook=Overcast)∨(outlook=Rain∧Wind=false)THENStudyIF(outlook=sunny∧Humidity=High∨(outlook=Rain∧Wind=true)THENPlay48用決策規(guī)則進行分類或預(yù)測給定一種天氣情況用套用規(guī)則就決定是Study還是Play。如：天晴，沒有風，氣溫不高，濕度不大。是在家學習還是出去玩。用決策規(guī)則天晴，濕度不大就study。49決策樹的構(gòu)造問題決策樹不唯一，由分支選擇來決定是一個怎樣的樹。分枝怎樣進行有不同偏向，信息熵是其中的一種。分枝由屬性劃分方法決定了樹的規(guī)模和形狀。屬性選擇不同得到的決策樹的規(guī)模不一樣。我們隨意選擇屬性會得到不同的樹。比如，我們從Temperature屬性劃分會得到下面的樹50由決策表生成的決策樹-2同一個例子，另一棵決策樹Temperatureoutlookstudystudywindyoutlook

windyhumidwindyhumidwindyoutlookstudyplayplaystudystudyplaystudystudyplaystudystudyplay51由樹-2也可產(chǎn)生一些規(guī)則也可由決策樹-2生成規(guī)則：

IF(temperature=cool∧outlook=sunny)∨………∨(……)THENStudyIF(temperature=cool∧outlook=rain∧Windy=true)∨………∨(……)THENPlay523決策樹剪枝為了提高效率和避免過擬合問題（提高樹的分類和預(yù)測能力,過擬合在有噪聲會對精度有影響）,要對決策樹剪枝：剪枝策略：1.先剪枝：決定提前對樹停止往下構(gòu)造，即不再生成（分裂）新結(jié)點。停止的那個點就為葉結(jié)點，這個葉結(jié)點的取值為到此處樣本集的最頻繁類（最多類別的那個類，或者為樣本的概率分布)。怎樣決定停止在那里？有很多策略：一種是定義樹的層數(shù)（如10層，就停止），一種是事先定義閾值，判定時屬性劃分時小于事先定義的閾值，就停止分裂。532.后剪枝：生成一個完全樹，然后對其剪枝。對一個大的樹剪去一部分。剪枝后的葉結(jié)點取值，也是用它先前的分枝中最頻繁類標記。理論上后剪枝比前剪枝好，但開銷大。544基本決策樹的歸納加強

歸納加強就是使決策樹適應(yīng)更多情況和更準確：對連續(xù)值，取一個劃分值，A≦V,A＞V.數(shù)據(jù)碎片問題：一個屬性取值太多。樹的分枝就太多，使得每個分枝樣本數(shù)太少，一個方法就是用二叉樹代替多叉樹，或者將一些取值歸一個分支，使分支減少，使每支樣本多些。根據(jù)情況不用信息增益，用其他方法。信息增益有傾斜，傾向于具有許多值的屬性。提出許多其他改進辦法。信息增益比，互信息，其它評價函數(shù)。55ID3算法開窗口取一部分訓(xùn)練例，構(gòu)造樹，再用其他例測試，通過了，樹就算訓(xùn)練完，不通過，將分錯的例，加入，再訓(xùn)練。56C4.5算法ID3方法的不足：有人質(zhì)疑ID3方法，用信息增益過分偏向取值多的屬性，為此R.Quinlan對ID3提出改進建議，給出C4.5方法。C4.5有兩點改進：（1）用信息增益比代替信息增益：

Gain(A)=I(s1,s2,..sm)-E(A)=GainRadio(A)=Gain(A)／SplitI(A)SplitI(A)=57C4.5(2)能處理連續(xù)屬性

ID3方法形成的的決策樹，對于每個屬性均為離散值屬性。C4.5處理連續(xù)屬性。處理方法：

根據(jù)連續(xù)屬性值進行排序，用不同的值對數(shù)據(jù)集進行動態(tài)劃分，把數(shù)據(jù)集分為兩部分，一部分大于某值，一部分小于某值。然后根據(jù)劃分進行增益比計算，計算最大的那個為最后劃分。目前商業(yè)上用的均為C4.5,或其改進型C5.0。586決策樹的伸縮性問題數(shù)據(jù)量大無法一次調(diào)入內(nèi)存，采用分塊，形成多個決策樹，然后用組合方法，確定其類別。

利用維歸約或特征約減，把數(shù)據(jù)中無用特征剪掉，使數(shù)據(jù)量減少。選樣方法：必須在數(shù)據(jù)一致性較好的情況下才可行。597決策樹新方向1.用Bagging與boosting方法來提高精度。有人通過實驗說明Bagging的決策數(shù)目要在20個左右較合適。2.多元樹方法：用多個屬性來分裂，把幾個屬性統(tǒng)一來考慮，這樣的分枝可能更有意義和分類更好。608決策樹的應(yīng)用決策樹有廣泛的應(yīng)用：醫(yī)療診斷：癥狀疾病信用卡的評級：各種特征信用等級圖像識別:圖像的特征可能的某種圖像故障診斷:各種故障特征可能的故障客戶的分類：客戶的特征客戶級別信貸評級：企業(yè)的特征信貸等級個人的特征信貸等級納稅分析：企業(yè)的特征納稅評級個人的特征納稅評級61例子：數(shù)據(jù)集“buys_computer”62例子：

“buys_computer”的決策樹age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..4063決策樹的應(yīng)用例子:UabcdeUabcde11211014442222135501541232314151164424141515117412525221101841311622152195351072332020525118234102133330924341223134110322102334351112231024334101241141253542013412102635230E為決策因子,選擇d為類/決策屬性,構(gòu)造相應(yīng)的決策樹.64假設(shè)一組事務(wù)及涉及的項目如下：TIDABCDET111100T211111T310110T410111T511110T600101E為分類屬性.利用決策樹對(1,0,1,0)進行分類.log102=0.3010,log103=0.4771,log105=0.6990log107=0.8451,log2X=log10X/log102Apriori算法中的例子.65I(C0,C1)=-3/6*log2(3/6)-3/6*log2(3/6)=1對屬性A,取值0有1個,屬C0的0個,C1的1個;//I1(0,1)=0取值1有5個,屬C0的3個,C1的2個;//I5(3,2)=0.9712E(A)=1/6*I1(0,1)+5/6*I5(3,2)=0.8093Gain(A)=I(C0,C1)-E(A)=0.1907對屬性B,取值0有3個,屬C0的2個,C1的1個;//I3(2,1)=0.9183取值1有3個,屬C0的1個,C1的2個;//I3(1,2)=0.9183E(B)=3/6*I3(2,1)+3/6*I3(2,1)=0.9183Gain(B)=I(C0,C1)-E(B)=0.0817Apriori算法.66對屬性C,取值0有0個,屬C0的0個,C1的0個;//I0(0,0)=0取值1有6個,屬C0的3個,C1的3個;//I6(3,3)=1E(C)=0/6*I0(0,0)+6/6*I6(3,3)=1Gain(C)=I(C0,C1)-E(C)=0對屬性D,取值0有2個,屬C0的1個,C1的1個;//I2(1,1)=1取值1有4個,屬C0的2個,C1的2個;//I4(2,2)=1E(D)=2/6*I2(1,1)+4/6*I4(2,2)=1Gain(D)=I(C0,C1)-E(D)=0Apriori算法.67首先,按屬性A進行分裂.然后考慮滿足A=1的子集(5條記錄):TIDBCDET11100T21111T30110T40111T51110對該子集,I(C0,C1)=I5(3,2)=3/5*log22(5/3)+2/5*log22(5/2)=log105/log102-0.6*log103/log102-0.4=0.9712對屬性B,取值0有2個,屬C0的1個,C1的1個;//I2(1,1)=1取值1有3個,屬C0的2個,C1的1個;//I3(2,1)=0.9183E(B)=2/5*I2(1,1)+3/5*I3(2,1)=0.9510Gain(B)=I(C0,C1)-E(B)=0.9712-0.9510=0.0202Apriori算法.68對屬性C,取值0有0個,屬C0的0個,C1的0個;//I0(0,0)=0取值1有5個,屬C0的3個,C1的2個;//I5(3,2)=0.9712E(C)=0/5*I0(0,0)+5/5*I5(3,2)=0.9712Gain(C)=I(C0,C1)-E(C)=0對屬性D,取值0有1個,屬C0的1個,C1的0個;//I1(1,0)=0取值1有4個,屬C0的2個,C1的2個;//I4(2,2)=1E(D)=1/5*I1(1,0)+4/5*I4(2,2)=0.8Gain(D)=I(C0,C1)-E(D)=0.9712-0.8=0.1712Apriori算法.69現(xiàn)在,按屬性D進行分裂.然后考慮滿足D=1的子集(4條記錄):TIDBCET2111T3010T4011T5110對該子集,I(C0,C1)=I4(2,2)=1對屬性B,取值0有2個,屬C0的1個,C1的1個;//I2(1,1)=1取值1有2個,屬C0的1個,C1的1個;//I2(1,1)=1E(B)=2/4*I2(1,1)+2/4*I2(1,1)=1Gain(B)=I(C0,C1)-E(B)=0對屬性C,取值0有0個,屬C0的0個,C1的0個;//I0(0,0)=0取值1有4個,屬C0的2個,C1的2個;//I4(2,2)=1E(C)=0/4*I0(0,0)+4/4*I4(2,2)=1Gain(C)=I(C0,C1)-E(C)=0按屬性B或C分裂均可.//實際上,原數(shù)據(jù)庫中有矛盾的元組!Apriori算法.70練習:帶有標記的數(shù)據(jù)集71log102=0.3010,log103=0.4771,log105=0.6990log107=0.8451,log2X=log10X/log102C0表示buy_computers=yes,C1表示buy_computers=no.I(C0,C1)=I14(10,4)=-10/14*log2(10/14)-4/14*log2(4/14)=0.8631對屬性Age,取值<=30有5個,屬C0的4個,C1的1個;//I5(4,1)=0.7223取值31..40有4個,屬C0的3個,C1的1個;//I4(3,1)=0.8112取值>40有5個,屬C0的3個,C1的2個;//I5(3,2)=0.9712E(Age)=5/14*I5(4,1)+4/14*I4(3,1)+5/14*I5(3,2)=0.8367Gain(Age)=I(C0,C1)-E(Age)=0.8631-0.8367=0.0264練習:帶有標記的數(shù)據(jù)集72對屬性income,取值high有3個,屬C0的2個,C1的1個;//I3(2,1)=0.9183取值medium有6個,屬C0的4個,C1的2個;//I6(4,2)=0.9183取值low有5個,屬C0的4個,C1的1個;//I5(4,1)=0.7223E(income)=3/14*I3(2,1)+6/14*I6(4,2)+5/14*I5(4,1)=0.8483Gain(income)=I(C0,C1)-E(income)=0.0148對屬性student,取值yes有8個,屬C0的5個,C1的3個;//I8(5,3)=0.9542取值no有6個,屬C0的5個,C1的1個;//I6(5,1)=0.6498E(student)=8/14*I8(5,3)+6/14*I6(5,1)=0.8238Gain(student)=I(C0,C1)-E(student)=0.0393(最大值.)練習:帶有標記的數(shù)據(jù)集73studentyes

no按照分出的子集，再進行信息熵的計算再進行劃分。一直到葉結(jié)點或到規(guī)定層。生成決策樹:??74練習:帶有標記的數(shù)據(jù)集75對student=yes分支:I(C0,C1)=I8(5,3)=0.9542對屬性Age,取值<=30有3個,屬C0的2個,C1的1個;//I3(2,1)=0.9183取值31..40有2個,屬C0的2個,C1的0個;//I2(2,0)=0取值>40有3個,屬C0的1個,C1的2個;//I3(1,2)=0.9183E(Age)=3/8*I3(2,1)+3/8*I3(1,2)=0.6887Gain(Age)=I(C0,C1)-E(Age)=0.9542-0.6887=0.2655練習:帶有標記的數(shù)據(jù)集76對屬性income,取值high有1個,屬C0的1個,C1的0個;//I1(1,0)=0取值medium有3個,屬C0的1個,C1的2個;//I3(1,2)=0.9183取值low有4個,屬C0的3個,C1的1個;//I4(3,1)=0.8112E(income)=3/8*I3(1,2)+4/8*I4(3,1)=0.7500Gain(income)=I(C0,C1)-E(income)=0.9542-0.75=0.2042按age屬性進行第二次分裂.局部決策樹如下:練習:帶有標記的數(shù)據(jù)集77studentyes

no生成決策樹:age?78對student=no分支:I(C0,C1)=I6(5,1)=0.6498對屬性Age,取值<=30有2個,屬C0的2個,C1的0個;//I2(2,0)=0取值31..40有2個,屬C0的1個,C1的1個;//I2(1,1)=1取值>40有2個,屬C0的2個,C1的0個;//I2(2,0)=0E(Age)=2/6*I2(1,1)=0.3333Gain(Age)=I(C0,C1)-E(Age)=0.6498-0.3333=0.3165練習:帶有標記的數(shù)據(jù)集79對屬性income,取值high有2個,屬C0的1個,C1的1