决策树算法之 AdaBoost

简介: AdaBoost 是一种更高级的「森林」类型的决策树,和随机森林比起来,它有以下三个特点 1. AdaBoost 的每棵树都只有一个根节点和两个叶子节点,实际上叫树桩(stump)可能会更合适 2. AdaBoost 的每个树桩的权重是不同的,而随机森林中的每棵树的权重是相同的 3. 前一个树桩的错误数据会影响后一个树桩的生成,意味着后面的树桩是前面树桩的补足。这种思想也被称为 Boos

AdaBoost 是一种更高级的「森林」类型的决策树,和随机森林比起来,它有以下三个特点

  1. AdaBoost 的每棵树都只有一个根节点和两个叶子节点,实际上叫树桩(stump)可能会更合适
  2. AdaBoost 的每个树桩的权重是不同的,而随机森林中的每棵树的权重是相同的
  3. 前一个树桩的错误数据会影响后一个树桩的生成,意味着后面的树桩是前面树桩的补足。这种思想也被称为 Boosting,除 AdaBoost 外,GBDT 和 XGBoost 也是这样的思想(很明显它们中都有 Boost)。

AdaBoost 的生成步骤

假设我们有以下训练数据,我们想通过「胸口疼痛」、「血管堵塞」和「体重」这三个特征来训练一个心脏病预测模型:

胸口疼痛 血管堵塞 体重 患心脏病
Yes Yes 205 Yes
No Yes 180 Yes
Yes No 210 Yes
Yes Yes 167 Yes
No Yes 156 No
No Yes 125 No
Yes No 168 No
Yes Yes 172 No

首先,我们需要为每个样本附上一个相同的权重,因为只有 8 条数据,所以每个样本的权重均为 1/8,如下

胸口疼痛 血管堵塞 体重 患心脏病 样本权重
Yes Yes 205 Yes 1/8
No Yes 180 Yes 1/8
Yes No 210 Yes 1/8
Yes Yes 167 Yes 1/8
No Yes 156 No 1/8
No Yes 125 No 1/8
Yes No 168 No 1/8
Yes Yes 172 No 1/8

接下来,我们利用基尼不纯度在这 3 个特征中找一个最合适的作为树根,经过计算,当「体重 >176」 时,基尼不纯度最小,则第一个树桩的节点为「体重 >176」,如下图所示:

产生出一个树桩后,我们把该树桩判断错误的样本拿出来,将它们的权重相加,便得出该树桩的总误差,上述树桩只有一个错误样本:

胸口疼痛 血管堵塞 体重 患心脏病 样本权重
Yes Yes 167 Yes 1/8

则该树桩的总误差(Total Error)即这条错误样本的权重——0.125。通过总误差,我们便可以计算出该树桩的 Weight:

$$ Weight_{stump} = \frac{1}{2}\log(\frac{1-TotalError}{TotalError}) $$

该公式的曲线如下图所示,可以看到,误差的取值范围在 0 到 1 之间,随着误差越大,树桩的 Weight 越小,上例中,我们的误差为 0.125,所对应的 Weight 为 0.973,也就是图中蓝色点所处的位置:

一棵树桩产生出来后,接着就要产生第二棵,前面说了,后一棵树的生成依赖于前一棵树的误差,具体的,我们会根据这个误差来调整每个样本的权重,这样,后面的树就可以根据样本的新权重来训练了,更进一步,前一棵树中错误的样本,我们希望在下一棵树的训练中,提高这些样本的权重,同时降低正确样本的权重,这样下一棵树便会更倾向于把错误样本处理好,起到了对前面树的补足作用

整体误差和树的 Weight 成负相关关系,Weight 越高代表置信度越高,这时错误的样本相对于 Weight 低的树来说,样本权重要调的更高,而正确的样本的权重要调的更低,错误样本权重和正确样本权重的调整分别如下面左图和右图所示:

对于本例来说,第一个树桩的 Weight 为 0.973,则错误样本的权重根据左图公式,将调整为 $0.125 \times 2.646 = 0.33$,同理,正确样本的权重根据右图公式,将调整为 $0.125 \times 0.378=0.05$,归一化后,最终所有样本的权重调整如下:

序号 旧样本权重 新样本权重 归一化后
1 1/8 0.05 0.07
2 1/8 0.05 0.07
3 1/8 0.05 0.07
4 1/8 0.33 0.49
5 1/8 0.05 0.07
6 1/8 0.05 0.07
7 1/8 0.05 0.07
8 1/8 0.05 0.07

