参与：沈泽江、吴攀

决策树算法是一个强大的预测方法，它非常流行。因为它们的模型能够让新手轻而易举地理解得和专家一样好，所以它们比较流行。同时，最终生成的决策树能够解释做出特定预测的确切原因，这使它们在实际运用中倍受亲睐。

同时，决策树算法也为更高级的集成模型（如 bagging、随机森林及 gradient boosting）提供了基础。

在这篇教程中，你将会从零开始，学习如何用 Python 实现《Classification And Regression Tree algorithm》中所说的内容。

在学完该教程之后，你将会知道：

如何计算并评价数据集中地候选分割点（Candidate Split Point）

如何在决策树结构中排分配这些分割点

如何在实际问题中应用这些分类和回归算法

一、概要

本节简要介绍了关于分类及回归树（Classification and Regression Trees）算法的一些内容，并给出了将在本教程中使用的钞票数据集（Banknote Dataset）。

1.1 分类及回归树

分类及回归树（CART）是由 Leo Breiman 提出的一个术语，用来描述一种能被用于分类或者回归预测模型问题的回归树算法。

我们将在本教程中主要讨论 CART 在分类问题上的应用。

二叉树（Binary Tree）是 CART 模型的代表之一。这里所说的二叉树，与数据结构和算法里面所说的二叉树别无二致，没有什么特别之处（每个节点可以有 0、1 或 2 个子节点）。

每个节点代表在节点处有一个输入变量被传入，并根据某些变量被分类（我们假定该变量是数值型的）。树的叶节点（又叫做终端节点，Terminal Node）由输出变量构成，它被用于进行预测。

在树被创建完成之后，每个新的数据样本都将按照每个节点的分割条件，沿着该树从顶部往下，直到输出一个最终决策。

创建一个二元分类树实际上是一个分割输入空间的过程。递归二元分类（Recursive Binary Splitting）是一个被用于分割空间的贪心算法。这实际上是一个数值过程：当一系列的输入值被排列好后，它将尝试一系列的分割点，测试它们分类完后成本函数（Cost Function）的值。

有最优成本函数（通常是最小的成本函数，因为我们往往希望该值最小）的分割点将会被选择。根据贪心法（greedy approach）原则，所有的输入变量和所有可能的分割点都将被测试，atv，并会基于它们成本函数的表现被评估。（译者注：下面简述对回归问题和分类问题常用的成本函数。）

回归问题：对落在分割点确定区域内所有的样本取误差平方和（Sum Squared Error）。

分类问题：一般采用基尼成本函数（Gini Cost Function），它能够表明被分割之后每个节点的纯净度（Node Purity）如何。其中，节点纯净度是一种表明每个节点分类后训练数据混杂程度的指标。

分割将一直进行，直到每个节点（分类后）都只含有最小数量的训练样本或者树的深度达到了最大值。

1.2 Banknote 数据集

Banknote 数据集，需要我们根据对纸币照片某些性质的分析，来预测该钞票的真伪。

该数据集中含有 1372 个样本，每个样本由 5 个数值型变量构成。这是一个二元分类问题。如下列举 5 个变量的含义及数据性质：

1. 图像经小波变换后的方差（Variance）（连续值）

2. 图像经小波变换后的偏度（Skewness）（连续值）

3. 图像经小波变换后的峰度（Kurtosis）（连续值）

4. 图像的熵（Entropy）（连续值）

5. 钞票所属类别（整数，离散值）

如下是数据集前五行数据的样本。

3.6216,8.6661,-2.8073,-0.44699,0

　　4.5459,8.1674,-2.4586,-1.4621,0

　　3.866,-2.6383,1.9242,0.10645,0

　　3.4566,9.5228,-4.0112,-3.5944,0

　　0.32924,-4.4552,4.5718,-0.9888,0

　　4.3684,9.6718,-3.9606,-3.1625,0

　　使用零规则算法（Zero Rule Algorithm）来预测最常出现类别的情况（译者注：也就是找到最常出现的一类样本，然后预测所有的样本都是这个类别），对该问的基准准确大概是 50%。

你可以在这里下载并了解更多关于这个数据集的内容：UCI Machine Learning Repository。

请下载该数据集，放到你当前的工作目录，并重命名该文件为 data_banknote_authentication.csv。

二、教程

本教程分为五大部分：

1. 对基尼系数（Gini Index）的介绍

2.（如何）创建分割点

3.（如何）生成树模型

4.（如何）利用模型进行预测

5. 对钞票数据集的案例研究

这些步骤能帮你打好基础，直播，让你能够从零实现 CART 算法，并能将它应用到你子集的预测模型问题中。

2.1 基尼系数

基尼系数是一种评估数据集分割点优劣的成本函数。