機(jī)器學(xué)習(xí)決策樹(shù)算法

1、 山東大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：決策樹(shù)算法ID3學(xué)號(hào)： 日期：班級(jí)： 2014級(jí)4班姓名： Email：實(shí)驗(yàn)?zāi)康模? 熟悉matlab環(huán)境及相關(guān)函數(shù)的熟練使用。2 學(xué)習(xí)如何構(gòu)造一棵決策樹(shù)，并且用matlab畫(huà)出樹(shù)形狀。3 學(xué)習(xí)如何使用一棵決策樹(shù)，即將測(cè)試數(shù)值代入時(shí)，如何判斷屬于哪一類。4 會(huì)寫測(cè)試集代入的分類表達(dá)式和類別的邏輯表達(dá)式并化簡(jiǎn)。5 分析該算法準(zhǔn)確性。硬件環(huán)境：  windows10操作系統(tǒng)軟件環(huán)境： matlab環(huán)境，Azure ML平臺(tái)實(shí)驗(yàn)步驟：一、背景知識(shí)及原理決策樹(shù)算法：樹(shù)狀結(jié)構(gòu)，每一個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)分類決策樹(shù)方法在分類、預(yù)測(cè)、規(guī)則提取等領(lǐng)域有著廣泛的應(yīng)用

2、。在20世紀(jì)70年代后期和80年代初期，機(jī)器學(xué)習(xí)研究者J.Ross Quinilan提出了ID3算法以后，決策樹(shù)在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘領(lǐng)域得到極大的發(fā)展。Quinilan后來(lái)又提出了C4.5，成為新的監(jiān)督學(xué)習(xí)算法。1984年幾位統(tǒng)計(jì)學(xué)家提出了CART分類算法。ID3和ART算法大約同時(shí)被提出，但都是采用類似的方法從訓(xùn)練樣本中學(xué)習(xí)決策樹(shù)的。決策樹(shù)是一樹(shù)狀結(jié)構(gòu)，它的每一個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)分類，非葉子節(jié)點(diǎn)對(duì)應(yīng)著在某個(gè)屬性上的劃分，根據(jù)樣本在該屬性上的不同取值將其劃分成若干個(gè)子集。構(gòu)造決策樹(shù)的核心問(wèn)題是在每一步如何選擇適當(dāng)?shù)膶傩詫?duì)樣本進(jìn)行拆分。對(duì)一個(gè)分類問(wèn)題，從已知類標(biāo)記的訓(xùn)練樣本中學(xué)習(xí)并構(gòu)造出決策樹(shù)

3、是一個(gè)自上而下分而治之的過(guò)程。ID3算法簡(jiǎn)介及基本原理  ID3算法基于信息熵來(lái)選擇最佳的測(cè)試屬性，它選擇當(dāng)前樣本集中具有最大信息增益值的屬性作為測(cè)試屬性；樣本集的劃分則依據(jù)測(cè)試屬性的取值進(jìn)行，測(cè)試屬性有多少個(gè)不同的取值就將樣本集劃分為多少個(gè)子樣本集，同時(shí)決策樹(shù)上相應(yīng)于該樣本集的節(jié)點(diǎn)長(zhǎng)出新的葉子節(jié)點(diǎn)。ID3算法根據(jù)信息論的理論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標(biāo)準(zhǔn)，用信息增益值度量不確定性：信息增益值越大，不確定性越小。因此，ID3算法在每個(gè)非葉節(jié)點(diǎn)選擇信息增益最大的屬性作為測(cè)試屬性，這樣可以得到當(dāng)前情況下最純的劃分，從而得到較小的決策樹(shù)。 設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定

4、類別屬性具有m個(gè)不同的值：，設(shè)是類中的樣本數(shù)。對(duì)一個(gè)給定的樣本，它總的信息熵為，其中，是任意樣本屬于的概率，一般可以用估計(jì)。 設(shè)一個(gè)屬性A具有k個(gè)不同的值，利用屬性A將集合S劃分為k個(gè)子集，其中包含了集合S中屬性A取值的樣本。若選擇屬性A為測(cè)試屬性，則這些子集就是從集合S的節(jié)點(diǎn)生長(zhǎng)出來(lái)的新的葉節(jié)點(diǎn)。設(shè)是子集中類別為的樣本數(shù)，則根據(jù)屬性A劃分樣本的信息熵為  其中，是子集中類別為的樣本的概率。 最后，用屬性A劃分樣本集S后所得的信息增益（Gain）為 顯然越小，Gain(A)的值就越大，說(shuō)明選擇測(cè)試屬性A對(duì)于分類提供的信息越大，選擇A之后對(duì)分類的不確定程度越小。屬性A的k個(gè)不同的值對(duì)應(yīng)

