教程 | 从头开始：用Python实现决策树算法

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

同时，决策树算法也为更高级的集成模型（如 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）原则，所有的输入变量和所有可能的分割点都将被测试，并会基于它们成本函数的表现被评估。（译者注：下面简述对回归问题和分类问题常用的成本函数。）

• 回归问题：对落在分割点确定区域内所有的样本取误差平方和（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 基尼系数

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

数据集的分割点是关于输入中某个属性的分割。对数据集中某个样本而言，分割点会根据某阈值对该样本对应属性的值进行分类。他能根据训练集中出现的模式将数据分为两类。

基尼系数通过计算分割点创建的两个类别中数据类别的混杂程度，来表现分割点的好坏。一个完美的分割点对应的基尼系数为 0（译者注：即在一类中不会出现另一类的数据，每个类都是「纯」的），而最差的分割点的基尼系数则为 1.0（对于二分问题，每一类中出现另一类数据的比例都为 50%，也就是数据完全没能被根据类别不同区分开）。

下面我们通过一个具体的例子来说明如何计算基尼系数。

我们有两组数据，每组有两行。第一组数据中所有行都属于类别 0（Class 0），第二组数据中所有的行都属于类别 1（Class 1）。这是一个完美的分割点。

首先我们要按照下式计算每组数据中各类别数据的比例：

proportion = count(class_value) / count(rows)

那么，对本例而言，相应的比例为：

group_1_class_0 = 2 / 2 = 1

group_1_class_1 = 0 / 2 = 0

group_2_class_0 = 0 / 2 = 0

group_2_class_1 = 2 / 2 = 1

基尼系数按照如下公式计算：

gini_index = sum(proportion * (1.0 - proportion))

将本例中所有组、所有类数据的比例带入到上述公式：

gini_index = (group_1_class_0 * (1.0 - group_1_class_0))

(group_1_class_1 * (1.0 - group_1_class_1))

(group_2_class_0 * (1.0 - group_2_class_0))

(group_2_class_1 * (1.0 - group_2_class_1))

化简，得：

gini_index = 0 0 0 0 = 0

如下是一个叫做 gini_index() 的函数，它能够计算给定数据的基尼系数（组、类别都以列表（list）的形式给出）。其中有些算法鲁棒性检测，能够避免对空组除以 0 的情况。

# Calculate the Gini index for a split dataset

def gini_index(groups, class_values):

gini = 0.0

for class_value in class_values:

for group in groups:

size = len(group)

if size == 0:

continue

proportion = [row[-1] for row in group].count(class_value) / float(size)

gini = (proportion * (1.0 - proportion))

return gini

我们可以根据上例来测试该函数的运行情况，也可以测试最差分割点的情况。完整的代码如下：

# Calculate the Gini index for a split dataset

def gini_index(groups, class_values):

gini = 0.0

for class_value in class_values:

for group in groups:

size = len(group)

if size == 0:

continue

proportion = [row[-1] for row in group].count(class_value) / float(size)

gini = (proportion * (1.0 - proportion))

return gini

# test Gini values

print(gini_index([[[1, 1], [1, 0]], [[1, 1], [1, 0]]], [0, 1]))

print(gini_index([[[1, 0], [1, 0]], [[1, 1], [1, 1]]], [0, 1]))

运行该代码，将会打印两个基尼系数，其中第一个对应的是最差的情况为 1.0，第二个对应的是最好的情况为 0.0。

1.0

0.0

2.2 创建分割点

一个分割点由数据集中的一个属性和一个阈值构成。

我们可以将其总结为对给定的属性确定一个分割数据的阈值。这是一种行之有效的分类数据的方法。

创建分割点包括三个步骤，其中第一步已在计算基尼系数的部分讨论过。余下两部分分别为：

1. 分割数据集。

2. 评价所有（可行的）分割点。

我们具体看一下每个步骤。

2.2.1 分割数据集

分割数据集意味着我们给定数据集某属性（或其位于属性列表中的下表）及相应阈值的情况下，将数据集分为两个部分。

一旦数据被分为两部分，我们就可以使用基尼系数来评估该分割的成本函数。

分割数据集需要对每行数据进行迭代，根据每个数据点相应属性的值与阈值的大小情况将该数据点放到相应的部分（对应树结构中的左叉与右叉）。

如下是一个名为 test_split() 的函数，它能实现上述功能：

# Split a dataset based on an attribute and an attribute value

def test_split(index, value, dataset):

left, right = list(), list()

for row in dataset:

if row[index]