属性选择

属性的感觉就是最大限度的增加样本的纯度，并且不要产生产生样本数少的分枝。

属性选择标准有信息增益（Information Gain）和Gini系数
信息增益作为标准时，选择信息增益大的作为分裂点
Gini是一种不纯度函数，衡量数据关于类别的纯度，数据均匀分布于各个类别时，不纯度就很大

大小规模合适的树

1. 树停止生长的条件（最小划分实例数，划分阈值，最大树深度）
2. 对完全生长的树进行剪枝（评估子树，如去掉性能更好，则进行剪枝）

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系数最大的呢一组，这种感觉就是选最不纯的一组，用你的下限去和别的属性竞争，以达到全局的最优