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

1、决策树分类算法的时间和性能测试姓名:学号:ls32咬K怒忠埋甬 料也愕整湫氽.E回te膜.16监畜怒象s 寸戛芸M m曲#n E爵皿wf眠皿一、项目要求(1)设计并实现决策树分类算法(可参考网上很多版本的决策树算法及代码， 但算法的基本思想应为以上所给内容)。使用UCI的基准测试数据集，测试所实现的决策树分类算法。评价指标 包括：总时间、分类准确性等。(3)使用UCI Iris Data Set进行测试。二、基本思想决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性变 量上的测试，每个分支代表一个测试输出，而每个叶子节点代表类或分布，树的 最顶层节点是根节点。当需要预测一个未知样

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

3、例。这样信 息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本 中正负样本的能力，其计算公式是G讷(S, A) = Entropy (S) - -EiUropy (Sr)】宅衫IS | F(A)是届性A的值域, S是样本集合. M是S中在属性A上值等于V曲样本集合三、样本处理以 UCI 提供的 Iris Plants Database 为测试样本，Iris Plants 共有 sepal-length , sepal-width , petal-length , petal-width四种属性，根据属性的不同分为三种： class:-Iris Setosa-Iris Ver

4、sicolour-Iris Virginica为方便实现，只取Iris Setosa和Iris Versicolour这两种植物的样例进行测试。 实现该算法的样例集合如下：5.1,3.5,1.4,0.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-seto

5、sa4.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,Iris-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

6、.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-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,

7、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-setosa0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 5 5 3 5 3 6 0 3 4 0 5 0 4 3 4 5 0 5 1 8 3 5 2 3 4 4.1.4,.1.5,5.0,3.2,1.2,.1.3,.1.5,4.4,3.0,1.3,.1.5,5.0,3.5,1.3,.1.3,.1.3,5.0,3.5,1.6,5.1,3.8,1.9,4.8,3.0,1.4,.1.6,.1.4,.1.5,5.0,3.3,1.4,7.

8、0,3.2,4.7,1.4.5.1.4.9.1.5.5,2.3,4.0,1.4.6.1.4.5.1.4.7.1.3.3.1.4.6.1.3.9.1.5.0,2.0,3.5,1.5.9,3.0,4.2,1.6.0,2.2,4.0,1.4.7.1.3.6.1.4.4.1.5.6,3.0,4.5,1.4.1.1.4.5.1.3.9.1.4.8.1.6.1,2.8,4.0,1.4.9.1.4.7.1.4.3.1.6.6,3.0,4.4,1.4.8.1.2,Iris-setosa.1,Iris-setosa.2,Iris-setosa.2,Iris-setosa.1,Iris-setosa.2,Iris

9、-setosa.2,Iris-setosa.3,Iris-setosa.3,Iris-setosa.2,Iris-setosa.6,Iris-setosa.4,Iris-setosa.3,Iris-setosa.2,Iris-setosa.2,Iris-setosa.2,Iris-setosa.2,Iris-setosa,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versi

10、color,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor,Iris-versicolor6.7,3.0

11、,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.5,1.5,Iris-versicolor6.0,3.4,4.5,1.6,Iris-versicolor6.7,3.1,4.7,1.5,Iris-versico

12、lor6.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-versicolor5.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,Ir

13、is-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根据样本说明中对样本的总统计:Summary Statistics:MinMaxM已anSDClass Correlationsepallength: 4. 37. 95. 840. 830. 7826sepalwidth: 2. 04. 43. 050. 43-0. 4194petallength: 1. 06. 93. 761. 760.9490 (high!)petalwidth

14、: 0. 12. 51. 200. 760.9565 (high!)对四种属性进行进一步划分:sepal-length4.3-5.84 a5.84-7.9 bsepal-width2.0-3.05 c3.05-4.4 dpetal-length1.0-3.76 e3.76-6.9 fpetal-width0.1-1.20 g1.20-2.5 h得到处理后的测试样例集为：test sepal-length sepal-width petal-length petal-width classa d e g Iris-setosaa c e g Iris-setosaa d e g Iris-set

