常见决策树的启发函数比较

1 ID3 算法

存在的缺点
​ (1) ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.

​ (2) ID3算法只能对描述属性为离散型属性的数据集构造决策树。

2 C4.5算法

• 做出的改进(为什么使用C4.5要好)
  ​ (1) 用信息增益率来选择属性
  ​ (2) 可以处理连续数值型属性
  ​ (3)采用了一种后剪枝方法
  ​ (4)对于缺失值的处理

• C4.5算法的优缺点
  ​ - 优点：产生的分类规则易于理解，准确率较高。

• 缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
  ​ 此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

3 CART算法

CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。C4.5不一定是二叉树，但CART一定是二叉树。

4 多变量决策树(multi-variate decision tree)

• 定义：无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。
• 这个算法的代表是OC1
• 如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

5 决策树变量的两种类型

1、数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。

2、名称型（Nominal）：类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使用“=”来分割。

6 如何评估分割点的好坏？

• 如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。

• 比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。

• 构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。