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

1、山東大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：決策樹(shù)算法ID3學(xué)號(hào)：日期：2016.12.6班級(jí)：2014級(jí)4班姓名：Email：實(shí)驗(yàn)?zāi)康模?熟悉matlab環(huán)境及相關(guān)函數(shù)的熟練使用。2學(xué)習(xí)如何構(gòu)造一棵決策樹(shù)，并且用matlab畫出樹(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)境，Azu

2、reML平臺(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)用。在20世紀(jì)70年代后期和80年代初期，機(jī)器學(xué)習(xí)研究者J.RossQuinilan提出了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分設(shè)S是s個(gè)數(shù)據(jù)樣本的集合。假定類別屬性具有m個(gè)不同

3、的值：，設(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）為顯然越小，Ga

4、in(A)的值就越大，說(shuō)明選擇測(cè)試屬性A對(duì)于分類提供的信息越大，選擇A之后對(duì)分類的不確定程度越小。屬性A的k個(gè)不同的值對(duì)應(yīng)的樣本集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ù)