决策树
决策树（decision tree）是一种基本的分类与回归方法，这里主要讨论用于分类的决策树。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要的有点是模型具有可读性，分类速度快，学习时利用训练数据，根据损失函数最小化的原则简历决策树模型。决策树的学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。
决策树模型与学习
决策树模型
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
分类的时候，从根节点开始，当前节点设为根节点，当前节点必定是一种特征，根据实例的该特征的取值，向下移动，直到到达叶节点，将实例分到叶节点对应的类中。
决策树与if-then规则
决策树的属性结构其实对应着一个规则集合：由决策树的根节点到叶节点的每条路径构成的规则组成；路径上的内部特征对应着if条件，叶节点对应着then结论。决策树和规则集合是等效的，都具有一个重要的性质：互斥且完备。也就是说任何实例都被且仅被一条路径或规则覆盖。
决策树与条件概率分布
决策树还是给定特征条件下类的条件概率分布。该条件分布定义在特征空间的划分上，特征空间被花费为互不相交的单元，每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的每条路径对应于划分中的一个单元。给定实例的特征X，一定落入某个划分，决策树选取该划分里最大概率的类作为结果输出。如图：
关于b图，将a图的基础上增加一个条件概率的维度P，代表在当前特征X的情况下，分类为+的后验概率。图中的方块有些地方完全没有，比如x2轴上[a2,1]这个区间，说明只要X落在这里，Y就一定是-的，同理对于[0,a1]和[0,a2]围起来的一定是+的。有些地方只有一半，比如x1轴上[a1,1]这个区间，说明决策树认为X落在这里，Y只有一半概率是+的，根据选择条件概率大的类别的原则，就认为Y是-的（因为不满足P(+)>0.5)。
决策树学习
决策树学习，假设给定训练数据集D={(x1,y1),(x2,y2),⋯,(xN,yN)}
其中，xi为输入实例（特征向量）yi为类标记，N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
决策树学习本质上是从训练数据集中归纳出一组分类规则。
我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。另一个角度看，决策树学习是由训练数据集估计条件概率模型。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习用损失函数表示这一目标。如下所述，决策树学习的损失函数通常是正则化的极大似然函数。
决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优(sub-optimal)的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
特征选择
特征选择问题
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比
信息增益
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为$P(X=x_i)=pi,i=1,2,\cdots,n$，则随机变量X的熵定义为$H(X) = -\sum\limits{i=1}^{n}{p_i\log{p_i}}$
通常上式中的对数以2为底或者以自然对数e为底，这时熵的单位分别称作比特（bit）或纳特（nat）。由定义可知，熵只依赖于X分布，而与X的取值无关.
熵越大，随机变量的不确定性就越大。从定义可以验证 $0 \le H(p)\le \log n$,当随机变量只取两个值，例如1,0时，即X的分布为 P(X=1)=p,P(X=0)=1−p,0≤p≤1熵为$H(p)=-p \log_2p-(1-p)\log_2(1-p)$
由此可知熵随p变化的曲线图：
所以当p取0或1时，熵的值为1，变量X完全没有不确定性，当p取0.5时，变量X的不确定性最大。
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，定义为在X给定的条件下，Y的条件概率分布对X的数学期望：$H(Y|X) = \sum\limits_{i=1}^{n}{p_iH(Y|X=x_i)}$,其中，$p_i=P(X=x_i), i=1,2,…,n$
信息增益（information gain）:表示在得知特征X的条件下，类Y的不确定性减少的程度。定义为训练数据D的经验熵与给定特征X的条件下的数据D的经验条件熵的差值。
特征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)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中的类与特征的互信息。
决策树学习应用信息增益准则选择特征。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D,计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。
信息增益比
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。
定义（信息增益比）：特征A对训练数据集D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集D关于特征A的值的熵$H_A(D)$之比，即 :
$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$
其中$HA(D)=-\sum{i=1}^n\frac{|D_i|}{|D|}\log_2 \frac{|D_i|}{|D|}$
决策树的生成
ID3算法
ID3算法（interative dichotomiser 3）的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。
C4.5的生成方法
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征。
决策树的剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树容易出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决这一问题的方法是考虑决策树的复杂度，对已生成的决策树进行简化。
在决策树学习中讲已生成的树进行简化的过程称为剪枝（pruning）。
决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。
