一. 决策树
决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。
- 根节点：包含样本的全集
- 内部节点：对应特征属性测试
- 叶节点：代表决策的结果
比较常用的决策树有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。
1. ID3（信息增益）
信息熵：度量样本集合纯度常用的一种指标。信息熵的值越小，纯度越高。
信息增益：信息增益越大，则使用属性a来进行划分所获得的“纯度提升”越大。
（属性a对样本集D进行划分所获得的信息增益）
2. C4.5 (增益率)?
信息增益准则对可取值数目较多的属性有所偏好。（例如某个属性的每个分支仅包含一个样本，这些分支结点的纯度已达最大。）——————> 所以使用增益率来选择最优划分属性。
?IV(a) 被称为属性a的固有值。
增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
3. CART（基尼指数）
Gini指数反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini指数越小，则数据集D的纯度越高。
所以选择使得划分后基尼指数最小的属性作为最优划分属性。?
?4. 剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。
预剪枝：在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点
后剪枝：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
二.?随机森林
随机森林属于 集成学习 中的 Bagging.?随机森林是由很多决策树构成的，不同决策树之间没有关联。
当我们进行分类任务时，新的输入样本进入，就让森林中的每一棵决策树分别进行判断和分类，每个决策树会得到一个自己的分类结果，决策树的分类结果中哪一个分类最多，那么随机森林就会把这个结果当做最终的结果。
构造随机森林的步骤：
?三. 集成学习
- Boosting：个体学习器间存在强依赖关系，必须串行生成的序列化方法。
- Bagging和随机森林：个体学习器间不存在强依赖关系，可同时生成的并行化方法。