決策樹分類算法的時(shí)間和性能測(cè)試

1、決策樹分類算法的時(shí)間和性能測(cè)試 姓名： ls 學(xué)號(hào)： 目錄一、項(xiàng)目要求3二、基本思想3三、樣本處理4四、實(shí)驗(yàn)及其分析91.總時(shí)間92.分類準(zhǔn)確性.12五、結(jié)論及不足13附錄14一、項(xiàng)目要求(1) 設(shè)計(jì)并實(shí)現(xiàn)決策樹分類算法（可參考網(wǎng)上很多版本的決策樹算法及代碼，但算法的基本思想應(yīng)為以上所給內(nèi)容）。(2) 使用 UCI 的基準(zhǔn)測(cè)試數(shù)據(jù)集，測(cè)試所實(shí)現(xiàn)的決策樹分類算法。評(píng)價(jià)指標(biāo)包括：總時(shí)間、分類準(zhǔn)確性等。(3) 使用 UCI Iris Data Set 進(jìn)行測(cè)試。2、 基本思想決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性變量上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，而每個(gè)葉子節(jié)點(diǎn)代表類或

2、分布，樹的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。當(dāng)需要預(yù)測(cè)一個(gè)未知樣本的分類值時(shí)，基于決策樹，沿著該樹模型向下追溯，在樹的每個(gè)節(jié)點(diǎn)將該樣本的變量值和該節(jié)點(diǎn)變量的閾值進(jìn)行比較，然后選取合適的分支，從而完成分類。決策樹能夠很容易地轉(zhuǎn)換成分類規(guī)則，成為業(yè)務(wù)規(guī)則歸納系統(tǒng)的基礎(chǔ)。決策樹算法是非常常用的分類算法，是逼近離散目標(biāo)函數(shù)的方法，學(xué)習(xí)得到的函數(shù)以決策樹的形式表示。其基本思路是不斷選取產(chǎn)生信息增益最大的屬性來劃分樣例 集和，構(gòu)造決策樹。信息增益定義為結(jié)點(diǎn)與其子結(jié)點(diǎn)的信息熵之差。信息熵是香農(nóng)提出的，用于描述信息不純度(不穩(wěn)定性)，其計(jì)算公式是Pi為子集合中不同性(而二元分類即正樣例和負(fù)樣例)的樣例的比例。這樣信息收益可

3、以定義為樣本按照某屬性劃分時(shí)造成熵減少的期望，可以區(qū)分訓(xùn)練樣本中正負(fù)樣本的能力，其計(jì)算公式是三、樣本處理以UCI提供的Iris Plants Database為測(cè)試樣本，Iris Plants共有sepal-length ，sepal-width ，petal-length ，petal-width四種屬性，根據(jù)屬性的不同分為三種： class: - Iris Setosa - Iris Versicolour - Iris Virginica為方便實(shí)現(xiàn)，只取Iris Setosa和Iris Versicolour這兩種植物的樣例進(jìn)行測(cè)試。實(shí)現(xiàn)該算法的樣例集合如下：5.1,3.5,1.4,0.

4、2,Iris-setosa4.9,3.0,1.4,0.2,Iris-setosa4.7,3.2,1.3,0.2,Iris-setosa4.6,3.1,1.5,0.2,Iris-setosa5.0,3.6,1.4,0.2,Iris-setosa5.4,3.9,1.7,0.4,Iris-setosa4.6,3.4,1.4,0.3,Iris-setosa5.0,3.4,1.5,0.2,Iris-setosa4.4,2.9,1.4,0.2,Iris-setosa4.9,3.1,1.5,0.1,Iris-setosa5.4,3.7,1.5,0.2,Iris-setosa4.8,3.4,1.6,0.2,I

5、ris-setosa4.8,3.0,1.4,0.1,Iris-setosa4.3,3.0,1.1,0.1,Iris-setosa5.8,4.0,1.2,0.2,Iris-setosa5.7,4.4,1.5,0.4,Iris-setosa5.4,3.9,1.3,0.4,Iris-setosa5.1,3.5,1.4,0.3,Iris-setosa5.7,3.8,1.7,0.3,Iris-setosa5.1,3.8,1.5,0.3,Iris-setosa5.4,3.4,1.7,0.2,Iris-setosa5.1,3.7,1.5,0.4,Iris-setosa4.6,3.6,1.0,0.2,Iris

