機器學(xué)習(xí)決策樹算法id3

1、山東大學(xué)計算機學(xué)院實驗報告實驗題目：決策樹算法ID3學(xué)號：日期：2016.12.6班級：2014級4班姓名：Email：實驗?zāi)康模?熟悉matlab環(huán)境及相關(guān)函數(shù)的熟練使用。2學(xué)習(xí)如何構(gòu)造一棵決策樹，并且用matlab畫出樹形狀。3學(xué)習(xí)如何使用一棵決策樹，即將測試數(shù)值代入時，如何判斷屬于哪一類。4會寫測試集代入的分類表達式和類別的邏輯表達式并化簡。5分析該算法準(zhǔn)確性。硬件環(huán)境：windows10操作系統(tǒng)軟件環(huán)境：matlab環(huán)境，Azu

2、reML平臺實驗步驟：一、背景知識及原理決策樹算法：樹狀結(jié)構(gòu)，每一個葉子節(jié)點對應(yīng)著一個分類決策樹方法在分類、預(yù)測、規(guī)則提取等領(lǐng)域有著廣泛的應(yīng)用。在20世紀(jì)70年代后期和80年代初期，機器學(xué)習(xí)研究者J.RossQuinilan提出了ID3算法以后，決策樹在機器學(xué)習(xí)、數(shù)據(jù)挖掘領(lǐng)域得到極大的發(fā)展。Quinilan后來又提出了C4.5，成為新的監(jiān)督學(xué)習(xí)算法。1984年幾位統(tǒng)計學(xué)家提出了CART分設(shè)S是s個數(shù)據(jù)樣本的集合。假定類別屬性具有m個不同

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

4、in(A)的值就越大，說明選擇測試屬性A對于分類提供的信息越大，選擇A之后對分類的不確定程度越小。屬性A的k個不同的值對應(yīng)的樣本集S的k個子集或分支，通過遞歸調(diào)用上述過程（不包括已經(jīng)選擇的屬性），生成其他屬性作為節(jié)點的子節(jié)點和分支來生成整個決策樹。ID3決策樹算法作為一個典型的決策樹學(xué)習(xí)算法，其核心是在決策樹的各級節(jié)點上都用信息增益作為判斷標(biāo)準(zhǔn)來進行屬性的選擇，使得在每個非葉子節(jié)點上進行測試時，都能獲得最大的類別分類增益，使分類后的數(shù)據(jù)