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、决策树的优缺点
优点：易于解释；分类速度快
缺点：不支持在线学习，当新样本到来后，决策树需全部重建；容易过拟合