15、osaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa c e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa c e g Iris-setosaa c e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris

16、-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa c e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g

17、Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa c e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa c e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa c e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosaa d e g Iris-setosab d

18、f h Iris-versicolorb d f h Iris-versicolorb d f h Iris-versicolora c f h Iris-versicolorb c f h Iris-versicolora c f h Iris-versicolorb d f h Iris-versicolora c e g Iris-versicolorb c f h Iris-versicolora c f h Iris-versicolora c e g Iris-versicolorb c f h Iris-versicolorb c f g Iris-versicolorb c f

19、 h Iris-versicolora c e h Iris-versicolorb d f h Iris-versicolora c f h Iris-versicolora c f g Iris-versicolorb c f h Iris-versicolora c f g Iris-versicolorb d f h Iris-versicolorb c f h Iris-versicolorb c f h Iris-versicolorb c f g Iris-versicolorb c f h Iris-versicolorb c f h Iris-versicolorb c f

20、h Iris-versicolorb c f h Iris-versicolorb c f h Iris-versicolora c e g Iris-versicolora c f g Iris-versicolora c e g Iris-versicolora c f g Iris-versicolorb c f h Iris-versicolora c f h Iris-versicolorb d f h Iris-versicolorb d f h Iris-versicolorb c f h Iris-versicolora c f h Iris-versicolora c f h

21、 Iris-versicolora c f g Iris-versicolorb c f h Iris-versicolora c f g Iris-versicolora c e g Iris-versicolora c f h Iris-versicolora c f g Iris-versicolora c f h Iris-versicolorb c f h Iris-versicolora c e g Iris-versicolora c f h Iris-versicolorEnd四、实验及其分析1.总时间.抽取不同规模的样例进行测试，比较决策树构造时间随机抽取10组样例进行测试，

22、运行结果如图2.6，总时间为0.05sEE:算法设计作业展策树Debugg策树.exeIris-setosa Iris-setosaI ris-setosaI vis-ueis ico lorI vis-ueis ico lor 11is-uers ico lor Iris-uers icolor I ris-uers icolorest sepal-length sepal-width petal-length petal-width class a d e g Iris-setosa a c e g Ipis-setosa a3678tree is :Y a nd he dec is io

23、n epal-width dIris-setosapetal-length esepal-length apetal-width3Iiis-uersicolorIris-setosaIris-setosaI r is-u e rs ic o lo r随机抽取40组样例进行测试，运行结果如图2.6,总时间为0.167she decision tree is :etal-lengthesepal-width dIris-setosacpetal-widthgsepal-lengthaIris-setosabIris-setosahIris-uersicolorfIris-uersicolorree

24、_size：9图2 40组样例构建决策树随机抽取70组样例进行测试，运行结果如图2.6,总时间为0.369sUE:算法设计作业牍策树bu g欢策】nd he decision tree is : etal-length e sepal-width d Iris-setosa c petal-width g sepal-length aIris-setosa bIris-setosa hIris-uersicolor f Iris-uersicolorree_size :9选取100组样例进行测试，运行结果如图2.6，总时间为0.646s图4 100组样例构建决策树得到样例数一时间表:样例个数1

25、04070100运行时间(s)0.050.1670.3690.646表1.样例数一时间表画出样例数一时间折线图:图4样例数一时间折线图由图4可以看出，本文的决策树分类算法的运行时间与样例数成正比关系。2.分类准确性我们知道样本数越多对总体的估计就越准确，即对Iris Plants的种类的预估就越准确，所以我们只对100样例数时的运行结果进行分类准确性测试。可以用图形表示为:Ins随机抽取10组样例集合7,13,26,37,48,55,62,71,89,94进行带入测试，/V,V,V,V,V,V,V,x）得到准确率为 90%；随机抽取10组样例集合2,14,27,39,41,52,65,78,8

