如何修改基本決策樹算法

1、如何修改基本決策樹算法，以便考慮每個(gè)廣義數(shù)據(jù)元組(即每一行)的count?使用修改過的算法，構(gòu)造給定數(shù)據(jù)的決策樹。給定一個(gè)數(shù)據(jù)元組，它的屬性department,age和salary的值分別為“systems”“2630”，和“46K50K”該元組status的樸素貝葉斯分類是什么？為給定的數(shù)據(jù)設(shè)計(jì)一個(gè)多層前饋神經(jīng)網(wǎng)絡(luò)。標(biāo)記輸入和輸出層節(jié)點(diǎn)。使用上面得到的多層前饋神經(jīng)網(wǎng)絡(luò)，給定訓(xùn)練實(shí)例(sales,senior,3135,46K50K),給出后向傳播算法一次迭代后的權(quán)重值。指出你使用的初始權(quán)重和偏倚以及學(xué)習(xí)率。解答：如何修改基本決策樹算法，以便考慮每個(gè)廣義數(shù)據(jù)元組(即每一行)的count？使用

2、修改過的算法，構(gòu)造給定數(shù)據(jù)的決策樹。給定一個(gè)數(shù)據(jù)元組，它的屬性department，age和salary的值分別為“systems”，“2630”，和“46K50K”。該元組status的樸素貝葉斯分類是什么？解一：設(shè)元組的各個(gè)屬性之間相互獨(dú)立，所以先求每個(gè)屬性的類條件概率：P(systems|junior)=(20+3)/(40+40+20+3+4+6)=23/113;P(26-30|junior)=(40+3+6)/113=49/113；P(46K-50K|junior)=(20+3)/113=23/113；*.*X=(department=system,age=2630,salary=4

3、6K50K)；P(Xljunior)=P(systemsljunior)P(26-30ljunior)P(46K-50Kljunior)=23x49x23/1133=25921/1442897=0.01796；P(systems|senior)=(5+3)/(30+5+3+10+4)=23/52;P(26-30lsenior)=(0)/53=0;P(46K-50Klsenior)=(30+10)/52=40/52；*.*X=(department=system,age=2630,salary=46K50K)；P(Xlsenior)=P(systemslsenior)P(26-30lsenior

4、)P(46K-50Klsenior)=0;P(junior)=113/165=0.68；*.*P(senior)=52/165=0.32；P(Xljunior)P(junior)=0.01796X0.68=0.01221280=0=P(Xlsenior)P(senior)；所以：樸素貝葉斯分類器將X分到j(luò)unior類。解二：設(shè)元組的各屬性之間不獨(dú)立，其聯(lián)合概率不能寫成份量相乘的形式。所以已知：X=(department=system,age=2630,salary=46K50K)，元組總數(shù)為：30+40+40+20+5+3+3+10+4+4+6=165。先驗(yàn)概率：當(dāng)status=senior時(shí)

5、，元組總數(shù)為：30+5+3+10+4=52，P(senior)=52/165=0.32；當(dāng)status=junior時(shí)，元組總數(shù)為：40+40+20+3+4+6=113，P(junior)=113/165=0.68；因?yàn)閟tatus=senior狀態(tài)沒有對應(yīng)的age=2630區(qū)間，所以：P(Xlsenior)=0；因?yàn)閟tatus=junior狀態(tài)對應(yīng)的partment=systems、age=2630區(qū)間的總元組數(shù)為：3，所以：P(Xljunior)=3/113；因?yàn)椋篜(Xljunior)P(junior)=3/113X113/165=0.0180=P(Xlsenior)P(senior)

6、；所以：樸素貝葉斯分類器將X分到j(luò)unior類。為給定的數(shù)據(jù)設(shè)計(jì)一個(gè)多層前饋神經(jīng)網(wǎng)絡(luò)。標(biāo)記輸入和輸出層節(jié)點(diǎn)。使用上面得到的多層前饋神經(jīng)網(wǎng)絡(luò)，給定訓(xùn)練實(shí)例(sales,senior,3135,46K50K),給出后向傳播算法一次迭代后的權(quán)重值。指出你使用的初始權(quán)重和偏倚以及學(xué)習(xí)率。7.3.1判定樹歸納7.3.1判定樹歸納判定樹歸納的基本算法是貪心算法，它以自頂向下遞歸的劃分-控制方式構(gòu)造判定樹。算法在圖7.3中，是一種著名的判定樹算法ID3版本。算法的擴(kuò)展將在7.3.2到7.3.6小節(jié)討論。算法的基本策略如下：樹以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開始（步驟1）。如果樣本都在同一個(gè)類，則該結(jié)點(diǎn)成為樹葉，并用

