大家好，又见面了，我是你们的朋友全栈君。
决策树最大的特点就是直观，易解释。大家生活中在某一个时刻也在无意或有意的使用它，比如我们之前举的借钱的栗子。决策树算法根据特征选择的方式不同，可以分为ID3算法，C4.5算法，CART算法。在CART算法中，使用Gini指数做特征选择，选择Gini指数最小的特征以及其对应的切分点作为最优特征与最优的切分点，循环反复直到满足停止条件。由于决策树几乎不对训练数据做任何的假设，在不添加任务约束，树结构将会根据训练数据的特性自由生长，达到百分百的正确率。为了提高决策树的泛化能力，决策树使用了剪枝的方法。但是剪枝在减少模型方差的同时，也减小了模型的偏差（准确度）。那么有没有其他方法，在降低模型方差的同时，又不降低显著降低模型偏差？非常巧，上一篇我们提到的bagging集成方法正好有这个特性。使用bagging集成多颗决策树（CART树）就叫做随机森林。
我们在上篇在探讨bagging集成学习方法时，提到bagging集成方法有效的前提条件是，基模型之间必须保持低相关性，低相关性才能保证基模型之间的差异性，有差异性的基模型组合在一起才能成为一个更强大模型。为了让CART树有更大差异性，随机森林除了对样本进行随机过采样，增加训练集的随机性之外，还在树的生成时引入了额外的随机，即特征随机。在树的生成时，选择随机采样的特征中的最好的特征作为分裂节点，这样使得每棵树有更大的差异性。
下面我们总结下随机森林的算法过程：输入：数据量为 m m m的训练集 D D D， T T T颗CART树输出：最终的随机森林 f ( x ) f(x) f(x)1）对训练集 D D D进行 m m m次随机过采样，得到样本量为 m m m的采样集 D s a m p l e D_{sample} Dsample；2）在所有属性特征中随机选择 k k k个属性特征，选择最佳分割属性特征作为节点构建CART树 T ( x ) T(x) T(x)；3）重复以上两步 T T T次，即建立了 T T T颗决策树；4）这 T T T颗决策树组成随机森林。如果是分类算法预测，则通过投票表决数据最终属于哪一个类别；如果是回归预测，则 通过平均作为最终模型的输出。
对于Bagging，采用有放回的采样，那么一些样本可能被多次重复采样，有一些可能不会被采样。对于一个大小为 m m m的训练集进行随机采样，样本每一次被采样的概率为 1 m \frac{1}{m} m1，没有被采样到的概率为 1 − 1 m 1-\frac{1}{m} 1−m1， m m m次都没有被采样到的样本的概率为 ( 1 − 1 m ) m {(1-\frac{1}{m})}^m (1−m1)m，当 m → ∞ m\rightarrow \infty m→∞时，lim m → + ∞ = 1 e ≈ 0.368 {\lim_{m \to +\infty}}=\frac{1}{e}\approx0.368 limm→+∞=e1≈0.368也就是说，对于大小为 m m m的训练集，平均只有63.2%的样本被每个分类器采样，剩余的36.8%没有被采样到，没有被采样的样本被称为Out of Bag。注意，每个分类器的36.8%的样本是不一样的。由于分类器在训练的时候没有使用到Out of Bag的样本数据，因此这部分可以用来评估分类器，进而不需要另外划分验证集或者做交叉验证了。在sklearn随机森林库类中，你可以通过oob_score=True来自动评估，评估结果通过oob_score_查看，具体我们下篇再探讨。