26、2,90进行带入测试，/V,V,V,V,V,V,x,V得到准确率为 90%；随机抽取10组样例集合1,12,29,32,45,59,67,74,85,97进行带入测试，/,/,V,V,V,V,V,V,X,V得到准确率为 100%；综上，可以估计平均准确率约为93.3%。五、结论及不足结论：本文实现的决策树分类算法的运行时间与样例数成正比关系。用本算法进行Iris Plants预估的平均准确率约为93.3%。不足：强行取平均值进行划分的方法略显僵硬。（我觉得还是可以.）只实现了两种Iris Plants的预估，Iris-virginica的样本没有用到。（详细代码在附录中）附录#include

27、#include #include #include #include #include #includeusing namespace std;#define MAXLEN 6/输?入?每？行D的？数筋据Y个?数筋多d叉?树骸？的?实害?现？/1广?义?表括？/2父?指?针?表括?示?法勤？，？适酣?于？经-常找。父?结d点？的?应畖用？/3子哩?女?链i ?表括?示?法勤？，？适酣?于？经-常找。子哩？结d点？的？应畖用？/4左哩?长Q子哩？，？右？兄?弟台?表括?示?法打实害?现？比括?较?麻6烦？/5每?个?结d点？的?所H有甄孩C子哩?用？vector保馈?存？教1训U :数筋据Y结