6、-setosa5.1,3.3,1.7,0.5,Iris-setosa4.8,3.4,1.9,0.2,Iris-setosa5.0,3.0,1.6,0.2,Iris-setosa5.0,3.4,1.6,0.4,Iris-setosa5.2,3.5,1.5,0.2,Iris-setosa5.2,3.4,1.4,0.2,Iris-setosa4.7,3.2,1.6,0.2,Iris-setosa4.8,3.1,1.6,0.2,Iris-setosa5.4,3.4,1.5,0.4,Iris-setosa5.2,4.1,1.5,0.1,Iris-setosa5.5,4.2,1.4,0.2,Iris-se

7、tosa4.9,3.1,1.5,0.1,Iris-setosa5.0,3.2,1.2,0.2,Iris-setosa5.5,3.5,1.3,0.2,Iris-setosa4.9,3.1,1.5,0.1,Iris-setosa4.4,3.0,1.3,0.2,Iris-setosa5.1,3.4,1.5,0.2,Iris-setosa5.0,3.5,1.3,0.3,Iris-setosa4.5,2.3,1.3,0.3,Iris-setosa4.4,3.2,1.3,0.2,Iris-setosa5.0,3.5,1.6,0.6,Iris-setosa5.1,3.8,1.9,0.4,Iris-setos

8、a4.8,3.0,1.4,0.3,Iris-setosa5.1,3.8,1.6,0.2,Iris-setosa4.6,3.2,1.4,0.2,Iris-setosa5.3,3.7,1.5,0.2,Iris-setosa5.0,3.3,1.4,0.2,Iris-setosa7.0,3.2,4.7,1.4,Iris-versicolor6.4,3.2,4.5,1.5,Iris-versicolor6.9,3.1,4.9,1.5,Iris-versicolor5.5,2.3,4.0,1.3,Iris-versicolor6.5,2.8,4.6,1.5,Iris-versicolor5.7,2.8,4

9、.5,1.3,Iris-versicolor6.3,3.3,4.7,1.6,Iris-versicolor4.9,2.4,3.3,1.0,Iris-versicolor6.6,2.9,4.6,1.3,Iris-versicolor5.2,2.7,3.9,1.4,Iris-versicolor5.0,2.0,3.5,1.0,Iris-versicolor5.9,3.0,4.2,1.5,Iris-versicolor6.0,2.2,4.0,1.0,Iris-versicolor6.1,2.9,4.7,1.4,Iris-versicolor5.6,2.9,3.6,1.3,Iris-versicolo

10、r6.7,3.1,4.4,1.4,Iris-versicolor5.6,3.0,4.5,1.5,Iris-versicolor5.8,2.7,4.1,1.0,Iris-versicolor6.2,2.2,4.5,1.5,Iris-versicolor5.6,2.5,3.9,1.1,Iris-versicolor5.9,3.2,4.8,1.8,Iris-versicolor6.1,2.8,4.0,1.3,Iris-versicolor6.3,2.5,4.9,1.5,Iris-versicolor6.1,2.8,4.7,1.2,Iris-versicolor6.4,2.9,4.3,1.3,Iris

11、-versicolor6.6,3.0,4.4,1.4,Iris-versicolor6.8,2.8,4.8,1.4,Iris-versicolor6.7,3.0,5.0,1.7,Iris-versicolor6.0,2.9,4.5,1.5,Iris-versicolor5.7,2.6,3.5,1.0,Iris-versicolor5.5,2.4,3.8,1.1,Iris-versicolor5.5,2.4,3.7,1.0,Iris-versicolor5.8,2.7,3.9,1.2,Iris-versicolor6.0,2.7,5.1,1.6,Iris-versicolor5.4,3.0,4.

12、5,1.5,Iris-versicolor6.0,3.4,4.5,1.6,Iris-versicolor6.7,3.1,4.7,1.5,Iris-versicolor6.3,2.3,4.4,1.3,Iris-versicolor5.6,3.0,4.1,1.3,Iris-versicolor5.5,2.5,4.0,1.3,Iris-versicolor5.5,2.6,4.4,1.2,Iris-versicolor6.1,3.0,4.6,1.4,Iris-versicolor5.8,2.6,4.0,1.2,Iris-versicolor5.0,2.3,3.3,1.0,Iris-versicolor

13、5.6,2.7,4.2,1.3,Iris-versicolor5.7,3.0,4.2,1.2,Iris-versicolor5.7,2.9,4.2,1.3,Iris-versicolor6.2,2.9,4.3,1.3,Iris-versicolor5.1,2.5,3.0,1.1,Iris-versicolor5.7,2.8,4.1,1.3,Iris-versicolor根據(jù)樣本說明中對(duì)樣本的總統(tǒng)計(jì)：對(duì)四種屬性進(jìn)行進(jìn)一步劃分：sepal-length 4.3-5.84 a5.84-7.9 bsepal-width2.0-3.05 c3.05-4.4 dpetal-length 1.0-3.76

