属性选择
属性的感觉就是最大限度的增加样本的纯度，并且不要产生产生样本数少的分枝。
属性选择标准有信息增益（Information Gain）和Gini系数
信息增益作为标准时，选择信息增益大的作为分裂点
Gini是一种不纯度函数，衡量数据关于类别的纯度，数据均匀分布于各个类别时，不纯度就很大
大小规模合适的树
- 树停止生长的条件（最小划分实例数，划分阈值，最大树深度）
- 对完全生长的树进行剪枝（评估子树，如去掉性能更好，则进行剪枝）
ID3
思想：选信息增益大的属性建立分支，递归选取知道子树只包含一个类别的数据
自顶向下的贪婪的搜索算法，构造出与训练数据一致的决策树
用信息增益作为属性选择的标准，使划分后的数据集的信息熵最小
ID3的问题
- 只能处理属性数据，无法处理连续型数据
- 属性的每个取值都会产生一个对应分支，会有许多小的子集，过小的子集会导致统计特征不充分，使算法停止
- 信息增益在类别值多的属性上计算结果，大于类别值少的属性，导致算法天生偏向选择分支多的属性，会导致过度拟合
C4.5
- 能处理连续性和离散型属性
- 能处理有缺失值的数据
- 信息增益作为决策树属性选择标准
- 对生成树进行剪枝处理
- 决策树到规则自动生成
不同于ID3
C4.5不是直接衡量信息增益，是用的信息增益率来衡量属性的
ID3中的信息增益是根据所属类别（y）来计算的，C4.5以信息增益率为标准，引入分裂信息的概念，考虑了获取增益的代价，克服了ID3偏心多属性特征的缺点
分裂信息用来衡量属性分裂数据的广度和均匀，公式如下
Paste_Image.png
属性值越多，分布越平均的分裂信息越大，对应的信息增益率则越小
对于连续值的求解
Paste_Image.png
处理缺失值，这个ID3也没有
- 直接抛弃
- 平均数或者众数
- C4.5中用概率的方法，为每个可能的赋值都设置一个概率
剪枝
不用预剪枝是因为预剪枝对不同数据的表现很不一样
后剪枝方法
- 从叶节点开始，检查每个非叶节点
- 如果以某个叶节点（或其子节点中使用频率最高的子节点），替换该非叶节点
- 整个决策树的误差率降低就剪去改节点
预剪枝方法
- 限制树的最大深度
- 限制叶节点最小记录数
C4.5后剪枝
针对每个节点，以其中的类别众数作为预测类别
利用每个节点的错误率，根据假设正态分布对真实误差进行估计
悲观误差剪枝
CART树
改进ID3的3个方面
- 不纯度计算用GINI指数，取最小最为分裂点，就是差异损失最大的点（Gini父-Gini子最大的）
- 特征双化（towing），二元分类树
- 输出为离散时为分类树，为连续时为回归树
特征双化
构建二叉树，双化时尽量时2个类别的输出差异性的和，保持最小，就是纯度最大。
具体操作就是穷举法，对每对都计算Gini系数（带全局的权重），然后选择Gini系数最大的呢一组，这种感觉就是选最不纯的一组，用你的下限去和别的属性竞争，以达到全局的最优
