文档介绍：随机森林实验报告
实验目的
实现随机森林模型并测试。
实验问题
Kaggle 第二次作业 Non-linear classification
算法分析与设计
算法设计背景：
随机森林的原子分类器一般使用决策树，决策树又分为拟合树和分类树。这两者的区别在于代价估值函数的不同。
根据经验，用拟合树做分类的效果比分类树略好。
对于一个N分类问题,它总是可以被分解为N个2分类问题，这样分解的好处是其决策树更加方便构造，更加简单，且更加有利于用拟合树来构建分类树。对于毎一个2分类问题，构造的树又叫CART树，它是一颗二叉树。
将N个2分类树的结果进行汇总即可以得到多分类的结果。
CART树构造：
输入：训练数拯集D,停止训练条件
输出:CART决策树
根据训练数据集，从根节点开始，递归地对每个节点进行以下操作，递归构造二叉决笫树
(1) 设节点的训练数据集为D,计克现有特征对该数据集的基尼系数，此时，对每一个特征
A,对于每一个可能的划分值根据大于a及小于等于a将训练数据隼分成DI, D2两
部分。计??gini系数公式如F：
Gini(D)
Zk^iPk
在所有可能特征A以及其所有可能划分点a中，选择gini系数最小的特征及切分值，将D1 和D2分配到左右两个子节点去。
对左右节点分别递归的调用(1), (2),直到满足一定条件为止。
随机森林构造：
(1) 随机取样，降低树与树之间的关联性
RF在每次构造一棵决策树时，先随机的有放回的从训练集中抽取(60%)或n (sizeof
training set)个样本D,在毎个节点分裂前，先随机从总共M个特征中选取m个(m
« M, 一般取根号M)作为分裂用的候选特征，这有效降低了树与树之间的关联性。
算法思路：
将一个N分类问题转化为N个二分类问题。转化方法是：构造N棵二叉拟合树，这里假设N为26,然后我们给N棵二叉树依次标号为1, 2, 3...26。1号树的结果对应于该条记录是不是屈于笫一类，是则输出1, 二类，是则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个索引做是否判断的二分类树视为一个整体，在多线程的环境下，构造多个这样的整体，然后进行求和运算，最后取出每个结果序列屮值最大的元素的下标作为分类值，那么久得到了我们想要的结果，随机森林完成。
算法流程：
读入训练集trainset,测试集testset
将训练集分割为输入(rainin,输出trainOut
3•这里假设类别数N为26,将trainOut[记录条数]映射为tran$formTrainOut[训练记录数][26]
初始化transfomiTestOut[测试记录数][26]全部为0
For i = 1 : ForestSize:
〃对训练集采样，这