0 通俗的理解
对于一个根据特征向量来对样本进行分类的问题，首先挑出一个最有价值的特征，对该特征进行提问，如样本颜色是什么；然后根据得到的不同回答，如红色、蓝色等，将数据集划分成子集，对每个子集重复上述操作，也就是说总是在剩下的特征集合里面找一个对最终分类任务最有用的特征，根据不同的取值再划分成更小的子集，知道最终子集内的样本都属于或者几乎属于同一类，那么此时我们就认为模型已经训练好。 （提问即决策规则，把提问保留来划分子集 ‘依据’）
决策树也是用来处理有监督的分类问题。它处理的数据的特征往往也是类别变量，而不是连续值。（SVM、逻辑斯蒂回归、线性回归都默认做分类预测的样本的特征向量是连续值）
当然，决策树也是可以处理连续变量的分类的。通常决策树适合处理特征向量中类别变量比较多的任务，以及对模型的可解释性要求较高的任务。
1 模型思路与算法流程
（1）模型思路
选择特征（选择顺序有策略，先对重要特征提问，再慢慢偏向细节），提问过程组成了一棵树的结构。
决策树模型不但能预测出类别，还能告诉用户它是根据哪些特征、如何判断，猜得到最终预测结果的。
（2）基本流程
a. 输入训练集S;
b. 若S中的所有样本为同一类别，标记为该类别，return；
c. 若S中的所有样本各个特征均相同，标记为数目最多的类别，return；
d. 待划分集合M初始化为S，初始化根节点root；
重复以下操作：
在所有特征中找到最优的特征α*，根据α*的不同取值将M划分成不同的子集，记为U1，U2，U3，...，并产生一个划分节点node。
对于每个子集Un的处理方式如下：
①如果无法划分，以最多类别作为预测类别，成为树的一个叶子，return；
②如果无须划分，将该子集样本类别作为预测类别，成为树的一个叶子，return；
③如果不是以上两种情况，则把该子集作为待划分集合M，成为上次划分的节点的孩子节点，重复步骤d。
注：①和②其实是两种停止条件，无须划分是说自己内的所有样本已经是同一类别了，没必要划分了；无法划分是指子集内的样本特征都是一样的，但是类别不同，同样无法继续划分。
e. 待全部划分结束，可得一棵以root为根节点的决策树。
（3）决策树模型的关键问题——特征的优选
在遍历所有的特征时，需要根据以该特征划分得到子集的纯度为这些特征打分，从而选取最优特征，那么，这个分数该如何计算呢？？？
计算该特征的分数就是计算划分后子集的纯度。即该特征划分以后，子集的纯度比未划分时增加了多少，增加的多，说明该特征更有用，所以应该给分高一些；反之，说明基于该特征的划分作用不大，应该给分低一些。
（自己的理解：纯度就是某一特征中类别的分布，某一类所占比重明显大的话，说明样本集比较纯）
2 特征选择原则
（1）信息增益原则（Information Gain Criteria）
定义：用信息量的变化来度量按照某个特征划分后，自己的纯度的增加程度。
信息量即一个事件包含的信息的量。在信息论中，通常用信息熵（熵，Entropy）对随机事件的信息进行度量。信息熵表示一个随机事件的不确定程度，即混乱程度。其数学公式为：
$H(X) = -\sum _{i=1}^{k}p_{i}logp_{i}$
其中，X是一个随机事件，总共有k种可能的情况，每种情况发生的概率分别为p1，p2，...，pk 。
在决策树特征选择与节点分裂时，将该节点上包含的训练集样本的类别看成一个随机事件，通过统计各类别的比例，代替上面各类别的比例，代替上面各种情况中的概率，就可以计算出某个节点的信息熵。
信息增益：指的是按照某个特征将节点分裂后，相对于分裂前的节点，分裂后的各个子节点的加权平均信息熵减少了多少。即通过某个特征的辅助，对于样本集类别的认知的不确定性消除了多少。
信息增益的数学形式：
$InfoGain(X,F) = H(X) - \sum _{i}\frac{X_{i}}{X}H(X_{i})$
其中，X为划分前的数据集，F为用来划分的特征，Xi为划分后每个集合的数据集。
（2）信息增益比原则
定义：信息增益与特征本身的信息熵的比值。
信息增益原则有缺陷，即其倾向于情况更多的特征。但多数情况下，这种特征过于细致，不能真正表达特征与类别的关系，容易过拟合。
这种特征有一个共同点，即本身的取值比较多，也就是特征本身的信息熵较大。因此，通过改进，得到信息增益比原则。数学形式如下：
$InfoGainRatio(X,F) = InfoGain(X,F) / H(F)$
（3）基尼系数原则
基尼系数依旧是用来度量集合中样本类别纯度的方法。数学含义是：在一个集合中任意取出两个样本，其不属于同一类的概率。
基尼系数的计算公式：
$Gini(S) = 1 - \sum _{i}p_{i}^{2}$
其中，pi为取到的样本为第i类的概率。
集合越“纯”，即类别越单一，取到同一样本的概率就越大，基尼系数越小。所以，我们更加倾向于选择分裂之后基尼系数的加权和最小的划分方式。作为决策树特征选择的基尼系数公式为：
$GiniInd(N,a) = \sum _{i=1}^{k}\frac{|N_{i}|}{|N|}Gini(N_{i})$
其中，N为节点分裂前的集合；Ni为分割成的子集合；a为用来分裂的特征。最终的目标特征式为：
$a^{*} = arg min GiniInd(N,a)$
3 剪枝策略
剪枝是防止决策树模型过拟合的策略之一。于决策树而言，模型的复杂度是分支的多少。剪枝操作就是将无益于模型泛化能力提高的节点分支“剪掉”。
抛出一个问题。如何判断有益还是无益？答案是 基于验证集的检验来判断是否剪枝的。
剪枝的具体操作如下：
对于一个节点来说，如果分裂后比分裂前在验证机上表现得更好，那么就允许这个节点分裂，形成“树枝”；反之，如果一个节点在分裂后反而在验证集上的表现更差了，那么就不希望这个节点分裂，就需要把已经分裂的“树枝”进行“剪枝”，避免模型的泛化能力下降。
剪枝分为预剪枝和后剪枝。
预剪枝：选择特征分裂节点过程中，如果判断一个节点需要剪枝，那么就直接不对该节点进行分裂。（缺点，可能错失更优解）
后剪枝：先分裂，得到一棵完整的决策树后，再考察每个节点，对需要剪枝的节点进行剪枝处理。（缺点，计算量大很多）
4 常用决策树模型
（1）ID3算法
ID指的是Iterative Dichotomister ，即迭代二分法。
①如果集合(节点)无法划分或无须划分，则返回该节点。其中，无法划分的用样本数最多的类别表示该节点预测类别，无须划分的用样本的类别表示该节点预测类别，否则转入步骤②。
②计算现有集合(节点)的信息熵。对于所有的特征，分别计算以其为划分标准所得的子集的信息熵(各个子集加权平均)，选择能使信息增益最大的特征。
③如果信息增益大于设定的阚值，那么选择该特征分裂节点，并转入步骤④，否则返回该节点。
④对于分裂得到的各个子集（子节点），重复步骤①-③。
（2）C4.5算法（ID3的改进）
①如果集合(节点)无法划分或无须划分，则返回该节点。其中，无法划分的用样本数最多的类别表示该节点预测类别，无须划分的用样本的类别表示该节点预测类别，否则转入步骤②。
②计算现有集合(节点)的信息熵。对于所有的特征，分别计算以其为划分标准所得的子集的信息熵(各个子集加权平均)及特征本身的信息熵，选择能使信息增益比最大的特征。
③如果信息增益大于设定的阚值，那么选择该特征分裂节点，并转入步骤④，否则返回该节点。
④对于分裂得到的各个子集（子节点），重复步骤①-③。
5 多变量决策树
基本思想：在每个节点都用多个特征共同参与决策。
具体实现：在每个节点用一个线性分类器代替单一属性的阈值。