ID3决策树的Python实现与理解 _决策树

简单介绍
决策树是一个非常常见并且优秀的机器学习中监督学习的算法，它易于理解、可解释性强，是一种简单且广泛使用的分类器。通过数据来训练该预测模型，从而高效对未打标签的数据进行分类。因此简单来说那，决策树就是可以看做一个if-then规则的集合。我们从决策树的根结点到每一个都叶结点构建一条规则，根据数据不同的输入选择下一个结点，直到达到了最终的叶结点。

文章插图
ID3算法核心
知晓了决策树实现的功能之后，假如我们构建决策树，那么应该如何选择属性特征值呢。如上图所示，怎么判断出纹理这个特征就是树的根节点，为何不是触感，而色泽又凭什么要排在根蒂结点之后。这个问题也就是决策树学习的关键。其实就是选择最优划分属性，希望划分后，分支结点的“正确性”越来越高。如何计算该特征的正确性即为区分不同决策树的关键，下面就要引入一个信息的度量概念，信息增益，而ID3决策树在构建树的过程中，就是以信息增益来判断的。
香浓理论中的信息熵是度量样本集合不确定度（纯度）的最常用的指标。而在ID3算法中，我们采取信息增益这个量来作为纯度的度量。我们选取使得信息增益最大的特征进行分裂！信息熵是代表随机变量的复杂度（不确定度），条件熵代表在某一个条件下，随机变量的复杂度（不确定度）。而我们的信息增益恰好是：信息熵-条件熵。
数据的（ Ck表示集合 D 中属于第 k 类样本的样本子集）信息熵公式为：
【ID3决策树的Python实现与理解】针对某个特征 A，对于数据集 D 的条件熵为：
信息增益 = 信息熵 - 条件熵：
信息增益就表示为如果我们知道了属性A的信息，则可以使得样本集合不确定度减少的程度。那么我们选择决策树分裂的条件即为当前特征中信息增益最大的特征。
ID3决策树的构建过程
ID3决策树的构建过程如上所示，现在我们以周志华老师的《机器学习》一书中的例子来看一个具体的过程。数据集合如下：

文章插图
正例(好瓜)占 8/17，反例占 9/17 ，根结点的信息熵为：

文章插图
计算当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益。
色泽有3个可能的取值：{青绿，乌黑，浅白}
D1(色泽=青绿) = {1, 4, 6, 10, 13, 17}，正例 3/6，反例 3/6
D2(色泽=乌黑) = {2, 3, 7, 8, 9, 15}，正例 4/6，反例 2/6
D3(色泽=浅白) = {5, 11, 12, 14, 16}，正例 1/5，反例 4/5
三个分支结点的信息熵值为：

文章插图
那么我们可以知道属性色泽的信息增益为：

文章插图
同理其他的特征值的信息增益为：

文章插图
于是我们找到了信息增益最大的属性纹理，它的Gain(D，纹理) = 0.381最大。
于是我们选择的划分属性为“纹理” 。
如下：

文章插图
于是，我们可以得到了三个子结点，对于这三个子节点，我们可以递归的使用刚刚找信息增益最大的方法进行选择特征属性，
比如：D1(纹理=清晰) = {1, 2, 3, 4, 5, 6, 8, 10, 15}，第一个分支结点可用属性集合{色泽、根蒂、敲声、脐部、触感}，基于 D1各属性的信息增益，分别求的如下：