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

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

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

4、在決策樹的某一路徑上被檢驗多次?？乖胄圆睿柧毨又姓头蠢谋壤^難控制。三、ID3 算法3.1 ID3算法主要針對屬性選擇問題，是決策樹學習方法中最具影響和最為典型的算法。ID3采用貪心方法，其中決策樹以自頂向下遞歸的分治方式構(gòu)造。 大多數(shù)決策樹歸納算法都沿用這種自頂向下的方法，從訓練元組集和它們的相關(guān)聯(lián)的類標號開始構(gòu)造決策樹。隨著樹的構(gòu)建，訓練集遞歸地劃分成較小的子集。ID3算法中關(guān)鍵的一步是屬性選擇度量，即選擇分裂準則。其中的三種度量方法分別是信息增益、增益率和Gini指標。（示例算法選擇了第一種方法）。當獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。 算法的基本策

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

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

7、ntropy(X)=SUM( (|Ti|/|T|)* Exp (X) ； Gain(X)= Exp (X)- E ntropy(X) ；為保證生成的決策樹最小，ID3 算法在生成子樹時，選取使生成的子樹的熵( 即 Gain(S) 最小的特征來生成子樹。四、 實驗內(nèi)容實驗目的：研究糖尿病數(shù)據(jù)（diabetes數(shù)據(jù)集），構(gòu)造一顆決策樹。實驗數(shù)據(jù)：Title: Pima Indians Diabetes DatabaseFor Each Attribute: (all numeric-valued)1. Number of times pregnant2. Plasma glucose concen

8、tration 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 Value Number of instances0 5001 268%*% 構(gòu)建一個決策樹%*f

9、unction 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,clas

10、sity,'names',AttributName);t=prune(t,'level',5);disp(t);end%*% 繪制一個決策樹%*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','plas','pres','ski

11、n','insu','mass','pedi','age't=classregtree(D,classity,'names',AttributName);t=prune(t,'level',8);view(t);end%*% 計算錯誤率并繪制成曲線%*function errorrate()S1,S2,S3,S4,S5,S6,S7,S8,classity=textread('train.txt','%f %f %f %f %f %f %f %f%s');D=S

12、1 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:10cost=test(t,'cross',D,

13、classity);costsum=costsum+cost;endcostsum=costsum/10;i=1:10;plot(i,costsum,'-o');xlabel(' 交叉次數(shù) ');ylabel(' 錯誤率 ');title(' 決策樹 k 倍交叉錯誤率曲線 ');end五、實驗結(jié)果如下：>> decisiontreeDecision tree for classification 1 if plas<127.5 then node 2 elseif plas>=127.5 then node

14、 3 else neg 2 if age<28.5 then node 4 elseif age>=28.5 then node 5 else neg 3 if mass<29.85 then node 6 elseif mass>=29.85 then node 7 else pos 4 if mass<45.4 then node 8 elseif mass>=45.4 then node 9 else neg 5 if mass<26.35 then node 10 elseif mass>=26.35 then node 11 else

15、neg 6 if plas<145.5 then node 12 elseif plas>=145.5 then node 13 else neg 7 if plas<157.5 then node 14 elseif plas>=157.5 then node 15 else pos 8 class = neg 9 class = pos10 if mass<9.65 then node 16 elseif mass>=9.65 then node 17 else neg11 if plas<99.5 then node 18 elseif plas

16、>=99.5 then node 19 else neg12 class = neg13 if age<61 then node 20 elseif age>=61 then node 21 else pos14 if age<30.5 then node 22 elseif age>=30.5 then node 23 else pos15 class = pos16 class = pos17 class = neg18 if plas<28.5 then node 24 elseif plas>=28.5 then node 25 else ne

17、g19 if pedi<0.561 then node 26 elseif pedi>=0.561 then node 27 else pos20 if age<25.5 then node 28 elseif age>=25.5 then node 29 else pos21 class = neg22 if pres<61 then node 30 elseif pres>=61 then node 31 else neg23 if pedi<0.4295 then node 32 elseif pedi>=0.4295 then node

18、33 else pos24 class = pos25 class = neg26 if pedi<0.2 then node 34 elseif pedi>=0.2 then node 35 else neg27 if preg<6.5 then node 36 elseif preg>=6.5 then node 37 else pos28 class = neg29 if mass<27.1 then node 38 elseif mass>=27.1 then node 39 else pos30 class = pos31 if mass<4

19、1.8 then node 40 elseif mass>=41.8 then node 41 else neg32 if mass<45.55 then node 42 elseif mass>=45.55 then node 43 else pos33 class = pos34 class = neg35 if preg<1.5 then node 44 elseif preg>=1.5 then node 45 else neg36 if insu<120.5 then node 46 elseif insu>=120.5 then node

20、47 else pos37 class = pos38 class = pos39 if pres<82 then node 48 elseif pres>=82 then node 49 else neg40 if pedi<1.1415 then node 50 elseif pedi>=1.1415 then node 51 else neg41 class = pos42 if pres<92 then node 52 elseif pres>=92 then node 53 else neg43 class = pos44 class = pos4

21、5 if pres<67 then node 54 elseif pres>=67 then node 55 else neg46 if age<34.5 then node 56 elseif age>=34.5 then node 57 else neg47 class = pos48 class = pos49 class = neg50 class = neg51 class = pos52 if pedi<0.1365 then node 58 elseif pedi>=0.1365 then node 59 else neg53 class = pos54 class = pos55 if mass<34.45 then node 60