0%

从决策树到Adaboost算法

决策树算法

决策函数选择

决策树训练算法


信息熵和信息增益



决策树算法的改进

数值型特征

剪枝

Adaboost算法

Boosting

Adaptive Boosting

基本训练过程

算法流程描述

其中,$z_t = \sum_{i=1}^N p^{t-1}(i)exp(-a_ty_ih_t(x_i))$ 。
关于分类器权重的更新,对于正确样本,$y_ih_t(x_i) \gt 0$,所以 $exp(-a_ty_ih_t(x_i)) \lt 1$,权重变小,错误样本相反则变大。

AdaBoost在训练集上错误率

对方框中的证明如下:

对于红色部分的说明:当 $f_T(x_i) \neq y_i$ 时,$y_if_T(x_i) \gt 0$,于是有 $exp(-y_if_T(x_i)) \ge 1$,据此易得上式。


注:$4,5$ 行中的 $\epsilon_t$ 和 $ 1- \epsilon_t$ 出现笔误,应该交换位置,但不影响最终结果。

AdaBoost的损失函数

参考文献:
[1] 徐君,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程