数据挖掘十大算法之决策树详解（2）

ID3算法

ID3和C4.5都是由澳大利亚计算机科学家Ross Quinlan开发的决策树构建算法，其中C4.5是在ID3上发展而来的。

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。ID3相当于用极大似然法进行概率模型的选择。 下面我们给出一个更加正式的ID3算法的描述：

输入：训练数据集D，特征集A，阈值ϵ； 
输出：决策树T。

若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T；

若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T;

否则，计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；

(1) 如果Ag的信息增益小于阈值ϵ，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T；

(2) 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；

对第i个子结点，以Di为训练集，以A−{Ag}为特征集，递归地调用步骤(1)~(3)，得到子树Ti，返回Ti。

下面我们来看一个具体的例子，我们的任务是根据天气情况计划是否要外出打球： 

首先来算一下根节点的熵： 

然后再分别计算每一种划分的信息熵，比方说我们选择Outlook这个特征来做划分，那么得到的信息熵为

据此可计算采用Outlook这个特征来做划分时的信息增益为 

同理，选用其他划分时所得到之信息增益如下： 

取其中具有最大信息增益的特征来作为划分的标准，然后你会发现其中一个分支的熵为零（时间中阈值可以设定来惩罚过拟合），所以把它变成叶子，即得 

对于其他熵不为零（或者大于预先设定的阈值）的分支，那么则需要做进一步的划分 

根据上述的规则继续递归地执行下去。最终，我们得到了如下一棵决策树。 

C4.5算法

C4.5是2006年国际数据挖掘大会票选出来的十大数据挖掘算法之首，可见它应该是非常powerful的！不仅如此，事实上，C4.5的执行也相当的straightforward。

C4.5算法与ID3算法相似，C4.5算法是由ID3算法演进而来的。C4.5在生成的过程中，用信息增益比来选择特征。下面我们给出一个更加正式的C4.5算法的描述：

输入：训练数据集D，特征集A，阈值ϵ； 
输出：决策树T。

如果D中所有实例属于同一类Ck，则置T为单结点树，并将Ck作为该结点的类，返回T；

如果A=∅，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类，返回T；

否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征Ag；

(1) 如果Ag的信息增益比小于阈值ϵ，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类，返回T；

(2) 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；

对结点i，以Di为训练集，以A−{Ag}为特征集，递归地调用步骤(1)~(3)，得到子树Ti，返回Ti。

How to do it in practice?

易见，C4.5跟ID3的执行步骤非常类似，只是在划分时所采用的准则不同。我们这里不再赘述。但是这里可以来看看在实际的数据分析中，该如何操作。我们所使用的数据是如下所示的一个csv文件，文件内容同本文最初给出的Play Ball例子中的数据是完全一致的。 

使用Weka进行数据挖掘是非常容易的，你不再需要像R语言或者MATLAB那样编写代码或者调用函数。基于GUI界面，在Weka中你只需要点点鼠标即可！首先我们单击“Explorer”按钮来打开操作的主界面，如下图所示。 

然后我们单击“Open File…”，并从相应的目录下选择你要用来进行模型训练的数据文件，如下图所示。 

Weka提供了非常易于操作的各种数据预处理功能，你可以自己尝试探索一下。注意到属性Day其实在构建决策树时是不需要的，我选中该属性，并将其移除，如下图所示。 

完成数据预处理后，我们就可以开始进行模型训练了。因为我们是要建立决策树，所以选择“Classify”选项卡，然后在“Classifier”中选择J48。你可以能会疑惑我们不是要使用C4.5算法建立决策树吗？为什么要选择J48呢？其实J48是一个开源的C4.5的Java实现版本（J48 is an open source Java implementation of the C4.5 algorithm），所以J48就是C4.5。 数据分析师培训

然后你可以自定义的选择“Test options”中的一些测试选项，这里我们不做过多说明。然后单击“Start”按钮，Weka就为我们建立了一棵决策树，你可以从“Classifier output”栏目中看到模型训练的一些结果。但是对于决策树而言，你可以觉得文字看起来还不够直观。不要紧，Weka还为你提供了可视化的决策树建模呈现。为此，你需要右键单击刚刚训练好的模型，然后从右键菜单中选择“Visualize tree”，如下图所示。 

最后我们得到了一棵与前面例子中相一致的决策树，如下图所示。 

在后续的决策树系列文章中，我们将继续深入探讨CART算法等相关话题。