前言

文章来自http://www.saedsayad.com/decision_tree.htm
这里提供给那些没法翻墙的同学学习。文章写的很不错，因为自己是自学，看《机器学习实战》看的一脸懵逼，这篇文章通过数学形式介绍了构造决策树的过程，特别适合新手入门。当你理解了数学过程再去构造代码就会简单很多了。

简介

决策树以树结构的形式构建分类或回归模型。其最终结果是具有决策节点和叶节点的树。决策节点（例如，Outlook）具有两个或更多个分支（例如，Sunny，Overcast和Rainy）。叶节点（例如，Play）表示分类或决定。树中最顶层的决策节点，对应于称为根节点的最佳预测器。决策树可以处理分类和数字数据。

Decision_Tree_1.png

算法

JR Quinlan 构建决策树的核心算法，称为ID3，它采用自上而下的贪婪搜索方式，通过可能的分支空间进行无回溯。ID3使用Entropy和Information Gain构建决策树。

熵（Entropy）

决策树是从根节点自上而下构建的，涉及将数据分区为包含具有相似值（同质）的实例的子集。ID3算法使用熵来计算样本的同质性。如果样本是完全均匀的，则熵为零，如果样本是等分的，则其熵为1。

Entropy.png

要构建决策树，我们需要使用频率表计算两种类型的熵，如下所示：
a）使用一个属性的频率表计算熵：

image

b）使用两个属性的频率表进行熵：

Entropy_2.png

信息增益

信息增益基于在属性上拆分数据集后熵的减少。构建决策树就是找到返回最高信息增益的属性（即，最同质的分支）。

第1步：计算目标的熵。

image

*步骤2 *：然后将数据集拆分为不同的属性。计算每个分支的熵。然后按比例添加，以获得拆分的总熵。在分割之前从熵中减去所得到的熵。结果是信息增益或熵减少。

image Outlook Temp

*步骤3 *：选择具有最大信息增益的属性作为决策节点，将数据集除以其分支，并在每个分支上重复相同的过程。

image image

*步骤4a *：熵为0的分支是叶子节点。

image

*步骤4b *：熵大于0的分支需要进一步分裂。

image

这里如果你做过多次练习，可以一眼看出Sunny之后的决策节点是Windy，因为该分支是明确的，当Windy为False，结果一定是Yes；当Windy为True，结果一定是No。分支的熵为0，最小，则信息增益最大。
同样的Rainy之后可以看出决策节点应该是Humidity。当然看不出来也没关系，程序会自行计算。

*步骤5 *：ID3算法在非叶子分支上递归运行，直到所有数据都被分类。

决策规则决策树

通过逐个从根节点到叶节点的映射，可以容易地将决策树转换为一组规则。

image

总结

要构造一个决策树的步骤如下：
第一步：计算最终目标标签（最后一列）的信息熵
第二步：计算每个分支的熵，获得最大信息增益熵对应的特征（属性）作为决策节点
第三步：递归（分支熵为0则作为叶子节点，否则重复上面的过程）

最后在搞定数学过程之后，下一篇我们可以尝试使用python代码（不导入第三方包）实现决策树。