博客

1.约束决策树

约束决策树可以根据情况来选择或组合

• （1）设置每个叶子节点的最小样本数，可以避免某个特征类别只适用于极少数的样本。
• （2）设置每个节点的最小样本数，从根节点开始避免过度拟合。
• （3）设置树的最大深度，避免无限往下划分。
• （4）设置叶子节点的最大数量，避免出现无限多次划分类别。
• （5）设置评估分割数据是的最大特征数量，避免每次都考虑所有特征为求“最佳”，而采取随机选择的方式避免过度拟合。

2.剪枝

对每个节点或子树进行裁剪，适用算法评估裁剪前后决策树模型对数据的预测能力是否降低，若没有降低则说明可以剪枝。

• （1）错误率降低剪枝
  
  使用某种顺序遍历节点，删除以此结点为根的子树。试此节点为叶节点。将训练集中该节点调整出现概率最大的那一类赋予此节点，计算整体误判率或准确率，若比剪枝前好，则剪枝。
• （2）悲观剪枝
  
  评估单个节点（非子树）是否裁剪，使用该节点下的所有叶节点的误差值和评估，当裁剪前后的误差率不超过某个标准值，裁剪。
• （3）代价复杂度剪枝
  
  Cart使用代价复杂度剪枝，代价是指样本错分率，复杂度是指树t的叶节点数，定义是如下：
  
  cc（t）=E/N+α
  
  Leaft
  
  其中N为决策树训练样本数，E为决策树错分样本数，Leaft为t子树的叶子数，参数α用来衡量代价与复杂度关系，表示减值后树的复杂度降低的程度与代价间的关系。对于t子树，剪去其子树s，用t中最优叶节点代替，得到新树new_t。New_t会比t对于训练数据分错M个，但是new_t包含的叶节点数比t少Leaf_s-1个。领替换之后代价复杂度相等：
  
  cc(t)=cc(new_t)=>E/N+αLeaft=(E+M)/N+α
  
  [leaft-(leafs-1)]=>α=M/N(leafs-1)。
  
  M为用叶节点替换t的s子树后，增加的分错样本数，leafs是子树s的叶节点数。

剪枝步骤：

• 1.计算完全决策树T_max的每个非叶节点的α值
• 2.循环减掉具有最小α值的子树，直到剩下根节点
• 3.得到一系列剪枝（嵌套）树（T0，T1，，，Tm），T0为完全决策树Tmax。Ti+1为对Ti进行剪枝得到的结果。
• 4.使用独立的剪枝集（非训练集）对第一步中的Ti进行评估，得到最佳剪枝树。
• 标准错误SE公式： SE（E’）=根号下E’*（N’-E’）/N’

N’为剪枝集的大小，Ei为树Ti对剪枝集的错分数，E’=min{Ei}

最佳剪枝树为Tbest是满足如下条件且包含节点数最少的那颗剪枝树：Ei<=E’+SE(E’)

决策树的优劣

• 优势：简单易懂，可处理数值和类别两种类型的数据，只需要少量的训练集即可使用，使用白盒模型，可清洗观察每个步骤，对大数据量的处理性能较好，更贴近人类思维。
• 劣势：准确性不如其他算法，对连续性字段难预测，特别是时间顺序的数据，需要较多预处理工作，树的稳定性不足，训练集的小变化可能引起整个树的巨变，容易过拟合，决策树处理包含不同数值类别的特征数据时，容易倾向选择取值更多的特征作为分割节点，对字段特立化严重的数据更容易出现过拟合且类别越多错误或增加更加快。