7、該類標(biāo)號(hào)（步驟2和3）。否則，算法使用稱為信息增益的基于熵的度量作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性（步驟6）。該屬性成為該結(jié)點(diǎn)的“測試”或“判定”屬性（步驟7）。在算法的該版本中，所有的屬性都是分類的，即離散值。連續(xù)屬性必須離散化。對測試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分枝，并據(jù)此劃分樣本（步驟8-10）。算法使用同樣的過程，遞歸地形成每個(gè)劃分上的樣本判定樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)結(jié)點(diǎn)上，就不必該結(jié)點(diǎn)的任何后代上考慮它（步驟13）。遞歸劃分步驟僅當(dāng)下列條件之一成立停止：（a）給定結(jié)點(diǎn)的所有樣本屬于同一類（步驟2和3）。（b）沒有剩余屬性可以用來進(jìn)一步劃分樣本（步驟4）。在此情況下，使用多

8、數(shù)表決（步驟5）。這涉及將給定的結(jié)點(diǎn)轉(zhuǎn)換成樹葉，并用樣本中的多數(shù)所在的類標(biāo)記它。替換地，可以存放結(jié)點(diǎn)樣本的類分布。（c）分枝test_attribute=a沒有樣本（步驟11）。在這種情況下，以samples中i的多數(shù)類創(chuàng)建一個(gè)樹葉（步驟12）。屬性選擇度量在樹的每個(gè)結(jié)點(diǎn)上使用信息增益度量選擇測試屬性。這種度量稱作屬性選擇度量或分裂的優(yōu)劣度量。選擇具有最高信息增益（或最大熵壓縮）的屬性作為當(dāng)前結(jié)點(diǎn)的測試屬性。該屬性使得對結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或“不純性”。這種信息理論方法使得對一個(gè)對象分類所需的期望測試數(shù)目最小，并確保找到一棵簡單的（但不必是最簡單的）樹。

9、設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類C（i=i1,.,m）。設(shè)s.是類C中的樣本數(shù)。對一個(gè)給定的樣本分類所需的期望信息由下式給出：ii1（s，s，,S）二乙p.log（p.）12mi2ii=1（7.1）其中，p.是任意樣本屬于C.的概率，并用s./s估計(jì)。注意，對數(shù)函數(shù)以2為底，因?yàn)閕ii信息用二進(jìn)位編碼。設(shè)屬性A具有v個(gè)不同值何，a?？梢杂脤傩訟將S劃分為v個(gè)子集、，S；1v1v其中，S.包含S中這樣一些樣本，它們在A上具有值a.。如果A選作測試屬性（即，最好的jj劃分屬性），則這些子集對應(yīng)于由包含集合S的結(jié)點(diǎn)生長出來的分枝。設(shè)s.是子集S.中類.jjC.的

10、樣本數(shù)。根據(jù)A劃分子集的熵或期望信息由下式給出：.vS+SE（A）=工1jj（s,.,s）S1jmjj=1（7.2）S12=4S22=0s+.+s項(xiàng)1jmj充當(dāng)?shù)趈個(gè)子集的權(quán)，并且等于子集(即，A值為a.)中的樣本個(gè)數(shù)除sj以S中的樣本總數(shù)。熵值越小，子集劃分的純度越高。注意，對于給定的子集S.，jI(s,S，,S)=-p.log(p.)1j2jmjij2iji=1(7.3)s其中，Pj=茴，是Sj中的樣本屬于q的概率。j在A上分枝將獲得的編碼信息是Gain(A)=I(s,s,.,s)-E(A)12m(7.4)換言之，Gain(A)是由于知道屬性A的值而導(dǎo)致的熵的期望壓縮。算法計(jì)算每個(gè)屬性的信

11、息增益。具有最高信息增益的屬性選作給定集合S的測試屬性。創(chuàng)建一個(gè)結(jié)點(diǎn)，并以該屬性標(biāo)記，對屬性的每個(gè)值創(chuàng)建分枝，并據(jù)此劃分樣本。例7.2判定樹歸納。表7.1給出了取自AllElectronics顧客數(shù)據(jù)庫數(shù)據(jù)元組訓(xùn)練集。(該數(shù)據(jù)取自Qui86)。類標(biāo)號(hào)屬性buys_computer有兩個(gè)不同值(即,yes,no)，因此有兩個(gè)不同的類(m=2)。設(shè)類q對應(yīng)于yes，而類C2對應(yīng)于no。類yes有9個(gè)樣本，類no有5個(gè)樣本。為計(jì)算每個(gè)屬性的信息增益，我們首先使用(7.1)式，計(jì)算對給定樣本分類所需的期望信息：9955I(s,s)=I(9,5)=-9log9log=0.940121421414214表

12、7.1AllElectronics顧客數(shù)據(jù)庫訓(xùn)練數(shù)據(jù)元組RIDageincomestudentcreditratingClass:buyscomputer1=30highnofairno240mediumnofairyes540lowyesfairyes640lowyesexcellentno731.40lowyesexcellentyes8=30mediumnofairno940mediumyesfairyes1140mediumnoexcellentno下一步，我們需要計(jì)算每個(gè)屬性的熵。讓我們從屬性age開始。我們需要觀察age的每個(gè)樣本值的yes和no分布。我們對每個(gè)分布計(jì)算期望信息。對

