机器学习第八课(决策树)

Entropy

做决策树就是建立一个entropy不断下降的树(但是如果entropy下降的太厉害会有可能过拟合)

ID3  Information gain(选择entropy下降最快的)

C4.5  Gain ratio

CART Gini index(Gini系数可以看做为熵的一阶近似)

ID3算法：
以信息增益为准则选择信息增益最大的属性。
缺点：1）信息增益对可取值数目较多的属性有所偏好，比如通过ID号可将每个样本分成一类，但是没有意义。2）ID3只能对离散属性的数据集构造决策树。
鉴于以上缺点，后来出现了C4.5算法。

C4.5算法：
以信息增益率为准则选择属性；在信息增益的基础上对属性有一个惩罚，抑制可取值较多的属性，增强泛化性能。
其他优点：1）在树的构造过程中可以进行剪枝，缓解过拟合；2）能够对连续属性进行离散化处理（二分法）；3）能够对缺失值进行处理；
缺点：构造树的过程需要对数据集进行多次顺序扫描和排序，导致算法低效；
刚才我们提到 信息增益对可取值数目较多的属性有所偏好；而信息增益率对可取值数目较少的属性有所偏好！OK，两者结合一下就好了！
解决方法：先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。而不是大家常说的 直接选择信息增益率最高的属性！


CART算法（Classification and Regression Tree）：
顾名思义，可以进行分类和回归，可以处理离散属性，也可以处理连续的。
分类树使用GINI指数来选择划分属性：在所有候选属性中，选择划分后GINI指数最小的属性作为优先划分属性。回归树就用最小平方差。