决策树有哪些常用的启发函数?
决策树有哪些常用的启发函数?
1、ID3—— 最大信息增益
2、C4.5——最大信息增益比
3、CART——最大基尼指数(Gini)
ID3—— 最大信息增益
对于样本集合D，类别数为K，数据集D的经验熵表示为
其中Ck是样本集合D中属于第k类的样本子集，|Ck|表示该子集的元素个数，|D|表示
样本集合的元素个数。 然后计算某个特征A对于数据集D的经验条件熵H(D|A)为
其中，Di表示D中特征A取第i个值的样本子集，Dik表示Di中属于第k类的样本子集。
于是信息增益g(D,A)可以表示为二者之差，可得
选择g(D，A）最大的那个，进行分叉。
C4.5——最大信息增益比
有时候我们会发现，当特征为ID或者有某一个特征有很多值的时候，ID3就不起作用，举个栗子🌰，当特征值为ID的时候，每个样本是一类，那么所求出来的最大信息增益，肯定是最大的。由此可见，其他特征有很多值的情况。因此引入最大信息增益比来减少某个特征类别过多带来的影响。
特征A对于数据集D的信息增益比定义为
其中，
称为数据集D关于A的取值熵。
CART——最大基尼指数(Gini)
Gini描述的是数据的纯度，与信息熵含义类似。
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。 但与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据 按特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义为
三者之间的差异。
1、ID3是采用信息增益作为评价标准， 会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少 的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越 大。这在实际应用中是一个缺陷。比如，我们引入特征“DNA”，每个人的DNA都 不同，如果ID3按照“DNA”特征进行划分一定是最优的(条件熵为0)，但这种分 类的泛化能力是非常弱的。因此，C4.5实际上是对ID3进行优化，通过引入信息增 益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提 升决策树的泛化能力。
2、从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以 处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的 分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转 换多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行 二值划分，因此可以很好地适用于连续性变量。
3、应用角度，ID3和C4.5只能用于分类任务，而CART(Classification and Regression Tree，分类回归树)从名字就可以看出其不仅可以用于分类，也可以应 用于回归任务(回归树使用最小平方误差准则)。
4、从实现细节、优化过程等角度，这三种决策树还有一些不同。
比如，（1） ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处 理;
（2）ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复 用，而CART每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特 征可以被重复使用;
（3）ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART 直接利用全部数据发现所有可能的树结构进行对比。
