基于matlab的決策樹

1、數(shù)據(jù)挖掘大作業(yè)-ID3決策樹 學(xué)號:02105111姓名:張旭一.決策樹算法.決策樹的基本概念機(jī)器學(xué)習(xí)中,決策樹是一個預(yù)測模型;它代表的是對象屬性值與對象值之間的一種映射關(guān)系。樹中每個節(jié)點(diǎn)表示某個對象,每個分叉路徑則代表的某個可能的屬性值,而每個葉結(jié)點(diǎn)則對應(yīng)具有上述屬性值的子對象。決策樹僅有單一輸出;若需要多個輸出,可以建立獨(dú)立的決策樹以處理不同輸出。從數(shù)據(jù)產(chǎn)生決策樹的機(jī)器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí),通俗說就是決策樹。決策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個普通的方法。在這里,每個決策樹都表述了一種樹型結(jié)構(gòu),它由它的分支來對該類型的對象依靠屬性進(jìn)行分類。每個決策樹可以依靠對源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測試。這個過程

2、可以遞歸式的對樹進(jìn)行修剪。當(dāng)不能再進(jìn)行分割或一個單獨(dú)的類可以被應(yīng)用于某一分支時,遞歸過程就完成了。另外,隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。決策樹同時也可以依靠計算條件概率來構(gòu)造。決策樹如果依靠數(shù)學(xué)的計算方法可以取得更加理想的效果。決策樹一般可歸納為2類:分類與預(yù)測。本文著重關(guān)于其分類的作用,并以此來構(gòu)建一個完整的決策樹。.決策樹分類器的優(yōu)點(diǎn)以此次用的ID3算法為例,以此算法產(chǎn)生的決策樹分類器具有很多優(yōu)點(diǎn):決策樹的構(gòu)造不需要任何領(lǐng)域知識或參數(shù)設(shè)置,因此適合于探測式知識發(fā)現(xiàn);決策樹可以處理高維數(shù)據(jù),推理過程完全依賴于屬性變量的取值特點(diǎn),可自動忽略目標(biāo)變量沒有貢獻(xiàn)的屬性變量,也為