5、的樣本集S的k個(gè)子集或分支，通過(guò)遞歸調(diào)用上述過(guò)程（不包括已經(jīng)選擇的屬性），生成其他屬性作為節(jié)點(diǎn)的子節(jié)點(diǎn)和分支來(lái)生成整個(gè)決策樹(shù)。ID3決策樹(shù)算法作為一個(gè)典型的決策樹(shù)學(xué)習(xí)算法，其核心是在決策樹(shù)的各級(jí)節(jié)點(diǎn)上都用信息增益作為判斷標(biāo)準(zhǔn)來(lái)進(jìn)行屬性的選擇，使得在每個(gè)非葉子節(jié)點(diǎn)上進(jìn)行測(cè)試時(shí)，都能獲得最大的類別分類增益，使分類后的數(shù)據(jù)集的熵最小。這樣的處理方法使得樹(shù)的平均深度較小，從而有效地提高了分類效率。ID3算法的具體流程 1）對(duì)當(dāng)前樣本集合，計(jì)算所有屬性的信息增益； 2）選擇信息增益最大的屬性作為測(cè)試屬性，把測(cè)試屬性取值相同的樣本劃為同一個(gè)子樣本集； 3）若子樣本集的類別屬性

6、只含有單個(gè)屬性，則分支為葉子節(jié)點(diǎn)，判斷其屬性值并標(biāo)上相應(yīng)的符號(hào)，然后返回調(diào)用處；否則對(duì)子樣本集遞歸調(diào)用本算法。二、實(shí)驗(yàn)步驟1.因?yàn)橐郧敖?jīng)常使用微軟的Azure平臺(tái)，這次仍然想用這個(gè)平臺(tái)實(shí)驗(yàn)一下。測(cè)試使用決策樹(shù)算法求出的準(zhǔn)確率和召回率等以及改變參數(shù)對(duì)結(jié)果的影響。a.兩分類決策樹(shù)（第一個(gè)圖是數(shù)據(jù)，前12個(gè)數(shù)據(jù)；第二個(gè)圖是平臺(tái)上的流程圖） 參數(shù)配置：（隨機(jī)種子0，0.25的測(cè)試集）結(jié)果：測(cè)試集共3個(gè)數(shù)據(jù)，分錯(cuò)了2個(gè)，準(zhǔn)確率為33.3%，召回率1%。通過(guò)可視化平臺(tái)的結(jié)果對(duì)比可以發(fā)現(xiàn)決策樹(shù)算法的準(zhǔn)確率很低，我感覺(jué)這個(gè)的原因是數(shù)據(jù)太少，所以偶然性太強(qiáng)，數(shù)據(jù)若是多一些，可能會(huì)好一些。2.開(kāi)始自己著手寫mat

7、lab程序，剛開(kāi)始看到題感覺(jué)挺簡(jiǎn)單的，不就是算出熵，然后算信息增益得到每次要判斷的屬性，那樹(shù)不就畫(huà)出來(lái)了么。然而事實(shí)告訴我，用筆算的簡(jiǎn)單但是寫程序就不那么容易了。每次傳進(jìn)去的是一批數(shù)據(jù)，得根據(jù)數(shù)據(jù)去畫(huà)樹(shù)。然后我就通過(guò)看清華大學(xué)那本機(jī)器學(xué)習(xí)的書(shū)，找到了一個(gè)偽代碼的算法，思路沒(méi)有錯(cuò)，就是一個(gè)遞歸算法，輸入的變量是數(shù)據(jù)和屬性，輸出的變量是一棵樹(shù)的結(jié)構(gòu)。照著這個(gè)循環(huán)寫完之后，運(yùn)行出來(lái)又出現(xiàn)了錯(cuò)誤，然后和同學(xué)討論發(fā)現(xiàn)是結(jié)構(gòu)體的問(wèn)題，結(jié)構(gòu)體比較BT的地方是要求參數(shù)數(shù)目是相同的，所以每次定義結(jié)構(gòu)體的以及每個(gè)return的時(shí)候都需要寫全所有的參數(shù)，即使為空。（第一張圖片是算法偽代碼，第二張是結(jié)構(gòu)體的寫法）3.

8、把樹(shù)構(gòu)造好后，返回的是一棵樹(shù)的結(jié)構(gòu)，里面包含了好幾層，可以用plot的專門畫(huà)樹(shù)的方法畫(huà)出來(lái)。但是，如何使用這棵樹(shù)呢？我是把每棵樹(shù)的每個(gè)節(jié)點(diǎn)也就是結(jié)構(gòu)體構(gòu)造了好幾個(gè)屬性（如上圖所示），保存了節(jié)點(diǎn)的類別（1或者2），保存了節(jié)點(diǎn)下一個(gè)屬性（最大信息增益的屬性），保存了它是否是葉子節(jié)點(diǎn)。這樣每次使用樹(shù)的時(shí)候，代入數(shù)值后，先比較第一個(gè)最大信息增益的屬性，然后找下一個(gè)，直到葉子節(jié)點(diǎn)就可以判斷出類別了。第二個(gè)問(wèn)題是第二個(gè)測(cè)試數(shù)據(jù)中的第二維是D，并不在該有的屬性集中，然后我按照老師上課講的方法，把它設(shè)置為屬性集（1，2，3）中出現(xiàn)次數(shù)最多的值3，然后去計(jì)算。4.算法的過(guò)程：a是ID3算法中最后的包括了遞歸的循

