决策树分类算法的时间和性能测试

1、决策树分类算法的时间和性能测试 姓名： ls 学号： 目录一、项目要求3二、基本思想3三、样本处理4四、实验及其分析91.总时间92.分类准确性.12五、结论及不足13附录14一、项目要求(1) 设计并实现决策树分类算法（可参考网上很多版本的决策树算法及代码，但算法的基本思想应为以上所给内容）。(2) 使用 UCI 的基准测试数据集，测试所实现的决策树分类算法。评价指标包括：总时间、分类准确性等。(3) 使用 UCI Iris Data Set 进行测试。2、 基本思想决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性变量上的测试，每个分支代表一个测试输出，而每个叶子节点代表类或

2、分布，树的最顶层节点是根节点。当需要预测一个未知样本的分类值时，基于决策树，沿着该树模型向下追溯，在树的每个节点将该样本的变量值和该节点变量的阈值进行比较，然后选取合适的分支，从而完成分类。决策树能够很容易地转换成分类规则，成为业务规则归纳系统的基础。决策树算法是非常常用的分类算法，是逼近离散目标函数的方法，学习得到的函数以决策树的形式表示。其基本思路是不断选取产生信息增益最大的属性来划分样例 集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。信息熵是香农提出的，用于描述信息不纯度(不稳定性)，其计算公式是Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。这样信息收益可

3、以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是三、样本处理以UCI提供的Iris Plants Database为测试样本，Iris Plants共有sepal-length ，sepal-width ，petal-length ，petal-width四种属性，根据属性的不同分为三种： class: - Iris Setosa - Iris Versicolour - Iris Virginica为方便实现，只取Iris Setosa和Iris Versicolour这两种植物的样例进行测试。实现该算法的样例集合如下：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根据样本说明中对样本的总统计：对四种属性进行进一步划分：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得到处理后的测试样例集为：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四、实验及其分析1.总时间(1).抽取不同规模的样例进行测试，比较决策树构造时间 随机抽取10组样例进行测试，运行结果如图2.6，总时间为0.05s图1 10组样例构建决策树随机抽取40组样例进行测试，运行结果如图2.6，总时间为0.167s图2 40组样例构建决策树随机抽取70组样例进行测试，运行结果如图2.6，总时间为0.369s图3 70组样例构建决策树选取100组样例进

23、行测试，运行结果如图2.6，总时间为0.646s图4 100组样例构建决策树得到样例数时间表：样例个数104070100运行时间(s)0.050.1670.3690.646表1. 样例数时间表画出样例数时间折线图：图4 样例数时间折线图由图4可以看出，本文的决策树分类算法的运行时间与样例数成正比关系。2. 分类准确性我们知道样本数越多对总体的估计就越准确，即对Iris Plants的种类的预估就越准确，所以我们只对100样例数时的运行结果进行分类准确性测试。图5 100组样例构建决策树可以用图形表示为：图 6 决策树随机抽取10组样例集合7,13,26,37,48,55,62,71,89,94

24、进行带入测试，×得到准确率为90%；随机抽取10组样例集合2,14,27,39,41,52,65,78,82,90进行带入测试，×，得到准确率为90%；随机抽取10组样例集合1,12,29,32,45,59,67,74,85,97进行带入测试，×，得到准确率为100%；综上，可以估计平均准确率约为93.3%。五、结论及不足结论：1. 本文实现的决策树分类算法的运行时间与样例数成正比关系。2. 用本算法进行Iris Plants预估的平均准确率约为93.3%。不足：1. 强行取平均值进行划分的方法略显僵硬。(我觉得还是可以.)2. 只实现了两种Iris Plants

25、的预估，Iris-virginica的样本没有用到。（详细代码在附录中）附录#include <iostream> #include <string> #include <vector> #include <map> #include <algorithm> #include <cmath> #include<time.h>using namespace std; #define MAXLEN 6/输?入?每?行D的?数簓据Y个?数簓 /多à叉?树骸?的?实害?现? /1 广?义?表括? /2 父?指

