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

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

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

有人認(rèn)為分類(lèi)是人類(lèi)具有的最基本知識(shí)。分類(lèi)與預(yù)測(cè)2

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

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

指紋識(shí)別，人臉識(shí)別

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

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

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

1滑動(dòng)平均

2線(xiàn)性回歸

2非線(xiàn)性回歸6概述：1.什么是分類(lèi)（1）分類(lèi)：

是給一個(gè)樣本（對(duì)象、元組、實(shí)例）按照給定分類(lèi)體系用一定方法將其歸于某類(lèi)。分類(lèi)體系可能是人為的，也可能是學(xué)習(xí)到的（如聚類(lèi)的得到的）。

71.什么是分類(lèi)（2）分類(lèi)的定義：

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

和類(lèi)集

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

任意給定一個(gè)沒(méi)有標(biāo)記樣本，用學(xué)到的模型對(duì)其進(jìn)行分類(lèi)，即給出其類(lèi)標(biāo)記。為了測(cè)試模型的準(zhǔn)確性，可用一個(gè)測(cè)試樣本集。1.什么是分類(lèi)（3）9

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

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

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

構(gòu)造模型（學(xué)習(xí)過(guò)程）分類(lèi)學(xué)習(xí)算法IFage=’31..40’andIncome=‘high’THENCredit_rate=‘excellent’

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

學(xué)習(xí)到的分類(lèi)器/模型12

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

是構(gòu)造模型來(lái)評(píng)估給定樣本的類(lèi)或值。

對(duì)于離散值用分類(lèi)方法預(yù)測(cè)其類(lèi)

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

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

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

K-近鄰方法

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

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

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

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

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

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

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

//一個(gè)劃分11）ifsi為空then12)加上一個(gè)樹(shù)葉，標(biāo)記為samples中最普通的類(lèi)；13）else加上一個(gè)由Generate_decision_tree

（si，attibute_list－

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

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

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

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

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

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

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

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

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

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

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

一個(gè)小孩根據(jù)天氣情況決定選擇在家學(xué)習(xí)

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

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

study2類(lèi)play3,Overcast4中類(lèi)study4類(lèi)play0，Rain5中類(lèi)

study3

類(lèi)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屬性選擇

同樣可計(jì)算出：

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

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

第一次迭代時(shí)每個(gè)屬性的取值及在某個(gè)取值下的樣本子集的類(lèi)別分布//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按照分出的子集，再進(jìn)行信息熵的計(jì)算再進(jìn)行劃分。一直到葉結(jié)點(diǎn)或到規(guī)定層。生成決策樹(shù)45outlooksunny

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

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

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

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

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

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

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

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

