2023年随机森林实验报告.docx

《2023年随机森林实验报告.docx》由会员分享，可在线阅读，更多相关《2023年随机森林实验报告.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、随机森林实验报告实验目的实现随机森林模型并测试。实验问题Kaggle 第二次作业 Non-linear class i fica t ion算法分析与设计一.算法设计背景：1 .随机森林的原子分类器一般使用决策树，决策树又分为拟合树和分类树。这两者的 区别在于代价估值函数的不同。2 .根据经验，用拟合树做分类的效果比分类树略好。3 .对于一个N分类问题,它总是可以被分解为N个2分类问题，这样分解的好处是其决 策树更加方便构造，更加简朴，且更加有助于用拟合树来构建分类树。对于每一个2分类问 题，构造的树又叫CART树，它是一颗二叉树。4 .将N个2分类树的结果进行汇总即可以得到多分类的结果。5

2、.CART树构造:trace.pusn(u);树的初始化(插入头节点)完成后，正式开始决策树的构建while (!trace.empty()int current_node = trace.topO；trace.popQ;int container2 = 0 ;(*Tree).getPartition(current_node, container);判断当前节点是否成功分割if (container0 != -1) trace.push(containerl);trace.push(container0);训练完成，计算输出下面再重点说一下函数:bool decisionTree:getPa

3、rtition(int index, int container2)这个函数是单棵决策树构造的核心，调用这个函数，假如当前节点的G ini值己经为0,那么这个函数会计算当前节点的拟合值：if (Nodesindex.gini = = 0 | Nodesindex.layer = MaxLayerNum/* | /4Nodesindex.dataSet.sizeO 10*/) Nodesmdex.isLeaf = 1;计籁叶子节点的拟合值double sum = 0;for (int i = 0; i Nodesindex.datalndex.size(); +i)sum = trainOutN

4、ode$(index.dataIndexIi;/Node$index.resiiNode$mdex.value = sum / Node$index.dataIndex.$izeO；containerfO = containerl = -1;return false;d-结束条件是g ini = 0|层数等于10假如当前节点不满足结束分割条件，那么函数将对属性进行抽样，抽样的方法是打乱后取前se 1 ectedCol u mn s列。然后调用getN o deA 11 r (s,index)获取当前节点的备选分割值，这里的s是抽取的属性的列号的集合。获得打乱后的索引，并选取前面的25个作为选取

5、的列的索引，传递给getAttr ,获得所需要的分割值 vector sequence(numparametres -2);srand(unsigned)time(NULL);for (i = 0; i sequence sizeQ; +i)sequencei.index = i;sequence(i).value = rand();)std:sort(sequence.begin()r sequence.endO.cmp);vectors(SelectedColumns);for (int i = 0; i SelectedColumns; +i)s(i = sequencei.index;

6、在得到备选的属性分割值后，将进入循环，寻找最优分割点for (i = 0; i SelectedColumns; +i) vector:iterator cursorfor (cursor = Nodesindex.attributesij.beginO； cursor != Nodes(index.attributesi.endO； cursor) temp_gini = computeGini(index, s(ij, cursor);if (min_gini temp_gini) min_gini = temp_gini;par_label = si;par_value = *curso

7、r;6 .最终结果计算在m a in函数中，我们将四个线程所得的transf o rmOu t T相加,最后遍历取每一行最大值的 下标,即可得到最终结果。六.算法优化.应用了数组+校建树取代了普通的函数递归建树，加快了建树速度。1 .在传递每个节点的节点数据集时，使用了传递数据集的索引而非数据自身，这样做的好处 是，本来假如传递条数据需要复制617个double类型的数量，而现在只需要传递个 Ini型的索引，这种快了 61 7倍的数据集传递方式使程序运营效率提高了 10倍以上。2 .在每个属性中选择备选分割值的时候，采用了一种下采样的策略。即：假如该节点的数据 集大小小于某一数值，则将这个数据

8、集的这个属性的所有值都纳入候选分割值列表。但是假 如大于了这个阈值，则将属性所相应的列进行排序后再进行等间距采样得到样本数等于阈值 的子集作为候选分割集。代码详见getPartition().这样做的好处是需要计算的分割gini 值大大减少了(本人取的采样阈值时100,相比原数据集，样本空间缩小了尽3 0倍)，这里也再 一次加速了程序运营。但是这个优化随机而来的个问题是：有也许每次分割都不是最佳分 割。3 .使用了 C+I 1的vihread库进行了并行实现，开出4个线程，程序相比单线程加速了 4倍。七.并行实现C+1 1thread库创建线程，为每个线程赋予独立的数据容器，并将随机森林提成等

9、量的4部分（由于我使用的是4个线程）。即,每个线程中执行的函数承担1/4规模的随机森 林的构造，实现代码如下:threat threadl(mainInThread. transformOutPerTimeTl, trainlnPerTimeTl, tran$formTe$tOutTl,&Treel); thread thread2(mainInThread, transformOutPerTimeT2, trainInPerTimeT2, transformTestOutT2, &Tree2); threat： thread3(mainInThread, transformOutPerTim

10、eT3, trainInPerTimeT3, transformTestOutT3, &Tree3); thread thread4(mainInThread, transformOutPerTimeT4, trainInPerTimeT4, transformTestOutT4, &Tree4);threadl.join();thread2.join();thread3.join();thread4.join();int mainInThread(int transformOutPerTime_type$Num + 1. double trainInPerTime_lnumparametre

11、s - 2, double transformTestOut /廉财地入口for (int times = 0; times ForestSize / 4; times+ +)最后将4个线程得到的结果累加再做转换即可得到最终结果。r (int i = 0; i testsetNum; +i) (for (intj = 0;j test I n . test I D。这个函数使用的f stream逐行读入的方法，这里不做详述。2 .训练集输出转化为相应的2 6维0 1数组tra n sformOuttype s Num在da t aD e fine.h中，我们定义了分类类别数t y pesNum

12、:在 main. cpp 中,我们定义了全局变量 tr a n s f ormOut t ypesNumint transformOuttrainsetNumtypesNum + 1 = 0 ; / 类别数这里的t ransfo r mOu t是用于储存将trai nOut每行的值映射为行相应的2 6维01序列 后所产生的结果。这里面的相应关系是：例如tra i nOu t 10中的值是13那么transfo r mOu t 1 0 =l,t rans formOutl 0除1 3外其他列=0;假如值是14,那么14列为1 ,其他列为0,行 号代表的是它们相应的是第几条记录;tra inOut

13、llO和tra n sforni 0 u tl 0 J都表达的是第 10行的分类值为某个值，只是表达方式不同。前者用数字表达，后者将相应下标的值置1 表达。转换接口由1。 i n.c p p中的函数void indexTransform(inttransformresHt.pesK+ 1, double ogresl); /户弓启始W出丫，化力Y,”,定义,它的输入参数依次为转换输出的承接容器t r ans f ormre s，盛放原始输出的容器org它所做的事情是将tra n s f o r mresfi o r g es i 的值置1.并行构建随机森林在ma in. cpp中，我们构建了d

14、ouble trainInPerTimeperTimeNumnumparametres - 2;double trainInPerTimeTlperTimeNumnumparametres - 2;double trainInPerTimeT2perTimeNumnumparametres - 2;double trainInPerTimeT3perTimeNumnumparametres - 2;double trainInPerTimeT4perTimeNumnumparametres - 2;int transformOutPerTimeperTimeNum typesNum + 1 =

15、 0 ;int transformOutPerTimeTlperTimeNumtypesNum + 1 = 0 ; int transformOutPerTimeT2(perTimeNumtypesNum + 1 = 0 ; int transformOutPerTimeT3perTimeNumtypesNum + 1 = 0 ; int transformOutPerTimeT4perTimeNum(typesNum + 1 = 0 ;double transformTestOutTltestsetNumtypesNum + 1 = 0 ;double transformTestOutT2(

16、testsetNumtypesNum + 1 = 0 ;double transformTestOutT3testsetNumtypesNum + 1 = 0 ;double transformTestOutT4testsetNumtypesNum + 1 = 0 ;tra i n I n pefTime代表的是随机森林算法中通过采样环节后选取的训练输入.Tra n s f ormO u tPerTime 代表的是与 t r ai n InperT i m e 相应的转换输;|t ran s form test Ou t是承接本支线程的所有CART树的决策值之和的结构，这与算法思绪 是相应的，

17、我们将所有CART树的预测结果在意个转换输出容器上累加，然后对于每行取 该行最大列的卜标，即可得到由随机森林得到的分类结果。我们可以看此这几个变量都是只有最后的TX有区别，事实上，反复的创建相似的变量只 是为了方便多线程操作不会冲突。多线程入口:decisionTree & tasd = Treel;thread threadl(mainInThread, transformOutPerTimeTl, trainlnPerTimeTl, transformTestOutTl,&Treel);thread thread2(mainInThread, transformOutPerTimeT2,

18、trainIrPerTimeT2, transformTestOutT2, &Tree2);thread thread3(mainInThread, transformOutPerTimeT3, trainInPerTimeT3, transformTestOutT3, &Tree3);thread thread4(mainInThread, transformOutPerTimeT4, trainInPerTimeT4, transformTestOutT4, &Tree4);这里使用的是C+11的thread库，简朴好用。每一个线程的随机森林框架定义在mai n .c p p的这个函数采用

19、循环的方式，每次循环，对训练集及相应转换输出进行打乱后采样，然后输入TRAIN(trainInPerTime_, transformOutPerTime_, transformTestOuC Tree);中进行一轮决策树的训练,这一轮训练将会生成2 6棵CART树，相应26个分类值。这里输 入的参数Tree就是我们所用的决策树容器，这里注意，我们一个线程中只需要公用一个决 策树结构即足够了.在训练完毕后，我们用ItransformTestOutij=累加训练结果。4一轮训练26棵树由于2 6棵CART树才干完整的等价于一棵26分类树，因此我们将构建这26棵CART树的过程当作是一个整体。这个过

20、程由函数TRAIN(trainInPerTime_, transformOutPerTime_, transformTestOuC Tree);实现。它的输入依次是本轮的训练输入（通过了卜.采样，随机森林规定的），相应的转换训练输出，以及一个决策树容器Tr ee。决策树的定义我们将在下文中描述。这个函数有一个校stacktrace; 用于追踪树的遍历过程，这里我们假定用的是先根遍历;并且有一个从1： 2 6的循环for (int typesN = 1; typesN = typesNum; typesN + +)每次循环会建立一棵关于相应的分类值得CA RT树，CART树的构造是由栈t r a

21、ce维护 的，t r ace维护的是一个先序的遍历顺序。当循环完毕后，将会计算本轮的转换输出结果的变更:for (int i = 0; i testsetNum; +i)/testresPerTimeitypesN = TputeRes(testIni);transformTestOut_itypesN += (*T ree).computeRes(testIni);5.每科CART树的构造CART树的数据结构如下:struct decisionTree double trainIn(perTimeNumnumparametres -2;int trainOutperTimeNum;node

22、NodesnodesNum;在建树时需要使用的可用节点索引记录int usableNode;tr a inIn tr a inO u t相应于输入该树的输入输出集,N ode s表达的是节点序列，在这里我们 的树的构造使用的是数组，且树的节点间的索引是通过索引值维护的，这颗树非常紧密(假如 只看NODES是看不出节点间的层级关系的)。它有如下成员函数：decisionTree。；void setDecisionTree(double trainln_numparametres - 2, int trainOut);bool getPartition(int index, int contain

23、er。)；double computeGini(int index, int label, double value);/double computeNodeGini(int index);计算某一节点的Ginidouble computeRes(doublenumparametres - 2);训练完成后,用于痴809函数,输入是窝试输入向void getNodesSequence(nodel);/初始你对，void initialize(node ele);对于每个节点的一些操作，void getNodeAttr(vectorselectedCols,intindex);void comp

24、utePerNodeGini(int index);void computeNodeValue(int index);selDecis i onTree 用于给 trai n I n 和 tra i nOu t 赋值g e t NodeSe q uence ( nodel)本来是用来输出节点参数的，这里不做详述initi a 1 i z e用初始化决策树。g etN o deAttr用于得到某一节点的备选属性分割值compu t ePerN o dcG ini用于计算某一节点的G I NI值，这在停止节点分割时有用C o m p u t e N ode Value是用于计算某一叶子节点的拟合值

25、的。我们再说一下Nodes节点，它的结构如下vectordatalndex; 用于装该节点的却醐春题用于记录该节点的分割点vectorattributes(SelectedColumns;int leftChild, rightchild;子节点的Indexint isLeaf;/ 0表示内部节点，1表示外部节点int splitLabel;记录当前的分割属性的位置double labelvalue;节点分割俏double value;该节点的平均值，用于拟合时的运算int layer;用于记录所在层数double gini;当前节点的GINK!A ttrbutes sei e ct e dC

26、olumns是用于存放候选的分割值的容器其余变最的功能见图片中的文字注释这里我们用d a talnde x存放相应记录所在索引的方法取代了直接存放记录，这里是一个巨大的改善，将程序的执行速度提高了至少10倍。在构造一棵决策树时，当train函数相应的t r ace栈的栈顶非空时，我们会不断的取出栈顶 元素，对其进行bool getPartition(int index, int container1);用于做树的节点分割操作Jndex指的是节点所在的索引值，container用于存放这个节点的左右叶子索引，由于 树的构建是由外部栈维护的，所以这个container是必不可少的，在当前节点分割完毕后， 我们会将这个节点的索引值出栈，假如contain e r的值不是-1 ,我们会将container0,con tain c r 1 入栈。建树的相应模块在main. c pp下的train函数中的