Decision Tree
决策树是最简单的也是最具解释性和表达性的一种机器学习算法，既可以处理分类问题（ID3，C4.5，C50），也可以处理回归问题（CART）。决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。
理解角度：
- 一棵树
- if-then规则的集合，该集合是决策树上的所有从根节点到叶节点的路径的集合
- 定义在特征空间与类空间上的条件概率分布，决策树实际上是将特征空间划分成了互不相交的单元，每个从根到叶的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中，哪个类别有较高的条件概率，就把该单元中的实例强行划分为该类别。
它是根据特征（feature）的值逐步把数据分类，直到所有的叶子节点属于同一个类型结束。注意决策树都是贪婪的。
ID3算法：以信息增益为准则来选择最优划分属性。ID3决策树偏向于取值较多的属性进行分割，存在一定的偏好；不能直接处理连续属性，只有通过离散化将连续性数据转化成离散型数据再进行处理。
C45算法：以信息增益比为准则来选择最优划分属性。C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的；可以处理连续性属性。
CART算法：以基尼指数（分类）为准则来选择最优划分属性。可以应用于分类和回归。（只有两个分支的二叉树）
CART算法
两个重要的问题：
- 如何评价最优二分结果。分类问题，可以选择GINI；回归问题，可以使用最小二乘偏差（LSD）或最小绝对偏差（LAD）。
- 什么时候停止和如何确定叶子节点的值。
CART算法的步骤：
- 回归树的生成/分类树的生成
- 剪枝CCP算法(Cost-Complexity Pruning)
与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
停止分裂的条件
节点样本属于同一类或者值一样；结点样本个数小于预定阈值；样本集的信息增益/信息增益比小于预定阈值或基尼指数小于预定阈值（此时样本基本属于同一类）；或者没有更多特征。