008. 决策树

决策树:
1. 简述决策树原理？
  决策树是一种自上而下，对样本数据进行树形分类的过程，由节点和有向边组成。
  节点分为内部节点和叶节点，其中每个内部节点表示一个特征或属性，叶节点表示类别。
  从顶部节点开始，所有样本聚在一起，经过根节点的划分，样本被分到不同的子节点中，再根据子节点的特征进一步划分，直至所有样本都被归到某个类别。

2. 为什么要对决策树进行减枝？如何进行减枝？
  剪枝是决策树解决过拟合问题的方法。
  在决策树学习过程中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，于是可能将训练样本学得太好，
  以至于把训练集自身的一些特点当作所有数据共有的一般特点而导致测试集预测效果不好，出现了过拟合现象。
  因此，可以通过剪枝来去掉一些分支来降低过拟合的风险。
  决策树剪枝的基本策略有“预剪枝”和“后剪枝”。
  预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
  后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，
  若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。 
  预剪枝使得决策树的很多分支都没有"展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。
  但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；
  预剪枝基于"贪心"本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
  后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
  但后剪枝过程是在生成完全决策树之后进行的 并且要自底向上对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。 

3. 简述决策树的生成策略？
  决策树的生成策略主要有ID3、C4.5、CART，算法的适用略有不同，但它们有个总原则，即在选择特征、向下分裂、树生成中，它们都是为了让信息更“纯”。
  举一个简单例子，通过三个特征：是否有喉结、身高、体重，判断人群中的男女，
  是否有喉结把人群分为两部分，一边全是男性、一边全是女性，达到理想结果，纯度最高。 
  通过身高或体重，人群会有男有女。 
  上述三种算法，信息增益、增益率、基尼系数对“纯”的不同解读，如下详细阐述：
  ID3:
  最大信息增益。
  C4.5:
  最大信息增益率。增益率准则对可取特征值较少的属性有所偏好，因此，C.5算法并不是直接选择增益率最大的作为划分属性，
  而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。
  CART:
  最小基尼指数。CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类，
  但是与ID3、C4.5不同的是，CART是一棵二叉树，采用二元切割法，
  每一步将数据按照特征A的取值切成两份，分别进入左右子树。
  综上，ID3采用信息增益作为划分依据，会倾向于取值较多的特征，
  因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着不确定性更高。
  C4.5对ID3进行优化，通过引入信息增益率，对特征取值较多的属性进行惩罚。