26、?针?表括?示?法?，?适酣?于?经-常找ò父?结á点?的?应畖用? /3 子哩?女?链?表括?示?法?，?适酣?于?经-常找ò子哩?结á点?的?应畖用? /4 左哩?长¤子哩?，?右?兄?弟台?表括?示?法?实害?现?比括?较?麻é烦? /5 每?个?结á点?的?所ù有瓺孩子哩?用?vector保馈?存? /教ì训:数簓据Y结á构1的?设?计?很ü重?要癮，?本?算?法?采é用?5比括?较?合?适酣?，?同?时骸? /注痢?意癮维?护¤剩骸?余?样ù例和

27、í剩骸?余?属?性?信?息，?建¨树骸?时骸?横á向ò遍括?历?考?循-环·属?性?的?值，? /纵罽向ò遍括?历?靠?递蘗归é调獭?用? vector <vector <string> > state;/实害?例集 vector <string> item(MAXLEN);/对?应畖一?行D实害?例集 vector <string> attribute_row;/保馈?存?首骸?行D即属?性?行D数簓据Y string end("end");/输?入?结&

28、#225;束? string Irissetosa("Iris-setosa"); string Irisversicolor("Iris-versicolor"); string Irisvirginica("Iris-virginica");string blank(""); map<string,vector < string > > map_attribute_values;/存?储洹?属?性?对?应畖的?所ù有瓺的?值 int tree_size = 0; struct

29、Node/决?策?树骸?节ú点? string attribute;/属?性?值 string arrived_value;/到?达?的?属?性?值 vector<Node *> childs;/所ù有瓺的?孩子哩? Node() attribute = blank; arrived_value = blank; ; Node * root; /根ù据Y数簓据Y实害?例计?算?属?性?与?值组哩?成é的?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(); /根ù据Y具?体?属?性?和í值来?计?算?熵? 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记?录?是?否?算?父?节ú点? if(!remain_stateiMAXLEN -

33、 1.compare(Irissetosa) count0+; else count1+; done_flag = true; if(count0 = 0 | count1 = 0 ) return 0;/全?部?是?正y实害?例或ò者?负o实害?例 /具?体?计?算?熵? 根ù据Y+count0,-count1,log2为a底獭?通?过y换?底獭?公?式?换?成é自?然?数簓底獭?数簓 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; /计?算?按恪?照?属?性?attribute划?分?当獭?前°剩骸?余?实害?例的?信?息增?益? double ComputeGain(vector <vector <string> > remain_state, string attribute) unsigned int j,k,m; /首骸?先è求ó不?做?划?分?时骸?的?熵? double parent_entropy = ComputeEntropy(remain_state

35、, attribute, blank, true); double children_entropy = 0; /然?后ó求ó做?划?分?后ó各÷个?值的?熵? 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占?多à数簓的?正y/负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负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; /计?算?信?息增?益?，?DFS构1建¨决?策?树骸? /current_node为a当獭?前°的?节ú点? /remain_state为a剩骸?余?待鋣分?类?的?样ù例 /remian_attribute为a剩骸?余?还1没?有瓺考?虑?的?属?性? /返?回?根ù结á点?指?针? 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)/所ù有瓺的?属?性?均ù已?经-考?虑?完?了?,还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、面?根ù据Ymax_it指?向ò的?属?性?来?划?分?当獭?前°样ù例，?更ü新?样ù例集和í属?性?集 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)/表括?示?当獭?前°没?有瓺这a个?分?支§的?样ù例

47、，?当獭?前°的?new_node为a叶?子哩?节ú点? new_node->attribute = MostCommonLabel(remain_state); else BulidDecisionTreeDFS(new_node, new_state, new_attribute); /递蘗归é函数簓返?回?时骸?即回?溯Y时骸?需è要癮1 将?新?结á点?加ó入?父?节ú点?孩子哩?容器÷ 2清?除ynew_state容器÷ p->childs.push_back(new_node);

48、new_state.erase(new_state.begin()+1,new_state.end();/注痢?意癮先è清?空?new_state中D的?前°一?个?取?值的?样ù例，?准?备?遍括?历?下?一?个?取?值样ù例 return p; void Input() string s; while(cin>>s,pare("end")!= 0)/-1为a输?入?结á束? item0 = s; for(int i = 1;i < MAXLEN; i+) cin>>itemi; state.push_back(item);/注痢?意癮首骸?行D信?息也?输?入?进?去?，?即属?性? 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 <