接下来,我们需要根据新的特征权重来训练树桩,其中的一种办法是根据权重来抽样,即在每抽一条数据之前,产生一个 0-1 的随机数,根据随机数来决定抽哪条数据。以上面的数据举例,当随机数落在 [0, 0.07) 范围内时,则抽出第 1 条样本,落在 [0.07, 0.14) 范围内时,则抽出第 2 条样本,以此类推。

抽样完成后,我们重新对这些样本赋予等值的权重,如下:

胸口疼痛 血管堵塞 体重 患心脏病 样本权重
No Yes 156 No 1/8
Yes Yes 167 Yes 1/8
No Yes 125 No 1/8
Yes Yes 167 Yes 1/8
Yes Yes 167 Yes 1/8
Yes Yes 172 No 1/8
Yes Yes 205 Yes 1/8
Yes Yes 167 Yes 1/8

因为在选样本时,第 4 条样本的权重最高,它被抽到的概率就最大,从上表也可以看出,第 4 条样本重复了 4 次,这样做的好处是,使用这批数据训练后,新的树桩会更倾向于把第 4 条样本分类正确。推而广之,在 AdaBoost 中,后面的树桩会更擅长于处理前面树桩的错误情况。

接下来的步骤和最开始的一样,重复上面的过程就可以了。

AdaBoost 的预测

在构建完 AdaBoost 后,我们该如何做预测呢?预测过程和随机森林类似,都是用每棵树的结果来投票,差别在于这里采用的是加权投票。例如我们有条数据,每棵树对该数据的预测结果如下:

树序号 树 Weight 预测结果
1 0.97 1
2 0.34 0
... ... ...
100 0.46 1

聚合后,把相同预测结果的 Weight 相加,如下

预测结果 树 Weight 之和
1 43.7
0 20.1

取 Weight 较大者,所以该条数据的预测结果为 1.

总结

本文我们一起学习了 AdaBoost 的构建过程,AdaBoost 和随机森林比起来,有 3 个特点:

  1. 每棵树只有一个根节点和两个叶子节点
  2. 后一棵树由前一棵树的误差决定
  3. 每棵树都有不同的权重,预测时会根据权重来聚合预测结果

此外,文中对样本加权的手段很有借鉴意义,我们可以把这种方法运用到预测 CTR 等模型的场景中

参考:AdaBoost, Clearly Explained

相关文章
|
3月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
102 1
|
11天前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
20 2
|
1月前
|
机器学习/深度学习 算法 Python
探索机器学习中的决策树算法:从理论到实践
【10月更文挑战第5天】本文旨在通过浅显易懂的语言,带领读者了解并实现一个基础的决策树模型。我们将从决策树的基本概念出发,逐步深入其构建过程,包括特征选择、树的生成与剪枝等关键技术点,并以一个简单的例子演示如何用Python代码实现一个决策树分类器。文章不仅注重理论阐述,更侧重于实际操作,以期帮助初学者快速入门并在真实数据上应用这一算法。
|
16天前
|
机器学习/深度学习 人工智能 算法
探索机器学习中的决策树算法
【10月更文挑战第29天】本文将深入浅出地介绍决策树算法,一种在机器学习中广泛使用的分类和回归方法。我们将从基础概念出发,逐步深入到算法的实际应用,最后通过一个代码示例来直观展示如何利用决策树解决实际问题。无论你是机器学习的初学者还是希望深化理解的开发者,这篇文章都将为你提供有价值的见解和指导。
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
20 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
56 2
|
1月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
24 0
|
1月前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
16 0
|
2月前
|
机器学习/深度学习 算法 数据挖掘
决策树算法大揭秘:Python让你秒懂分支逻辑,精准分类不再难
【9月更文挑战第12天】决策树算法作为机器学习领域的一颗明珠,凭借其直观易懂和强大的解释能力,在分类与回归任务中表现出色。相比传统统计方法,决策树通过简单的分支逻辑实现了数据的精准分类。本文将借助Python和scikit-learn库,以鸢尾花数据集为例,展示如何使用决策树进行分类,并探讨其优势与局限。通过构建一系列条件判断,决策树不仅模拟了人类决策过程,还确保了结果的可追溯性和可解释性。无论您是新手还是专家,都能轻松上手,享受机器学习的乐趣。
48 9