“buys_computer”的決策樹(shù)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..4063決策樹(shù)的應(yīng)用例子:UabcdeUabcde11211014442222135501541232314151164424141515117412525221101841311622152195351072332020525118234102133330924341223134110322102334351112231024334101241141253542013412102635230E為決策因子,選擇d為類(lèi)/決策屬性,構(gòu)造相應(yīng)的決策樹(shù).64假設(shè)一組事務(wù)及涉及的項(xiàng)目如下：TIDABCDET111100T211111T310110T410111T511110T600101E為分類(lèi)屬性.利用決策樹(shù)對(duì)(1,0,1,0)進(jìn)行分類(lèi).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對(duì)屬性A,取值0有1個(gè),屬C0的0個(gè),C1的1個(gè);//I1(0,1)=0取值1有5個(gè),屬C0的3個(gè),C1的2個(gè);//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對(duì)屬性B,取值0有3個(gè),屬C0的2個(gè),C1的1個(gè);//I3(2,1)=0.9183取值1有3個(gè),屬C0的1個(gè),C1的2個(gè);//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對(duì)屬性C,取值0有0個(gè),屬C0的0個(gè),C1的0個(gè);//I0(0,0)=0取值1有6個(gè),屬C0的3個(gè),C1的3個(gè);//I6(3,3)=1E(C)=0/6*I0(0,0)+6/6*I6(3,3)=1Gain(C)=I(C0,C1)-E(C)=0對(duì)屬性D,取值0有2個(gè),屬C0的1個(gè),C1的1個(gè);//I2(1,1)=1取值1有4個(gè),屬C0的2個(gè),C1的2個(gè);//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進(jìn)行分裂.然后考慮滿(mǎn)足A=1的子集(5條記錄):TIDBCDET11100T21111T30110T40111T51110對(duì)該子集,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對(duì)屬性B,取值0有2個(gè),屬C0的1個(gè),C1的1個(gè);//I2(1,1)=1取值1有3個(gè),屬C0的2個(gè),C1的1個(gè);//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對(duì)屬性C,取值0有0個(gè),屬C0的0個(gè),C1的0個(gè);//I0(0,0)=0取值1有5個(gè),屬C0的3個(gè),C1的2個(gè);//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對(duì)屬性D,取值0有1個(gè),屬C0的1個(gè),C1的0個(gè);//I1(1,0)=0取值1有4個(gè),屬C0的2個(gè),C1的2個(gè);//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進(jìn)行分裂.然后考慮滿(mǎn)足D=1的子集(4條記錄):TIDBCET2111T3010T4011T5110對(duì)該子集,I(C0,C1)=I4(2,2)=1對(duì)屬性B,取值0有2個(gè),屬C0的1個(gè),C1的1個(gè);//I2(1,1)=1取值1有2個(gè),屬C0的1個(gè),C1的1個(gè);//I2(1,1)=1E(B)=2/4*I2(1,1)+2/4*I2(1,1)=1Gain(B)=I(C0,C1)-E(B)=0對(duì)屬性C,取值0有0個(gè),屬C0的0個(gè),C1的0個(gè);//I0(0,0)=0取值1有4個(gè),屬C0的2個(gè),C1的2個(gè);//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í)際上,原數(shù)據(jù)庫(kù)中有矛盾的元組!Apriori算法.70練習(xí):帶有標(biāo)記的數(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對(duì)屬性Age,取值<=30有5個(gè),屬C0的4個(gè),C1的1個(gè);//I5(4,1)=0.7223取值31..40有4個(gè),屬C0的3個(gè),C1的1個(gè);//I4(3,1)=0.8112取值>40有5個(gè),屬C0的3個(gè),C1的2個(gè);//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練習(xí):帶有標(biāo)記的數(shù)據(jù)集72對(duì)屬性income,取值high有3個(gè),屬C0的2個(gè),C1的1個(gè);//I3(2,1)=0.9183取值medium有6個(gè),屬C0的4個(gè),C1的2個(gè);//I6(4,2)=0.9183取值low有5個(gè),屬C0的4個(gè),C1的1個(gè);//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對(duì)屬性student,取值yes有8個(gè),屬C0的5個(gè),C1的3個(gè);//I8(5,3)=0.9542取值no有6個(gè),屬C0的5個(gè),C1的1個(gè);//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(最大值.)練習(xí):帶有標(biāo)記的數(shù)據(jù)集73studentyes

no按照分出的子集，再進(jìn)行信息熵的計(jì)算再進(jìn)行劃分。一直到葉結(jié)點(diǎn)或到規(guī)定層。生成決策樹(shù):??74練習(xí):帶有標(biāo)記的數(shù)據(jù)集75對(duì)student=yes分支:I(C0,C1)=I8(5,3)=0.9542對(duì)屬性Age,取值<=30有3個(gè),屬C0的2個(gè),C1的1個(gè);//I3(2,1)=0.9183取值31..40有2個(gè),屬C0的2個(gè),C1的0個(gè);//I2(2,0)=0取值>40有3個(gè),屬C0的1個(gè),C1的2個(gè);//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練習(xí):帶有標(biāo)記的數(shù)據(jù)集76對(duì)屬性income,取值high有1個(gè),屬C0的1個(gè),C1的0個(gè);//I1(1,0)=0取值medium有3個(gè),屬C0的1個(gè),C1的2個(gè);//I3(1,2)=0.9183取值low有4個(gè),屬C0的3個(gè),C1的1個(gè);//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屬性進(jìn)行第二次分裂.局部決策樹(shù)如下:練習(xí):帶有標(biāo)記的數(shù)據(jù)集77studentyes

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