一 Bagging算法与AdaBoost算法

将多个弱分类器组合成强分类器
前提：弱分类器为“不稳定”分类法，即数据集微小变动导致结果显著变化，如决策树、神经网络

（一）Bagging算法——放回采样+投票

（给定弱学习算法）
放回采样生成T个独立子集，用每个独立子集训练一个弱分类器，预测采用多数投票（分类问题）或均值（回归问题）

（二）AdaBoost算法——动态调整样本权重+加权组合弱分类器

【流程】
1.样本权重初始化；
2.迭代：
选择错误率最低的分类器，计算其权重
更新所有样本的权重，错误样本权重增大 正确分类 $D_{t+1}(i)=D_t(i)\times e^{-{\alpha }_t}$，错误分类 $D_{t+1}(i)=D_t(i)\times e^{{\alpha }_t}$[或者正确样本权重不变，错误样本$D_{t+1}(i)=D_t(i)\times （1-{\epsilon }_t）/{\epsilon }_t$]
样本权重归一化
3.结果：强分类器H(x)=sign(Σαₜhₜ(x))

二 决策树（ID3、C4.5和CART）

选最优属性划分节点

ID3-信息增益

选择信息增益大的特征

信息增益 Gain(S,A)=H(S)-H(S|A)=H(S)-∑_ap(A=a)H(S|A=a)=H(S)−∑_{a∈Values(A)​}​H(Sa​)*∣S_a∣/∣S∣ 其中|S_a|/|S|是子集权重
熵 H(S) = -∑^c_j=1P(c_j)log₂P(c_j) （子集含c个类别）

缺点：偏向选择取值多的属性（如”ID“类信息增益大，但实际无意义）

C4.5-信息增益比

是ID3的改进，平衡取值多的属性

Gain Ratio(S,A) = Gain(S,A)/SplitInfo(S,A)
其中SplitInfo衡量属性取值的分布均匀性 SplitInfo=-∑_{a∈Values(A)}$\frac{|Sa|}{|S|}lo{g}_2\frac{|Sa|}{|S|}$
※对连续属性排序，取相邻值中点为候选阈值，选最优阈值离散化

CART（分类与回归树）-二叉树

1.分类：加权Gini指数最小的特征
加权Gini指数Gini_feature=$\frac{|S1|}{|S|}Gini(S1)+\frac{|S2|}{|S|}Gini(S2)$
Gini(S)=1-∑^c_j=1P(c_j)²
2.剪枝：
代价函数： Cost(T)=Err(T)+α⋅∣L(T)∣ 其中Err(T)是树T的分类误差，∣L(T)∣是叶节点数，α是惩罚成本（α≥0）。

三 随机森林

步骤:

1. 样本随机有放回采样；
2. 随机属性选择：从所有属性（d个）中随机选择k个属性（特征），再选择 最佳分割属性作为节点建立CART决策树；
3. 重复以上两步m次，即建立了m棵CART决策树