随机森林实验报告
实验目的
实现随机森林模型并测试。
实验问题
Kaggle第二次作业Non-linear classification
算法分析与设计
一．算法设计背景:
1.随机森林的原子分类器一般使用决策树，决策树又分为拟合树和分类树。这两者的区别在于代价估值函数的不同。
2.根据经验，用拟合树做分类的效果比分类树略好。
3.对于一个N分类问题,它总是可以被分解为N个2分类问题，这样分解的好处是其决策树更加方便构造，更加简单，且更加有利于用拟合树来构建分类树。对于每一个2分类问题，构造的树又叫CART树，它是一颗二叉树。
4.将N个2分类树的结果进行汇总即可以得到多分类的结果。 5.CART树构造：
6.随机森林构造：
二．算法思路：
将一个N分类问题转化为N个二分类问题。转化方法是：构造N棵二叉拟合树，这里假设N为26，然后我们给N棵二叉树依次标号为1，2，3...26。1号树的结果对应于该条记录是不是属于第一类，是则输出1，否则输出0.2号树的结果对应于该条记录是不是属于第二类，是则1否则0，依此类推。这样，我们的26棵二叉树的结果就对应了26个下标。 例如对于某条记录，这26个二叉树的结果按序号排列为{0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，...1,0}，那么这条记录的分类应该为25。要将一个26维的0，1序列变回 一个索引，我们只需要找出这个序列中值最大的元素的索引，这个索引即是序列号。 我们将上面的26棵分别对26个索引做是否判断的二分类树视为一个整体，在多线程的环境下，构造多个这样的整体，然后进行求和运算，最后取出每个结果序列中值最大的元素的下标作为分类值，那么久得到了我们想要的结果，随机森林完成。
三．算法流程：
1.读入训练集trainset,测试集testset
2.将训练集分割为输入trainIn,输出trainOut 3.这里假设类别数N为26，将trainOut[记录条数] 映射为 transformTrainOut[训练记录数][26] 4.初始化transformTestOut[测试记录数][26]全部为0 5.For i = 1 : ForestSize:
//对训练集采样，这里要注意输入和输出一致
[sampleIn,transformSampleOut] = TakeSample(trainIn,transformTrainOut) For category = 1 : 26:
//CartTree 数组存放着26棵二分类树
CartTree[category] = TrainCartTree(sampleIn,transformSampleOut); end
//transformTestOut[测试记录数][26]为承接二分类树输出的容器 for i1 = 1 : testSetNum: For category = 1 : 26:
transformTestOut[i1][category] += predict(CartTree[category],testset[i1]) end End
End
6.遍历 transformTrainOut[]，将其每一行的最大值的下标作为该行记录的索引值。
四．决策树及随机森林的配置 1.决策树
在这里，我们每一次26分类是由26棵CART共同完成的，CART的cost function采用的是gini系数，CART的最大层数为7，分裂停止条件为当前节点GINI为0或者当前节点所在层数到达了7. 2.随机森林
a.随机森林每次循环的训练集采样为原训练集的0.5. b.对于森林中每一棵决策树每一次分割点的选取，对属性进行了打乱抽样，抽样数为25，即每次分割只在25个属性中寻找最合适的值。并且对于每个选取的属性，我们进行了行采样。即如果这个属性所拥有的属性值数大于30，我们选取其中30个作为分割候选，如果小于30，则全部纳入分割候选。
五．代码详解
1.训练集/测试集的读入
a.在dataDefine.h中定义了：
训练集记录列数numparametres （ID（1） + 参数数量（617） + 输出（1） = 619） 训练集记录条数transetNum 测试集记录条数testsetNum 分类类型数typesNum
而在main.cpp中，我们声明了全局变量
trainIn用于装载训练集输入，trainOut用于装载训练集的输出（这里trainOut是二维数组是出于模型如果泛化，那么输出值不一定只有一个的情况，在本次实验中并未派上什么真正用场，可以将trainOut看作一个普通一维数组）。trainID用于装载训练集中每一行的第一列ID号。testIn,testID则对应测试集的输入和ID号。这里注意，没有testOut的原因是测试集的结果理论上应该是不存在的。 然后通过自己编写的读入函数
读入测试集合训练集，这个函数将分别装载我们在前面提到的trainIn、trainOut、trainID、 testIn、testID。这个函数使用的fstream逐行读入的方法，这里不做详述。
2.训练集输出转化为对应的26维01数组transformOut[typesNum] 在dataDefine.h中，我们定义了分类类别数typesNum:
在main.cpp中，我们定义了全局变量transformOut[typesNum]
这里的transformOut是用于储存将trainOut每行的值映射为一行对应的26维01序列后所 产生的结果。
这里面的对应关系是：例如trainOut[10]中的值是13那么transformOut[10][13] = 1,transformOut[10][除13外其他列] = 0；如果值是14，那么14列为1，其他列为0，行号代表的是它们对应的是第几条记录；trainOut[10] 和transformOut[10] 都表示的是第10行的分类值为某个值，只是表达方式不同。前者用数字表示，后者将对应下标的值置1表示。 转换接口由main.cpp中的函数
定义，它的输入参数依次为转换输出的承接容器transformres,盛放原始输出的容器orges。 它所做的事情是将transformres[i][orges[i]]的值置1
3.并行构建随机森林
在main.cpp中，我们构建了
trainInperTime代表的是随机森林算法中经过采样步骤后选取的训练输入， TransformOutPerTime 代表的是与trainInperTime对应的转换输出
transformtestOut是承接本支线程的所有CART树的决策值之和的结构，这与算法思路是对应的，我们将所有CART树的预测结果在意个转换输出容器上累加，然后对于每行取该行最大列的下标，即可得到由随机森林得到的分类结果。
我们可以看出，这几个变量都是只有最后的TX有区别，实际上，重复的创建相似的变量只是为了方便多线程操作不会冲突。 多线程入口：
这里使用的是C++11的
这个函数采用循环的方式，每次循环，对训练集及对应转换输出进行打乱后采样，然后输入
中进行一轮决策树的训练，这一轮训练将会生成26棵CART树，对应26个分类值。这里输入的参数Tree就是我们所用的决策树容器，这里注意，我们一个线程中只需要公用一个决策树结构即足够了. 在训练完成后，我们用
累加训练结果。
4.一轮训练26棵树
因为26棵CART树才能完整的等价于一棵26分类树，因此我们将构建这26棵CART树的过程看成是一个整体。这个过程由函数
实现。它的输入依次是本轮的训练输入（经过了下采样，随机森林要求的），对应的转换训练输出，以及一个决策树容器 Tree。决策树的定义我们将在下文中描述。 这个函数有一个栈
并且有一个从1:26的循环
每次循环会建立一棵关于对应的分类值得CART树，CART树的构造是由栈trace维护的，trace维护的是一个先序的遍历顺序。
当循环完成后，将会计算本轮的转换输出结果的变更：
5.每科CART树的构造 CART树的数据结构如下：