发帖
雷达卡
决策树还有一个集成版本：随机森林。随机森林本质上代表了 N 个决策树的集合，从而增加了预测的稳健性。
在本文中，我们简要概述了决策树生长背后的算法、其质量度量、避免过度拟合训练集的技巧，以及决策树随机森林引入的改进。
什么是决策树？
决策树是一个类似流程图的结构，由节点和分支（图。1）。在每个节点，根据输入特征之一对数据进行拆分，生成两个或多个分支作为输出。在即将到来的节点中进行越来越多的拆分，并且生成越来越多的分支来划分原始数据。这种情况一直持续到生成一个节点，其中所有或几乎所有数据都属于同一类，并且不再可能进一步拆分或分支。
这整个过程生成了一个树状结构。第一个分裂节点称为根节点。末端节点称为叶子并与类标签相关联。从根到叶的路径产生分类规则。如果只有二叉分裂是可能的，我们就谈论二叉树。然而，在这里，我们想要处理更通用的非二元决策树实例。
让我们用一个例子来形象化。我们根据各种外部条件或“输入特征”（例如风速（节）、最高温度、前景以及是否船在冬季存放。输入特征通常也称为非目标属性或自变量。我们现在想要构建一个决策树来预测航行结果（是或否）。航行结果特征也称为目标或因变量。
如果我们知道确切的分类规则，我们可以手动构建决策树。但这种情况很少见。我们通常拥有的是数据：一侧的输入特征和另一侧要预测的目标特征。许多自动程序可以帮助我们从数据中提取规则来构建这样的决策树，例如 C4.5、ID3 或CART 算法 （J.罗斯昆兰）。在所有这些中，目标是训练决策树来定义预测目标变量的规则，在我们的示例中，目标变量是我们是否会在新的一天航行。
图 1. 基于航行经验数据（左）的决策树（右）示例，用于预测是否在新的一天航行。
构建决策树
让我们探索如何按照上面列出的算法之一自动构建决策树。
这些算法中的任何一个的目标都是将训练集划分为子集，直到每个分区就目标类而言是“纯的”或足够小。要清楚：
纯子集是仅包含一个类的样本的子集。
每个分区操作都由一个规则实现，该规则根据输入特征之一的值拆分传入数据。
总而言之，决策树由三个不同的构建块组成：节点、分支和叶子。节点识别分割特征并对输入的数据子集进行分割操作；分支离开一个节点并识别分区操作产生的不同数据子集；路径末端的叶子识别数据的最终子集并将类与该特定决策路径相关联。
例如，在图 1 的树中，第一个节点中的拆分涉及“存储”功能，并将输入子集划分为两个子集：一个存储为“是”，一个存储为“否”。如果我们遵循 Storage = yes 的数据行的路径，我们会找到第二个分区规则。这里输入数据集被分成两个数据集：一个“Wind” > 6 和一个“Wind” <= 6。算法如何决定在每个点使用哪个特征来分割输入子集？
这些算法中的任何一个的目标都是递归地将训练集划分为子集，直到每个分区在输出类方面尽可能纯。因此，在每一步，算法都使用导致最纯输出子集的特征。
质量措施
在每次迭代中，为了确定哪个特征导致最纯粹的子集，我们需要能够测量数据集的纯度。过去已经提出了不同的指标和指数。我们将在这里描述其中的一些，可以说是最常用的：信息增益、基尼指数和增益比。
在训练期间，会为所有候选特征计算所选的质量度量，以确定哪一个会产生最佳分割。
熵
熵是一个用来衡量信息或无序的概念。当然，我们可以用它来衡量数据集的纯度。
如果我们将目标类视为数据集中某个点的可能状态，则数据集的熵在数学上可以定义为所有类的概率之和乘以它的对数。因此，对于二元分类问题，熵的范围在 0 和 1 之间。
其中p是整个数据集，N 是类数，p i是同一数据集中类i 的频率。
为了更好地理解熵，让我们研究两个不同的示例数据集，它们都有两个类，分别表示为蓝点和红叉（图 2）。在左侧的示例数据集中，我们混合了蓝点和红叉。在右侧数据集的示例中，我们只有红十字。第二种情况——一个只有一个类样本的数据集——是我们的目标：一个“纯”数据子集。
图 2. 两类：红十字和蓝点。两个不同的数据集。混合了属于两个类的点的数据集（左侧）和仅包含一个类的点的数据集（右侧）。
现在让我们计算这两个二进制数据集的熵。
对于左侧的示例，带有红叉的类的概率为 7/13，而带有蓝点的类的概率为 6/13。请注意，在这里，一个类的数据点几乎与另一类的数据点一样多。上面的公式导致熵值为 0.99。
对于右侧的示例，带有红叉的类的概率为 13/13 = 1.0，而带有蓝点的类的概率为 0/13 = 0.0。请注意，这里我们只有红色交叉点。在这种情况下，上面的公式导致熵值为 0.0。
熵可以是纯度、无序或信息的量度。由于混合类，左边的数据集不那么纯净，更混乱（更无序，即更高的熵）。然而，更多的混乱也意味着更多的信息。实际上，如果数据集只有一类的点，那么无论您尝试多长时间，都无法从中提取太多信息。相比之下，如果数据集具有来自两个类的点，则它也具有更高的信息提取潜力。所以，左边数据集的熵值越高，也可以看作是潜在信息量越大。
决策树中每个拆分的目标是从混淆的数据集移动到两个（或更多）更纯的子集。理想情况下，分裂应该导致熵为 0.0 的子集。然而，在实践中，如果拆分导致子集的总熵低于原始数据集就足够了。
图 3. 树节点中的拆分应该从熵较高的数据集移动到总熵较低的子集。
信息增益 (ID3)
为了评估一个特征对分裂的好坏，计算分裂前后的熵差。
也就是说，我们首先计算分割前数据集的熵，然后计算分割后每个子集的熵。最后，在拆分之前从数据集的熵中减去由子集大小加权的输出熵之和。这种差异衡量了信息的增益或熵的减少。如果信息增益是一个正数，这意味着我们从一个混乱的数据集转移到了一些更纯粹的子集。
其中“before”为拆分前的数据集，K为拆分后生成的子集数量，(j, after)为拆分后的子集j。
然后，在每一步，我们将选择在信息增益值最高的特征上分割数据，因为这会产生最纯粹的子集。应用此度量的算法是 ID3 算法。ID3算法的缺点是偏爱具有大量值的特征，生成更大的决策树。
增益率 (C4.5)
C4.5 算法中使用的增益比度量引入了 SplitInfo 概念。SplitInfo 定义为权重的总和乘以权重的对数，其中权重是当前子集中的数据点数量与父数据集中的数据点数量之比。
然后通过将来自 ID3 算法的信息增益除以 SplitInfo 值来计算增益比。
其中“before”为拆分前的数据集，K为拆分后生成的子集数量，(j, after)为拆分后的子集j。
基尼指数 (CART)
CART 算法使用的另一种纯度（或实际上是杂质）的衡量标准是基尼指数。
基尼指数基于基尼杂质。Gini 杂质定义为 1 减去数据集中类概率的平方和。
其中p是整个数据集，N 是类数，p i是同一数据集中类i 的频率。
然后将基尼指数定义为拆分后不同子集的基尼杂质的加权和，其中每个部分按子集大小相对于父数据集大小的比率加权。
对于具有两个类别的数据集，基尼指数的范围在 0 和 0.5 之间：如果数据集是纯的，则为 0，如果两个类别平均分布，则为 0.5。因此，具有最低基尼指数的特征被用作下一个分裂特征。
其中K是拆分后生成的子集的数量，(j, after)是拆分后的子集j。
识别分裂
对于标称特征，我们有两种不同的拆分选项。我们可以为训练集中所选特征的每个值创建一个子节点，也可以进行二分分裂。在二进制分割的情况下，所有可能的特征值子集都被测试。在最后一种情况下，该过程的计算成本更高，但仍然相对简单。
在数值特征中，识别最佳分割更为复杂。所有数值实际上都可以拆分候选。但这会使质量度量的计算变得过于昂贵！因此，对于数值特征，分割总是二进制的。在训练数据中，候选分割点取在所选数值特征的每两个连续值之间。同样，采用产生最佳质量度量的二元拆分。然后，分割点可以是该特征上两个分区之间的平均值，即较低分区的最大点或较高分区的最小点。
尺寸和过拟合
与许多其他机器学习算法一样，决策树可能会过度拟合训练数据。太深的树可能会导致模型过于详细并且无法概括新数据。另一方面，太浅的树可能会导致模型过于简单，无法拟合数据。你看，决策树的大小至关重要。
图 4. 决策树的大小很重要。一棵大而太详细的树（右侧）可能会过度拟合训练数据，而一棵太小（左侧）的树可能太简单而无法拟合数据。
有两种方法可以避免过度专业化的树：修剪和/或提前停止。
修剪
在训练阶段之后将修剪应用于决策树。基本上，我们让树在其设置允许的范围内自由增长，而不应用任何明确的限制。最后，我们继续削减那些没有充分填充的分支，以避免过度拟合训练数据。事实上，没有足够填充的分支可能过于专注于特殊数据点。这就是为什么删除它们应该有助于对新的看不见的数据进行泛化。
有许多不同的修剪技术。在这里，我们要解释一下最常用的两个：减少错误剪枝和最小描述长度剪枝，简称MDL.
在减少错误修剪中，在每次迭代中，修剪低填充分支并将树再次应用于训练数据。如果分支的修剪不会降低训练集的准确度，则该分支将被永久移除。
MDL 修剪使用描述长度来决定是否修剪一棵树。描述长度定义为对树进行编码所需的位数加上对训练集的错误分类数据样本进行编码所需的位数。当修剪树的一个分支时，计算并比较未修剪树和修剪树的描述长度。如果剪枝树的描述长度较小，则保留剪枝。
提前停止
避免过度拟合的另一个选择是基于停止标准的提前停止。
一种常见的停止标准是每个节点的最小样本数。当创建的节点包含的数据样本数少于或等于最小集数时，分支将停止增长。所以这个最小值的值越大，树越浅，而值越小，树越深。
决策树的随机森林
正如我们在开始时所说，为了提供更强大的性能而进化的决策树导致了随机森林。让我们看看创新的随机森林模型与原始决策树算法的比较。
许多比一个好。简单来说，这就是随机森林算法背后的概念。也就是说，许多决策树可以产生比仅仅一棵决策树本身更准确的预测。事实上，随机森林算法是一种有监督的分类算法，它构建了 N 个经过稍微不同训练的决策树，并将它们合并在一起以获得更准确和稳定的预测.
让我们再次强调这个概念。整个想法依赖于多个决策树，这些决策树都经过略微不同的训练，并且所有这些决策树都被考虑到最终决策中。
图 5. 随机森林算法依赖于多个决策树，它们的训练略有不同；所有这些都被考虑用于最终分类。
训练集的引导
让我们专注于“训练略有不同”。
这训练算法对于随机森林应用一般技术装袋给树学习者。在整个训练集上单独训练一个决策树。在一个随机森林中，N 棵决策树在通过获得的原始训练集的一个子集上进行训练自举原始数据集，即通过带放回的随机抽样。
此外，输入特征也可能因树而异，作为原始特征集的随机子集。通常，如果m是原始数据集中输入特征的数量，则使用随机提取的 [ m的平方根]输入特征的子集来训练每个决策树。
图 6. 随机森林中的决策树都在原始数据集的自举子集上进行了略微不同的训练。对于随机森林中的每棵决策树，输入特征集也会有所不同。
多数规则
N 个稍有不同训练的树将对相同的输入向量产生 N 个稍有不同的预测。通常，多数规则适用于做出最终决定。N棵树中的大多数提供的预测被用作最后一棵。
这种策略的优势是显而易见的。虽然来自一棵树的预测对训练集中的噪声高度敏感，但来自大多数树的预测却不是——只要这些树不相关。Bootstrap 采样是通过在不同的训练集上训练树来去相关树的方法。
袋外 (OOB) 错误
衡量随机森林预测误差的一个流行指标是袋外误差。
袋外误差是对所有训练样本 xᵢ 计算的平均预测误差，仅使用自举训练集中没有 xᵢ 的树。袋外误差估计避免了对独立验证数据集的需要，但可能低估了实际的性能改进。
结论
在本文中，我们回顾了决策树的几个重要方面：如何训练决策树以实现分类问题，使用哪些质量度量来选择要分割的输入特征，以及避免过拟合问题的技巧。
我们还尝试解释了随机森林算法的策略，以使决策树预测更加稳健；也就是说，限制对训练集中噪声的依赖。事实上，通过使用一组 N 个去相关决策树，随机森林提高了最终分类的准确性和鲁棒性。
相关帖子DA内容精选
|
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
