# 决策树

  • ID3 是采用信息增益作为评价标准,会倾向于取值较多的特征。因为信息增益反映的是给定条件以后不确定性减少的程度,特征取值越多就越意味着确定性更高,也就是条件熵越小,信息增益越大

  • C4.5 实际上是对 ID3 进行优化,通过引入信息增益比,一定程度上对取值比较多的特征进行惩罚,避免 ID3 出现过拟合的特征,提升决策树的泛化能力

  • 样本类型的角度,ID3 只能处理离散型变量,而 C4.5 和 CART 都可以处理连续型变量

  • C4.5 处理连续型变量时,通过对数据排序之后找到类别不同的分割线作为切分点,根据切分点把连续属性转换为布尔型,从而将连续型变量转换为多个取值区间的离散型变量

  • CART 在其构建时每次都会对特征进行二值划分,因此可以很好地适用于连续变量

  • 应用角度,ID3 和 C4.5 只能用于分类任务,而 CART 不仅可以用于分类,也可以应用于回归任务(回归树使用最小平方误差准则)

  • ID3 对样本特征缺失值比较敏感,而 C4.5 和 CART 可以对缺失值进行不同方式的处理

  • ID3 被 C4.5 可以在每个结点上产生出多叉分支,且每个特征在层级之间不会复用,而 CART 每个结点只会产生两个分支,因此最后会形成一棵二叉树,且每个特征可以被重复使用

  • ID3 和 C4.5 通过剪枝来权衡树的准确性与泛化能力,而 CART 直接利用全部数据发现所有可能的树结构进行对比。

# 剪枝

  • 决策树的剪枝通常有两种方法,预剪枝(Pre-Pruning)后剪枝(Post-Pruning)

  • 预剪枝具有思想直接、算法简单、效率高等特点,适合解决大规模问题。但如何准确地估计何时停止树的生长,针对不同问题会有很大区别,需要一定经验判断。目前预剪枝存在一定局限性,有欠拟合的风险

  • 相比预剪枝,后剪枝方法通常可以得到泛化能力更强的决策树,但时间开销会更大。

  • 常见的后剪枝方法包括错误率降低剪枝(Reduced Error Pruning,REP)、悲观剪枝(Pessimistic Error Pruning,PEP)、代价复杂度剪枝(Cost Complexity Pruning,CCP)、最小误差剪枝(Minimum Error Pruning,MEP)、CVP(Critical Value Pruning)、OPP(Optimal Pruning)等方法

  • 代价复杂度剪枝 CCP 使用交叉验证策略时,不需要测试数据,精确度与 REP 差不多,但形成的树复杂度小。而从算法复杂度角度,由于生成子树序列的时间复杂度与原始决策树的非叶结点个数呈二次关系,导致算法相比 REP、PEP、MEP 等线性复杂度的后剪枝方法,运行时间开销更大

Copyright © 2020 CheeReus_11 | 鄂ICP备2020022304号

鄂公网安备 42011502001280号