数据挖掘十大算法之C4.5以及CART算法。

决策树的工作原理

决策树是一类常见的机器学习方法。一般的，一个决策树包含一个根节点、若干个内部节点和若干个叶节点；叶节点对应于决策结果，其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”(divide-and-conquer)策略。

构建决策树

Hunt算法

Hunt算法是一种采用局部最优策略的决策树构建算法，它同时也是许多决策树算法的基础，包括ID3、C4.5和CART等。该算法的具体执行步骤如下：

在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式建立决策树。设 $D_{t}$ 是与结点 t 相关联的训练记录集，而$y={y_{1},y_{2},⋯,y_{c}}$是类标号，Hunt算法的递归定义如下：
(1) 如果$D_{t}$中所有记录都属于同一个类，则 t 是叶结点，用$y_{t}$标记。

(2) 如果$D_{t}$中包含属于多个类的记录，则选择一个属性测试条件（attribute test condition），将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果将$D_{t}$中的记录分布到子女结点中。然后，对于每个子女结点，递归地调用该算法。

为了演示这方法，我们选用文献【2】中的一个例子来加以说明：预测贷款申请者是会按时归还贷款，还是会拖欠贷款。对于这个问题，训练数据集可以通过考察以前贷款者的贷款记录来构造。在下图所示的例子中，每条记录都包含贷款者的个人信息，以及贷款者是否拖欠贷款的类标号。

该分类问题的初始决策树只有一个结点，类标号为“拖欠货款者＝否”（见图a），意味大多数贷款者都按时归还贷款。然而，该树需要进一步的细化，因为根结点包含两个类的记录。根据“有房者”测试条件，这些记录被划分为较小的子集，如图b所示。接下来，对根结点的每个子女递归地调用Hunt算法。从下图给出的训练数据集可以看出，有房的贷款者都按时偿还了贷款，因此，根结点的左子女为叶结点，标记为“拖欠货款者二否”（见图b)。对于右子女，我们需要继续递归调用Hunt算法，直到所有的记录都属于同一个类为止。每次递归调用所形成的决策树显示在图c和图d中。

如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯一的类标号，则Hunt 算法是有效的。但是对于大多数实际情况，这些假设太苛刻了，因此，需要附加的条件来处理以下的情况：

1. 算法的第二步所创建的子女结点可能为空，即不存在与这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合，这种情形就可能发生。这时，该结点成为叶结点，类标号为其父结点上训练记录中的多数类。
2. 在第二步，如果与$D_{t}$相关联的所有记录都具有相同的属性值（目标属性除外），则不可能进一步划分这些记录。在这种情况下，该结点为叶结点，其标号为与该结点相关联的训练记录中的多数类。

此外，在上面这个算法过程中，你可能会疑惑：我们是依据什么原则来选取属性测试条件的，例如为什第一次选择“有房者”来作为测试条件。事实上，如果我们选择的属性测试条件不同，那么对于同一数据集来说所建立的决策树可能相差很大。

决策树归纳的设计问题

决策树归纳的学习算法必须解决下面两个问题。

1. 如何分裂训练记录？ 树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分成较小的子集。为了实现这个步骤，算法必须提供不同类型的属性制定测试条件的方法，并且评估每种测试条件的客观度量。

2. 如何停止分裂过程？ 需要有结束条件，以终止决策树的生长过程。一个可能的策略是分裂节点，直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。尽管两个结束条件对于结束决策树归纳算法都是充分的，但还可以使用其他的标准提前终止树的生长过程。

最佳度量选择

设$p(i|t)$表示给定节点t中属于类i的记录所占的比例，有时，我们省略节点t，直接用pi表示该比例。

选择最佳划分的度量通常是根据划分后子女节点不纯性的程度。不纯的程度越低，类分布就越倾斜。例如，类分布为(0,1)的节点具有零不纯性，而均衡分布(0.5,0.5)的节点具有最高的不纯性。不纯性度量的例子包括：

$$Entropy\left( t\right) =-\sum ^{c-1}_{i=0}p\left( i|t\right)\log _{2}p\left( i|t\right)$$ $$Gini(t)=1-\sum^{c-1}_{i=0}[p(i|t)]^{2}$$ $$Classification error(t)=1-max_{i}[p(i|t)]$$

其中c是类的个数，并且在计算熵时，$Olog_{2}0=0$。

三种不纯性度量方法的计算实例如下：

为了确定测试条件的效果，我们需要比较父节点的不纯程度和子女节点的不纯程度，他们的查越大，测试条件的效果就越好。增益$\Delta$是一种可以用来确定划分效果的标准：

$$\Delta=I(parent)-\sum^{k}_{j-1}\dfrac {N\left( v_{j}\right) }{N}I\left( v_{j}\right)$$

其中，$I(.)$是给定节点的不纯性度量，N是父节点上的记录总数，k是属性值的个数，$N(v_{j})$是与子女节点$v_{j}$想关联的记录个数。决策树归纳算法通常选择最大化增益等价于最小化子女节点的不纯性度量的加权平均值。最后当选择熵(entropy)作为增益的不纯性度量时，熵的差值就是所谓的信息增益(information gain)$\Delta_{info}$。

决策树归纳算法

剪枝

连续值与缺失值的处理

参考：