13、于age=”=30”對于age=”31.40”對于age=”40”s=211S21=3I(S115S21)=0.971I(s,s)=01222I(s,s)=0.971使用(7.2)式，如果樣本按age劃分，對一個(gè)給定的樣本分類所需的期望信息為:545E(age)=I(s,s)+I(s,s)+I(s,s)=0.694141121141222141323因此，這種劃分的信息增益是gain(age)=I(,s)一E(age)=0.246類似地，我們可以計(jì)算Gain(income)=0.029,Gain(student)=0.151和Gain(credit_rating)=0.048。由于age在屬性

14、中具有最高信息增益，它被選作測試屬性創(chuàng)建一個(gè)結(jié)點(diǎn)，用age標(biāo)記，并對于每個(gè)屬性值，引出一個(gè)分枝。樣本據(jù)此劃分，如圖7.4所示。注意，落在分區(qū)age=“31.40”的樣本都屬于同一類。由于它們都屬于同一類yes,因此要在該分枝的端點(diǎn)創(chuàng)建一個(gè)樹葉，并用yes標(biāo)記。算法返回的最終判定樹如圖7.2所示。mcLimestudentcreditratingclasshighhighmediumlowmedium1LUnonoyesyesfail-excellentfanfanexcellenty已呂yesiiLCumestudentcreditratingclassmediumlowlowmediumme

15、diumyesy已呂y已呂fairfairexcellentfairexcellentyesjresyesiiLCumestudentcreditratingclasshighlowmediuinhighnoyes1LUyesfanexcellentexcellentfany已呂yesyesyes圖7.4:屬性age具有最高信息增益，因此成為判定樹根的測試屬性。由每個(gè)age引出分枝，樣本據(jù)此劃分總而言之，判定樹歸納算法已在廣泛的應(yīng)用領(lǐng)域用于分類。這種系統(tǒng)不使用領(lǐng)域知識(shí)判定樹歸納的學(xué)習(xí)和分類步驟通常很快。7.4.2樸素貝葉斯分類樸素貝葉斯分類，或簡單貝葉斯分類的工作過程如下：1-每個(gè)數(shù)據(jù)樣本用一

16、個(gè)n維特征向量X=X1,x2,xn表示描述由屬性A1,A2,An對樣本的*個(gè)度量。假定有m個(gè)類C,CC。給定一個(gè)未知的數(shù)據(jù)樣本X(即，沒有類標(biāo)號(hào))，分類法將預(yù)測X屬于具有最高后驗(yàn)12m概率(條件X下)的類。即，樸素貝葉斯分類將未知的樣本分配給類C,當(dāng)且僅當(dāng)：iP(CIX)P(CIX)1jP(XIC)P(C)1jmj豐i.iijj換言之，X被指派到其P(XIC.)P(C.)最大的類c。iii“貝葉斯分類的效率如何？”理論上講，與其它所有分類算法相比，貝葉斯分類具有最小的出錯(cuò)率。然而，實(shí)踐中并非總是如此。這是由于對其應(yīng)用的假定(如，類條件獨(dú)立性)的不正確性，以及缺乏可用的概率數(shù)據(jù)造成的。然而，種種

17、實(shí)驗(yàn)研究表明，與判定樹和神經(jīng)網(wǎng)絡(luò)分類算法相比，在某些領(lǐng)域，該分類算法可以與之媲美。貝葉斯分類還可以用來為不直接使用貝葉斯定理的其它分類算法提供理論判定。例如，在某種假定下，可以證明正如樸素貝葉斯分類一樣，許多神經(jīng)網(wǎng)絡(luò)和曲線擬合算法輸出最大的后驗(yàn)假定。例7.4使用樸素貝葉斯分類預(yù)測類標(biāo)號(hào):給定與例7.2判定樹歸納相同的訓(xùn)練數(shù)據(jù)，我們希望使用樸素貝葉斯分類預(yù)測一個(gè)未知樣本的類標(biāo)號(hào)。訓(xùn)練數(shù)據(jù)在表7.1中。數(shù)據(jù)樣本用屬性age,income,student和credit_rating苗述。類標(biāo)號(hào)屬性buys_computer具有兩個(gè)不同值(即，yes,no)。設(shè)q對應(yīng)于類buys_computer二“

18、yes”，而C2對應(yīng)于類buys_computer=“no”。我們希望分類的未知樣本為：X=(age=30,income=medium,student=yes,credit_rating=fair).我們需要最大化P(XIc.)P(C.)，i=1,2。每個(gè)類的先驗(yàn)概率P(C.)可以根據(jù)訓(xùn)練樣本計(jì)算：P(buys_computer=yes)=9/14=0.643P(buys_computer=no)=5/14=0.357為計(jì)算P(XICj)，i=1,2。我們計(jì)算下面的條件概率：P(age=“30”|buys_computer=“yes”)=2/9=0.222P(age=“30”|buys_computer=“no”)=3/5=0.600P(income=“medium”|buys_computer=4/9=“yes”)0.444P(income=“medium”|buys_computer=2/5=“no”)0.400P(student=“yes”|buys_computer=6/9=“yes”)0.667P(student=“yes”|buys_computer=1/5=“no”)0.200P(credit_rating=“fair”|=6/9=buys_computer=“yes”)0.667P(credit_rating=“fair”|=2/5=buys_co