機器學習決策樹算法

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

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

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

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

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

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

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

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

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

10、xtsx=0;%樹的每個節(jié)點的下一個要選擇的屬性 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;%樹的每個節(jié)點的下一個要選擇的屬性 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);%每次都得到按照某一個屬性分開的矩陣 l1(i,:)=size(x1,2)/12,size(x2,2)/12,size(x3,2)/12,size(x4,2)/12;%5行4列，5種特征，每種特征中每種節(jié)點占總結(jié)點，

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; 三、實驗結(jié)果1.樹的結(jié)構(gòu)：算上根節(jié)點分成了4層，屬性依次選的是1，2，5（第一張圖是畫的

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