7. 决策树

1. 决策树
   1. 基于树结构来进行预测
   2. 决策过程中提出的每个判定问题都是对某个属性的“测试”
   3. 决策过程的最终结论对应了我们所希望的判定结果
   4. 每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内
   5. 从根结点到每个叶结点的路径对应了一个判定测试序列
   6. 决策树学习的目的:为了产生一棵泛化能力强，即处理未见示例能力强的决策树
2. 基本算法
   1. 当前结点包含的样本全部属于同一类别
   2. 当前属性集为空，或所有样本在所有属性上取值相同
   3. 当前结点包含的样本集合为空
3. 划分选择
   1. 决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高
   2. 集合属于同一类别的纯度；属性划分集合属于同一类别的纯度
   3. 经典的属性划分方法：
      1. 信息增益
         1. 
         2. 
         3. 存在的问题
            1. 若把“编号”也作为一个候选划分属性，则其信息增益一般远大于其他属性。显然，这样的决策树不具有泛化能力，无法对新样本进行有效预测
            2. 信息增益对可取值数目较多的属性有所偏好
      2. 增益率
         1. 
      3. 基尼指数
         1. 
4. 剪枝处理
   1. 为什么剪枝
      1. “剪枝”是决策树学习算法对付“过拟合”的主要手段
      2. 可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合
   2. 剪枝的基本策略
      1. 预剪枝
      2. 后剪枝
   3. 判断决策树泛化性能是否提升的方法
      1. 留出法：预留一部分数据用作“验证集”以进行性能评估
   4. 预剪枝
      1. 决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别；
      2. 针对上述数据集，基于信息增益准则，选取属性“脐部”划分训练集。分别计算划分前（即直接将该结点作为叶结点）及划分后的验证集精度，判断是否需要划分。若划分后能提高验证集精度，则划分，对划分后的属性，执行同样判断；否则，不划分。
      3. 预剪枝的优缺点
         1. 优点
            1. 降低过拟合风险
            2. 显著减少训练时间和测试时间开销
         2. 缺点
            1. 欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险
   5. 后剪枝
      1. 先从训练集生成一棵完整的决策树，然后自底向上的对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
      2. 后剪枝的优缺点
         1. 优点
            1. 后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树
         2. 缺点
            1. 训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察
5. 连续与缺失值一连续值处理
   1. 
   2. 
   3. 与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
   4. 不完整样本，即样本的属性值缺失
      1. 仅使用无缺失的样本进行学习?
      2. 对数据信息极大的浪费
   5. 缺失值处理
      1. 
      2. 
      3. 根据无缺失样本所占比例来打折
         
      4. 
6. 多变量决策树
   1. 单变量决策树分类边界:轴平行
   2. 多变量决策树
      
   3. 随机森林
      1. 建立多个决策树，通过多棵树的投票来进行决策；
      2. 采用自助法（自举重）采样，得到多个样本集为每个样本集构造一个决策树，得到多棵决策树；
      3. 对多棵决策树的输出进行投票，以得票最多的类作为随机森林的决策，
      4. 被认为是一种集成学习方法。
7. homemessage 1. 属性划分选择 2. 剪枝处理（预剪枝，后剪枝） 3. 属性连续值和缺失值的处理 4. 单变量决策树到多变量决策树