全局概览
决策树模型呈树形结构，它是基于特征对样本进行分类的过程，可认为是If-then的集合或者定义在特征空间和类空间上的条件概率分布。
优点：可读性、分类速度快。
决策树目的是构建一个与训练数据拟合很好，并且复杂度很小的决策树，因为从所有可能的决策树中选取最优的决策树是个NP难问题。所以一般采用启发式方法学习次优的决策树。
决策树学习的策略是以损失函数为目标函数的最小化。（其实就是最小化对数概率损失函数）
决策树学习算法包含特征选择、决策树的生成和决策树的剪枝过程。决策树其实表示的是一个条件概率分布，所有深浅不同的决策树对应于不同复杂度的概率模型。决策树的生成对应于模型的局部选择（考虑了局部最优），但是生成过程由于在学习时过多地考虑了如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。而过于复杂的决策树会导致过拟合的现象。
为了避免过拟合现象，就需要采用结构风险最小化模型（经验损失加上正则化项），而这种模型在决策树中称为剪枝过程（相当于用正则化的极大似然估计进行模型选择）。而剪枝对应于模型的全局选择（考虑了全局最优）
特征选择的准则包括信息增益和信息增益比、基尼指数。
信息增益和信息增益比
熵：表示随机变量不确定性的度量。熵越大，随机变量的不确定性越大。
信息增益：表示由于特征A而使得对数据集D的分类的不确定性减少的程度。具体来说，定义为训练集合D的经验熵H（D）与基于特征A，训练集合的经验条件熵H（D|A）之差(也称为训练数据集中类与特征的互信息。)：
$$g(D,A)=H(D)-H(D|A)$$
由于信息增益偏向于选择取值较多的特征，所以信息增益比运用而生。
信息增益比：对于一个特征来说，它的信息增益g(D,A)与训练数据集D关于该特征的值的熵H_A(D)之比，即：
$$g_R(D,A)=g(D,A)/H_A(D)$$
决策树算法：ID3、C4.5
ID3算法核心是在每个结点上用信息增益选择特征，递归地构建决策树。具体讲：从根节点出发，对每个特征计算信息增益，选择信息增益最大的特征作为该结点，然后由该结点的各个值建立子结点，再对子结点递归地进行上述操作，构建决策树；直到所有特征选择完毕为止。ID3相当于用极大似然法进行模型选择。
C4.5算法步骤差不多，只是用信息增益比来代替信息增益选择特征。
决策树的剪枝往往是对那个已经生成的树上剪掉一些子树或者叶子结点，并将其父结点或根结点作为新的叶节点，从而简化生成的决策树。
