基于matlab的決策樹pdf(共9頁(yè))

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

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

3、高維數(shù)據(jù)，推理過(guò)程完全依賴于屬性變量的取值特點(diǎn)，可自動(dòng)忽略目 標(biāo)變量沒(méi)有貢獻(xiàn)的屬性變量，也為判斷屬性變量的重要性，減少變量的數(shù)目提供 參考，同時(shí)對(duì)噪聲數(shù)據(jù)具有很好的健壯性；決策樹歸納的學(xué)習(xí)和分類步驟是簡(jiǎn)單 和快速的，推理過(guò)程可以表示成 If Then 形式，并且具有很好的準(zhǔn)確率；獲取的 知識(shí)用樹的形式表示是直觀的，并且容易被人理解。因而，決策樹歸納分類是目 前應(yīng)用最廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中受到研究者的廣泛關(guān)注。但是其缺點(diǎn)也是很多的，如：信息增益的計(jì)算依賴于特征數(shù)目較多的特征， 而屬性取值最多的屬性并不一定最優(yōu)。ID3 是非遞增算法。ID3 是單變量決策樹 (在分枝節(jié)點(diǎn)上只考慮單個(gè)屬

4、性)，許多復(fù)雜概念的表達(dá)困難，屬性相互關(guān)系強(qiáng)調(diào) 不夠，容易導(dǎo)致決策樹中子樹的重復(fù)或有些屬性在決策樹的某一路徑上被檢驗(yàn)多 次?？乖胄圆睿?xùn)練例子中正例和反例的比例較難控制。二 ID3 算法ID3 算法(sun f)主要針對(duì)屬性選擇問(wèn)題，是決策樹學(xué)習(xí)方法中最具影響(yngxing)和最為典型 的算法(sun f)。ID3 采用貪心方法，其中決策樹以自頂向下遞歸的分治方式構(gòu)造。大多 數(shù)決策樹歸納算法都沿用這種自頂向下的方法，從訓(xùn)練元組集和它們的相關(guān)聯(lián)的 類標(biāo)號(hào)開始構(gòu)造決策樹。隨著樹的構(gòu)建，訓(xùn)練集遞歸地劃分成較小的子集。ID3 算法中關(guān)鍵的一步是屬性選擇度量，即選擇分裂準(zhǔn)則。其中的三種度量方法 分別是

5、信息增益、增益率和 Gini 指標(biāo)。（示例算法選擇了第一種方法）。當(dāng)獲 取信息時(shí)，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。算法的基本策略如下： 1.選擇一個(gè)屬性放置在根節(jié)點(diǎn)，為每個(gè)可能的屬性值產(chǎn)生一個(gè)分支2.將樣本劃分成多個(gè)(du )子集，一個(gè)子集對(duì)應(yīng)(duyng)于一個(gè)分支3.在每個(gè)分支上遞歸地重復(fù)這個(gè)(zh ge)過(guò)程，僅使用真正到達(dá)這個(gè)分支的樣本4.如果在一個(gè)節(jié)點(diǎn)上的所有樣本擁有相同的類別，即停止該部分樹的擴(kuò)展此次問(wèn)題在選擇屬性值時(shí)采用啟發(fā)式標(biāo)準(zhǔn)，其內(nèi)容為： 只跟本身與其子樹有關(guān)，采取信息理論用熵來(lái)量度。屬性選擇度量是一種選擇分裂準(zhǔn)則，將給定的類標(biāo)記的訓(xùn)練元組的數(shù)據(jù)劃分 D“

6、最好”地分成個(gè)體類的 啟發(fā)式方法。如果我們要根據(jù)分裂準(zhǔn)則的輸出將 D 劃分成較小的劃分，理想地， 每個(gè)劃分是“純”的，即，落在給定劃分的所有元組都屬于相同的類。從概念上 講，最好的劃分準(zhǔn)則是導(dǎo)致最接近這種情況的劃分。此次問(wèn)題采用一種流行的屬 性選擇度量信息增益。信息增益度量基于 Claude Shannon 在研究消息的值或“信息內(nèi)容”的信息 論方面的先驅(qū)工作。設(shè)節(jié)點(diǎn) N 代表或存放劃分 D 的元組。選擇具有最高信息增益 的屬性作為節(jié)點(diǎn) N 的分裂屬性。該屬性使結(jié)果劃分中的元組分類所需的信息量最 小，并反映這些劃分中的最小隨機(jī)性或“不純性”。這種方法使對(duì)給定元組分類 所需的期望測(cè)試數(shù)目最小，并

