分而治之—利用决策树和规则进行分类

当在几个具有不同薪资和福利水平的工作机会之间做出选择时，很多人会从列出利弊开始，并基于简单的规则来排除选项。比如，“如果我上下班的时间超过1小时，那么我会不高兴”。通过这种方式，通过这种方式，预测一个人未来幸福的既复杂又困难的决定就可以简化为一系列简单的决定。在机器学习算法中，同样有两种算法可以根据简单的选择集做出复杂的决策，即决策树和规则学习，今天大家跟着图图一起来了解下这两种算法的概念及应用过程。

一、理解决策树

决策树学习是强大的分类器，他利用树形结构对特征和潜在结果之间的关系建立模型；如下图所示，从树干到树叶。例：预测工作机会是否被接受：

要考虑的工作机会从根节点开始，随后遍历决策节点，决策节点要求基于工作的属性做出选择，这些选择通过用指示决策潜在结果的分支来划分数据。决策树在叶节点终止，叶节点表示因一系列决策而采取的行动，即预期结果/终点事件。决策树算法的巨大好处是类似流程图的树形结构不一定专为学习算法内部使用。在模型被创建后，许多决策树算法以人类可读的形式输出产生的结构，这为模型如何以及为什么对干特定任务能否很好地运行提供了深人了解。

决策树的建立使用一种称为递归划分的探索法。这种方法也通常称为分而治之，因为它将数据分解成子集，然后反复分解成更小的子集，以此类推，直到当算法决定数据内的子集足够均匀或者另一种停止准则已经满足时，该过程才停止。停止的情况如下：

节点上所有的案例均属于同一类
没有剩余的特征来分辨案例之间的区别
决策树已经达到预先定义的大小限制

为了说明决策树的建立过程，我们考虑一个简单的例子。想象你在一家好莱坞电影制片厂工作，你的角色是决定工作室是否应该推进生产由有前途的新作家投递的剧本。你通过研究一个决策树算法来预测一部有潜力的电影是否会落入十分成功、受主流欢迎和票房崩溃这三大类中。为了建立决策树，你转向工作室的档案去研究导致公司最近30个版本的电影成功和失败的因素。发现电影的估计拍摄预算和一线明星的数量与电影成功密切相关，并制作散点图如下：

由上图可以看出，我们通过两个切分条件（明星数量和预算）将电影结果分为三类。如果需要我们可以继续分而治之，根据越来越具体的预算范围和名人数量划分数据，直到每一种当前被错误分类的值都分配到它自己微小的分区，被正确分类，但这种方式并不可取。过度具体的决策树并不能够更广泛的概括，为了避免过拟合，当每组中超过80%样本为同一类时，我们就停止分类。根据上述例子，我们可以构建决策树：

由于在现实世界的数据包含的不仅仅是两个特征，所以决策树很快就会变得比上图更复杂，会有更多的节点、分支和叶子。

二、C5.0决策树算法

C5.0决策树算法是最常用的决策树算法，所建立的决策树一般表现的与其他先进的模型几乎一样好。让我们来研究探索下该算法是如何运作的：

1. 选择最优的分割：

决策树面临的第一个挑战就是需要确定根据哪个特征进行分割。在前面的例子中，我们寻找一种方式来分割数据，以使得到的分区主要包含来源于一个单一类的案例。一个案例子集仅包含单个类的程度称为纯度，由单个类构成的任意子集都认为是纯的。C5.0算法在一个类值集合中使用熵，熵是一个从量化随机性或者无序性的信息论中借用的概念。具有高熵值的集合是非常多样化的，且提供的关于可能属于这些集合的其他项的信息很少，因为没有明显的共同性。决策树希望找到可以降低熵值的分割，最终增加组内的同质性。

通常情况下，熵以位(bit)为单位。如果只有两个可能的类，那么熵值的范围为0~1;对于n个类，熵值的范围为0~log2(n)。在每一个案例中，最小值表示样本是完全同质的，而最大值表示数据是尽可能多样化的，甚至没有组具有最小的相对多数。根据数学概念，熵定义为：