9、環(huán)（注意每次遞歸進(jìn)去的是去掉了已使用過(guò)的屬性值的，數(shù)據(jù)data和屬性attributes都要去掉）；b是信息增益的求法；c是判斷樣本在屬性上取值是否相同：a.%從屬性中選擇最優(yōu)劃分屬性a，求最優(yōu)屬性位于第a行，后面遞歸傳入data時(shí)記得去掉那一行a=gain(data,attributes);tree.nextsx=a;ma=length(unique(data(a,:);%首先對(duì)每一個(gè)屬性循環(huán)，生成node的一個(gè)分支for i=1:ma node=struct('value', 'null'); node.node='null' node.ne

10、xtsx=0;%樹(shù)的每個(gè)節(jié)點(diǎn)的下一個(gè)要選擇的屬性 tree.node(i)=node; %得到data中在該屬性上不同取值的樣本子集dd % d1,d2,d3,d4=fkjz(data,a); dd=; for t=1:l if data(a,t)=i dd=dd,data(:,t); end end if (isempty(dd) %fprintf('data中在屬性上不同取值的樣本子集為空n'); if (last_sum >= ( l / 2)*l); tree.node(i).value= 'true' else tree.node(i).valu

11、e = 'false' end tree.node(i).nextsx=0;%樹(shù)的每個(gè)節(jié)點(diǎn)的下一個(gè)要選擇的屬性 else dd(a,:)=; shux=attributes; shux(a)=; tree.node(i)=ID3(dd,shux); % tree.node(i)=a; endendb.for i=1:m2 x1,x2,x3,x4=fkjz(x,i);%每次都得到按照某一個(gè)屬性分開(kāi)的矩陣 l1(i,:)=size(x1,2)/12,size(x2,2)/12,size(x3,2)/12,size(x4,2)/12;%5行4列，5種特征，每種特征中每種節(jié)點(diǎn)占總結(jié)點(diǎn)，

12、也就是Sv/S if size(x1,2)/12=0 p11(i,1),p12(i,1),entro1(i,1)=entropy(x1(m,:),1,2); end if size(x2,2)/12=0 p11(i,2),p12(i,2),entro1(i,2)=entropy(x2(m,:),1,2); end if size(x3,2)/12=0 p11(i,3),p12(i,3),entro1(i,3)=entropy(x3(m,:),1,2); end if size(x4,2)/12=0 p11(i,4),p12(i,4),entro1(i,4)=entropy(x4(m,:),1,

13、2); end gain2(i)=entro-(l1(i,1)*entro1(i,1)+l1(i,2)*entro1(i,2)+l1(i,3)*entro1(i,3)+l1(i,4)*entro1(i,4);end%求最大的信息增益位于的行數(shù)gain_max=find(gain2=(max(gain2);gain_max = gain_max(1);c.m,l=size(x);a=0;for i=2:l for w=1:m-1 if x(w,1)=x(w,i) return end end enda=1; 三、實(shí)驗(yàn)結(jié)果1.樹(shù)的結(jié)構(gòu)：算上根節(jié)點(diǎn)分成了4層，屬性依次選的是1，2，5（第一張圖是畫(huà)的

14、這次分出的樹(shù)的結(jié)構(gòu)；第二張圖是調(diào)用算法后返回了的樹(shù)；后面幾張圖是打開(kāi)樹(shù)的結(jié)構(gòu)體的內(nèi)部參數(shù)和結(jié)構(gòu)：其中，true是指w1類，false是指w2類。每個(gè)結(jié)構(gòu)體都是包含了3個(gè)屬性，value是類別，nextsx是下一個(gè)要選擇的信息增益最大的屬性位于的行數(shù)（因?yàn)槊看挝掖脒f歸的時(shí)候是去掉已用過(guò)的屬性，所以顯示的第一次nextsx=1即第一行屬性，第二次nextsx=1，也就是第二行，第三次nextsx=3，也就是第五行）tree是根節(jié)點(diǎn)，按照第一個(gè)屬性往下分出了4個(gè)子集，其中第二個(gè)子集又按照第二個(gè)屬性分出了3個(gè)子集，這3個(gè)子集的第一個(gè)子集按照第五個(gè)屬性分出3個(gè)節(jié)點(diǎn)，自此分好）2.第二題分類兩個(gè)測(cè)試數(shù)據(jù)，第一個(gè)數(shù)據(jù)為2，3，2，1，2，第二個(gè)數(shù)據(jù)為3，3，3，2，1，分類結(jié)果為第一個(gè)數(shù)據(jù)分到w1類，第二個(gè)數(shù)據(jù)分到w2類。3.第三題寫出測(cè)試數(shù)據(jù)的邏輯表達(dá)式a1=(A-D=B)(E-G=G)a2=(A-D=C)4.第四題寫出w1,w2的邏輯表達(dá)式w1=(A-D=A)+(A-D=B)(E-G=G)+(A-D=B)(E-G=E)(M-N=M);w2=(A-D=B)(E-G=E)(M-N=N)+(A-D=B)(E-G=F)+