决策树

基本流程：

  略

划分选择：

  “信息熵”是度量样本集合纯度最常用的一项指标
  
  “信息增益”是度量某个属性对划分的增益
  
  表示该属性的权重值

剪枝处理：

  剪枝是决策树学习算法对“过拟合”的主要手段，若不采取剪枝有时会造成决策树分支过多，导致过拟合。决策树剪枝的基本策略有“预剪枝”和“后剪枝”。

预剪枝：

  在决策树每个结点划分前进行估计，若划分不能带来决策树的泛化能力的提升，则停止划分并且将当前结点标记为叶结点。
  预剪枝使得部分分支没有“展开”，不仅降低了过拟合的风险还显著减少了决策树的训练时间开销和测试时间。但是预剪枝基于“贪心”的思想，给决策树带来了欠拟合的风险。

后剪枝：

  后剪枝先从生成完整决策树，然后对分支进行计算，若将分支替换为叶结点能提升泛化能力则替换。
  后剪枝一般比预剪枝保留了更多的分支，欠拟合的风险很小，泛化能力优于预剪枝，但是由于要生成完整的决策树且自底向上的对结点逐一考察，开销要大得多。

连续与缺失值：

连续值

  在连续值取件中选择一个划分点，一侧为正例另一侧为反例。

缺失值处理

  将属性A为缺失部分进行信息增益计算，然后乘以属性A未缺失值所占比例，为属性A的信息增益。

多变量决策树：

  显然决策树的每个属性结点在坐标轴中都是垂直于坐标轴的直线，由此在实际情况中较为复杂，因此采用多变量决策树。例如：
    
  这样的属性结点在坐标上为非垂直于坐标轴的直线。