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

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

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

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

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

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

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

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

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

10、xtsx=0;%樹的每個節點的下一個要選擇的屬性 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;%樹的每個節點的下一個要選擇的屬性 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種特征，每種特征中每種節點占總結點，

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%求最大的信息增益位于的行數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; 三、實驗結果1.樹的結構：算上根節點分成了4層，屬性依次選的是1，2，5（第一張圖是畫的

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