1. 简介
决策树是一种树形结构，树中每个内部节点表示一个特征上的判断，每个分支代表一个判断结果的输出，每个叶子节点代表一种分类结果
1.1 决策树的创建过程
- 特征选择：选取有较强分类能力的特征。
- 决策树生成：根据选择的特征生成决策树
- 决策树也易过拟合，采用剪枝的方法缓解过拟合
2. ID3决策树
2.1 信息熵
"信息熵" (information entropy) 是度量样本集合纯度最常用的一种指标。假定当前样本集合中第类(按标签分类)样本所占的比例为 ，则的信息熵定义为
的值越小，则的纯度越高。
2.2 信息增益
假定离散属性有个可能的取值，若使用来对样本集进行划分，则会产生个分支结点，其中第个分支结点包含了中所有在属性上取值为的样本，记为。我们可先计算出的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重，即样本数越多的分支结点的影响越大，于是可计算出用属性对样本集进行划分所获得的"信息增益" (information gain)
一般而言，信息增益越大，则意味着使用属性来进行划分所获得的"纯度提升"越大。因此，我们可用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益来进行决策树划分属性选择。
2.3 ID3决策树构建
- 计算每个特征的信息增益
- 使用信息增益最大的特征将数据集拆分为子集
- 使用该特征（信息增益最大的特征）作为决策树的一个节点
- 使用剩余特征对子集重复上述过程
2.3.1 案例
3. C4.5 决策树
3.1 ID3决策树缺陷
ID3决策树存在一定的不足：它偏向于选择种类多的特征作为分裂依据。例：看下面数据集，特征a有2个取值，特征b有6个取值
特征b | 特征a | 目标值 |
1 | α | A |
2 | α | A |
3 | β | B |
4 | α | A |
5 | β | B |
6 | α | B |
显然，特征b的信息增益比特征a的信息增益高。特征b作为分裂特征，会构造一棵深度为2的决策树，该树的预测准确率可能非常高，但整棵树过于依赖少数的特征（只根据少数特征进行学习），导致过拟合。
3.2 信息增益率
信息增益率：信息增益 / 特征熵
其中， 为属性的”固有值“(intrinsic value)
- 特征的信息增益 ➗ 特征的内在信息
- 相当于对信息增益进行修正，增加一个惩罚系数
- 特征取值个数较多时，惩罚系数较小；特征取值个数较少时，惩罚系数较大。
- 惩罚系数：数据集D以特征a作为随机变量的熵的倒数
3.2.1 案例：求特征a、b的信息增益率
特征b | 特征a | 目标值 |
1 | α | A |
2 | α | A |
3 | β | B |
4 | α | A |
5 | β | B |
6 | α | B |
- 特征a的信息增益率：
- 信息增益：
- IV信息熵：
- 信息增益率：信息增益 / 信息熵= 0.46/0.92=0.5
- 特征b的信息增益率：
- 信息增益：
- IV信息熵：
- 信息增益率：信息增益 / 信息熵=1/2.58=0.39
- 结论：特征a的信息增益率大于特征b的信息增益率，根据信息增益率，应该选择特征a作为分裂特征
4. CART 决策树
Cart模型是一种决策树模型，它即可以用于分类，也可以用于回归。
- Cart回归树使用平方误差最小化策略，
- Cart分类生成树采用的基尼指数最小化策略
4.1 基尼值和基尼指数
4.1.1 基尼值
基尼值：从数据集中随机抽取两个样本，其类别标记不一致的概率。故值越小，数据集的纯度越高。
4.1.2 基尼指数
属性的基尼指数：
于是，我们在候选属性集合中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
4.1.3 案例：计算各特征的基尼指数，选择最优分裂点
第一轮：计算各特征值的基尼指数
- 计算是否有房的基尼指数：
- 有房的基尼值：
- 无房的基尼值：
- 有无房的基尼指数：
- 婚姻状况
- 计算{married} 和 {single,divorced} 情况下的基尼指数：
- 结婚的基尼值：
- 不结婚的基尼值：
- 基尼系数：
- 计算 {single} | {married,divorced} 情况下基尼指数
- 计算 {divorced} | {single,married} 情况下基尼指数
- 最终，该特征的基尼值为 0.3，并且预选分裂点为：{married} 和 {single,divorced}
- 年收入
- 先将数值型属性升序排列，以相邻中间值作为待确定分裂点：
- 以年收入 65 将样本分为两部分，计算基尼指数
- 节点为65时：{年收入}=
- 以此类推计算所有分割点的基尼指数，最小的基尼指数为 0.3
特征点 | 基尼系数 |
是否有房 | 0.343 |
婚姻状况 | 0.3 |
年收入 | 0.3 |
注：当婚姻状况和年收入为分裂特征计算的基尼系数都一样选，则随机选择某一特征。
第二轮：
- 样本 2、4、6、9 样本的类别都是 no，已经达到最大纯度 所以，该节点不需要再继续分裂。
- 样本 1、3、5、7、8、10 样本中仍然包含 4 个 no，2 个 yes 该节点并未达到要求的纯度，需要继续划分。
- 右子树的数据集变为： 1、3、5、7、8、10，在该数据集中计算 不同特征的基尼指数，选择基尼指数最小的特征继续分裂。
重复上述过程直到构建完整的决策树
5. CART决策树案例：
数据：
5.1 案例背景
- 1912年4月15日，在她的处女航中，泰坦尼克号在与冰山相撞后沉没，在2224名乘客和机组人员中造成1502人死亡。
- 造成海难失事的原因之一是乘客和机组人员没有足够的救生艇。尽管幸存生存有一些运气因素，但有些人比其他人更容易生存，例如妇女，儿童和上流社会。
- 有了遇难和幸运数据，运用机器学习工具来预测哪些乘客可幸免于悲剧。
5.2 数据情况
- 数据集中的特征包括票的类别，是否存活，乘坐班次，年龄，登陆，home.dest，房间，船和性别等
- 乘坐班是指乘客班（1，2，3），是社会经济阶层的代表
- age数据存在缺失
5.3 简版算法实现
5.4 特征工程
- 特征编码
- one-hot
- 男 1,0
- 女 0, 1
- 顺序编码 0,1,2,3,4
- 特征离散
- 连续 —> 类别
- 年龄 —> 少年, 青年, 中青年, 中老年, 老年3
- 票价→ 0,1,2,3,4,5
- 离散好处
- 可以避免异常值的影响
- 增强模型的稳定性
- 方便做特征交叉
- 缺失值填充
- 年龄 使用标准正态分布进行随机填充