14、e3.76-6.9 fpetal-width0.1-1.20 g1.20-2.5 h得到處理后的測(cè)試樣例集為：test sepal-length sepal-width petal-length petal-width class1 a d e g Iris-setosa2 a c e g Iris-setosa3 a d e g Iris-setosa4 a d e g Iris-setosa5 a d e g Iris-setosa6 a d e g Iris-setosa7 a d e g Iris-setosa8 a d e g Iris-setosa9 a c e g Iris-se

15、tosa10 a d e g Iris-setosa11 a d e g Iris-setosa12 a d e g Iris-setosa13 a c e g Iris-setosa14 a c e g Iris-setosa15 a d e g Iris-setosa16 a d e g Iris-setosa17 a d e g Iris-setosa18 a d e g Iris-setosa19 a d e g Iris-setosa20 a d e g Iris-setosa21 a d e g Iris-setosa22 a d e g Iris-setosa23 a d e g

16、 Iris-setosa24 a d e g Iris-setosa25 a d e g Iris-setosa26 a c e g Iris-setosa27 a d e g Iris-setosa28 a d e g Iris-setosa29 a d e g Iris-setosa30 a d e g Iris-setosa31 a d e g Iris-setosa32 a d e g Iris-setosa33 a d e g Iris-setosa34 a d e g Iris-setosa35 a d e g Iris-setosa36 a d e g Iris-setosa37

17、 a d e g Iris-setosa38 a d e g Iris-setosa39 a c e g Iris-setosa40 a d e g Iris-setosa41 a d e g Iris-setosa42 a c e g Iris-setosa43 a d e g Iris-setosa44 a d e g Iris-setosa45 a d e g Iris-setosa46 a c e g Iris-setosa47 a d e g Iris-setosa48 a d e g Iris-setosa49 a d e g Iris-setosa50 a d e g Iris-

18、setosa51 b d f h Iris-versicolor52 b d f h Iris-versicolor53 b d f h Iris-versicolor54 a c f h Iris-versicolor55 b c f h Iris-versicolor56 a c f h Iris-versicolor57 b d f h Iris-versicolor58 a c e g Iris-versicolor59 b c f h Iris-versicolor60 a c f h Iris-versicolor61 a c e g Iris-versicolor62 b c f

19、 h Iris-versicolor63 b c f g Iris-versicolor64 b c f h Iris-versicolor65 a c e h Iris-versicolor66 b d f h Iris-versicolor67 a c f h Iris-versicolor68 a c f g Iris-versicolor69 b c f h Iris-versicolor70 a c f g Iris-versicolor71 b d f h Iris-versicolor72 b c f h Iris-versicolor73 b c f h Iris-versic

20、olor74 b c f g Iris-versicolor75 b c f h Iris-versicolor76 b c f h Iris-versicolor77 b c f h Iris-versicolor78 b c f h Iris-versicolor79 b c f h Iris-versicolor80 a c e g Iris-versicolor81 a c f g Iris-versicolor82 a c e g Iris-versicolor83 a c f g Iris-versicolor84 b c f h Iris-versicolor85 a c f h

21、 Iris-versicolor86 b d f h Iris-versicolor87 b d f h Iris-versicolor88 b c f h Iris-versicolor89 a c f h Iris-versicolor90 a c f h Iris-versicolor91 a c f g Iris-versicolor92 b c f h Iris-versicolor93 a c f g Iris-versicolor94 a c e g Iris-versicolor95 a c f h Iris-versicolor96 a c f g Iris-versicol

22、or97 a c f h Iris-versicolor98 b c f h Iris-versicolor99 a c e g Iris-versicolor100 a c f h Iris-versicolorEnd四、實(shí)驗(yàn)及其分析1.總時(shí)間(1).抽取不同規(guī)模的樣例進(jìn)行測(cè)試，比較決策樹構(gòu)造時(shí)間 隨機(jī)抽取10組樣例進(jìn)行測(cè)試，運(yùn)行結(jié)果如圖2.6，總時(shí)間為0.05s圖1 10組樣例構(gòu)建決策樹隨機(jī)抽取40組樣例進(jìn)行測(cè)試，運(yùn)行結(jié)果如圖2.6，總時(shí)間為0.167s圖2 40組樣例構(gòu)建決策樹隨機(jī)抽取70組樣例進(jìn)行測(cè)試，運(yùn)行結(jié)果如圖2.6，總時(shí)間為0.369s圖3 70組樣例構(gòu)建決策樹選取100組樣例進(jìn)

