决策树算法的大概流程

首先我们要知道，决策树是根据训练集构造一个树结构，每个分叉相当于一次判断，每个叶子节点就是模型的输出。如下图所示：

• 步骤1：就对于每一个节点，选取最优分叉属性。选择最优属性的方法有很多种，最常见的是信息增益法。

• 步骤2：把当前节点的训练样本集合，按照最优分叉的属性值分成几个子集，分别作为下一个节点。

  举个例子：如果步骤1告诉我们，当前节点最优属性是“纹理”，且纹理有三个值，分别为“清晰”、“稍糊”、“模糊”。则子节点应该分裂为三部分。第一部分是训练集中“纹理”属性为“清晰”的，第二部分是训练集中“纹理”属性为“稍糊”的，第三部分是训练集中“纹理”属性为“模糊”的。对于最优属性是连续的值的情况，往往采用二分法，也就是寻找一个值（可以是中位数），大于这个值的是一类，小于的是另一类。

• 步骤3：判断子节点是否符合终止条件，如果符合，就停止分裂，不符合就回到步骤1。

以输入特征为离散值的分类决策树为例，周志华老师《机器学习》给出的算法伪代码：

决策树分类

决策树分类算法选择最优属性算法常用信息增益法。

首先了解信息熵，它的公式如下：
${Ent{ \left( {D} \right) } =-{\mathop{ \sum } \limits_{ {k=1} } ^{ { { \left| {Y} \right| } } } {p\mathop{ {} } \nolimits_{ {k} } log\mathop{ {} } \nolimits_{ {2} } p\mathop{ {} } \nolimits_{ {k} } } } }$Ent(D)=−k=1∑∣Y∣​pk​log2​pk​
其中，D为当前训练样本集合，集合中的真实值有|Y|类。

从公式可见，信息熵越小，集合的纯度越高，如果信息熵为0，那么训练集D是属于同一类。

每一次树的划分的时候，需要以输入的一个特征a *来对树进行划分，也就是说，划分成的子数将不含特征a *。对于去掉任意属性a对样本集D划分的信息增益可以用下式表示：
${Gain{ \left( {D,a} \right) } \text{ } =\text{ } Ent{ \left( {D} \right) } -{\mathop{ \sum } \limits_{ {v=1} } ^{ { { \left| {V} \right| } } } {\frac{ { { \left| {D\mathop{ {} } \nolimits^{ {v} } } \right| } } } { { { \left| {D} \right| } } } Ent{ \left( {D\mathop{ {} } \nolimits^{ {v} } } \right) } } } }$Gain(D,a) = Ent(D)−v=1∑∣V∣​∣D∣∣Dv∣​Ent(Dv)
其中，D^v是D中在a属性取值为v的样本集合。

那么我们如何选取当前节点划分特征呢？很显然，应该把让信息熵变化最小的特征去掉。举个极端的例子，如果有一个特征的信息熵为0，那么利用这个特征进行节点分裂就可以直接划分出结果，所以这个特征是优先被考虑的。所以在每次选划分当前节点的时候，我们只需要去掉的特征a *满足：
${a\mathop{ {} } \nolimits_{ {*} } =\mathop{ {argmax} } \limits_{ {a \in A} } Gain{ \left( {D,a} \right) } \text{ } }$a∗​=a∈Aargmax​Gain(D,a) 
其中，A为当前划分节点剩余的特征集合。（如果输入特征为离散的属性，则A的个数为特征的维度）

决策树回归

决策树求解回归问题的方法有以下两种：

• 将每个节点的标签的平均值作为节点的值，利用方差最小进行节点分裂。选择分裂属性的方法如下：

${min{\mathop{ \sum } \limits_{ {v=1} } ^{ { { \left| {V} \right| } } } {\frac{ { { \left| {D\mathop{ {} } \nolimits^{ {v} } } \right| } } } { { { \left| {D} \right| } } } var{ \left( {D\mathop{ {} } \nolimits^{ {v} } } \right) } } } }$minv=1∑∣V∣​∣D∣∣Dv∣​var(Dv)

​ 其中，D^v是D中在某一属性取值为v的样本集合。可以看出，此方法得到是输出也是有限个离散的值。

• 将每个节点表示为当前节点训练集的线性回归模型，利用求每个集合的均方误差进行节点分裂。选择分裂属性的方法如下：
  ${min{\mathop{ \sum } \limits_{ {v=1} } ^{ { { \left| {V} \right| } } } {\frac{ { { \left| {D\mathop{ {} } \nolimits^{ {v} } } \right| } } } { { { \left| {D} \right| } } } { \left( {line\mathop{ {} } \nolimits_{ {D\mathop{ {} } \nolimits^{ {v} } } } { \left( {x} \right) } -y} \right) } \mathop{ {} } \nolimits^{ {2} } } } }$minv=1∑∣V∣​∣D∣∣Dv∣​(lineDv​(x)−y)2
  其中，D^v是D中在某一属性取值为v的样本集合。lineDv是在Dv集合下得到的线性回归模型。