基于matlab的決策樹pdf_第1頁
基于matlab的決策樹pdf_第2頁
基于matlab的決策樹pdf_第3頁
基于matlab的決策樹pdf_第4頁
基于matlab的決策樹pdf_第5頁
已閱讀5頁,還剩4頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、數(shù)據(jù)挖掘大作業(yè)-ID3 決策樹學(xué)號(hào):02105111姓名:張旭一 決策樹算法.決策樹的基本概念機(jī)器學(xué)習(xí)中,決策樹是一個(gè)預(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í), 通俗說就是決策樹。決 策樹學(xué)習(xí)也是數(shù)據(jù)挖掘中一個(gè)普通的方法。在這里,每個(gè)決策樹都表述了一種樹 型結(jié)構(gòu),它由它的分支來對(duì)該類型的對(duì)象依靠屬性進(jìn)行分類。每個(gè)決策樹可以依 靠對(duì)源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)

2、測(cè)試。這個(gè)過程可以遞歸式的對(duì)樹進(jìn)行修剪。當(dāng)不 能再進(jìn)行分割或一個(gè)單獨(dú)的類可以被應(yīng)用于某一分支時(shí),遞歸過程就完成了。另 外,隨機(jī)森林分類器將許多決策樹結(jié)合起來以提升分類的正確率。決策樹同時(shí)也可以依靠計(jì)算條件概率來構(gòu)造。決策樹如果依靠數(shù)學(xué)的計(jì)算方法可以取得更加理想的效果。決策樹一般可歸納為 2 類:分類與預(yù)測(cè)。本文著重關(guān)于其分類的作用,并以 此來構(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);決策 樹可以處理高維數(shù)據(jù),推理過程完全依賴于屬性變量的取值特點(diǎn),可自動(dòng)忽略

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

4、導(dǎo)致決策樹中子樹的重復(fù)或有些屬性在決策樹的某一路徑上被檢驗(yàn)多 次??乖胄圆?,訓(xùn)練例子中正例和反例的比例較難控制。二 ID3 算法ID3 算法主要針對(duì)屬性選擇問題,是決策樹學(xué)習(xí)方法中最具影響和最為典型 的算法。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)則。其中的三種度量方法 分別是信息增益、增益率和 Gini 指標(biāo)。(示例算法選擇了第一種方法)。當(dāng)獲 取信息時(shí),將不確定的內(nèi)容轉(zhuǎn)為確定

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

6、組都屬于相同的類。從概念上 講,最好的劃分準(zhǔn)則是導(dǎo)致最接近這種情況的劃分。此次問題采用一種流行的屬 性選擇度量信息增益。信息增益度量基于 Claude Shannon 在研究消息的值或“信息內(nèi)容”的信息 論方面的先驅(qū)工作。設(shè)節(jié)點(diǎn) N 代表或存放劃分 D 的元組。選擇具有最高信息增益 的屬性作為節(jié)點(diǎn) N 的分裂屬性。該屬性使結(jié)果劃分中的元組分類所需的信息量最 小,并反映這些劃分中的最小隨機(jī)性或“不純性”。這種方法使對(duì)給定元組分類 所需的期望測(cè)試數(shù)目最小,并確保找到一棵簡(jiǎn)單的樹。熵是選擇事件時(shí)選擇自由度的量度,其計(jì)算方法為: P=freq(Cj,S)/|S|; Exp(S)=-SUM(P*LOG(

7、P) ; SUM() 函 數(shù) 是 求 j 從 1 到 n 的 和 。 Entropy(X)=SUM( (|Ti|/|T|)*Exp(X);Gain(X)=Exp(X)- Entropy(X);為保證生成的決策樹最小,ID3 算法在生成子樹時(shí),選取使生成的子樹的熵 (即 Gain(S)最小的特征來生成子樹。三 實(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 DatabaseFor Each Attribute: (all numeric-valued)1. Number of times preg

8、nant2. Plasma glucose concentration a 2 hours in an oral glucose tolerance test3. Diastolic blood pressure (mm Hg)4. Triceps skin fold thickness (mm)5. 2-Hour serum insulin (mu U/ml)6. Body mass index (weight in kg/(height in m)2)7. Diabetes pedigree function8. Age (years)Class ValueNumber of instan

9、ces05001268實(shí)驗(yàn)代碼:%* %目錄 %*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 hi

10、dden ;show_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(&#

11、39;Error!')end%* %構(gòu)建一個(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',

12、'age' t=classregtree(D,classity,'names',AttributName);t=prune(t,'level',5);disp(t); end%* %繪制一個(gè)決策樹%* function show_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',

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

14、,'%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

15、,1);for k=1:10 cost=test(t,'cross',D,classity); costsum=costsum+cost;end costsum=costsum/10; i=1:10;plot(i,costsum,'-o');xlabel('交叉次數(shù)');ylabel('錯(cuò)誤率'); title('決策樹 k 倍交叉錯(cuò)誤率曲線');end實(shí)驗(yàn)結(jié)果:Decsion tree:Decision tree for classification1 if plas<127.5 then node 2 else node 32 if age<28.5 then node 4 else node 53 if mass<29.95 then node 6 else node 74 if mass<45.4 then node 8 else node 95 if mass<26.35 then node 10 else node 116 if plas&l

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論