# 决策树

## 第四章 决策树

* Page73: 决策树(363)（decision tree）

  以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新示例进行分类，这儿把样本分类的任务，可以看做为当前样本是否属于正类这个问题的决策或判定过程，决策树是基于树结构进行决策的，决策时通常会进行一系列判断或子决策，决策的过程形成一个树结构。
* Page73: 判定树

  同决策树
* Page74: 分而治之（divide-and-conquer）

  分解问题分别进行处理的策略。
* Page75: ID3决策树（Iterative Dichotomiser decision tree）

  以信息增益为准则来划分属性的迭代二分器决策树。
* Page75: 划分选择

  决策树学习算法最重要的地方就是选择最优划分属性。
* Page75: 信息增益（information gain）

  属性划分减少的信息熵，信息熵是度量样本集合纯度的一种指标，假设第k类样本所占比例为pk，则数据集D的信息熵为：$$Ent(D)=-\sum pklogpk$$，$$Ent(D)$$越小，D的纯度越高。

  $$Gain(D,a)=Ent(D)-\sum \frac{Dv}{D\*Ent(Dv)}$$，Dv是某个属性a的某个可能取值的样本集合
* Page77: 增益率（gain ratio）

  信息增益准则对可取值数目较多的属性有偏好，为减少这种偏好的不利影响，使用增益率选择最优划分属性，增益率定义为:$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$, $$IV(a)=-\sum \frac{Dv}{D\*log(Dv/D)}$$，IV(a)称为为a的固有值。属性可能取值数目越多，IV(a)的值越大，增益率即增益/固有值
* Page78: C4.5决策树(page83)

  基于增益率和二分法，可处理连续值的决策树
* Page79: CART决策树(Classfication and Regression Tree)

  使用基尼指数划分属性的决策树。
* Page79: 后剪枝（postpruning）

  先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若将该结点子树替换成叶节点能提升泛化性能，则进行替换，后剪枝训练时间开销大。
* Page79: 基尼指数（Gini index）

  $$Gini(D) = \sum\sum p(x=k)\*p(x \neq k)$$,反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。
* Page79: 剪枝(352)（pruning） 决策树学习算法对付过拟合的主要手段，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，因训练样本过度学习导致将训练集自身的特点当做所有数据都具有的一般性质而导致过拟合，因此可通过主动去掉一些分支来降低过拟合的风险。
* Page79: 预剪枝(352)（prepruning）

  在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶节点，预剪枝基于贪心存在欠拟合的风险。
* Page82: 决策树桩(decison stump)

  仅有一层划分的决策树。
* Page83: 离散化

  连续属性转为离散值，可用二分法。
* Page85: 缺失值

  样本在某些属性上的取值未知。
* Page88: 多变量决策树(92)（multivariate decision tree）

  每个结点结合多个变量学习一个线性分类器，比如-0.8\*密度-0.044\*含糖率<=-0.313，这样的多个结点构成的决策树。
* Page90: 斜决策树（oblique descision tree）

  同多变量决策树
* Page92: 增量学习(109)（incremental learning）

  在接收到新样本后对已学得的模型进行调整，不用完全重新学习，主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构。