决策树——三种基本算法
前言
决策树算法学习
一、ID3
ID3算法使用信息增益来划分节点，信息增益越大说明使用该属性划分获得的纯度越高。 ID3的不足：信息增益准则对取值较多的属性所有偏好！ 例如：使用身份证号对全国人民进行分类，显然这个属性的取值的个数为全国人口总数，每一个人就是一个类别，信息熵为0，信息增益最大。更加直观一点就是，信息增益的本质是通过选择当前属性，使得当前节点的纯度最大(即样本尽可能都属于同一类)。**当样本总数一定的情况下，属性取值越多，那么每个取值下的样本数量越少，纯度越大。**从信息熵的角度出发就是当类别越多，不确定性越大，纯度越低。
案例
二、C4.5
C4.5算法选择信息增益率作为属性划分的条件，信息增益率越大越好。 C4.5算法对可取值数目较少的属性有所偏好，故C4.5算法采用一个启发式的思想，先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高。
三、CART
cart算法采用基尼系数对属性进行划分，基尼系数越小越好。
案例
参考：
四、预剪枝和后剪枝
预剪枝基于贪心，虽然能节省训练时间和防止过拟合，但是有欠拟合的风险。 后剪枝自底向上进行判断，虽然有着良好的泛化性能，但是训练时间过长。
