决策树
基本流程
通过对一系列属性的值进行判断，预测数据分类的方式
根节点（属性测试）-内部节点（属性测试）-叶节点（分类结果）
根节点包括所有的样本集，之后没经过一个节点，进行一次划分
终止判断条件
- 节点样本全部属于同一个类别，无需划分
- 属性集为空或样本在所有属性上数值均相同 =》叶节点，分类为具有最多样本的类别
- 当前节点样本集为空 =》叶节点，分类为父节点上具有最多样本的类别
如何选择属性测试序列
1、信息增益
含义：通过第K类样本数量在所有样本中所占的比例，度量样本集合的纯度
公式：
西瓜书 信息增益.png
缺点：index类的属性很容易获得最高权重，但并不利于泛化
2、增益率
含义：在信息增益的基础上引入固有值，纠正对取值较多的属性值的偏好
公式：
西瓜书 增益率.png
缺点：与信息增益相反，对取值较少的属性有所偏好，因此通常与信息增益共同使用
3、基尼指数
含义：从数据集中随机抽取两个样本，其类别不一致的概率
公式：
西瓜书 基尼值.png
基尼指数.png
泛化策略
方法：基于验证集进行性能评估，去掉部分降低性能的分支从而降低过拟合
1、预剪枝
在生成过程中，对节点划分前后的泛化性能进行估计，提升的保留，不提升或降低的停止
优点：减少了时间开销
缺点：可能导致欠拟合
2、后剪枝
在训练出一颗完整的决策树后，自底向上进行评估，当内部节点转化为叶节点有利于性能提升时，进行替换
优点：欠拟合风险小
缺点：时间开销大
连续值和缺失值
1、如何对连续属性使用：
连续属性离散化：将连续值排序，划分为二或多个数值范围，后续步骤和离散分类一致
2、如何处理缺失值：
缺失值：样本不完整或部分缺失
数据缺失条件下计算信息增益：
西瓜书 信息增益计算式变型.png
划分属性时对缺失样本的划分：
- 取值已知：正常划分，正常权重
- 取值未知：同时划分进所有子节点，并调整权重
多变量决策树
问题：决策树对应的分类边界通常为互相平行或垂直的，分类任务复杂时，很难获得较好的近似，时间开销大
解决方案：用属性组合替代属性进行测试，即对属性的线性组合测试，建立一个线性分类器
西瓜书 多变量决策树示例.png
