决策树的经典构造算法ID3&C4.5

决策树概述：
   决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。一般的数据挖掘工具，允许选择分裂条件和修剪规则，以及控制参数（最小节点的大小，最大树的深度等等），来限制决策树的。决策树作为一棵树，树的根节点是整个数据集合空间，每个分节点是对一个单一变量的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一类别的记录。构造决策树的过程为：首先寻找初始分裂。整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的。决定哪个属性域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。建决策树，就是根据记录字段的不同取值建立树的分支，以及在每个分支子集中重复建立下层结点和分支。建决策树的关键在于建立分支时对记录字段不同取值的选择。选择不同的字段值，会使划分出来的记录子集不同，影响决策树生长的快慢以及决策树结构的好坏，从而导致找到的规则信息的优劣。可见，决策树算法的技术难点也就是选择一个好的分支取值。利用一个好的取值来产生分支，不但可以加快决策树的生长，而且最重要的是，产生的决策树结构好，可以找到较好的规则信息。相反，如果根据一个差的取值来产生分支，不但减慢决策树的生长速度，而且会使产生的决策树分支过细，结构性差，从而难以发现一些本来可以找到的有用的规则信息。

以下转自 祥子的BLOG http://blog.sina.com.cn/u/4d8d63030100096x#sort_1
对分类树中的ID3和C4.5算法做了比较“实在”的介绍。

决策树的经典构造算法（一）——ID3

ID3算法是1986年由Quilan提出的，它是一个从上到下、分而治之的归纳过程。ID3算法的核心是：在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。其具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。

    有关信息增益的定义以及具体的计算方法和实例，可以参考马瑜和王有刚的论文《ID3算法应用研究》的第1、2两节。

    ID3算法思想描述如下：

(1) 初始化决策树T为只含一个树根(X,Q)，其中X是全体样本集，Q为全体属性集。

(2) if(T中所有叶节点(X’,Q’)都满足X属于同一类或Q’为空)then 算法停止；

(3) else

    {任取一个不具有(2)中所述状态的叶节点(X’,Q’)；

(4) for each Q’中的属性A do 计算信息增益gain(A,X’)；

(5)     选择具有最高信息增益的属性B作为节点(X’,Q’)的测试属性；

(6) for each B的取值b_i do

        {从该节点(X’, Q’)伸出分支，代表测试输出B=b_i；

        求得X中B值等于b_i的子集X_i，并生成相应的叶节点(X_i’,Q’-{B})；}

(7) 转(2)；}

    ID3算法是决策树的一个经典的构造算法，在一段时期内曾是同类研究工作的比较对象，但通过近些年国内外学者的研究，ID3算法也暴露出一些问题，具体如下：

    (1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。

    (2)ID3是非递增算法。

    (3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。

    (4)抗噪性差，训练例子中正例和反例的比例较难控制。

    于是Quilan改进了ID3，提出了C4.5算法。C4.5算法现在已经成为最经典的决策树构造算法，排名数据挖掘十大经典算法之首，下一篇文章将重点讨论。

决策树的经典构造算法（二）——C4.5

由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。

    C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

    1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；有关信息增益率的定义可以参考栾丽华和吉根林的论文《决策树分类技术研究》1.2节。

    2) 在树构造过程中进行剪枝；

    3) 能够完成对连续属性的离散化处理；

    4) 能够对不完整数据进行处理。

    C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。