23、行測(cè)試，運(yùn)行結(jié)果如圖2.6，總時(shí)間為0.646s圖4 100組樣例構(gòu)建決策樹得到樣例數(shù)時(shí)間表：樣例個(gè)數(shù)104070100運(yùn)行時(shí)間(s)0.050.1670.3690.646表1. 樣例數(shù)時(shí)間表畫出樣例數(shù)時(shí)間折線圖：圖4 樣例數(shù)時(shí)間折線圖由圖4可以看出，本文的決策樹分類算法的運(yùn)行時(shí)間與樣例數(shù)成正比關(guān)系。2. 分類準(zhǔn)確性我們知道樣本數(shù)越多對(duì)總體的估計(jì)就越準(zhǔn)確，即對(duì)Iris Plants的種類的預(yù)估就越準(zhǔn)確，所以我們只對(duì)100樣例數(shù)時(shí)的運(yùn)行結(jié)果進(jìn)行分類準(zhǔn)確性測(cè)試。圖5 100組樣例構(gòu)建決策樹可以用圖形表示為：圖 6 決策樹隨機(jī)抽取10組樣例集合7,13,26,37,48,55,62,71,89,94

24、進(jìn)行帶入測(cè)試，×得到準(zhǔn)確率為90%；隨機(jī)抽取10組樣例集合2,14,27,39,41,52,65,78,82,90進(jìn)行帶入測(cè)試，×，得到準(zhǔn)確率為90%；隨機(jī)抽取10組樣例集合1,12,29,32,45,59,67,74,85,97進(jìn)行帶入測(cè)試，×，得到準(zhǔn)確率為100%；綜上，可以估計(jì)平均準(zhǔn)確率約為93.3%。五、結(jié)論及不足結(jié)論：1. 本文實(shí)現(xiàn)的決策樹分類算法的運(yùn)行時(shí)間與樣例數(shù)成正比關(guān)系。2. 用本算法進(jìn)行Iris Plants預(yù)估的平均準(zhǔn)確率約為93.3%。不足：1. 強(qiáng)行取平均值進(jìn)行劃分的方法略顯僵硬。(我覺得還是可以.)2. 只實(shí)現(xiàn)了兩種Iris Plants

25、的預(yù)估，Iris-virginica的樣本沒有用到。（詳細(xì)代碼在附錄中）附錄#include <iostream> #include <string> #include <vector> #include <map> #include <algorithm> #include <cmath> #include<time.h>using namespace std; #define MAXLEN 6/輸?入?每?行D的?數(shù)簓據(jù)Y個(gè)?數(shù)簓 /多à叉?樹骸?的?實(shí)害?現(xiàn)? /1 廣?義?表括? /2 父?指

26、?針?表括?示?法?，?適酣?于?經(jīng)-常找ò父?結(jié)á點(diǎn)?的?應(yīng)畖用? /3 子哩?女?鏈?表括?示?法?，?適酣?于?經(jīng)-常找ò子哩?結(jié)á點(diǎn)?的?應(yīng)畖用? /4 左哩?長(zhǎng)¤子哩?，?右?兄?弟臺(tái)?表括?示?法?實(shí)害?現(xiàn)?比括?較?麻é煩? /5 每?個(gè)?結(jié)á點(diǎn)?的?所ù有瓺孩子哩?用?vector保饋?存? /教ì訓(xùn):數(shù)簓據(jù)Y結(jié)á構(gòu)1的?設(shè)?計(jì)?很ü重?要癮，?本?算?法?采é用?5比括?較?合?適酣?，?同?時(shí)骸? /注痢?意癮維?護(hù)¤剩骸?余?樣ù例和

27、í剩骸?余?屬?性?信?息，?建¨樹骸?時(shí)骸?橫á向ò遍括?歷?考?循-環(huán)·屬?性?的?值，? /縱罽向ò遍括?歷?靠?遞蘗歸é調(diào)獺?用? vector <vector <string> > state;/實(shí)害?例集 vector <string> item(MAXLEN);/對(duì)?應(yīng)畖一?行D實(shí)害?例集 vector <string> attribute_row;/保饋?存?首骸?行D即屬?性?行D數(shù)簓據(jù)Y string end("end");/輸?入?結(jié)&