3、判斷屬性變量的重要性,減少變量的數(shù)目提供參考,同時對噪聲數(shù)據(jù)具有很好的健壯性;決策樹歸納的學(xué)習(xí)和分類步驟是簡單和快速的,推理過程可以表示成If Then形式,并且具有很好的準(zhǔn)確率;獲取的知識用樹的形式表示是直觀的,并且容易被人理解。因而,決策樹歸納分類是目前應(yīng)用最廣泛的歸納推理算法之一,在數(shù)據(jù)挖掘中受到研究者的廣泛關(guān)注。但是其缺點(diǎn)也是很多的,如:信息增益的計算依賴于特征數(shù)目較多的特征,而屬性取值最多的屬性并不一定最優(yōu)。ID3是非遞增算法。ID3是單變量決策樹(在分枝節(jié)點(diǎn)上只考慮單個屬性,許多復(fù)雜概念的表達(dá)困難,屬性相互關(guān)系強(qiáng)調(diào)不夠,容易導(dǎo)致決策樹中子樹的重復(fù)或有些屬性在決策樹的某一路徑上被檢驗

4、多次?？乖胄圆?訓(xùn)練例子中正例和反例的比例較難控制。二.ID3算法ID3算法主要針對屬性選擇問題,是決策樹學(xué)習(xí)方法中最具影響和最為典型的算法。ID3采用貪心方法,其中決策樹以自頂向下遞歸的分治方式構(gòu)造。大多數(shù)決策樹歸納算法都沿用這種自頂向下的方法,從訓(xùn)練元組集和它們的相關(guān)聯(lián)的類標(biāo)號開始構(gòu)造決策樹。隨著樹的構(gòu)建,訓(xùn)練集遞歸地劃分成較小的子集。ID3算法中關(guān)鍵的一步是屬性選擇度量,即選擇分裂準(zhǔn)則。其中的三種度量方法分別是信息增益、增益率和Gini指標(biāo)。(示例算法選擇了第一種方法。當(dāng)獲取信息時,將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容,因此信息伴著不確定性。算法的基本策略如下:1.選擇一個屬性放置在根節(jié)點(diǎn),為每

5、個可能的屬性值產(chǎn)生一個分支2.將樣本劃分成多個子集,一個子集對應(yīng)于一個分支3.在每個分支上遞歸地重復(fù)這個過程,僅使用真正到達(dá)這個分支的樣本4.如果在一個節(jié)點(diǎn)上的所有樣本擁有相同的類別,即停止該部分樹的擴(kuò)展此次問題在選擇屬性值時采用啟發(fā)式標(biāo)準(zhǔn),其內(nèi)容為:只跟本身與其子樹有關(guān),采取信息理論用熵來量度。屬性選擇度量是一種選擇分裂準(zhǔn)則,將給定的類標(biāo)記的訓(xùn)練元組的數(shù)據(jù)劃分D“最好”地分成個體類的啟發(fā)式方法。如果我們要根據(jù)分裂準(zhǔn)則的輸出將D劃分成較小的劃分,理想地,每個劃分是“純”的,即,落在給定劃分的所有元組都屬于相同的類。從概念上講,最好的劃分準(zhǔn)則是導(dǎo)致最接近這種情況的劃分。此次問題采用一種流行的屬性

6、選擇度量信息增益。信息增益度量基于Claude Shannon在研究消息的值或“信息內(nèi)容”的信息論方面的先驅(qū)工作。設(shè)節(jié)點(diǎn)N代表或存放劃分D的元組。選擇具有最高信息增益的屬性作為節(jié)點(diǎn)N的分裂屬性。該屬性使結(jié)果劃分中的元組分類所需的信息量最小,并反映這些劃分中的最小隨機(jī)性或“不純性”。這種方法使對給定元組分類所需的期望測試數(shù)目最小,并確保找到一棵簡單的樹。熵是選擇事件時選擇自由度的量度,其計算方法為:P=freq(Cj,S/|S|;Exp(S=-SUM(P*LOG(P;SUM(函數(shù)是求j從1到n的和。Entropy(X=SUM(|Ti|/|T|*Exp(X;Gain(X=Exp(X-Entropy

7、(X;為保證生成的決策樹最小,ID3算法在生成子樹時,選取使生成的子樹的熵(即Gain(S最小的特征來生成子樹。三.實(shí)驗內(nèi)容實(shí)驗?zāi)康?研究糖尿病數(shù)據(jù)(diabetes數(shù)據(jù)集,構(gòu)造一顆決策樹。實(shí)驗數(shù)據(jù):Title:Pima Indians Diabetes DatabaseFor Each Attribute:(all numeric-valued1.Number of times pregnant2.Plasma glucose concentration a2hours in an oral glucose tolerance test3.Diastolic blood pressure(m

8、m Hg4.Triceps skin fold thickness(mm5.2-Hour serum insulin(mu U/ml6.Body mass index(weight in kg/(height in m27.Diabetes pedigree function8.Age(yearsClass Value Number of instances05001268實(shí)驗代碼:%*%目錄%*close alls=menu('ID3Decision tree','Decision tree','Decision tree paint',

9、9;10-fold crossgraph','Express gratitude','Exit'switch scase1,clc;clear all;close all hidden;decisiontree(;IDmenucase2,clc;clear all;close all hidden;show_tree(;IDmenu;case3,clc;clear all;close all hidden;errorrate(;IDmenu;case4,clc;clear all;close all hidden;disp('Thanks for

10、 everyone who helped me in this programming period'IDmenu;case5,clc;clear all;close all hidden;clc;otherwise clc;clear all;close all hidden;disp('Error!'end%*%構(gòu)建一個決策樹%*function decisiontree(S1,S2,S3,S4,S5,S6,S7,S8,classity=textread('train.txt','%f%f%f%f%f%f%f%f %s'D=S1S2S

11、3S4S5S6S7S8;AttributName='preg','plas','pres','skin','insu','mass','pedi','age't=classregtree(D,classity,'names',AttributName;t=prune(t,'level',5;disp(t;end%*%繪制一個決策樹%*function show_tree(S1,S2,S3,S4,S5,S6,S7,S8,classity=

12、textread('train.txt','%f%f%f%f%f%f%f%f %s'D=S1S2S3S4S5S6S7S8;AttributName='preg','plas','pres','skin','insu','mass','pedi','age't=classregtree(D,classity,'names',AttributName;t=prune(t,'level',8;view(t;en

13、d%*%計算錯誤率并繪制成曲線%*function errorrate(S1,S2,S3,S4,S5,S6,S7,S8,classity=textread('train.txt','%f%f%f%f%f%f%f%f %s'D=S1S2S3S4S5S6S7S8;AttributName='preg','plas','pres','skin','insu','mass','pedi','age' t=classregtree(D,class

14、ity,'names',AttributName;t=prune(t,'level',5;costsum=zeros(10,1;for k=1:10cost=test(t,'cross',D,classity;costsum=costsum+cost;endcostsum=costsum/10;i=1:10;plot(i,costsum,'-o'xlabel('交叉次數(shù)'ylabel('錯誤率'title('決策樹k倍交叉錯誤率曲線'end實(shí)驗結(jié)果: Decsion tree:Dec

15、ision tree for classification1if plas<127.5then node2else node32if age<28.5then node4else node53if mass<29.95then node6else node74if mass<45.4then node8else node95if mass<26.35then node10else node116if plas<145.5then node12else node137if plas<157.5then node14else node158class=ne

16、g9class=pos10if mass<9.65then node16else node1711if plas<99.5then node18else node1912class=neg13if age<61then node20else node2114 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 if age<30.5 then node 22 else

17、 node 23 class = pos class = pos class = neg if plas<28.5 then node 24 else node 25 if pedi<0.561 then node 26 else node 27 if age<25.5 then node 28 else node 29 class = neg if pres<61 then node 30 else node 31 if pedi<0.4295 then node 32 else node 33 class = pos class = neg if pedi&l

18、t;0.2 then node 34 else node 35 if preg<6.5 then node 36 else node 37 class = neg if mass<27.1 then node 38 else node 39 class = pos if mass<41.8 then node 40 else node 41 if mass<45.55 then node 42 else node 43 class = pos class = neg if preg<1.5 then node 44 else node 45 if insu<

19、120.5 then node 46 else node 47 class = pos class = pos if pres<82 then node 48 else node 49 if pedi<1.1415 then node 50 else node 51 class = pos if pres<92 then node 52 else node 53 class = pos class = pos if pres<67 then node 54 else node 55 if age<34.5 then node 56 else node 57 class = pos if pedi<0.3975 then node 58 else node 59 class = neg class = neg class = pos i