决策树算法
决策树算法的发展历程：ID3（1970s） -> C4.5 -> CART
纯度：样本集合的不确定度。通常可以用信息熵 or 信息增益来表示。
ID3算法
使用信息增益来划分最优属性。
信息增益（信息不确定性减少的程度最大）： 信息熵-条件熵。
但这样做的局限性在于，如果存在一个唯一的属性，那么选择它作为最优划分属性时，信息增益最大，然而这样构建的树完全不具有泛化性。由此引入信息增益率。
C4.5算法
信息增益率：信息增益 / IV(a)
IV(a)：属性a的固有值，其中V=a属性可以被划分的类别数量
可以看出，V越大，IV(a)越大，信息增益率越小，从而避免偏好类别较多的属性。但单纯使用的局限性在于，会偏向选择类别最少的属性。
综合来看，经过两个步骤的选择是比较靠谱的：
step1.先选出信息增益高于平均水平的属性，step2.再在这些属性中选择信息增益率最高的属性。
CART算法
CART是一棵二叉树，可以是分类树（判断是否结婚），也可以是回归树（预测年龄）。
节点属性分裂的依据：分类树 -> 最小GINI值； 回归树 -> 最小方差。
GINI值：GINI值越小，纯度越高。
回归方差：方差越小，纯度越高。
CART剪枝（CCP代价复杂度剪枝法）
步骤1：计算所有非叶子节点{T1,T2,…Tn}的表面误差率增益值；
步骤2：对表面误差率增益值最小的非叶子节点剪枝（如果多个节点计算结果相同，选择子节点最多的那个）
参考 决策树算法 From 飞末 https://www.cnblogs.com/feiyumo/p/9284490.html