R语言实战演练：“贪心的”决策树

本篇我们学习的分类算法是——

决策树。

这是一种“贪心”算法，以树状图为基础，不仅能较好的用于数据的分类，还能较好的实现预测。

决策树的算法有很多，如CHAID，CART，C5.0等，今天我们主要学习最常用的C5.0算法。

基本思想

简单的说，决策树就是建立一个树形结构模型，并依照该树形结构模型对未知分类的数据进行分类。

我们举一个简单的例子。如某大龄女青年在某相亲网站上进行海选，根据男青年的一系列特征决定是否见面，但因为资源太多而自己精力有限，所以肯定是要做出相亲决策的，她的决策如下所示：

可以看到，最终只有两个类别：见面或者不见面。该树形图是通过一系列变量构成的树搭建的。在该女青年眼中，年龄变量最为重要，首先大于35岁的男青年直接拉黑，在小于35岁中的年龄中进行选择。进一步，该女青年依次会考虑收入、学历和身高等，例如考虑和硕士以上学历的男青年见面，不和硕士以下学历同时身高不足180的男青年见面等等。

上述过程就是构建决策树的过程。与之类似，决策树算法首先会从树的第一个分支开始，选择一个分类能力最好的变量来把数据分为多个子集，由此形成了几个树的分支，接下来算法再对每个分支进行递归处理，选择下一个分类能力最好的变量进行分类，直到满足：

l 剩下的样本都是同一类或者；

l 没有备选变量或者；

l 树已经达到了预先定义的大小限制

总的来说，决策树学习通常包括以下两个个步骤：变量选择和决策树的生成，决策树剪枝。

变量选择和决策树生成

上面提到，决策树算法首先从树的第一个分支开始，选择一个“分类能力最好”的变量，那么什么叫做分类能力最好？ C5.0算法使用的是数据的信息量作为分类的准则。由于C5.0算法是C4.5算法的改进版，而C4.5又是基于ID3算法产生的。所以我们先看一下ID3算法的计算过程。

为了把过程讲清楚，我们还以上面的相亲的例子来进行说明，假设数据如下：

ID3算法使用了信息增益来进行度量。它借用了热力学中熵的概念来度量数据的纯度。在高中化学中，我们知道熵表示物质的混乱程度。在数据科学中，熵有同样的意思，熵的计算公式如下：

这里的m表示类别数目，Pi代表了第i类的比例。上述例子中因变量为是否相亲，其中5人未参与相亲，7人参加相亲，因变量的熵值为：

接下来我们要做的是，找出分类能力最好的自变量，即上图中的第一个节点变量。这需要计算在给定一个自变量的条件下，熵的变化大小。加入某一个自变量后，熵的计算公式为：

v表示自变量A的类别数，Pj为第j个类别的取值概率，最后一项为第J个类别下的熵值。我们发现，考虑年龄情况下，有8人小于35岁（6人相亲，2人未相亲），4人大于35岁（3人不相亲，1人相亲），熵的大小：

信息增益定义为引入自变量后两个熵值的差，此处为0.98-0.81=0.17。同理，我们还可以计算变量身高，年收入，学历的信息增益。经计算分别为0.043，0.043，0.11。结果表明自变量年龄的信息增益最大，因此以变量年龄作为第一个分支生成决策树，接下来步骤相同的，选择信息增益最大的变量形成下一个分支，直到形成最终的决策树。

ID3算法有很多缺点，最明显的是，它倾向于选择多分类变量，而且不能处理连续性变量和带有缺失值的样本。在此基础上，人们又提出了C4.5算法。与ID3不同的是，C4.5采用的是信息增益率来而不是信息增益来进行度量。具体而言，C4.5算法需要计算自变量的熵，信息增益率等于信息增益除以该自变量的熵。例如，自变量年龄的熵为：

自变量年龄的信息增益率为0.17/0.918=0.185。同样再计算其他自变量的信息增益率，选择信息增益率最大的自变量作为节点变量。

