决策树与随机森林
2024-05-06 14:16
1. 决策树与随机森林
决策树（decision tree）是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，其主要优点是模型具有可读性，分类速度快。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。
本文将先对决策树特征选择的算法ID3, C4.5和CART进行计算，然后介绍决策树的剪枝策略，最后介绍随机森林。
在 信息论 中， 条件熵 描述了在已知第二个随机变量X的前提下，随机变量Y的信息熵还剩多少。基于X条件的Y的信息熵，用H(Y|X)表示。
如果H(Y|X=x)为变数Y在变数X取特定值x条件下的熵，那么H(Y|X)就是H(Y|X=x)在X取遍所有可能的x后取平均的结果。
首先需要知道的是熵的公式：
条件熵的推导公式如下：
决策树分类从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点。每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点，最后将实例分配到叶节点的类中。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行划分。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比，特征选择的常用算法有ID3，C4.5，CART。
信息增益表示得知特征A的信息而使得数据X的信息的不确定性的程度。 信息增益定义：特征A对训练数据集D的信息增益g(D, A)定义为集合D的经验熵H(D)与给定特征A的条件下D的经验条件熵H(D|A)之差，即：
根据信息增益选择特征的方法是：对于给定数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。使用信息增益选择特征的算法称为C3算法。
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类为题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。因此，使用信息增益比可以对这一问题进行校正，这是另一种特征选择算法，也即C4.5算法。
信息增益比定义 ：特征A对训练数据集D的信息增益比g R (D, A)定义为其信息增益g(D, A)与训练集D的经验熵之比：
基尼指数是CART分类树用来选择最优特征的算法，同时决定了该特征的最优二值切分点。
定义：假设有K个类，样本点属于第k类的概率为p k ，则概率分布的基尼指数定义：
对于给定的样本集合D，其基尼指数为：
一个特征的信息增益/基尼系数越大，表明特征对样本的熵减少的能力更强，这个特征使得数据由不确定性变成确定性的能力越强。
决策树生成算法产生的决策树对于训练数据的分类往往很准确，但对于未知数据的分类却没有这么准确，即容易出现过拟合情况。解决的办法便是考虑树的复杂度，对已生成的树进行剪枝简化。
决策树的剪枝往往通过极小化决策树整体的损失函数来实现。 设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有N t 个样本点，其中k类的样本点有N tk 个，k=1,2,3...K, H t (T)为叶节点t上的经验熵, α>=0为参数，则决策树学习的损失函数可以定义为：
损失函数中C(T)表示模型对训练数据的预测误差，也即拟合程度。|T|表示模型复杂度，即节点越多模型越复杂，使用参数α来控制两者之间的影响。α越大模型越简单，对数据拟合差；α越小模型越复杂，对数据拟合性好；α=0时则不考虑模型复杂度。
因此，剪枝就是在确定了α时，选择损失函数最小的树。
参考： 《统计学习方法》李航 机器学习. 邹博
2. 决策树与随机森林——原理篇（二）
第一篇我们主要关注了根结点及内部结点的选择 第二篇主要关注如何处理“过拟合”现象 参考
个性化 与 泛化 是一个相互矛盾概念，就像个体化诊疗与指南的矛盾一样。 决策树对训练数据可以得到很低的错误率，但是运用到测试数据上却得到非常高的错误率，这就是“过拟合现象”。 具体解释如下：对于决策树，我们希望每个叶子节点分的都是正确的答案，所以在不加限制的情况下，决策树倾向于把每个叶子节点单纯化，那如何最单纯呢？极端情况下，就是每个叶子节点只有一个样本，那这样，这个模型在建模集的准确率就非常高了。但是，这又带来了一个问题——过拟合，这会导致该模型在建模集效果显著，但是验证集表现不佳。 这可能有以下几个原因： 1、训练集里面有噪音数据，干扰了正常数据的分支 2、训练集不具有特征性 3、特征太多
使用信息增益来种树时，为了得到最优的决策树，算法会不惜带价倾向于将熵值降为最小（可能的话甚至为0），这颗树会显得非常的冗杂。
通过限制复杂度参数（complexity parameter），抓主要矛盾，来防止模型的过拟合。具体的计算过程可以参考，这里我直接引用
剪枝（pruning）则是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：
定义：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，如果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
相比于预剪枝，后剪枝往往应用更加广泛，
3. 10、决策树集成--随机森林
随机森林本质上是许多决策树的集合，其中每棵树都和其他树略有不同，每棵树的预测可能都相对较好，但可能对部分数据过拟合，我们对这些树的结果取平均值来降低过拟合，这样既保证了预测能力，又降低了过拟合。随机森林可用于回归RandomForestRegressor和分类RandomForestClassifier。
随机树构造方法： 一 每棵树随机选择数据，从n个数据中有放回地随机抽取一个样本，共抽取n次，这样会创建一个与原数据集大小相同的数据集，但有些数据会缺失（大约三分之一），有些会重复。 二 每棵树随机选择特征，选择部分特征而不是全部。
输出
在没有调节任何参数的情况下，随机森林的精度为97%，比分类算法（逻辑回归、线性SVM）或单棵决策树都要好。随机森林的默认参数通常就可以给出很好的结果。
输出
与单棵树相比，随机森林中有更多的特征的重要性不为0。它选择了“worst perimeter”（最大周长）作为信息量最大的特征，单棵决策树选的是“worst radius”（最大半径）。一般来说，随机森林给出的特征重要性要比单棵树给出的更为可靠，随机森林比单棵树更能从总体把握数据的特征。
这种方法非常强大，通常不需要反复调节参数就可以给出很好的结果，也不需要对数据进行缩放。随机森林拥有决策树的所有优点，同时弥补了决策树的一些缺陷。
随机森林是随机的，设置不同的随机状态（不设置random_state参数）可以彻底改变构建的模型。
随机森林中的树越多，模型的鲁棒性就越好。更多的树可以降低过拟合，但需要的内存也越多，即在内存允许的情况下尽量多。
对于维度非常高的稀疏数据（比如文本数据），随机森林的表现往往不是很好。
调节的参数主要有n_estimators（树的个数）、max_features和max_depth。n_estimators总是越大越好，较小的max_features可以降低过拟合，一般来说使用默认值就好。
4. 决策树算法之随机森林
在 CART 分类回归树 的基础之上，我们可以很容易的掌握随机森林算法，它们之间的区别在于，CART 决策树较容易过拟合，而随机森林可以在一定程度上解决该问题。
随机森林的主要思想是：使用随机性产生出一系列简单的决策树，并组合它们的预测结果为最终的结果，可谓三个臭皮匠赛过一个诸葛亮，下面我们就来具体了解一下。
产生随机森林的步骤大致为三步
在第 1 步，它是一个可放回抽样，即所产生的样本是允许重复的，这种抽样又被称为 Bootstrap，例如我们有以下 dummy 数据
在做完 Bootstrap 之后，可能的样本数据如下
可见，样本数据中，第 3 条和第 4 条样本是一样的，都对应的是原始数据中的第 4 条。
接下来，就是要使用上面的样本数据来产生决策树了，产生决策树的方法和 CART 基本一致，唯一的不同地方在于，节点的构建不是来自于全部的候选特征，而是先从中随机的选择 n 个特征，在这 n 个特征中找出一个作为最佳节点。
举个例子，假设 n = 2，且我们随机选择了「血液循环正常」和「血管堵塞」这两个特征来产生根节点，如下：
我们将在上述两个特征中选择一个合适的特征作为根节点，假设在计算完 Gini 不纯度之后，「血液循环正常」这个特征胜出，那么我们的根节点便是「血液循环正常」，如下图所示
接下来我们还需要构建根节点下面的节点，下一个节点将会在剩下的「胸口疼痛」、「血管堵塞」和「体重」三个特征中产生，但我们依然不会计算所有这 3 个特征的 Gini 不纯度，而是从中随机选择 2 个特征，取这 2 个特征中的 Gini 不纯度较低者作为节点。
例如我们随机选到了「胸口疼痛」和「体重」这两列，如下：
假设此时「体重」的 Gini 不纯度更低，那么第 2 个节点便是「体重」，如下图：
继续下去，我们便产生了一棵决策树。
随机森林是多棵决策树，在产生完一棵决策树后，接着会循环执行上述过程：Bootstrap 出训练样本，训练决策树，直到树的数量达到设置值——通常为几百棵树。
现在我们产生了几百棵树的随机森林，当我们要预测一条数据时，该怎么做呢？我们会聚合这些树的结果，选择预测结果最多的那个分类作为最终的预测结果。
例如我们现在有一条数据：
该条数据被所有树预测的结果如下：
上述结果聚合后为：
取最多的那项为最终的预测结果，即 Yes——该病人被诊断为患有心脏病。
以上，随机森林的两个过程： B ootstrap 和 Agg regate 又被称为 Bagging 。
本文我们一起学习了随机森林的算法，和 CART 决策树比起来，它主要被用来解决过拟合问题，其主要的思想为 Bagging，即随机性有助于增强模型的泛化（Variance） 能力。
参考：
相关文章：
5. 规则、决策树和森林
如果森林中的一棵树倒下了，但是没有人听见，那么它是否 发出了声音？
规则是一种 将知识模块用让人易于理解的方式结合起来 的方法。如果“客户很富有”，那么“他将会购买我的产品”。如果“体温超过 37 摄氏度”，那么“这个人生病了”。决策规则普遍应用于医疗、银行和保险领域，以及与客户打交道的特定流程中。
在一条规则中，人们区分 前件或前提 （一系列测试）和 后件或结论 。结论是对应输入并使得前提成立的输出类别；如果类别不能 100% 确定，就给出这些类别的概率分布。通常，这些前提都是用“且”连接起来的，也就是说，如果我们要“发射”这条规则，即得到结论，那么所有测试都必须通过。如果“距离小于 2 英里”且“晴天”，那么“步行”。一条测试可以针对类型变量的值（“晴天”），或者数值变量简单运算的结果（“距离小于 2 英里”）。如果想要让人理解，计算就必须简单。一个实用的改进是将前提为假时的分类也加入到同一个语句中。如果“距离小于 3 公里”且“没有私家车”，那么“步行”，否则“坐公交车”。
提取知识模块形成一个简单规则的集合是诱人的。但是 手动设计和维护规则是昂贵 且困难的。当规则集变大时，复杂性就会显现，就像图 1 中的规则会导致不同的甚至矛盾的分类。在这些情况下，分类可能与不同规则在数据上进行测试的排列顺序有关。从数据中 自动提取不矛盾的规则的方法是 很宝贵的。
相比处理带很多测试的非常长的前提，将规则分解成一串简单的问题更有价值。在贪心法中，那些信息量最大的问题最好放在这一序列的前面，这样可以 给问题加上层次结构 ，从信息量最大的问题到信息量最小的问题。如上这些动机很自然的让我们考虑到 决策树 ，它是决策规则的有组织的分层排列，并且没有矛盾（见图2）。
决策树，以及同一棵树中达到分类的一种情况（图3）。抵达拆分节点的数据点根据测试函数的结果被发送到其左子节点或右子节点。
决策树在机器学习（ ML ）诞生之初就非常普及了。现在，确实只有小而浅的树能够被人们“理解”，但是近年来由于计算和存储能力的极大提升，决策树的普及度越来越广了。很多树（在某些情况下可达到上百棵）可以组合使用，称为 决策森林 ，来得到具有健壮性的分类器。当考虑森林时，关心人们是否能理解这一问题被移至幕后，务实地寻找没有过度训练风险的、具有健壮性的高性能表现成为台前的主角。
决策树是以层次的方式组织起来的一个问题集，并且用一棵树的图形来表示。由于历史的原因，机器学习中的树，如同所有在计算机科学领域中的树那样，常常把根画在上方 —— 如果你在北半球，那就想象澳大利亚的那些树。对于一件给定的事物，决策树通过连续地提出关于其已知属性的问题来估计它的一个未知属性。下一个问题问什么取决于前一个问题的答案，如果用图形来表示，这一事物对应于这棵树中的一条路径，如图 3 的粗线条所显示的。决策则根据这条路径的终端节点来做出。终端节点称作叶子。决策树可以被看作将复杂问题分解为简单问题集的一种方法，分解过程在这个问题已足够简单，即已到达叶子节点并找到已有的答案时结束。
一个从已标记的实例来构造决策树的基本方法是按照贪心法来进行的：在层次结构中，信息量越大的问题就越靠前。考虑一下初始的被标记的实例集。一个有两个可能输出（“是”或“否”）的问题将这一实例集分为两个子集，其中一个子集包括答案为“是”的实例，另一个子集包括答案为“否”的实例。初始的实例集是混乱的，包含不同类的实例。当问完一串问题，从根到了叶子时，叶子中余下的集合就应该几乎是“纯”的了，也就是只包含同一类的实例。这一类别也就是所有到达这片叶子的实例所对应的输出。
我们需要从初始的混乱的集合过渡到最终一系列（几乎）纯的集合。一个瞄准这一目标的 贪心 法就是从“信息量最大的”问题开始。这会把初始的集合划分为两个子集，分别对应答案“是”或“否”，也是初始根节点的子节点（见图 4）。贪心法将以尽可能接近最终目标这一原则迈出第一步。在贪心法中，第一个问题的设计要使得这两个子集尽可能纯净。第一次划分完成之后，以 递归 的方式（见图 5），继续对左右两个子集使用同样的方法，设计合适的问题，如此重复，直到剩下的集合足够纯净，递归停止。完全的决策树是由一个从上到下的过程导出的，这一过程通过在创造的子集中实例的相对比例来引导。
决策树的两个最主要的组成部分，一是纯度的定量度量，二是每个节点问的问题的类型。我们都同意纯度最大值是在子集中只有一个类别的实例时取到，而不同的度量负责测量那些不只一个类别的情况。其他的组成部分与终止条件有关：记住我们的目标是泛化，因此我们不希望构造一棵非常大的树，而每片叶子只有一两个实例。某些情况下，我们允许在子集尚未达到十分纯净时停止训练，并且当一些实例到达某个给定的叶子节点时，输出一个概率值。
在下面的描述中，假设所有涉及的变量都是 类别变量 （即名称，像上面例子中的“欧洲人”）。还有两种广泛使用的子集纯度度量，一是 信息增益 ，二是 基尼混度 。注意我们处理的是 有监督 分类，因此我们知道这些训练实例的正确输出分类（有目标的）。
信息增益 设想我们从一个内部节点或叶子节点对应的集合中进行抽样。我们得到 y 类实例的概率 Pr(y) 正比于集合中该类实例所占的比例。所得类的统计不确定性由标记概率分布的香农 熵 来度量：
在信息论中，熵量化了确定某件事件发生所需的平均信息（见图6 ）。如果对数的底为 2 ，信息（也就是熵）的单位是二进制位（ bit ）。当所有 n 个类别的实例均分了一个集合时，熵就达到最大值， H(Y ) = logn ；而当所有实例都属于同一类别时（这种情况下，不需要任何信息，我们已经知道我们会得到什么类别了），熵就达到最小值， H(Y ) = 0 。
在信息增益方法中， 一个集合的混度由类别概率分布的熵来度量 。
知道一个问题的答案将会降低熵，或者熵保持不变，仅当答案不取决于类别时。令 S 表示目前的实例集，并且让 表示问过一个关于某属性问题之后的划分。理想的问题不会留下难以决策的情况： 中所有实例是一类，而 中所有实例是另一类，因此这两个生成的子集熵为零。
在知道了答案后，熵的平均减少量被称为“信息增益”，它也是答案与类别变量之间的互信息（ MI ）。信息增益（互信息）可表述如下：
计算熵所需的概率可以用样本子集内各类别的相应频率来逼近。信息增益是由 Quinlan 率先在 ID3 、 C4.5 和 C5.0 方法中使用的。值得注意的是，由于我们感兴趣的是泛化，信息增益对此是有用的，但并不完美。假设我们为描述某项业务客户的数据构造一棵决策树，每个节点可以有多于两个子节点。一个输入属性可能是客户的信用卡号码。因为这一属性唯一地标识每个客户，所以它与任何分类都有很高的互信息，然而我们不希望将其包含在决策树中：根据客户的信用卡号码来对客户作出相应决策，这一做法不太可能推广到之前没有见过的客户（这就是 过拟合 ）。
基尼混度 试想一下，我们从一个集合中随机抽取一个元素，并随机贴上标签，概率正比于不同类别在这个集合中所占的比例。尽管这种方法看起来很原始，如果集合是纯的，这种简单直接的方法的误差为零；如果某个类别在集合中占据了主要部分，这种方法的错误率也是很小的。
一般情况下，基尼混度（ GI ）测量从集合中随机选择的元素会被错误地标记的频率，标记是按照集合中标记的分布随机进行的。它可以用错误率的期望来计算：对于每个类别，将该类别中某个元素被误分为其他类的概率（即将其分配给任何不正确类别的概率： ）相加，再乘以该元素属于该类别的概率 ( ) ，然后将这些乘积加起来。假设有 m 个类，并且令 表示集合中标记为 i 的元素比例。然后，通过频率来估计概率（ ≈ ）：
当节点中所有实例都属于单一目标类别时， GI 为最小值（零）。 GI 被用在 Breiman 提出的CART 算法（分类回归树）中。
当考虑每个节点所问的问题类型时，实际上只需要考虑那些 有二元输出的问题 就足够了。对于类别变量，这个测试可以基于该变量的可能值的某个子集（例如，若某天是“星期六或星期天”，则回答 YES ，否则 NO ）。对于实值变量，每个节点对应的测试可以基于单一变量（例如，距离小于 2 英里）或者变量的简单组合，例如变量子集的一个线性函数与一个阈值进行比较（例如，客户花在汽车和摩托车上的钱的平均值多于 2 万美元）。上述概念可以被推广到要预测的数值变量，发展为 回归树 。每片叶子要么包含到达这里的所有实例的平均输出值，要么包含从这些实例推导出的一个简单模型，比如线性拟合（后一种情况称为 模型树 ）。
实际的数据中， 缺失值 就像冬天的雪花漫天飞舞。缺失值有两种可能的意义。在某些情况下，一个值如果缺失了，它会提供一些有用的信息（例如，在市场营销中，如果一个客户没有回答某个问题，我们可以假设他对此不是很感兴趣），缺失值可以被当作一个类型变量的另一个可能值。其他情况下，一个值的缺失并不提供任何明显的信息（例如，一个粗心的业务员忘了记录某个客户的数据）。决策树为处理第二种情况提供了一种自然的方法。如果一个实例到达了一个节点，但是由于数据缺失而无法回答该节点对应的问题，人们可以理想化地“将这个实例分成小块”，并且根据所包含训练实例数的比例，将这些小块送往各个分支。如图 7 所示，如果 30% 的训练实例往左走，那么一个有缺失值的实例在这个决策节点就被分为两部分，比重 0.3 的那一部分往左走，而比重 0.7 的那一部分往右走。当这个实例不同的小块最终都到达叶子节点时，我们计算对应叶子节点输出值的加权平均，或者计算出一个分布。加权平均中的权重与到达叶子部分的比重成正比。在这个例子中，输出值是 0.3 乘以左边的输出加上 0.7 乘以右边的输出。不用说，以左、右子树作为参数的同一程序的递归调用，是获得非常紧凑的软件实现的一个方法。
最后提醒一下，不要将构建中的决策树（使用已标记实例、纯度度量，以及选择合适的问题）和使用已构建好的决策树相混淆。当使用决策树时，通过一系列决策，输入样本会迅速从树的根节点分配到叶子节点。
在 20 世纪 90 年代，研究人员发现了如何用民主的方式将学习机集成起来（例如，比随机猜测性能略好的通用“弱”分类器），以得到更好的准确性和泛化性能。这可以类比于人类社会：很多情况下，设立专家团体是做出更优质决策的一个方法，专家或者达成共识，或者提出不同的方案并表决（在其他情况下，这也是推迟决策的方法，毕竟所有类比都有它的缺点）。“群众的智慧”是近来用以强调民主决策积极作用的一个术语。在机器学习中，输出常常由多数决定（对于分类）或由平均决定（对于回归）。
在处理高维数据时，民主式集成这一点似乎尤其正确，因为在现实的应用中，高维数据里可能有很多不相关的属性。这一话题并不像它看起来那样抽象：从光学字符识别中用到的神经网络到游戏机输入设备中树的集成 ，已经出现了很多相关的应用 。
为了让专家团体来做出高明的决策，这些专家需要有不同的思维方式（即不受群体思维的影响，以同样方式思考的专家是没有用的）并且具有较高的素质。获得不同的树的方式有多种，例如，用不同的实例集来训练它们，或者以不同的随机选择来训练它们（用人来打比方，想想学生会选择同一科目的不同课程）。
• 可以用 自助法 从初始集合中产生 不同的训练实例集 ：给定一个大小为 的标准训练集 D ，自助法通过从 D 中均匀带放回（有些实例可以重复）的抽样产生新的训练集。抽样之后，每个训练集中大概有 1 − 1/e ≈ 63.2% 的实例是互不相同的，其他的都是重复的。想想随机投球入筐：对于较大的 ，大概只有63.2% 的筐里有一个或以上的球。筐中的每个球对应一个实例。在每个自助法的训练集中，大概有三分之一的实例被排除了。将自助法用于创造不同样本集的方法称为 装袋法 （ bagging ，“自助汇合”）：用不同的随机自助样本来构造不同的树，输出是不同树的输出的平均（对于回归问题）或着表决（对于分类问题）。
• 在选择一个节点的最优问题时，可以通过限制选择，在训练时进行 不同的随机选择 。作为上述划分方法的一个例子，这里来看看它们是如何在 随机决策森林 中实现的。
• 每棵树用原始数据集的一个自助抽样（即允许重复）来进行训练；
• 每当一个叶子节点必须被分裂的时候，只考虑属性随机选择的一个子集。在极端情况下，只考虑一个随机属性（一维）。
更准确地说，令 d 为输入变量的总数，每棵树是这样构造的：选择 d' 个输入变量用以确定一个节点上的决策，d' 是个较小的数，通常比 d 要小得多（在极端情况下就是 1 ）。一个自助抽样（“包”）引导一棵树的构造，而那些不在包里的实例可以用来估计树的误差。对于树上的每个节点， d' 个属性是随机选择的，它们是在这个节点上做出决策的基础。我们计算基于这 d' 个变量的最优分割（“最优”要根据所选的纯度标准而定， IG 或者 GI ）。每次选择一个类型变量来对一个节点进行分割，可以随机选择这些类型的子集，并定义一个替换变量，当类型值在这个子集中就为 1 ，否则为 0 。每棵树都完全成长而不修剪（就像构造一棵普通的分类树那样。
通过上述步骤，我们实际上已经组建了一个团体（“森林”），其中的每一个专家（“树”）都已经接受了不同的训练，因为他们已经看到了一组不同的实例（包），也因为他们用不同的观点看待问题（每一个节点使用不同的随机选择的标准）。然而没有哪位专家可以完全保证胜任工作：每个专家关注变量的顺序远远没有达到贪心的标准，因此信息量最大的问题并没有最受关注，如此一来，单独的一棵树是非常弱的；然而，大多数专家都比随机分类器要好，因此多数占优原则（或者加权平均）将会提供合理的答案。
使用自助法时的泛化估计可以在训练过程中以一种自然的方式得到：记录包外的误差（不在包中的实例上的误差），并在整片决策森林上求平均。
不同变量（ 特征或属性排序 ）的相关性也可以在决策森林中用一种简单方式来估计。主体思路是：如果一个类别特征是重要的，那么随机地置换其值应该会导致其性能显著降低。用决策森林拟合数据之后，为了推导第 i 个特征的重要性，将第 i 个特征的值进行随机置换，并重新计算这个扰乱的数据集上的包外误差。求得扰乱前后的包外误差之差，并在所有树上求平均值。误判率增加的百分比与所有变量不变时包外误差率的比值就是该特征所得的分数。误判率增加较多的特征比误判率增加较少的特征更重要。
可以使用大量树（数以千计并不罕见）这一事实意味着，对于需要进行分类或预测的每个实例，会有非常多的可用的输出值。通过收集和分析如此多树的输出的分布，可以得出回归的置信界或者分类的概率。例如，如果有 300 棵树预测“晴天”，剩下的 700 棵树预测“下雨”，那么可以说估计“下雨”的概率是 70% 。
简单的“如果 – 那么”规则提炼出在某种程度上可以被人们理解的信息金块。避免可能的规则矛盾所带来的混乱，有一个简单方法是以层次结构来处理问题（首先是信息量最大的），由此引出带组织结构的简单的连续问题，称为 决策树 。
树可以用贪心和递归的方式习得：从一整套的实例集开始，选择一个测试，将它分为两个尽可能纯的子集，再重复产生子集。当子集的纯度足以在树叶上得到分类输出值时，递归过程终止。
充足的内存和强大的计算能力允许我们训练大量不同的树。通过收集所有输出以及平均（对于回归）或投票（对于分类），它们可以卓有成效地用作 决策森林 。决策森林有各种优点：像所有树那样，它们能自然地处理两类以上的分类问题以及缺失的属性；能提供基于概率的输出，以及概率和误差线；不会有过度训练的风险，因此能很好地泛化到从未见过的数据；由于其并行性，以及每个数据点上减少的测试问题集，它快速而高效。
虽然一棵树的树荫很小，但即使是最火热的机器学习应用，数以百计的树也可以带来清凉。
6. 12-分类算法-决策树、随机森林
决策树
生活中的决策树模型：
显然：判断依据的重要性从前往后越来越小
信息的度量和作用
在不知道任何信息的情况下猜测32支球队中的冠军：如果用二分法，需要猜5次，即需要的代价为5bit，这个5bit我们称之为信息熵（H） 5 = -(1/32log(1/32) + 1/32log(1/32) + ... + 1/32log(1/32))
公式：概率log概率 之和
如果我们知道了一些球队的信息，需要的代价会小于5bit 5 > -(1/4log(1/32) + 1/8log(1/32) + ... + 1/24log(1/32))
信息熵越大(比如，当每个球队的夺冠几率相等)，不确定性越大
结合决策数，之所以我们先对某些条件进行判断，是因为能够减少我们更多的不确定性
决策树的划分依据——信息增益
信息增益：当得知一个条件之后，减少的信息熵的大小
决策树的api
在泰坦尼克号和titanic2数据帧描述泰坦尼克号上的个别乘客的生存状态。在泰坦尼克号的数据帧不包含从剧组信息，但它确实包含了乘客的一半的实际年龄。关于泰坦尼克号旅客的数据的主要来源是百科全书Titanica。这里使用的数据集是由各种研究人员开始的。其中包括许多研究人员创建的旅客名单，由Michael A. Findlay编辑。 我们提取的数据集中的特征是票的类别，存活，乘坐班，年龄，登陆，home.dest，房间，票，船和性别。乘坐班是指乘客班（1，2，3），是社会经济阶层的代表。 其中age数据存在缺失。
决策树部分图例：
决策树的优缺点以及改进
优点：
缺点：
改进：
集成学习方法
集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是 生成多个分类器/模型 ，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。
随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。
随机森林建立多个决策树的过程：
ps：为什么要随机抽样？避免每颗树的训练集的一样，那么最终训练出的上面的分类结果也是完全一样的
随机森林案例：
随机森林的优点：
随机森林几乎没有缺点
最新文章
热门文章
推荐阅读