-
分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个if-then规则的集合，也可以是看作定义在特征空间划分上的类的条件概率分布。
-
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设
$X$ 是一个取有限个值的离散随机变量，其概率分布为$$P(X=x_i) = p_i, i = 1,2,\dots,n$$ 则随机变量$X$ 的熵定义为$$H(X) = - \sum_{i=1}^n p_i \log p_i$$ 熵越大，随机变量的不确定性就越大。 -
设有随机变量
$(X,Y)$ ，其联合概率分布为$$P(X=x_i,Y=y_i)=p_{ij},i=1,2,\dots,n;j=1,2,\dots,m$$ 条件熵$H(Y|X)$ 表示在已知随机变量$X$ 的条件下随机变量$Y$ 的不确定性。随机变量$X$ 给定的条件下随机变量$Y$ 的条件熵（conditional entropy）$H(Y|X)$ ，定义为$X$ 给定条件下$Y$ 的条件概率分布的熵对$X$ 的数学期望$$H(Y|X)=\sum_{i=1}^n p_i H(Y|X=x_i)$$ 这里，$p_i = P(X=x_i),i=1,2,\dots,n$ -
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。
-
特征
$A$ 对训练数据集$D$ 的信息增益（information gain）表示得知特征$X$ 的信息而使类$Y$ 的信息的不确定性减少的程度。（偏向于选择取值较多的特征）$$g(D,A) = H(D) - H(D|A)$$ -
特征
$A$ 对训练数据集$D$ 的信息增益比（information gain ratio）定义为其信息增益$g(D,A)$ 与训练数据集$D$ 关于特征$A$ 的值的熵$H_A(D)$ 之比（对可取值数目较少的属性有所偏好），即 $$ g_R(D,A) = \frac{g(D,A)}{H_A(D)}$$ -
基尼值反映了从数据集
$D$ 中随机抽取两个样本，其类别标记不一致的概率$$Gini(D) = 1 - \sum_{k=1}^\mathcal{Y}p_k^2$$ 特征$A$ 对训练数据集$D$ 的基尼指数（Gini index）定义为$$Gini_index(D,A) = \sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert}Gini(D^v)$$ -
决策树剪枝的基本策略有预剪枝（prepruning）和后剪枝（postpruning）。 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。 后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该叶结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
-
预剪枝与后剪枝对比 预剪枝基于贪心本质使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销，但带来了欠拟合的风险。 后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但训练时间开销较大。
-
统计学习方法中决策树的损失函数：设树
$T$ 的叶结点个数为$|T|$ ，$t$ 是树$T$ 的叶结点，该叶结点有$N_t$ 个样本点，$H_t(T)$ 为叶结点$t$ 上的经验熵，$\alpha \ge 0$ 为参数，则决策树学习的损失函数可定义为$$C_\alpha (T) = \sum_{t=1}^{|T|}N_tH_t(T) + \alpha |T|$$ -
CART剪枝算法由两步组成：首先从生成算法产生的决策树
$T_0$ 底端开始不断剪枝，直到$T_0$ 的根结点，形成一个子树序列${ T_0, T_1, \dots, T_n}$ ；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。 -
连续值处理，二分法，从小到大排序后依次取中位点划分。 缺失值处理，样本赋权，权重划分，让同一个样本以不同的概率划入到不同的子结点中去。
-
多变量决策树