1.6.2　基于数据的决策树

1.6.2.1　数据与信息

图1.13　数据和信息

数据和信息（图1.13）是相似的概念，但它们不是一回事。数据和信息的主要区别在于数据是“部分”，而信息是“整体”。

数据一词的定义简单来说就是“事实和数字”。每一个数据都是一个简单的事实，本身并没有什么意义。数据这个词可以用来表示单一的事实，也可以表示一个事实的集合。它来自拉丁语datum，意思是“给定的东西”。datum一词在技术上仍是数据的正确单数形式，但很少使用。

什么是信息？信息的定义很简单，就是“收到或得到的消息或知识”。信息是我们对事实进行处理、解释和组织后的结果。这个词来自拉丁语īnfōrmātiō，意思是“构成或概念”。

数据和信息这两个术语在不同的语境中有不同的含义，它们之间的主要区别是：

●数据是事实的集合，而信息是如何在上下文中理解这些事实。

●数据是无组织的，而信息是有结构的或有组织的。

●信息依赖于数据。

在计算机的世界里，数据是输入，或者说我们告诉计算机做什么或保存什么。信息是输出，或者说计算机如何解释数据并向我们显示所要求的行动或指令。

数据通常存在于信息之前，但很难说哪个更有用。例如，如果信息的处理或组织方式有偏差或不正确，它就没有用，但数据仍然有用。

数据挖掘是将原始数据转化为有用信息的过程。自信息时代开始以来，数据的积累和存储变得更加容易和廉价。遗憾的是，随着机器可读数据量的增加，理解和利用这些数据的能力却没有跟上其增长的步伐。

数据挖掘依赖于有效的数据收集、存储和处理。数据挖掘除了包含原始分析步骤外，还涉及数据管理、数据预处理、模型和推理、度量、复杂度、结构后处理、可视化和在线更新等方面。实际的数据挖掘任务是对大量数据进行半自动或自动分析，以提取以前未知的、有趣的模式，如数据分组（聚类分析）、异常数据（异常检测）和依赖关系（关联规则挖掘、顺序模式挖掘）等。这些模式可以被视为对输入数据的一种总结，并可用于进一步的分析或者用于机器学习和预测。

数据分析和数据挖掘的区别在于，数据分析用来检验数据集上的模型和假设，比如分析营销活动的效果，而不管数据量有多大；相反，数据挖掘是利用机器学习和统计模型来发现大量数据中的秘密或隐藏模式。

从数据中人工提取模式的历史已经有几个世纪了。早期识别数据模式的方法包括贝叶斯定理（18世纪）和回归分析（19世纪）。计算机技术的普及和日益强大极大地提高了数据收集、存储和操作能力。随着数据集的规模和复杂程度的增加，直接的“人工”数据分析越来越多地被间接的、自动化的数据处理所取代，这得益于计算机科学特别是机器学习领域的发现，如神经网络、聚类分析、遗传算法（20世纪50年代）、决策树和决策规则（20世纪60年代）以及支持向量机（20世纪90年代）。数据挖掘是应用这些方法的过程，它弥补了从应用统计学和人工智能（通常提供数学背景）到数据库管理的差距，利用数据库中数据存储和索引的方式，更有效地执行实际的学习和发现算法，使这种方法能够应用于越来越大的数据集。

数据挖掘主要可以分为两大类：面向验证的（验证用户的假设）和面向发现的（自主发现新的规则和模式）。而后者可以进一步细分为两个子类：描述方法和预测方法。描述方法侧重于理解基础数据的运行方式，如聚类、摘要或可视化等；而预测方法则旨在建立一个行为模型，用于获取新的和未见过的样本，并预测与样本相关的一个或多个变量的值。然而，一些面向预测的方法也可以促进对数据的理解。预测方法主要有分类和回归两种。回归方法将输入空间映射到一个实值域，例如，可以根据给定特征预测对某一产品的需求。分类方法则将输入空间映射到预定义的类别中，例如，用于将抵押贷款消费者分为好的（按时全额还贷）和坏的（延迟还贷），将电子邮件分配到“垃圾邮件”或“非垃圾邮件”，根据观察到的病人特征（性别、血压、是否存在某些症状等）进行诊断。