C5.0算法则是C4.5算法的商业版本，较C4.5算法提高了运算效率，它加入了boosting算法，从而使该算法更加智能化。

决策树剪枝

如果变量足够多，一棵决策树可能无限增长，树变得很大，最终每一条训练数据可能都会完全正确归类（机器学习中称为过拟合）。这并不是我们想要的，实际情况是，我们希望用较少的变量构建决策树模型，这样解释也比较方便，因此，需要对决策树进行修剪。

有两种决策树的修剪方法，一种是pre-pruning（先剪），即如果变量的数目达到了预定数目或者节点中样本数目少于一个给定值就停止。这种方法避免了不必要的工作，然而如果过早停止可能会错失一些细微但可能重要的模式。而post-pruning（后剪）则是先生成一棵大的树，然后再来修剪，其好处是算法能够查到所有重要的数据结构。C5.0算法的优点是可以自动修剪（总的来说，使用的还是后剪的策略），能自动选择相当的合理值，这对我们来说是很方便的。

决策树的优缺点

决策树很强大，但有其缺点，例如决策树是一种“贪心”算法，在选择节点过程中，都选择当前状态下的最优解，但是每一步最优并不能保证总体上是最优的，这样很容易导致模型过度匹配训练集，而缺乏与测试集匹配（过拟合问题）。

简而言之，决策树的优缺点可以概括如下：

其他决策树

C5.0算法采用的是信息量作为分类的规则，这并不代表决策树只有这一种算法。常见的决策树算法还有CHAID算法，CART算法等，感兴趣的同学可以参考其他书籍，三者的区别如下：

其他注意事项

上面提到的自变量都是分类变量，C5.0默认根据将分类自变量的每个类别作为一个分支，但是当自变量为连续型的时候怎么处理呢？C5.0算法会将该变量值从小到大排序，计算每个值作为分割点时的信息增益，选择信息增益最大的分割点，从而形成树的分支。

R实战

R语言中C50包中的C5.0函数可以实现C5.0算法，该函数的基本用法如下：

C5.0(x, y, ...)

其中x指定自变量（数据框或矩阵的形式），y指定因变量。

我们用经典的鸢尾花数据集来进行演示，该数据集可以从这里下载：

http://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data ，数据集包含150个样品和5个变量，前面4个变量分别表示花萼长度（cm），花萼宽度（cm），花瓣长度（cm），花瓣宽度（cm）,最后一个变量表示鸢尾花的种类，分别为Iris Setosa，Iris Versicolour，Iris Virginica。

现在我们希望依据前4个变量，建立决策树模型，来预测鸢尾花的种类。

首先，我们从网站读取数据，重命名变量名，同时将因变量转换为因子：

查看数据的描述性统计信息：

接下来，我们将数据集拆分为训练集和测试集，拆分比例为0.7。训练数据用于建立决策树模型，测试集用于模型评估

建立决策树模型

模型的汇总结果为

从结果可以看出，训练集中有105条观测，建立的决策树规则如下：

1、若变量petal length

2、 若若变量petal length>1.9，同时petal width

3、若若变量petal length>1.9，同时petal width>1.6，鸢尾花判为Iris-virginica类。

模型还输出了训练集的混淆矩阵，可见有3个样品被判错，误判率为2.9%。

我们建立的模型最主要是用来对未知样品进行分类，下面我们看一下，基于训练集构建的树模型对测试集的预测效果怎么样：

混淆矩阵及正确率输出结果如下：

3个样品被误判，分类正确率为93.3%，可见该模型预测效果较好。

下面是完整代码：

总结

决策树最突出的优点在于模型简单易懂，很好解释。但在实际使用中，也许并不会像上述过程这么简单。算法还会涉及很多参数的调整，如树的深度，节点数目选择等， C5.0函数也提供了很多参数来实现。这需要我们进一步学习。

注：文章授权转载自医学方，本文仅作学术分享，文章版权归原作者所有。

编辑|鸭血粉丝多多蒜