1、同学A的决策树：头发长、声音粗就是男生；头发长、声音细就是女生；头发短、声音粗是男生；头发短、声音细是女生。,决策树,这时又蹦出个同学B，想先根据声音判断，然后再根据头发来判断，如是大手一挥也画了个决策树，如图3所示：,图3 B同学的决策树,同学B的决策树：首先判断声音，声音细，就是女生；声音粗、头发长是男生；声音粗、头发长是女生。,决策树,那么问题来了：同学A和同学B谁的决策树好些？计算机做决策树的时候，面对多个特征，该如何选哪个特征为最佳的划分特征？,划分数据集的大原则是：将无序的数据变得更加有序。,我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。于是这么想，如果能测量数据的
2、复杂度，对比按不同特征分类后的数据复杂度，若按某一特征分类后复杂度减少的更多，那么这个特征即为最佳分类特征。,决策树,Claude Shannon 定义了熵和信息增益。用熵来表示信息的复杂度，熵越大，则信息越复杂。公式如下：,信息增益，表示两个信息熵的差值。信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好。,决策树,首先计算未分类前的熵，总共有8位同学，男生3位，女生5位。接着分别计算同学A和同学B分类后信息熵。同学A首先按头发分类，分类后的结果为：长头发中有1男3女。短头发中有2男2女。,决策树,决策树,同理，按同学B的方法，首先按声音特征来分。分类后的结果为
3、：声音粗中有3男3女。声音细中有0男2女。,按同学B的方法，先按声音特征分类，信息增益更大，区分样本的能力更强，更具有代表性。,集成学习,集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。随机森林是集成学习的一个子类，它依靠于决策树的投票选择来决定最后的分类结果。,图4 集成学习结构图,集成学习,（a）集成提升性能,（b）集成不起作用,集成学习,（c）集成提升性能,从以上看出：要获得好的集成效果，个体学习器应好而不同，即个体学习器要有一定的准确性，即学习器不能太坏，并且要有多样性
4、，即学习器间具有差异。,什么是随机森林？,随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支集成学习方法。随机森林的名称中有两个关键词，一个是“随机”，一个就是“森林”。“森林”很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，其实这也是随机森林的主要思想-集成思想的体现。“随机”的包括随机选取训练样本集和随机选取分裂属性集。（具体含义在随机森林的生成部分会解释）,什么是随机森林？,其实从直观角度来解释，每棵决策树都是一个分类器（假设现在针对的是分类问题），那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票
5、结果，将投票次数最多的类别指定为最终的输出。,随机森林的特点：优点：1.两个随机性的引入，使得随机森林不容易陷入过拟合；2.两个随机性的引入，使得随机森林具有很好的抗噪声能力；3.对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化且能够有效地运行在大数据集上；4.能够处理具有高维特征的输入样本，而且不需要降维；5.在生成过程中，能够获取到内部生成误差的一种无偏估计；6.对于缺省值问题也能够获得很好得结果。,随机森林的特点,缺点：1.在某些噪音较大的分类或回归问题上会过拟合；2.对于有不同级别的属性的数据，级别划分较多的属性会对随机森 林产生更大的影响，所以随机森林在
6、这种数据上产出的属性权值是不可信的。,随机森林的特点,随机森林中有许多的分类树。如果要将一个输入样本进行分类，需要将输入样本输入到每棵树中进行分类。打个比喻：森林中召开会议，讨论某个动物到底是老鼠还是松鼠，每棵树都要独立地发表自己对这个问题的看法，也就是每棵树都要投票。该动物到底是老鼠还是松鼠，要依据投票情况来确定，获得票数最多的类别就是森林的分类结果。森林中的每棵树都是独立的，99.9%不相关的树做出的预测结果涵盖所有的情况，这些预测结果将会彼此抵消。少数优秀的树的预测结果将会超脱于芸芸“噪音”，做出一个好的预测。将若干个弱分类器的分类结果进行投票选择，从而组成一个强分类器，这就是随机森林b
7、agging的思想。,随机森林的生成,有了树我们就可以分类了，但是森林中的每棵树是怎么生成的呢？每棵树的按照如下规则生成：a.给定一个训练样本集，数量为N，使用有放回采样到N个样本，构成一个新的训练集。注意这里是有放回的采样，所以会采样到重复的样本。b.从总量为M的特征向量中，随机选择m个特征（mM），其中m可以等于，然后计算m个特征的信息增益，选择最优特征（属性）。注意，这里的随机选择特征是无放回的选择。（在整个森林的生长过程中，m的值一般维持不变）,随机森林的生成,c.有了上面随机产生的样本集，就可以使用一般决策树的构建方法，得到一棵分类（或者预测）的决策树。需要注意的是，在计算节点最优分
8、类特征的时候，要使用b中的随机选择特征方法。d.通过以上三步，可以得到一棵决策树，重复这样的过程H次，就得到了H棵决策树。然后来了一个测试样本，就可以用每一棵决策树都对它分类一遍，得到了H个分类结果。这时，使用简单的投票机制，或者该测试样本的最终分类结果来判别该样本的所属类别。,随机森林的生成,一开始提到的随机森林中的“随机”就是指的a和b中的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。,随机森林的生成,为什么要随机抽样训练集？如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树
9、分类结果也是完全一样的，这样的话完全没有集成的必要；,随机森林的生成,为什么要有放回地抽样？如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是有偏的，都是片面的，也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是求同，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的。,随机森林的生成,随机森林分类效果（错误率）与两个因素有关：1.森林中任意两棵树的相关性：相关性越大，错误率越大；2.森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。减小特征选择个数m，树的相关性和分
10、类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。,袋外错误率（OOB error）,上面我们提到，构建随机森林的关键问题就是如何选择最优的m，要解决这个问题主要依据计算袋外错误率。随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第
11、k棵树的生成，它们称为第k棵树的袋外样本数据。,袋外错误率（OOB error）,而这样的采样特点就允许进行袋外估计，它的计算方式如下：a.对每个样本，计算它作为袋外样本的树对它的分类情况（约1/3的树）；b.然后以简单多数投票作为该样本的分类结果；c.最后用误分个数占样本总数的比率作为随机森林的袋外错误率。,袋外错误率（OOB error）,通俗的来讲就是：对每颗树，利用未被该树选中的训练样本点，统计该树的误分率；将所有树的误分率取平均得到随机森林的袋外错误率。,袋外错误率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。,随机森林的简单实例分析,描述：根据已有的训
12、练集已经生成了对应的随机森林，随机森林如何利用某一个人的年龄（Age）、性别（Gender）、教育情况（Highest Educational Qualification）、工作领域（Industry）以及住宅地（Residence）共5个字段来预测他的收入层次。,收入层次：Band 1:Below$40,000Band 2:$40,000 150,000Band 3:More than$150,000,随机森林的简单实例分析,随机森林中每一棵树都可以看做是一棵CART（分类回归树），这里假设森林中有5棵CART树，总特征个数N=5，取m=1（m为建立决策树时，随机选取的特征个数，这里假设每个
13、CART树对应一个不同的特征）。（表格中的百分数指的是在不同条件下的数据样本占对应类别的比例）,随机森林的简单实例分析,假如要预测的某个人的信息如下：1.Age:35 years;2.Gender:Male;3.Highest Educational Qualification:Diploma holder;4.Industry:Manufacturing;5.Residence:Metro.,随机森林的简单实例分析,根据这五棵CART树的分类结果，可以针对此人的信息建立收入层次的分布情况：,最后，我们得出结论，这个人的收入层次70%是一等，大约24%为二等，6%为三等，所以最终认定该人属于一等收入层次（小于$40,000）。,
