每天更新，学点记点
- 4.1基本流程
决策树是基本树结构来进行决策的，决策过程中提出的每个判定问题都是对某个属性的“测试”，每个测试的结果或是导出最终结论，或者导出进一步的判定问题。
决策树学习的目的是为了产生一棵泛化能力强（处理未见示例能力强的决策树），基本流程遵循简单且直观的“分而治之”策略。
决策树的生成是一个递归过程：
导致递归返回有三种情形：
（一）当前结点包含的样本全属于同一类别，无需划分。
（二）当前属性集为空，或是所有样本在所有属性上的取值相同，无法划分 。把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。后验分布。
（三）当前结点包含的样本集合为空，不能划分。把当前结点标记为叶结点，但将基类别设定为其父结点所含样本最多的类别。先验分布。
-
4.2划分选择
决策树学习的关键是选择最优划分属性。1信息增益。2增益率。3基尼指数。 -
4.2.1信息增益（ID3决策树）
计算出用属性a对样本集进行划分所划得的“信息增益”，用信息增益来进行决策 树的划分属性选择，信息增益越大，划分所获得的“纯度提升越大”。ID3决策树学习算法就是以信息增益为准则来选择划分属性。
信息熵：
Ent（D）的值越小，则D的纯度越高。
信息增益：
信息增益越大，划分所获得的“纯度提升越大” -
4.2.2增益率（C4.5决策树）
编号的信息增益大，但不具有泛化效果。
使用“增益率”来选择最估划分属性。
增益率则对可骤值数目较少的属性有所偏好，使用了启发式：先从候选划分属性中找出信息增益高于平均水平 的，再从中选取增益率最高的。 -
4.2.4基尼指数（Cart决策树）
从数据集中随机抽取两个样本，用基尼指数标记不一致的概率，越小，纯度越高。
属性a最小
基尼指数最小的为划分属性 -
4.3剪枝处理
去掉一些分支来降低过拟合的风险。
基本策略有：
1预剪枝。在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
2后剪枝。生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
一般情形下，后剪枝的欠拟合风险小，泛化能力往往优于预剪枝决策树，但其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。 -
4.4连续与缺失值
采用二分法对连续属性进行处理。
浙ICP备19012682号