信息科学与技术学院学士学位论文
3.2.1 ID3
ID3算法可以称得上是分类算法中决策树算法的鼻祖，我们所知道的C4.5和C5.0算法都是通过研究者基于ID3算法进行各方面的改进得到的。这个算法诞生于1986年，由J.R.Quinlan开发出来的，算法的核心为“信息熵”。该算法运用了信息论和贪心策略[10]（自顶向下增长）来对数据属性进行分类，在每个节点都会挑选出最好的样本属性。在决策树生长的过程中，该算法主要判断训练样本的信息增益（information gain）来确定最佳分组变量，直到所有的样本都使用过为止。下面列举这个简单的例子来向大家展示该算法在建立决策树的过程的具体细节，数据如表3-1所示。
表3-1 数据表
Age Income Student Credit_rating Buys_computer high high high medium low low low medium low medium medium medium high medium no no no no yes yes yes no yes yes yes no yes no fair excellent fair fair fair excellent excellent fair fair fair excellent excellent fair excellent no no yes yes yes no yes no yes yes yes yes yes no youth youth middle_aged senior senior senior middle_aged youth youth senior youth middle_aged middle_aged senior 表3-1数据总共14条记录，输出变量是：是否会购买电脑（buys_computer）,总共出现了两种情况，买（yes）和不买（no）。输入变量有：年龄（age），收入（income），是否为学生（student），信用等级（credit_rating）。输入变量年龄的取值有3种情况，分别为：youth，middle_aged，senior；输入变量收入的值也有3种情况：high，medium，low；输入变量是否为学生有2种情况，分别为：yes和no；输入变量信用
21
信息科学与技术学院学士学位论文
等级也只有有2种情况：fair和excellent。根据3-1表数据我们来先求每个变量的信息熵。信息熵属于数学这门学科中的内容，这里我先介绍一下计算信息熵的公式。假设有一组数据为：d1,d2,d3,d4....,dn,这组数据的和为sum，那么求信息熵的公式为：
H(D)???i?1ndidi log2sumsum根据上文提供的数据和公式我们可以计算输出变量（buys_computer）的信息熵：
H(D)??5599log2?log2?0.94 14141414 该运算式中的5代表5个在表3-1中的输出变量中的值为no的个数，9代表值为yes的个数，14即为输出变量的总个数。按照信息熵公式我们可以相继算出各个输入变量在取各自值对应的输出变量的信息熵，以输入变量年龄为例，分为3种取值情况：youth，middle，senior。咱们先计算当变量年龄的取值为youth时的信息熵。当输入变量年龄取值为youth时，对应的输出变量的取值有2个为yes，3个位no，总计5个输出变量值，所以信息熵为：
3322Hage(Dyouth)??log?log?0.971
5555 类似上面的思路分析我们可以得到当年龄变量的值为middle_aged和senior时的信息熵，经计算得值为：0和0.971。上面是分别求输入变量年龄不同取值情况下的信息熵，那么输入变量年龄(age)的信息熵为不同取值时信息熵的加权平均值：
Hage(D)?545*0.971?*0?*0.971?0.694 141414 信息熵是非常基础的一个建立决策树时需要计算的值，对数据进行分组不是通过该值但是必须建立在这个值之上。接下来我们需要计算的是信息增益值，这个值我们在这里用Gain（D）来表示，这个值代表着信息熵的减少量，该值越高表示着输出变量在该输入变量那失去的信息熵越多，那么这个输入变量应该建立在决策树的上层。那么我可以计算输入变量年龄（age）的信息增益为：
Gain(age)?H(D)?Hage(D)?0.246
22
信息科学与技术学院学士学位论文
类似上面求值的思路我们还可以计算出剩余的输入变量的信息增益，经计算的：Gain（income）=0.029，Gain（student）=0.151,Gain（credit_rating）=0.048。一比计较这几个输入变量的信息增益，我们可以知道，输入变量年龄（age）的信息增益最大，Gain（age）=0.246，所以分类树的地一层应该为输入变量年龄（age），因为输入变量年龄有3个值所以可以将数据分成3类,如图3-3所示。 age youth credit_rating fair excellent fair fair excellent income high low medium high student no yes no yes credit_rating fair excellent excellent fair 图3-3 初步分类图
class yes yes yes yes middle_aged class no no no yes yes income medium low low medium medium senior income high high medium low medium student no no no yes yes student no yes yes yes no credit_rating fair fair excellent fair excellent class yes yes no yes no 通过重复上面所述的求值分类过程，我们可以继续对各个分支的输入变量进行分类。当然分类并不会无止尽，那么设置终止的条件可以为以下两种：当分到某类时，输出变量的值全为一个值得时候，例如，年龄取值为middle_aged 的候对应的输出变量值全为yes，分类停止；给输入变量某个值所对应的输出变量设置个阈值，若比例到了这个阈值就也会停止分类。 3.2.2 C4.5和C5.0 （1）C4.5算法
C4.5算法是ID3算法的延伸，是由Quinlan提出的。既然C4.5是根据ID3的算
23
信息科学与技术学院学士学位论文
法结构加以改进开发出来的，那么C4.5不仅应该具有ID3算法的优势，而且还应该弥补了ID3的某些不足之处。那么实际上该算法在哪些方面对ID3算法进行了相应的改变，下面我将介绍C4.5算法的优缺点以及算法的详细步骤。
C4.5算法在ID3算法的哪些方面进行了改进：
①我们知道在ID3算法当中，它使用信息增益来选择用于分组的变量，但是这样做可能会出现偏向于取值比较多的变量的情况，那么就会导致模型预测的准确率下降。但是C4.5引入信息增益率这个概念，通过信息增益率来选择最佳分组变量，能够有效的解决上述ID3使用信息增益时出现的问题；
②C4.5算法在构造决策树的过程中可以对我们的决策树进行相应的剪枝，但是在实际应用中ID3算法并没有剪枝这个过程；
③3C4.5算法在对数据预处理的时候会对连续型的变量进行离散化处理，而ID3做不到；
④C4.5在实际应用中能够对缺失的数据进行相应的处理，并处理的十分妥当； C4.5算法的优点是：通过这个算法得到的规则集或者决策树具有非常高的预测率，而且生成的模型很容易让人理解。不过再完美的东西还是会存在缺陷，C4.5算法不足的地方有：算法相对低效，因为在处理数据时候需要重复查询数据库。另外，C4.5只适用于处理保存在内存中的数据，当我们需要分析的数据非常的大并且不能够完全的保存到机器的内存中的时候，使用C4.5算法极有可能导致程序运行时出现崩溃的情况。
C4.5算法的步骤：
①数据预处理，在这个过程中软件会自动的分析我们的数据是什么类型的，因为我们需要把连续型的数据改变成离散型的数据，若不含有连续型数据则此过程忽略，然后才获得需要构造决策树的训练样本集。
②计算出每个输入变量的信息增益然后根据信息增益值计算出相应的信息增益率值，因为算法使用计算得到的信息增益率作为最后对数据进行分组的标准，所以通过比较信息增益率得出决策树的根节点。
24
信息科学与技术学院学士学位论文
③根节点输入变量有多少个取值就表示决策树将生成多少个子节点，然后我们使用递归方法对样本子集重复执行第二步操作，直到每个子集中的训练样本的输入变量的取值和输出变量的取值完全相同，完成决策树的生长。当然，实际情况中这个步骤中还伴随着决策树的修剪过程。
④提取出我们需要的规则集，这样我们就可以使用已获得的规则集对我们的数据进行分类预测了。
（2）C5.0算法
C5.0算法的鼻祖也是ID3算法，通过上节介绍我们知道了C4.5算法的出现为决策树算法的研究树立了一个新的里程碑。C5.0算法更注重商业化应用，该算法挖掘的目标主要针对的是商业上的大数据集。C5.0算法构造决策树的过程几乎和C4.5一样。但是该算法在拆分数据的时候使用的标准是信息增益率。该决策树算法还加入了BoostingTrees技术，因为BoostingTrees技术能够非常有效的提高模型预测的准确率。下面我将向大家介绍该如何计算信息增益率和BoostingTrees技术以及该算法的优势。
计算信息增益率：
C5.0以信息增益率作为最佳分组变量和最佳分割点的选择标准，其不仅考虑信息增益的大小，还兼顾信息增益所付出的“代价”。该章介绍ID3算法的时候我已经向大家介绍了如何计算信息增益，此处不再介绍。本文通过实际例子来介绍计算信息增益率，那么下面我将使用表3-3的数据，计算输入变量年龄（age）的信息增益率。假如，根据表3-3数据，我们把建立决策树所需要的输出变量（buys_computer）看作信源U，输入变量（age,income,student,credit_rating）看作信宿收到的一系列信息V，那么信息增益率的数学公式为：
GainsR(U,V)?Gains(U,V)/Ent(V)
式中Gains（U，V）表示信息增益，Ent(V)表示不确定性。我根据公式可以计算得到输入变量年龄（age）的信息增益率：
GainsR(U,age)?0.246/(?554455log2()?log2()?log2())?0.156 14141414141425