一、如何建立决策树
1、Hunt算法
Hunt算法是许多决策树算法的基础，包括ID3、C4.5、CART。
Hunt算法步骤：
（1）如果Dt中所有数据都属于同一个类yt，则t是叶结点，用yt标记。
（2）如果Dt中包含属于多个类的数据，则选择一个属性，将数据划分为较小子集。创建子女结点，将数据按属性放入子女结点中，然后递归调用该算法。
但是该算法对于大多数情况太苛刻了，需要附加：
（1）没有可以选择的属性，则该结点为叶结点，类标号为父结点上较多数的类。
（2）如果与Dt相关的数据均为同一个属性，则不可以继续划分，类标号为多数类。
2、属性划分
（1）标称变量
标称变量，二元划分和多路划分。CART只产生二元划分，考虑k个属性的二元划分有$2^{k-1}-1$种方法。
（2）有序变量
有序变量，也可以是二元划分和多路划分，但是不能违背有序性。
3、属性划分标准
选择最佳划分的度量是根据划分后子女结点的不纯度度量。不纯度越低（纯度越高！），划分效果越好。
（1）不纯度度量：
$$Entropy(t)=-\sum_{i=0}^{c-1}p(i|t)log_{2}p(i|t),Entropy(t)\in[0,1]$$
$$Gini(t)=1-\sum_{i=0}^{c-1}[p(i|t)]^{2},Gini(t)\in[0,0.5]$$
$$ClassificationError(t)=1-max_{i}[p(i|t)],ClassificationError(t)\in[0,0.5]$$
三个度量方法都是希望取值越小越好（越纯）。
（2）结点度量：
为了确定测试结点效果，我们比较父节点（划分前）、子女结点（划分后）的不纯度变化。
信息增益：
$$\Delta = I(parent)-\sum_{j=1}^{k}\frac{N(v_{j})}{N}I(v_{j})$$
其中 $I$ 为不纯度的度量，关于 $N$ 的计算是划分后的个数加权。
$I$ 为熵（Entropy）的时候，$\Delta$ 为信息增益。
信息增益率（Gain Ratio）：
$$GainRatio=\frac{\Delta_{info}}{SplitInfo}=\frac{\Delta_{info}}{-\sum_{i=0}^{c-1}p(i)log_{2}p(i)}$$
使用信息增益率，好处是把属性测试条件产生的输出数也考虑进去。说明如果某个属性产生了大量的划分，它的划分信息会很大，从而降低了增益率。
注：信息增益、信息增益率，我们希望越大越好，表示变化。
（3）连续变量的划分：
先对数据进行排序后，按照离散点的取值计算。
Gini和熵趋向于有大量不同值的属性。
4、决策树算法
（1）决策树归纳算法：
|
|
（2）决策树特点：
1、是一种非参数方法，不要求任何的先验假设。
2、找到最佳的决策树是NP完全问题。
3、相对容易解释。
4、对于噪声有相当好的鲁棒性。
5、冗余属性不会对决策树准确率造成影响。即为强相关性，一个用于划分，另一个则将被忽略。相反，不相关的属性，可能在构建树的过程中被偶然选中，导致决策树过于庞大。
6、数据碎片问题。当深度越深的时候，数据可能会太少，从而不能做出有统计意义的判断，当样本量小于某个阈值的时候，应该停止分裂。
7、子树可能在决策树中重复多次，显得复杂，难以解释。
（3）斜决策树（oblique decision tree）：
这里涉及到的决策树都是每次选取一个变量分子集划分，对某些数据集（连续属性有着复杂建模）缺乏划分能力。
斜决策树可以克服这个问题。
测试条件为：
$$ x+y<1$$
另一种方法是，构造归纳法（constructive induction），该方法创建复合属性，代表已有的属性的算术、逻辑组合。
构造归纳的花费较低，而斜决策树要动态的确定属性组合，但构造归纳会产生冗余属性。
5、模型过拟合
分类模型误差分为：训练误差（training error）、泛化误差（generalization error）。
一个好的模型需要有较低的泛化误差和训练误差。
奥卡姆剃刀（Occam’s razor）：
给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。
悲观误差估计（pessimistic error estimate）：
$$e_{g}(T)=\frac{\sum_{i=1}^{k}[e(t_{i})+\Omega (t_{i})]}{\sum_{i=1}^{k}n(t_{i})}=\frac{e(T)+\Omega(T)}{N_{t}}$$
$k$是决策树的叶节点数目，$e(T)$为总训练误差，$N_{t}$为总训练样本数，$\Omega$为罚项。
对二叉树来说，0.5的罚项意味着只要至少能够改善一个训练记录分类，结点就应当扩展，当1位罚项，意味着除非能够减少一个以上训练记录的误分类，否则结点不应当扩展。
先剪枝：
当达到某个条件，提前终止。例如：当观察到某个不纯度度量低于某个确定阈值时就停止扩展叶结点，但是，难点在于很难确定正确终止的阈值。
后剪枝：
初始按照最大规模生长，按照自底向上修剪决策树。修剪方式：
（1）子树替换（subtree replacement）用叶结点替代子树，叶结点的类标号为子树的多数类；
（2）子树提升（subtree raising）子树中最常使用的分支替代子树。后剪枝能产生更好的结果。
6、评估分类器性能
自助法（bootstrap）：
训练集是对于原数据集的有放回抽样，如果原始数据集$N$，可以证明，大小为$N$的自助样本大约包含原数据63.2%的记录。当$N$充分大的时候，$1-(1-\frac{1}{N})^{N}$ 概率逼近 $1-e^{-1}=0.632$。抽样 $b$ 次，产生 $b$ 个bootstrap样本，则，总准确率为（$acc_{s}$为包含所有样本计算的准确率）：
$$ acc_{boot}=\frac{1}{b}\sum_{i=1}^{b}(0.632\times\varepsilon _{i}+0.368\times acc_{s})$$
准确度的区间估计：
将分类问题看做二项分布，则有：
令 $X $为模型正确分类，$p$ 为准确率，$X $服从均值 $Np$、方差 $Np(1-p)$的二项分布。$acc=\frac{X}{N}$为均值 $p$，方差 $\frac{p(1-p)}{N}$ 的二项分布。$acc$ 的置信区间：
$$ P\left(-Z_{\frac{\alpha }{2}} \leq \frac{acc-p}{\sqrt{p(1-p)/N}} \leq Z_{1-\frac{\alpha}{2}}\right)=1-\alpha$$
$$ P\in\frac{2\times N \times acc +Z_{\frac{\alpha}{2}}^{2}\pm Z_{\frac{\alpha}{2}}\sqrt{Z_{\frac{\alpha}{2}}^{2}+4\times N \times acc-4\times N \times acc^{2}}}{2(N+Z_{\frac{\alpha}{2}}^{2})}$$