决策树是一种预测模型，可以用来表示分类方法和回归方法。当决策树用于分类任务时，被称为分类树；用于回归任务时，被称为回归树。分类树用于根据对象或实例的属性值（如颜色、温度、湿度或风力）将其分为一组预定义的类或行为（如打网球/不打网球），常用于金融、营销、工程和医学等应用领域，但并不试图取代现有的传统统计方法。回归树，顾名思义，就是用树模型解决回归问题，每一片叶子都输出一个预测值。回归问题多用来预测一个具体的数值，如房价、气温、PM2.5值等。

下面，我们基于Hunt算法，看看简单的分类决策树的构建和应用。

1.6.2.2　基于Hunt算法的分类决策树的简单示例

Hunt算法是许多决策树算法的基础，反映了决策树“分而治之”的学习策略和基本思想。

从原则上讲，给定一个训练数据集，通过各种属性的组合能够构造出指数级数量的决策树，找出最佳的决策树在计算上是不可行的，所以决策树是复杂度和效率之间权衡的产物。

如今实用的决策树都采用贪心算法策略。在选择划分的数据属性时，采用一系列局部最优决策来构造决策树。其中的基础就是Hunt算法。在Hunt算法中，通过递归的方式建立决策树。主要的操作包括如下两个通用过程：

1）假设数据集D中的全部数据都属于一个类y，并将该节点标记为节点y。

2）假设数据集D中包括属于多个类的训练数据，并选择一个属性将训练数据划分为较小的子集。对于根据所选属性设定的测试条件的每一个输出，创建一个子节点，并依据测试结果将D中的记录数据分布到各个子节点中，然后对每一个子节点反复执行这两个过程。对子节点的子节点依旧递归调用这两个过程，直至最后停止。

我们使用表1.3中的数据集对决策树基础算法的过程做详细说明。

表1.3　关于是否购买汽车的数据

图1.14　划分年龄属性的决策树示意图

首先，数据集D内的样本不属于同一个类别，且没有在任一属性A上取值相同。所以，我们需要选择划分属性来作为决策树的节点向下展开。如图1.14所示，我们选择年龄属性作为根节点，并根据年龄属性的不同取值（20~30、30~40、40~50）将样本划分为三部分。

根据年龄属性进行划分后，每个取值将原数据集D划分为相应的子集，每个子集拥有各自的正类样本和负类样本。对于每个子集，我们可以在剩余属性中继续选择划分属性，将决策树向下延伸。同时，在年龄属性的子节点中，我们发现30~40路径对应的子样本全为正类，那么我们就可以将该子样本节点标记为正类“是”，且将该子节点设置为叶子节点，不再向下延伸。

重复上述操作，如图1.15、图1.16和图1.17所示。图1.17就是我们在该数据集下最终构造出的决策树。

图1.15　进一步划分贷款属性的决策树示意图

图1.16　进一步划分汽车价格属性的决策树示意图

图1.17　最终构造出的决策树

对于构造及应用分类决策树的整个过程，我们可以用图1.18来描述。首先，使用训练数据集，通过引入对应的决策树分类算法来进行训练，得到决策树模型，也就是前面步骤中得到的每个叶子节点都代表一个分类的决策树。接着，我们可以使用得到的模型来进行预测，即预测给定的数据对应的类别。

图1.18　决策树的训练及预测过程示意图

对于决策树的预测，我们使用测试集的数据，如图1.18所示。对于其中每一条要预测的数据，我们从年龄根节点属性出发搜索决策树，如图1.19所示。

图1.19　搜索决策树过程的开始阶段

根据年龄属性的取值（如图1.20所示），进入子节点是否贷款属性，如图1.21和图1.22所示。

图1.20　搜索决策树的根节点——年龄属性

图1.21　根据年龄属性值进入下一分支

图1.22　搜索决策树的下一节点——是否贷款属性

在是否贷款属性的判断中，依照同样的方法寻找下一个子节点。由于到达的子节点为类型节点（即叶子节点），故决策树搜索结束，得到该条数据所属的最终类型为“是”。如图1.23、图1.24所示。

图1.23　根据是否贷款属性值进入下一分支

图1.24　获得该条数据的最终预测结果