28、d构1的？设?计?很U重?要瘾，？本?算?法勤？采6用？5比括?较?合?适酣？，? 同？时骸？/注痢?意瘾维?护Q剩骸?余？样例 和i剩骸?余？属?性?信？息0，?建.树骸?时骸?横d向b遍括? 历?考？循-环属？性？的？值U，?/纵罽向b遍括?历 ?靠?递麋归6调獭?用？vector vector state; /实害?例 集一vector item(MAXLEN); /对?应畖一？行 D 实害？例 集一vector attribute_row;/保馈?存？首骸？行D即属?性?彳亍D数筋据Y string end(end);/输？入？结d束？ string Irissetosa(Iris-s

29、etosa);string Irisversicolor(Iris-versicolor);string Irisvirginica(Iris-virginica);string blank();mapstring,vector map_attribute_values;/存？储洹？属？性？对？应畖的？所H有甄的？ 值U int tree_size = 0;struct Node(/决？策？树骸？节U点？string attribute; /属？性？值 ustring arrived_value; /到？达？的？属？性?值 uvector childs;/所H有甄的？孩0子哩？Node()(a

30、ttribute = blank;arrived_value = blank;Node * root;根n据Y数筋据Y实害?例 计?算?属?性?与?值u组哩?成6的?mapvoid ComputeMapFrom2DVector()(unsigned int i,j,k;bool exited = false;vector 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

31、= true;if (!exited)(values.push_back(stateji);/注痢？意瘾 Vector 的？插？入？都？是？从洙？ 前。面?插?入？的？，？注痢？意瘾更U新？it, ?始?终?指？向ovector头？exited = false;map_attribute_valuesstate0i = values;values.erase(values.begin(), values.end();根n据y具?体?属?性?和H直u来勤？计?算?熵？double ComputeEntropy(vector vector remain_state, string attribut

32、e, string value, bool ifparent)(vector count (2,0);unsigned int i,j;bool done_flag = false;/哨?兵？值ufor(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 记？录？是？否？算？父？节U点？if (!remain_sta

33、teiMAXLEN - pare(Irissetosa) count0+;else count1+;done_flag = true;if(count0 = 0 | | count1 = 0 ) return 0;/全?部?是?正 y 实害?例 或b者?负 o 实害? 例具?体?计?算?熵？根H据Y+count0,-count1,log2为a底獭?通？过y换?底獭?公?式? 换?成6自？然?数筋底獭?数筋double sum = count0 + count1;double entropy = -count0/sum*log(count0/sum)/log(2.0)- count1/sum*l

34、og(count1/sum)/log(2.0);return entropy;计?算?按恪?照?属?性?attribute划?分？当獭?前。乘U骸?余？实害?例 的?信？息C增？益？ double ComputeGain(vector vector remain_state, string attribute)( unsigned int j,k,m;/首骸?先仓求6不?做?划?分?时骸？的?熵？double parent_entropy = ComputeEntropy(remain_state, attribute, blank, true);double children_entropy

35、 = 0;然?后6求6做?划?分?后6各：个?值u的?熵？vector values = map_attribute_valuesattribute;vector ratio;vector count_values;int tempint;for (m = 0; m values.size(); m+)(tempint = 0;for (k = 1; k MAXLEN - 1; k+)(if(!attribute_pare(attribute)for (j = 1; j remain_state.size(); j+)if (!remain_pare(valuesm) tempint+;cou

36、nt_values.push_back(tempint);for (j = 0; j values.size(); j+)ratio.push_back(double)count_valuesj / (double)(remain_state.size()-1);double temp_entropy;for (j = 0; j values.size(); j+)temp_entropy = ComputeEntropy(remain_state, attribute, valuesj, false); children_entropy += ratioj * temp_entropy;re

37、turn (parent_entropy - children_entropy);int FindAttriNumByName(string attri)(for(int i = 0; i MAXLEN; i+)( if(!pare(attri) return i;cerrcant find the numth of attributeendl;return 0;找b出?样n例 中D占？多&数筋的？正y/负o性？string MostCommonLabel(vector vector remain_state)( int p = 0, n = 0;for (unsigned i = 0; i

38、= n) return Irissetosa; else return Irisversicolor;判D断?样n例 是?否？正y负o性?都?为alabelbool AllTheSameLabel(vector vector remain_state, string label)( int count = 0;for (unsigned int i = 0; i remain_state.size(); i+)(if (!remain_stateiMAXLEN-pare(label) count+;if (count = remain_state.size()-1) return true;e

39、lse return false;计?算?信？息0增？益？，?DFS构1建.决?策?树骸？/current_node为a当獭？前的？节U点？/remain_state为a剩骸?余？待部分?类 ?的?样n例/remian_attribute为a剩骸?余？还1没?有甄考?虑？的？属？性？返关回？根n结d点？指?针？Node * BulidDecisionTreeDFS(Node * p, vector vector remain_state, vector remain_attribute)(/if(remain_state.size() 0)( /printv(remain_state);/ i

40、f (p = NULL)p = new Node();/先仓看搜?索：到?树骸？叶？的?情6况？if (AllTheSameLabel(remain_state, Irissetosa)( p-attribute = Irissetosa; return p;if (AllTheSameLabel(remain_state, Irisversicolor)( p-attribute = Irisversicolor; return p;if (remain_attribute.size() = 0)(/所H有甄的？属？性？均已？经-考?虑？完？了 ？，还 1 没？ 有甄分?尽？ string

41、label = MostCommonLabel(remain_state); p-attribute = label; return p;double max_gain = 0, temp_gain;vector :iterator max_it = remain_attribute.begin();vector :iterator itl;for (itl = remain_attribute.begin(); itl max_gain) ( max_gain = temp_gain; max_it = itl;下？面?根据Ymax_it指？向b的？属?性?来打划？分？当獭?前。样H例，？更

42、口新?样H例 集一 和i属?性?集一vector new_attribute;vector vector new_state;for (vector : iterator it2 = remain_attribute.begin(); it2 attribute = *max_it;vector values = map_attribute_values*max_it; int attribue_num = FindAttriNumByName(*max_it); new_state.push_back(attribute_row);for (vector : iterator it3 = v

43、alues.begin(); it3 values.end(); it3+)( for (unsigned int i = 1; i arrived_value = *it3;if (new_state.size() = 0)/表括?示？当獭？前没?有甄这a个?分?支的？样H例，？ 当獭?前的?new_node为a叶?子哩?节U点？new_node-attribute = MostCommonLabel(remain_state);elseBulidDecisionTreeDFS(new_node, new_state, new_attribute);/递麋归6函一数筋返 ?回？时骸？即回？溯Y时骸?需仓要瘾1将?新?结d点?加6入?父?节 U点？孩C子哩?容胃器：2清？除ynew_state容胃器：p-childs.push_back(new_node);new_state.erase(new_state.begin()+1,new_state.end(); /注痢?意瘾先仓清？空?new_state中D的？前。一?个?取?值U的?样H例，？准?备?遍括?历 ?下?一?个?取?值U样H例return p;void Input()(string s;while (cins,pare(end)!= 0)(/-1 为