我们可以考察所有可能的两个类划分的熵。如果我们知道在一个类中案例的比例为x，那么在另一个类中的比例就是1-x。使用函数curve()我们就可以绘制关于x的所有可能值的熵的图形:

结果如下图所示：

如图所示，熵的峰值在x=0.5时，一个50-50分类导致最大熵值。当一个类相对于其他类越来越占据主导地位时，熵值会逐渐减少到0。

2. 信息增益：

为了使用熵来确定最优特征以进行分割，决策树计算由每个可能特征的分割所引起的同质性(均匀性)变化，该计算称为信息增益(informationgain)。对于特征F，信息增益的计算方法是分割前的数据分区(S)的熵值减去由分割产生的数据分区(S)的熵值，即 InfoGain(F)=Entropy(S1)-Entropy(S2)。

复杂之处在于，一次分割后，数据被划分到多个分区中，因此计算Entropy(S2)的函数需要考虑所有分区熵值的总和。这可以通过记录落人每一个分区的比例来计算每一个分区的权重，可以用如下的公式来表示:

简单地说，从一个分割得到的总熵值就是根据案例落入分区中的比例w加权的n个分区的熵值的总和。

•信息增益越高，根据某一特征分割后创建的分组越均匀

•如果信息增益为零，那么根据该特征进行分割后的熵值就不会减少

•最大信息增益等于分割前的熵值，这意味着分割后熵值为零，即分割结果是在完全同质的分组中

3. 修剪决策树：

一棵决策树可以继续无限制地增长，选择需要分割的特征，分割成越来越小的分区直到每一个案例完全归类，或者算法中再也没有可用于分割的特征。然而，如果决策树增长得过大，将使许多决策过于具体，模型将过度拟合训练数据。而修剪一棵决策树的过程涉及减小它的大小，以使决策树能更好地推广到未知数据。

解决这个问题的一种方法就是一旦决策树达到一定数量的决策，或者当决策节点仅含有少量的案例时，我们就停止树的增长，这叫作提前停止法。该方法的一个不足之处是没有办法知道决策树是否会错过细微但很重要的模式，这种细微模式只有决策树生长到足够大时才能学习到。

另一种方法称为后剪枝决策树法，如果一棵决策树生长得太大，就修剪叶节点将决策树减小到更合适的大小。该方法通常比预剪枝法更有效，因为如果没有事先生成决策树，那么确定一棵决策树生长的最优程度是相当困难的，而事后修剪决策树肯定可以使算法发现所有重要的数据结构。

4. C5.0算法：

C5.0算法的优点之一就是它可以自动修剪，即它关注许多决策，能自动使用相当合理的默认值。该算法的总体策略就是事后修剪决策树，它先生成一个过度拟合训练数据的大决策树，然后删除对分类误差影响不大的节点和分枝。在某些情况下，整个分枝会被进一步向上移动或者被一些简单的决策所取代，这两种移植分枝的过程分别称为子树提升和子树替换。该算法在R中可通过C5.0（）函数实现。

三、理解分类规则

分类规则代表的是逻辑if-else语句形式的知识，可用来对无标记的案例指定一个分类。无标记的案例依据前件和后件的概念来指定，而前件和后件就构成了一个假设，即“如果这种情况发生，那么那种情况就会发生。”一个简单的规则或许会这样描述:“如果硬盘发出咔嗒声，那么硬盘出现故障了。”前件是由特征值的特定组合构成的，当规则的条件被满足时，后件描述用来指定的分类值。

规则学习经常以一种类似于决策树学习的方式被使用。对于某些任务，规则学习相对于决策树有明显的优势。与决策树不同的是决策树必须从上至下通过一系列决策应用，而规则是可以被被阅读的命题，很像事实的陈述。

规则学习分类算法使用了一种称为独立而治之的探索法。这个过程包括确定训练数据中覆盖一个案例子集的规则，然后再从剩余的数据中分离出该子集。随着规则的增加，更多的数据子集会被分离，直到整个数据集都被覆盖，不再有剩余案例。可以理解为通过创建用于标识分类值的越来越具体的规则来考虑向下挖掘数据。我们来举一个例子，来判断一个动物是不是哺乳动物，如下图所示：