今天简要学习了随机森林算法的背后原理，希望可以通过更深层次的理解来设计出更精确有效的特征处理与分析方法，争取早日吃透机器学习十大入门算法。
随机森林通过自助法（bootstrap）重采样技术，从原始训练样本集N中有放回地重复随机抽取k个样本生成新的训练样本集合，然后根据自助样本集生成k个分类树组成随机森林，新数据的分类结果按分类树投票多少形成的分数而定。其实质是对决策树算法的一种改进，将多个决策树合并在一起，每棵树的建立依赖于一个独立抽取的样品，森林中的每棵树具有相同的分布，分类误差取决于每一棵树的分类能力和它们之间的相关性。特征选择采用随机的方法去分裂每一个节点，然后比较不同情况下产生的误差。
能够检测到的内在估计误差、分类能力和相关性决定选择特征的数目。单棵树的分类能力可能很小，但在随机产生大量的决策树后，一个测试样品可以通过每一棵树的分类结果经统计后选择最可能的分类。
如何构造决策树：
构造一颗决策树的基本想法是随着树深度的增加，节点的熵迅速的降低。降低的速度越快越好，这样我们才有望得到一颗高度最矮的决策树。于是我们每一次做切割，都希望整棵树的熵下降得越快越好。一开始我们知道的信息只有每一个数据对应哪一个分类，这是一开始总的信息熵。这时候我们要开始切割了。我们枚举每一个字段，计算它们做了切割之后的信息熵，将这个信息熵和未做分割前的信息熵做一个比较，也就说用切割前总信息熵减去切割后总信息熵，得到的值我们称之为信息增益。也就是一刀下去之后，我们的信息更加明朗的程度。将信息熵下降地最多，也就是信息增益最大的的那一个信息作为我们的分割字段。如果字段是连续值（比年龄是1到n之间的一个值），那么我们还要选择一个值来做切割。选择哪个值呢？最简单粗暴的方法，我们可以先对该字段的值做一个排序，然后做n-1次切割，找到信息熵最小的点即可。
信息熵的数学定义：
其中-log2（P）是我们上面所说的信息量。每一个信息量乘上它发生的概率，做一个累加，不难看出这是求期望的公式。信息熵是跟一条信息的可能性数量有关系的。每个可能事件的发生都有个概率。所以数学上，信息熵其实是信息量的期望。从化学上对熵的定义我们可以知道，熵越大说明混乱程度越高，熵越小说明混乱程度越低，那么构造一颗决策树，就是为了让决策树的叶子节点的熵降低直到为0,也就是说所有叶子节点的分类都是明确的，它的信息没有任何不确定性，这时我们就完成了决策树的构建。
剪枝：预防过拟合，主要思路是从叶节点向上回溯，尝试对某个节点进行剪枝，比较剪枝前后的决策树的损失函数值。最后我们通过动态规划（树形dp）就可以得到全局最优的剪枝方案。
构建过程：
1.从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
2.对于n_tree个训练集，我们分别训练n_tree个决策树模型
3.对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
4.每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
5.将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果
优点：1.由于引入了两个随机性，不容易出现过拟合，且具有很好的抗噪声能力
2.能处理特征很多的高维度数据，且不用做特征选择。
3.既能处理离散，也能处理连续数据，适应能力很强
4.训练速度快，在训练的过程中能检测到feature之间的相互影响，可以得到变量重要性排序（可以应用到本次实验中，优化特征提取的过程）
5.可生成一个Proximities=（pij）矩阵，用于度量样本之间的相似性： pij=aij/N, aij表示样本i和j出现在随机森林中同一个叶子结点的次数，N随机森林中树的颗数