28、#225;束? string Irissetosa("Iris-setosa"); string Irisversicolor("Iris-versicolor"); string Irisvirginica("Iris-virginica");string blank(""); map<string,vector < string > > map_attribute_values;/存?儲(chǔ)洹?屬?性?對(duì)?應(yīng)畖的?所ù有瓺的?值 int tree_size = 0; struct

29、Node/決?策?樹骸?節(jié)ú點(diǎn)? string attribute;/屬?性?值 string arrived_value;/到?達(dá)?的?屬?性?值 vector<Node *> childs;/所ù有瓺的?孩子哩? Node() attribute = blank; arrived_value = blank; ; Node * root; /根ù據(jù)Y數(shù)簓據(jù)Y實(shí)害?例計(jì)?算?屬?性?與?值組哩?成é的?map void ComputeMapFrom2DVector() unsigned int i,j,k; bool exited = fa

30、lse; vector<string> values; for(i = 1; i < MAXLEN-1; i+)/按恪?照?列遍括?歷? for (j = 1; j < state.size(); j+) for (k = 0; k < values.size(); k+) if(!pare(stateji) exited = true; if(!exited) values.push_back(stateji);/注痢?意癮Vector的?插?入?都?是?從洙?前°面?插?入?的?，?注痢?意癮更ü新?it，?始?終?指

31、?向òvector頭? exited = false; map_attribute_valuesstate0i = values; values.erase(values.begin(), values.end(); /根ù據(jù)Y具?體?屬?性?和í值來?計(jì)?算?熵? double ComputeEntropy(vector <vector <string> > remain_state, string attribute, string value,bool ifparent) vector<int> count (2,0);

32、unsigned int i,j; bool done_flag = false;/哨?兵?值 for(j = 1; j < MAXLEN; j+) if(done_flag) break; if(!attribute_pare(attribute) for(i = 1; i < remain_state.size(); i+) if(!ifparent&&!remain_pare(value) | ifparent)/ifparent記?錄?是?否?算?父?節(jié)ú點(diǎn)? if(!remain_stateiMAXLEN -

33、 1.compare(Irissetosa) count0+; else count1+; done_flag = true; if(count0 = 0 | count1 = 0 ) return 0;/全?部?是?正y實(shí)害?例或ò者?負(fù)o實(shí)害?例 /具?體?計(jì)?算?熵? 根ù據(jù)Y+count0,-count1,log2為a底獺?通?過y換?底獺?公?式?換?成é自?然?數(shù)簓底獺?數(shù)簓 double sum = count0 + count1; double entropy = -count0/sum*log(count0/sum)/log(2.0) - cou

34、nt1/sum*log(count1/sum)/log(2.0); return entropy; /計(jì)?算?按恪?照?屬?性?attribute劃?分?當(dāng)獺?前°剩骸?余?實(shí)害?例的?信?息增?益? double ComputeGain(vector <vector <string> > remain_state, string attribute) unsigned int j,k,m; /首骸?先è求ó不?做?劃?分?時(shí)骸?的?熵? double parent_entropy = ComputeEntropy(remain_state

35、, attribute, blank, true); double children_entropy = 0; /然?后ó求ó做?劃?分?后ó各÷個(gè)?值的?熵? vector<string> values = map_attribute_valuesattribute; vector<double> ratio; vector<int> count_values; int tempint; for(m = 0; m < values.size(); m+) tempint = 0; for(k = 1; k &l

36、t; MAXLEN - 1; k+) if(!attribute_pare(attribute) for(j = 1; j < remain_state.size(); j+) if(!remain_pare(valuesm) tempint+; count_values.push_back(tempint); for(j = 0; j < values.size(); j+) ratio.push_back(double)count_valuesj / (double)(remain_state.size()-1); double temp_

37、entropy; for(j = 0; j < values.size(); j+) temp_entropy = ComputeEntropy(remain_state, attribute, valuesj, false); children_entropy += ratioj * temp_entropy; return (parent_entropy - children_entropy); int FindAttriNumByName(string attri) for(int i = 0; i < MAXLEN; i+) if(!pare(attr

38、i) return i; cerr<<"can't find the numth of attribute"<<endl; return 0; /找ò出?樣ù例中D占?多à數(shù)簓的?正y/負(fù)o性? string MostCommonLabel(vector <vector <string> > remain_state) int p = 0, n = 0; for(unsigned i = 0; i < remain_state.size(); i+) if(!remain_state

39、iMAXLEN-1.compare(Irissetosa) p+; else n+; if(p >= n) return Irissetosa; else return Irisversicolor; /判D斷?樣ù例是?否?正y負(fù)o性?都?為alabel bool AllTheSameLabel(vector <vector <string> > remain_state, string label) int count = 0; for(unsigned int i = 0; i < remain_state.size(); i+) if(!r

40、emain_stateiMAXLEN-1.compare(label) count+; if(count = remain_state.size()-1) return true; else return false; /計(jì)?算?信?息增?益?，?DFS構(gòu)1建¨決?策?樹骸? /current_node為a當(dāng)獺?前°的?節(jié)ú點(diǎn)? /remain_state為a剩骸?余?待鋣分?類?的?樣ù例 /remian_attribute為a剩骸?余?還1沒?有瓺考?慮?的?屬?性? /返?回?根ù結(jié)á點(diǎn)?指?針? Node * BulidDec

41、isionTreeDFS(Node * p, vector <vector <string> > remain_state, vector <string> remain_attribute) /if(remain_state.size() > 0) /printv(remain_state); / if (p = NULL) p = new Node(); /先è看搜?索÷到?樹骸?葉?的?情é況? if (AllTheSameLabel(remain_state, Irissetosa) p->attribute

42、 = Irissetosa; return p; if (AllTheSameLabel(remain_state, Irisversicolor) p->attribute = Irisversicolor; return p; if(remain_attribute.size() = 0)/所ù有瓺的?屬?性?均ù已?經(jīng)-考?慮?完?了?,還1沒?有瓺分?盡? string label = MostCommonLabel(remain_state); p->attribute = label; return p; double max_gain = 0, t

43、emp_gain; vector <string>:iterator max_it = remain_attribute.begin(); vector <string>:iterator it1; for(it1 = remain_attribute.begin(); it1 < remain_attribute.end(); it1+) temp_gain = ComputeGain(remain_state, (*it1); if(temp_gain > max_gain) max_gain = temp_gain; max_it = it1; /下?

44、面?根ù據(jù)Ymax_it指?向ò的?屬?性?來?劃?分?當(dāng)獺?前°樣ù例，?更ü新?樣ù例集和í屬?性?集 vector <string> new_attribute; vector <vector <string> > new_state; for(vector <string>:iterator it2 = remain_attribute.begin(); it2 < remain_attribute.end(); it2+) if(*it2).compare(*m

45、ax_it) new_attribute.push_back(*it2); /確?定¨了?最?佳?劃?分?屬?性?，?注痢?意癮保饋?存? p->attribute = *max_it; vector <string> values = map_attribute_values*max_it; int attribue_num = FindAttriNumByName(*max_it); new_state.push_back(attribute_row); for(vector <string>:iterator it3 = values.begin(

46、); it3 < values.end(); it3+) for(unsigned int i = 1; i < remain_state.size(); i+) if(!remain_stateiattribue_pare(*it3) new_state.push_back(remain_statei); Node * new_node = new Node(); new_node->arrived_value = *it3; if(new_state.size() = 0)/表括?示?當(dāng)獺?前°沒?有瓺這a個(gè)?分?支§的?樣ù例

47、，?當(dāng)獺?前°的?new_node為a葉?子哩?節(jié)ú點(diǎn)? new_node->attribute = MostCommonLabel(remain_state); else BulidDecisionTreeDFS(new_node, new_state, new_attribute); /遞蘗歸é函數(shù)簓返?回?時(shí)骸?即回?溯Y時(shí)骸?需è要癮1 將?新?結(jié)á點(diǎn)?加ó入?父?節(jié)ú點(diǎn)?孩子哩?容器÷ 2清?除ynew_state容器÷ p->childs.push_back(new_node);

48、new_state.erase(new_state.begin()+1,new_state.end();/注痢?意癮先è清?空?new_state中D的?前°一?個(gè)?取?值的?樣ù例，?準(zhǔn)?備?遍括?歷?下?一?個(gè)?取?值樣ù例 return p; void Input() string s; while(cin>>s,pare("end")!= 0)/-1為a輸?入?結(jié)á束? item0 = s; for(int i = 1;i < MAXLEN; i+) cin>>itemi; state.push_back(item);/注痢?意癮首骸?行D信?息也?輸?入?進(jìn)?去?，?即屬?性? for(int j = 0; j < MAXLEN; j+) attribute_row.push_back(state0j); void PrintTree(Node *p, int depth) for (int i = 0; i < depth; i+) cout <