什么是决策树
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有2种类型：内部节点和叶结点。内部节点表示一个特征或属性，叶结点表示一个类别。
决策树是一种分类和回归的基本模型，可从三个角度来理解它，即：
1.一棵树
2.if-then规则的集合，该集合是决策树上的所有从根节点到叶节点的路径的集合
3.定义在特征空间与类空间上的条件概率分布，决策树实际上是将特征空间划分成了互不相交的单元，每个从根到叶的路径对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。实际中，哪个类别有较高的条件概率，就把该单元中的实例强行划分为该类别。
决策树的优点
1.可解释性强，容易向业务部门人员描述
2.分类速度快
如何学习一棵决策树？
决策树的学习本质上就是从训练数据集中归纳出一组分类规则，使它与训练数据矛盾较小的同时具有较强的泛华能力。从另一个角度看，学习也是基于训练数据集估计条件概率模型（至此，回答完了模型部分，下面接着说策略和算法）。
决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化（说完了策略，该说算法了）。
由于这个最小化问题是一个NP完全问题，现实中，我们通常采用启发式算法（这里，面试官可能会问什么是启发式算法，要有准备，SMO算法就是启发式算法）来近似求解这一最优化问题，得到的决策树是次最优的。
该启发式算法可分为三步：
特征选择
模型生成
决策树的剪枝
特征选择
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的，所以这种特征理论上是可以扔掉了。通常特征选择的准则是信息增益或信息增益比。
信息增益
先给出熵和条件熵的定义：在概率统计中，熵表示随机变量的不确定性的度量。
设X是一个取有限个值的离散随机变量，概率分布为
$P(X = xi)=p_i,i=1,2,…,n$
则随机变量X的熵定义为$H(X) = -\sum{i=1}^npilogp_i$
由定义可知，熵只依赖于X的分布，而于X的取值无关，所以也可将X的熵记作$H(p)$
$H(p) = -\sum{i=1}^np_ilogp_i$
熵越大，随机变量的不确定性就越大。对同一个随机变量，当它的概率分布为均匀分布时，不确定性最大，熵也最大。对有相同概率分布的不同的随机变量，取值越多的随机变量熵越大（能取的值越多说明不确定性就越大？）。（这是精华）
条件熵$H(Y|X)$表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的H$H(Y|X)$,定义为X给定条件下Y的条件概率部分的熵对X的数学期望。
$H(Y|X) = \sum_{i=1}^np_iH(Y|X=x_i)$
这里，$p_i = P(X=x_i),i=1,2,…,n.$
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
信息增益的定义
特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D）与特征A给定条件下D的经验条件熵H(D|A)之差，$g(D,A)=H(D)-H(D|A)$
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。
H(D|A)小，证明A对D的分类不确定小，所以说A特征可以对D正确的分类，所以说信息增益越大越好。
设训练数据集为D，|D|表示其样本个数。设一共有K个类别$Ck$ , $|C_K|$表示属于类$C_k$的样本个数。设A有n个不同的取值{$a_1,a_2,…,a_n$},根据特征A的取值将D划分为n个子集{$D_1,D_2,…,D_n$}, |$D_i$|为$D_i$的样本个数 记子集$D_i$中属于类$C_k$的样本集合$D{ik}$, |$D{ik}$|为$D{ik}$的样本个数。
输入：训练数据集D和特征A：
输出：特征A对训练数据集的信息增益g(D,A)
先计算数据集D的熵H(D):
$H(D) = -\sum{k=1}^K\frac{|C_k|}{|D|}log\frac{|C_k|}{|D|} $
再计算条件熵H(D|a)
$H(D|A) = \sum{i=1}^n \frac{|Di|}{|D|}H(D_i) =-\sum{i=1}^n\frac{|Di|}{|D|}\sum{k=1}^K \frac{|D{ik}|}{|D_i|}log\frac{|D{ik}|}{|D_i|}$
$g(D,A)=H(D)-H(D|A)$
这种选择特征的思路就是ID3算法选择特征的核心思想。
信息增益比
公式为：$g_R(D,A)=g(D,A)/IntI(D,A)$
本来ID3算法计算信息增益好好的，但是C4.5一定要计算信息增益比这是为什么呢？
比如我们有10个样本，样本中有1个特征是学号我们把它叫作A，我们知道每个学生的学号都是不一样的，这样我们在计算H(D|A)的时候发现这个值是0，这种情况会导致你会认为这个特征是非常的好的，其实学号这个特征用来切分样本并不是什么好的特征。
那么导致这样的偏差的原因是什么呢？从上面的例子应该能够感受出来，原因就是该特征可以选取的值过多。解决办法自然就想到了如何能够对树分支过多的情况进行惩罚，这样就引入了下面的公式，属性A的内部信息
$IntI(D,A)=-\sum_{i=1}^n \frac{|D_i|}{|D|}log(\frac{|D_i|}{|D|})$
这样的话 如果还是对于学号这个特征会添加一个惩罚项10(-1/10)log(1/10),这个值一般是一个大于1的值。所以会起到惩罚的作用。
模型生成
ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归的构建决策树、
输入：训练数据集D，特征集A，阈值o
输出：决策树T
（1）如果D中所有实例属于同一类$C_k$,则T为单节点树，并将类$C_k$作为该结点的类标记，返回T；
（2）如果A=None，则T为单节点树，并将D中样本中类别最多的$C_k$作为该结点的类标记，返回T；
（3）否则选择信息增益最大的特征$A_g$;
(4) 如果$A_g$的信息增益小于阈值o，则说明所有的特征的信息增益都小于阈值，那么我们认为这些特征都很垃圾，那么我们就将D中样本类别最多的$C_k$作为该结点的类标记，返回T；
（5）否则，对$A_g$的每一可能值$a_i$，根据$A_g=a_i$将D分割为若干非空子集$D_i$,将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
（6）对每个子结点递归的调用，比如对第i个子结点，以$D_i$作为训练集，以A-${A_g}$作为可选特征集，调用（1）-（5），得到子树Ti,返回Ti.
c4.5算法
c4.5和ID3的唯一不同就是采用信息增益比来选择特征，其他全部一样。
一般递归的终止条件是什么：
1.所有训练数据子集被基本正确分类
2.没有合适的特征可选，即可用特征为0，或者可用特征的信息增益或信息增益比都很小了。
