​ 机器学习（九） ——构建决策树（离散特征值）

机器学习（九）

——构建决策树（离散特征值）

（原创内容，转载请注明来源，谢谢）

一、概述

1、概念

决策树，这个概念是一个很常见的概念，应该是机器学习中最好理解的一个算法。决策树是在已知训练结果的情况下，进行的分类。因此，决策树是一种监督学习方法。

根据分类的条件不同，决策树又可以分为离散特征值下的分类和连续特征值下的分类。

离散特征值，是每个特征值只有有限个结果，例如yes和no、0和1，或者多个结果如0、1、2、3，如下图所示：

连续特征值，是特征值是在一片连续的范围内，如0~10，这种情况下涵盖了0.0001等无穷多个数字的情况，如下图所示：

图形中，每个叶子节点表示分类的一个分支，即特征值按如此分类最终走向的结果。

连续特征值情况下，需要涉及到特征值的划分等，比较复杂，本文讨论的是离散特征值情况下的决策树分类。

2、比较其他算法

1）决策树和其他算法比起来，一大的优势在于，可以直观的看出样本每一列特征值的含义，而不仅仅是0、1这种数字形式。

2）决策树对中间值的缺失不敏感，且可以处理不相关特征数据。

3、决策树算法

决策树算法的过程，主要包括：决策树的构建、决策树的图形化绘制、决策树的存储与实际应用。每一部分都包含很多内容，故分三篇文章讨论。本文讨论的是决策树的构建。

4、构建决策树

构建决策树，步骤包括计算香农熵、递归选取最优划分特征切分数据集、递归构造决策树，下面逐一讨论。

决策树最主要的一点在于划分数据集。在决策树中，每个新的样本需要经过n次比较得出分类结果，不同的划分方式，会导致最终需要比较的次数有很大差异。因此，需要选取最优化的划分数据集的方式。

构造决策树，主要就是在得到最优化的划分方式，并且生成决策树。本文的划分方式采用ID3算法，另外比较流行的还有C4.5、CART等，后面学到连续特征值时，会采用CART算法进行回归。这里讨论ID3算法情况下的构造决策树。

二、测试构造决策树的数据集

为了便于理解，先把此次的测试数据集给出，如下：

其中，dataSet是样本集，每个样本的最后一个元素是分类的结果；labels是特征值含义集，每个元素对应样本的一个特征值。

三、香农熵

划分数据集的最大原则，是使数据由无序变得有序。香浓提出了熵的概念，熵表示信息的混乱程度，熵越大表示信息越杂乱，分类的目的是获取香农熵尽量小的结果。因此，首先需要一个计算香农熵代码。

熵定义信息的期望值，某个信息x的期望值公式：l(xi) = -log2 ，其中p(x)是x在这个信息中出现的概率。

总的香农熵，则是每个期望值乘以对应概率的和：

计算过程，即递归计算该数据集中，分类结果的熵。其中，概率计算，采用分别记录该分类数据集下，结果的类别数、每个类别结果出现的次数，并用这个次数除以总的结果数，得到该结果出现的概率。

代码如下：

另外，除了用熵，也可以用基尼不纯度来衡量数据集的无序程度，方法是从一个数据中随机选取子项，度量其被错误分到其他组的概率。这里不采用基尼不纯度方式。

四、给定特征划分数据集

这么做的目的是为下面递归获取最优划分服务。

根据给定的数据集、特征元素的在样本的下标、用于划分的特征值，遍历整个数据集，把该特征符合条件的样本都提取出来，并且删除掉这个特征，以便后面继续划分。

代码如下：

五、选择最好的划分方式

这里给定一个数据集，返回当前数据集的最优划分的特征值，实际上也是在给后面构建决策树时递归调用此方法服务。

选择最好的划分方式的算法，就是一个求最小值的算法，遍历数据集特征结果种类，并且去重，再遍历这个结果，计算出总的熵，并且比较得到最小的熵，则此时的特征值的下标就是最优的划分方式。

代码如下：

六、多数表决法

这个算法也是为构建决策树服务。当特征值都已经使用到划分决策树，但是仍有部分类别不相同，则采用此方法，将样本中出现次数最多的分类结果，作为最终的结果。

代码如下：

七、构建决策树

构建决策树，需要递归上面的划分。

1、递归结束的条件

递归结束的条件有两个：

1）类别完全相同，即本次递归下，样本集中的所有元素，分类结果都是同样的。

2）没有更多的特征值进行分类，则采用上述的多数表决法。

2、从特征值含义数组中获取当前最好的分类方式对应的值，并且删掉该特征值。

3、得到列表包含的所有属性，并且递归构造树。

代码如下：

八、测试

九、构造决策树小结

在理解构造决策树的过程中，我一开始有几个理解偏差，导致编码的时候遇到问题，分享如下：

1、labels

labels表示的是特征值的含义，而不是分类结果的含义，这个一定要搞清楚。我一开始就是这里理解错了，所以在尝试用不同的数据集来测试构造决策树的结果时，发现老是报labels数组下标超出。然后多次翻书查看，搞明白了含义。

2、构造的目的

一定要搞明白构造决策树的目的，这个是我在理解过程的另一大问题。其目的不是为了把样本进行分类，因为样本其实已经有分类结果了，再分类没有意义。构造决策树的目的，是通过现有的样本，构造出一个树，后面再有新的数据集且没有分类结果，可以直接拿这个树，通过样本特征的比对，得到结果。

因此，构造决策树的过程中，只需要记录分类的方式即可，并不需要得到分类结果。

——written by linhxx 2018.01.07