决策树要点总结

1、决策树的学习：特征选择、决策树的生成、决策树的剪枝

2、Greedy decision tree learning（生成）：

 step1: start with an empty tree

 step2: split on a feature

                  —— 选择哪个特征来分裂？

                  —— 信息增益 / 信息增益比

                  —— 注意使用信息增益会倾向于选择取值较多的特征来分裂，因此引入信息增益比进行校正

for each split of the tree:

          step3: if nothing more to, make predictions

                      —— 停止条件是什么？

                     —— 节点中的样本lablel都相同，特征都已经分裂完没得再选了

          step4: otherwise, go to step2 and continue on this split

3、如何处理连续型的特征？

将该特征的值进行排序，选取相邻两点间的均值作为候选分裂值，根据分裂后分类误差最小化选择最好的分裂值。

4、决策树的过拟合：当树的深度越来越大时，决策边界越来越复杂，训练误差越来越小，但是验证集的误差不降反升，模型泛化能力差。如何防止过拟合？

（1）early stopping：限制树的最大深度、设置分裂收益的门限值、设置节点应包含的最少data points

（2）剪枝：从底部向上，对每一个分裂节点，如果剪枝后的total cost更小，就进行剪枝。

            ——如何衡量树的复杂度？叶节点的个数L(T)

            ——Balance fit and complexity: total cost  C(T）=  Error(T)  +  lambda * L(T)

5、如何处理缺失值？

（1）skip data points with missing values / skip features with missing values

（2）fill in each missing value with a calculated guess(比如众数、平均值、中位数填充）

（3）adapt learning algorithm to be robust to missing values

6、决策树学习常用算法：ID3、C4.5、CART

ID3：树的生成算法，在决策树的各个节点上应用信息增益准则选择特征，递归地构建决策树，容易产生过拟合。

C4.5：在ID3的基础上进行了改进：

用信息增益比选择特征

增加了对连续值的处理

自动处理特征值缺失问题（丢弃有缺失值的样本）

采用后剪枝处理过拟合

CART：分类回归树，二叉树，包括生成和剪枝。

CART生成：递归地构建决策二叉树，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择。

CART剪枝：首先在生成算法产生的决策树低端开始不断剪枝，直到根节点，形成一个子树序列；然后通过交叉验证选出最优子树（平方误差/Gini指数最小）

7、决策树的优缺点

优点：易于解释；分类速度快

缺点：不支持在线学习，当新样本到来后，决策树需全部重建；容易过拟合