安徽新华学院2015届本科毕业论文（设计）
图3.1 决策树
3.2决策树的主要算法
近年来，决策树方法在很多机器学习、知识的探究等过程中得到了广泛的应用。迄今为止，国内外研究人员先后提出了十几种决策树的分类方法，因此决策树的算法还是挺多的，本文介绍了两种比较经典的决策树算法，分别是ID3算法和C4.5算法。
3.2.1 ID3算法
ID3(induction decision-tree)算法，它是一种用来由数据构造决策树的递归过程，是在1986年由Quinlan首先提出的，该算法以信息论为基础，信息论是数学中的概率论和数理统计的一个分支，用于处理信息和信息熵、通信系统、数据传输和率失真理论、密码学、信噪比、数据压缩和相关课题。以信息熵和信
息增益度为衡量标准，从而实现数据的归纳分类，它是一个从上到下、分而治之 的归纳过程[12]。
ID3算法的大概过程是：我们试探性的选择一个属性放置在根节点，并对该属性的每个值产生一个分支。这样，分裂根节点上的数据集，并一道子女节点，产生一个局部的树。在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录的最大的类别信息。其具体方法是：我们需要检测所有的属性，在它们中间选择信息增益最大的属性作为决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有的子集仅包含同一类别的数据为止。最后得到的一棵决策树，它可以用来对新的样本进行分类。 要想了解ID3算法，我们要了解ID3算法中的一些基本概念： （1）熵
熵是一个物理名词，源于热力学的概念，数值为温度除热量所得的值。1948年Shannon提出并发展了信息论并引入了信息熵。
一个训练集合S根据类别属性的值被分成m个互相独立的类C1、C2、..、Cn，则识别S的一个元组所属哪个类所需的信息量为Info（S）。
11
安徽新华学院2015届本科毕业论文（设计）
＋log2 P○＋-P○－log2 P○－ Info（S）= －?Pilog2（Pi）＝－P○
i?1n上述公式中，p+代表正样例，而p-则代表反样例。 （2）信息增益度
信息增益度是两个信息量之间的差值， 已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益（information gain）”。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：G（S,A）=Info（S）-Info（A）
最后根据信息增益最大的原则选择根节点来构成决策树。
3.2.2 C4.5算法
C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点：
1、用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度度量准则），也就是熵的变化值，而C4.5用的是信息增益率。
2、在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。 3、对非离散数据也能处理。 4、能够对不完整数据进行处理
由于ID3算法在实际应用中的一些局限，Quinlan再次改进了ID3算法。C4.5算法是ID3算法的改进版本，C4.5算法可以处理多种数据类型。此外，C4.5的效率相比于ID3算法也有了很多的提高。
通过对ID3算法的介绍我们已经了解熵，和信息增益。在C4.5算法中我们引入了新的概念信息增益率。 C4.5算法的具体步骤如下： （1）计算集合D的熵；
12
安徽新华学院2015届本科毕业论文（设计）
（2）计算各个属性的信息熵； （3）计算信息增益； （4）计算分裂信息度量； （5）计算信息增益率；
（6）选择增益率最大的作为根节点； (7)建立决策树；
本文以一个典型被引用多很多次的数据训练集D为例，来说明C4.5算法如何计算信息节点并切选择决策树结点。如图3.2: 天气 晴 晴 阴 雨 雨 雨 阴 晴 晴 雨 晴 阴 阴 雨 温度 炎热 炎热 炎热 适中 寒冷 寒冷 寒冷 适中 寒冷 适中 适中 适中 炎热 适中 湿度 高 高 高 高 正常 正常 正常 高 正常 正常 正常 高 正常 高 图3.2 根据图3.2我们可以看出上面的训练集有4个属性：{天气，温度，湿度，风速}，而类标签有2个，即类标签集合C={Yes, No}，分别表示适合户外运动和不适合户外运动。
根据前面的介绍，我们来计算信息熵，信息增益，以及信息增益率。
13
风速 弱 强 弱 弱 弱 强 强 弱 弱 弱 强 强 弱 强 活动 取消 取消 进行 进行 进行 取消 进行 取消 进行 进行 进行 进行 进行 取消 安徽新华学院2015届本科毕业论文（设计）
数据D中一共用14个训练样本，其中9个为正样例，5个位反样例。因此它的信息熵为：Info（D）=-9/14*log2（9/14）-5/14log2（5/14）=0.940
下面计算属性集合中每个属性的信息熵：
1：Info(天气) = 5/14 * [- 2/5 * log2(2/5) – 3/5 * log2(3/5)] + 4/14 * [ - 4/4 * log2(4/4) - 0/4 * log2(0/4)] + 5/14 * [ - 3/5 * log2(3/5) – 2/5 * log2(2/5)] = 0.694
2：Info(温度) = 4/14 * [- 2/4 * log2(2/4) – 2/4 * log2(2/4)] + 6/14 * [ - 4/6 * log2(4/6) - 2/6 * log2(2/6)] + 4/14 * [ - 3/4 * log2(3/4) – 1/4 * log2(1/4)] = 0.911
3：Info(湿度 = 7/14 * [- 3/7 * log2(3/7) – 4/7 * log2(4/7)] + 7/14 * [ - 6/7 * log2(6/7) - 1/7 * log2(1/7)] = 0.789
4：Info(风速) = 6/14 * [- 3/6 * log2(3/6) – 3/6 * log2(3/6)] + 8/14 * [ - 6/8 * log2(6/8) - 2/8 * log2(2/8)] = 0.892 根据上面的数据我们可以计算出信息增益：
1：Gain(天气) = Info(D) - Info(天气) = 0.940 - 0.694 = 0.246 2：Gain(温度) = Info(D) - Info(温度) = 0.940 - 0.911 = 0.029 3：Gain(湿度) = Info(D) - Info(湿度) = 0.940 - 0.789 = 0.151 4：Gain(风速) = Info(D) - Info（风速) = 0.940 - 0.892 = 0.048
接下来，我们计算分裂信息度量H(V)：
1、天气属性
属性天气有3个取值，其中晴有5个样本、雨有5个样本、阴有4个样本，则 H(天气) = - 5/14 * log2(5/14) - 5/14 * log2(5/14) - 4/14 * log2(4/14) =1.57740628285234 2、温度属性
属性温度有3个取值，其中热有4个样本、适中有6个样本、寒冷有4个样本，则
H(温度) = - 4/14 * log2(4/14) - 6/14 * log2(6/14) - 4/14 * log2(4/14) = 1.5566567074628228
14
