数据挖掘分类算法之决策树算法ID3

最近在看数据挖掘（Data Mining）的相关书籍，一直尝试使用程序实现书中的一些算法，怎奈实力有限，连MATLAB和Weka中现成的工具箱都不会使用。也就只能了解了解算法原理才能维持得了生活这样子了。不过懂得算法原理，基本离实现也不远了。

说到决策树算法就不能不说数据挖掘中的分类问题。分类与预测不同，分类的目的是获得一个分类函数或分类模型（也常常成为分类器），该模型能把数据集的实例映射到某一个给定类别。首先要声明的是，分类和预测是不同的，分类与聚类是两回事。分类是给出分类标号，这种标号是离散且无序的；而预测则建立连续值函数模型。聚类是无监督的学习，相应地，分类则是有监督的学习。

以上是摘自最近在看的《纵观大数据：建模、分析及应用》书中的解释。

那么什么是决策树算法呢？

决策树（如下图所示）算法是一种经典的分类算法。它采用自顶向下、递归的、各个击破的方式构造决策树。树的每一个节点上使用信息增益度量选择属性，可以从生成2的决策树中提取出分类规则，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类型。

ID3使用信息增益作为属性选择度量。

在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。在了解什么是信息增益之前，我们需要知道什么是信息熵。熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

假设一个随机变量X的取值为

每一种取到的概率为

那么就有如下，

信息增益定义为原来的信息需求与新的需求之间的差，即：

其中，A表示样本的属性，Value（A）是属性A所有的取值集合。V是A的其中一个属性值，Sv是S中A的值为V的样例集合。

以上的公式大概看一下，知道怎么计算就OK！

接下来，请看一个例子，下表（请自行放大）是14天的打网球记录，通过天气、温度、湿度和风力来预测是否打了网球。

从以上表格中，我们可以获取如下信息：

一共14个数据样本，其中Yes（正例）9个，No（负例）5个，因此当前的信息熵计算如下

在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。

首先利用属性Outlook来分类，那么如下图

可以看出Outlook这一属性被分成了三个部分，由上述的信息熵公式可以得到，

然后利用属性Temperature来分类

可以看出Temperature这一属性被分成了三个部分，由上述的信息熵公式可以得到，

然后利用属性Humidity来分类

可以看出Humidity这一属性被分成了两个部分，由上述的信息熵公式可以得到，

接下来到Wind属性，

综上所述，第一个分裂的属性应该是Outlook。

Outlook的下一级节点中Sunny和Rain节点仍然需要进一步分裂，分别计算剩余的温度、湿度和风力三个变量的信息增益，取得最大的值作为分裂属性，以此类推；而Overcast节点已经不需要分裂，可以直接判决为Yes类即可。

于是我们对Sunny节点和Rain节点分别进行进一步分裂。

首先我们先对Sunny节点进行分裂，我们此时需要比较温度湿度和风力三个变量的信息增益。（接下来对于公式我就不一一解释了，直接上公式计算。）

根据以上的计算接过来看，可以明显的看出Humidity是Sunny属性下进一步的分裂属性。所以正确的决策树应为下图

接下来轮到Rain属性的进一步分裂了，依次比较温度、湿度、风力的信息增益。

综上所述，可以看出在进一步的属性分裂中Wind的信息增益是最大的，而且最终结果都可以直接作出判别，故不需要再进一步的属性分裂。

因而最终的决策树为

总结：上述阐述了一个完整的决策树ID3算法。在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。以上就是ID3算法的核心思想。

p.s.恭喜RNG获得MSI世界冠军！LPL重回世界之巅！这比赛看得人真的很心惊肉跳（Happy），最后一盘掉线暂停了好多次。还是恭喜Uzi拿下了自己的第二座冠军！

p.s.封面是五一数模校赛时候做题二——《红楼梦》作者预测，所做的主要人物词云图，具体关于怎么做词云详情百度最好Google！下次打算写一写最简单的SVM（支持向量机）？看有没有时间吧。吐槽一波CASIO的计算器，我算信息熵的时候，计算器上总显示堆栈错误，233333，这是个什么错误啊。。。只好把等式拆开慢慢计算了，但是学过数值分析的同学应该知道，这样会存在很大的误差，所以上述计算可信值只精确到小数点后5位，切记！