7、確保找到一棵簡(jiǎn)單的樹。熵是選擇事件時(shí)選擇自由度的量度，其計(jì)算方法為： 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(X)；為保證生成的決策樹最小，ID3 算法在生成子樹時(shí)，選取使生成的子樹的熵 (即 Gain(S)最小的特征來(lái)生成子樹。三 實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)?zāi)康模貉芯刻悄虿?shù)據(jù)（diabetes 數(shù)據(jù)集），構(gòu)造一顆決策樹。 實(shí)驗(yàn)數(shù)據(jù)：Title: Pima Indians Diabetes

8、DatabaseFor Each Attribute: (all numeric-valued)Number of times pregnantPlasma glucose concentration a 2 hours in an oral glucose tolerance testDiastolic blood pressure (mm Hg)Triceps skin fold thickness (mm)2-Hour serum insulin (mu U/ml)Body mass index (weight in kg/(height in m)2)Diabetes pedigree

9、 functionAge (years)Class ValueNumber of instances05001268實(shí)驗(yàn)代碼：%* %目錄(ml) %*close alls=menu(ID3 Decision tree,Decision tree,Decision tree paint,10-fold crossgraph,Express gratitude,Exit); switch scase 1, clc;clear all;close all hidden;decisiontree();IDmenu case 2, clc;clear all;close all hidden ;sho

10、w_tree();IDmenu; case 3, clc;clear all;close all hidden ;errorrate();IDmenu;case 4, clc;clear all;close all hidden ;disp(Thanks for everyone who helped me in this programming period);IDmenu;case 5, clc;clear all;close all hidden;clc;otherwise clc;clear all;close all hidden;disp(Error!)end%* %構(gòu)建(u ji

11、n)一個(gè)決策樹%* function decisiontree()S1,S2,S3,S4,S5,S6,S7,S8,classity=textread(train.txt,%f %f %f %f %f %f %f %f %s);D=S1 S2 S3 S4 S5 S6 S7 S8;AttributName= preg,plas,pres,skin,insu,mass,pedi,age; t=classregtree(D,classity,names,AttributName);t=prune(t,level,5);disp(t); end%* %繪制(huzh)一個(gè)決策樹%* function s

12、how_tree()S1,S2,S3,S4,S5,S6,S7,S8,classity=textread(train.txt,%f %f %f %f %f %f %f %f %s);D=S1 S2 S3 S4 S5 S6 S7 S8;AttributName= preg,plas,pres,skin,insu,mass,pedi,age; t=classregtree(D,classity,names,AttributName);t=prune(t,level,8);view(t); end%* %計(jì)算錯(cuò)誤率并繪制(huzh)成曲線%* function errorrate()S1,S2,S3,

13、S4,S5,S6,S7,S8,classity=textread(train.txt,%f %f %f %f %f %f %f %f %s);D=S1 S2 S3 S4 S5 S6 S7 S8;AttributName= preg,plas,pres,skin,insu,mass,pedi,age; t=classregtree(D,classity,names,AttributName); t=prune(t,level,5);costsum=zeros(10,1);for k=1:10 cost=test(t,cross,D,classity); costsum=costsum+cost;

14、end costsum=costsum/10; i=1:10;plot(i,costsum,-o);xlabel(交叉(jioch)次數(shù));ylabel(錯(cuò)誤率); title(決策樹 k 倍交叉(jioch)錯(cuò)誤率曲線);end實(shí)驗(yàn)(shyn)結(jié)果：Decsion tree：Decision tree for classificationif plas127.5 then node 2 else node 3if age28.5 then node 4 else node 5if mass29.95 then node 6 else node 7if mass45.4 then node 8 else node 9if mass26.35 then node 10 else node 11if plas145.5 then node 12 else