21/33
2019/3/13
随机森林的生成
有了树我们就可以分类了，但是森林中的每棵树是怎么生成的呢？
每棵树的按照如下规则生成： a. 给定一个训练样本集，数量为N，使用有放回采样到N个样本 ，构成一个新的训练集。注意这里是有放回的采样，所以会采样到重 复的样本。 b.从总量为M的特征向量中，随机选择m个特征（m<M），其 中m可以等于 ，然后计算m个特征的信息增益，选择最优特 征（属性）。注意，这里的随机选择特征是无放回的选择。（在整个 森林的生长过程中， m的值一般维持不变）
随机森林
1/33
2019/3/13
目录
1 2
决策树 集成学习 随机森林 袋外错误率（OOB） 随机森林的简单实例分析
2019/3/13
3
4 5
2/33
决策树
决策树: 1.每个内部节点上选用一个属性进行分割 2.每个分叉对应一个属性值 3.每个叶子结点代表一个分类 如图1所示：
A1 a11 A2 a21 c1 a22 c2 a12 c1
头发 长 短 短 声音 粗 粗 粗 性别 男 男 男
长
短 短 长 长
细
细 粗 粗 粗
女
女 女 女 女
6/33
2019/3/13
决策树
机智的同学A想了想，先根据头发判断，若判断不出，再根据声 音判断，于是画了一幅图，如图2所示：
图2 A同学的决策树 于是，一个简单、直观的决策树就这么出来了。 同学A的决策树：头发长、声音粗就是男生；头发长、声音细就是 女生；头发短、声音粗是男生；头发短、声音细是女生。 7/33 2019/3/13
随机森林的简单实例分析
描述：
根据已有的训练集已经生成了对应的随机森林，随机森林如何利用某一 个人的年龄（Age）、性别（Gender）、教育情况（Highest Educational Qualification）、工作领域（Industry）以及住宅地（ Residence）共5个字段来预测他的收入层次。
13/33
2019/3/13
集成学习
集成学习通过建立几个模型组合的来解决单一预测问题。它的 工作原理是生成多个分类器，各自独立地学习和作出预测。这些预 测最后结合成单预测，因此优于任何一个单分类的做出预测。 随机森林是集成学习的一个子类，它依靠于决策树的投票选择 来决定最后的分类结果。
个体学习器1 个体学习器2 结合 模块 输出
25/33
2019/3/13
随机森林的生成
随机森林分类效果（错误率）与两个因素有关：
1.森林中任意两棵树的相关性：相关性越大，错误率越大；
2.森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错 误率越低。
减小特征选择个数m，树的相关性和分类能力也会相应的降低； 增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或 者是范围），这也是随机森林唯一的一个参数。
17/33
2019/3/13
什么是随机森林？
其实从直观角度来解释，每棵决策树都是一个分类器（假 设现在针对的是分类问题），那么对于一个输入样本，N棵树 会有N个分类结果。而随机森林集成了所有的分类投票结果， 将投票次数最多的类别指定为最终的输出。
18/33
2019/3/13
随机森林的特点
随机森林的特点：
27/33
2019/3/13
袋外错误率（OOB error）
而这样的采样特点就允许进行袋外估计，它的计算方式如下： a. 对每个样本，计算它作为袋外样本的树对它的分类情况（约1/3 的树）； b. 然后以简单多数投票作为该样本的分类结果；
c. 最后用误分个数占样本总数的比率作为随机森林的袋外错误率。
集成学习
测试例1 H1 H2 H3 √ Х Х 测试例2 Х √ Х 测试例3 Х Х √
集成
Х
Х
Х
（c）集成提升性能
从以上看出：要获得好的集成效果，个体学习器应‘好而 不同’，即个体学习器要有一定的‘准确性’，即学习器不能 太坏，并且要有‘多样性’，即学习器间具有差异。
16/33
2019/3/13
个体学习器T
图4 集成学习结构图
…
14/33
2019/3/13
集成学习
测试例1 H1 H2 √ √ 测试例2 √ Х 测试例3 Х √
H3
集成
Х
√
√
√
√
√
（a）集成提升性能
测试例1 H1 H2 √ √
测试例2 √ √
测试例3 Х Х
H3
集成
√
√
√
√
Х
Х
（b）集成不起作用
15/33
2019/3/13
26/33
2019/3/13
袋外错误率（OOB error）
上面我们提到，构建随机森林的关键问题就是如何选择最优的m，要 解决这个问题主要依据计算袋外错误率。 随机森林有一个重要的优点就是，没有必要对它进行交叉验证或 者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进 行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。 在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于 第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称 为第k棵树的袋外样本数据。
决策树
这时又蹦出个同学B，想先根据声音判断，然后再根据头发来判 断，如是大手一挥也画了个决策树，如图3所示：
图3 B同学的决策树 同学B的决策树：声音粗、头发长是女生。 8/33 2019/3/13
决策树
那么问题来了：同学A和同学B谁的决策树好些？计算机做 决策树的时候，面对多个特征，该如何选哪个特征为最佳 的划分特征？ 划分数据集的大原则是：将无序的数据变得更加有序。 我们可以使用多种方法划分数据集，但是每种方法都有各 自的优缺点。于是这么想，如果能测量数据的复杂度，对 比按不同特征分类后的数据复杂度，若按某一特征分类后 复杂度减少的更多，那么这个特征即为最佳分类特征。
31/33
2019/3/13
随机森林的简单实例分析
假如要预测的某个人的信息如下： 1. Age : 35 years ; 2. Gender : Male ; 3. Highest Educational Qualification : Diploma holder; 4. Industry : Manufacturing; 5. Residence : Metro.
接着分别计算同学A和同学B分类后信息熵。 同学A首先按头发分类，分类后的结果为：长头发中有1男3女。 短头发中有2男2女。
11/33
2019/3/13
决策树
12/33
2019/3/13
决策树
同理，按同学B的方法，首先按声音特征来分。 分类后的结果为：声音粗中有3男3女。声音细中有0男2女。
按同学B的方法，先按声音特征分类，信息增益更大，区分样本的能 力更强，更具有代表性。
a13
A3 a31 c2 a32 c1
图1 决策树结构图 3/33 2019/3/13
决策树
决策树生成算法分成两个步骤：
（1）树的生成 a.开始，数据都在根节点 b.递归的进行数据分片 （2）树的剪枝 a.防止过拟合
决策树使用: 对未知数据进行分割
按照决策树上采用的分割属性逐层往下，直 到一个叶子节点
22/33
2019/3/13
随机森林的生成
c.有了上面随机产生的样本集，就可以使用一般决策树的构建方 法，得到一棵分类（或者预测）的决策树。需要注意的是，在计算节 点最优分类特征的时候，要使用b中的随机选择特征方法。 d.通过以上三步，可以得到一棵决策树，重复这样的过程H次， 就得到了H棵决策树。然后来了一个测试样本，就可以用每一棵决策 树都对它分类一遍，得到了H个分类结果。这时，使用简单的投票机 制，或者该测试样本的最终分类结果来判别该样本的所属类别。
23/33
2019/3/13
随机森林的生成
一开始提到的随机森林中的“随机”就是指的a和b中的两个随机 性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的 引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（ 比如：对缺省值不敏感）。 为什么要随机抽样训练集？
如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树 分类结果也是完全一样的，这样的话完全没有集成的必要；
4/33
2019/3/13
决策树
优点： 计算复杂度不高，输出结果易于理解，对中间 值的缺失值不敏感，可以处理不相关特征数据。 缺点： 可能会产生过度匹配的问题。 使用数据类型： 数值型和标称型。
5/33
2019/3/13
决策树
例1为决策树的构建流程：
一天，老师问了个问题，只根据头发和声音怎么判断一位同学的 性别 为了解决这个问题，同学们马上简单的统计了7位同学的相关特 征，数据如表1所示： 表1 数据信息表
28/33
2019/3/13
袋外错误率（OOB error）
通俗的来讲就是：
对每颗树，利用未被该树选中的训练样本点，统计该 树的误分率；将所有树的误分率取平均得到随机森林的袋 外错误率。 袋外错误率是随机森林泛化误差的一个无偏估计，它的结 果近似于需要大量计算的k折交叉验证。
29/33
2019/3/13
24/33
2019/3/13
随机森林的生成
为什么要有放回地抽样？ 如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没 有交集的，这样每棵树都是"有偏的"，都是"片面的"，也就是说每棵 树训练出来都是有很大的差异的； 而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表 决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最 终分类结果是没有帮助的。