对于一个根据特征向量来对样本进行分类的问题，首先挑出一个最有价值的特征，对该特征进行提问，如样本颜色是什么；然后根据得到的不同回答，如红色、蓝色等，将数据集划分成子集，对每个子集重复上述操作，也就是说总是在剩下的特征集合里面找一个对最终分类任务最有用的特征，根据不同的取值再划分成更小的子集，知道最终子集内的样本都属于或者几乎属于同一类，那么此时我们就认为模型已经训练好。 （提问即决策规则，把提问保留来划分子集 ‘依据’）
决策树也是用来处理有监督的分类问题。它处理的数据的特征往往也是类别变量，而不是连续值。（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）信息增益比原则
定义：信息增益与特征本身的信息熵的比值。