[数据结构与算法]task3：西瓜书第四章（1）

? ? ? ?本次是阅读西瓜书第四章，以下为笔者是在阅读第四章决策树时一些之前不曾关注地方的补充。

? ? ? 1.实际决策树学习算法是基于启发式算法，如贪婪算法，寻求在每个节点上的局部最优决策。这样的算法思想决定了在执行过程中不能保证返回全局最优决策树。例如ID3算法实际是基于信息论中信息熵的概念，追求最大信息熵的过程。因此在判断决策树算法的好坏时，不同的决策树只是改变了决策指标的衡量标准，与其说ID3决策树的缺点不如说是考虑贪婪算法会带来的缺点。

? ? ? 2.信息增益反映的给定一个条件以后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是条件熵越小，信息增益越大。信息增益比率精髓在于采用信息增益比率通过引入分裂信息(Split information)的项来惩罚取值较多的Feature，在候选属性中选择基尼系数最小的属性作为最优划分属性，这样带来两个好处：其一是有效防止了较多取值的属性来进行划分带来的问题。其二是能有效处理连续型数据。

? ? ? 3.应用范围的比较：

? ? ? C4.5能处理连续性数据，将连续性数据转化为离散型数据。
? ? ? ID3，C4.5只能处理分类问题，而CART还能处理回归问题（ID3，C4.5再迭代创建树节点时，每个特征只能出现一次，但CART可以出现多次）。