决策树算法是一个强大的预测方法，它非常流行。因为它们的模型能够让新手轻而易举地理解得和专家一样好，所以它们比较流行。同时，最终生成的决策树能够解释做出特定预测的确切原因，这使它们在实际运用中倍受亲睐。
同时，决策树算法也为更高级的集成模型（如 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 = 1group_1_class_1 = 0 / 2 = 0group_2_class_0 = 0 / 2 = 0group_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 datasetdef gini_index(groups, class_values):gini = 0.0for class_value in class_values:for group in groups:size = len(group)if size == 0:continueproportion = [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 datasetdef gini_index(groups, class_values):gini = 0.0for class_value in class_values:for group in groups:size = len(group)if size == 0:continueproportion = [row[-1] for row in group].count(class_value) / float(size)gini += (proportion * (1.0 - proportion))return gini# test gini valuesprint(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.00.0
2.2 创建分割点
一个分割点由数据集中的一个属性和一个阈值构成。
我们可以将其总结为对给定的属性确定一个分割数据的阈值。这是一种行之有效的分类数据的方法。
创建分割点包括三个步骤，其中第一步已在计算基尼系数的部分讨论过。余下两部分分别为：
1. 分割数据集。
2. 评价所有（可行的）分割点。
我们具体看一下每个步骤。
2.2.1 分割数据集
分割数据集意味着我们给定数据集某属性（或其位于属性列表中的下表）及相应阈值的情况下，将数据集分为两个部分。
一旦数据被分为两部分，我们就可以使用基尼系数来评估该分割的成本函数。
分割数据集需要对每行数据进行迭代，根据每个数据点相应属性的值与阈值的大小情况将该数据点放到相应的部分（对应树结构中的左叉与右叉）。
如下是一个名为 test_split() 的函数，它能实现上述功能：
# split a dataset based on an attribute and an attribute valuedef test_split(index, value, dataset):left, right = list(), list()for row in dataset:if row[index] < value:left.append(row)else:right.append(row)return left, right
代码还是很简单的。
注意，在代码中，属性值大于或等于阈值的数据点被分类到了右组中。
2.2.2 评价所有分割点
在基尼函数 gini_index() 和分类函数 test_split() 的帮助下，我们可以开始进行评估分割点的流程。
对给定的数据集，对每一个属性，我们都要检查所有的可能的阈值使之作为候选分割点。然后，我们将根据这些分割点的成本（cost）对其进行评估，最终挑选出最优的分割点。
当最优分割点被找到之后，我们就能用它作为我们决策树中的一个节点。
而这也就是所谓的穷举型贪心算法。
在该例中，我们将使用一个词典来代表决策树中的一个节点，它能够按照变量名储存数据。当选择了最优分割点并使用它作为树的新节点时，我们存下对应属性的下标、对应分割值及根据分割值分割后的两部分数据。
分割后地每一组数据都是一个更小规模地数据集（可以继续进行分割操作），它实际上就是原始数据集中地数据按照分割点被分到了左叉或右叉的数据集。你可以想象我们可以进一步将每一组数据再分割，不断循环直到建构出整个决策树。
如下是一个名为 get_split() 的函数，它能实现上述的步骤。你会发现，它遍历了每一个属性（除了类别值）以及属性对应的每一个值，在每次迭代中它都会分割数据并评估该分割点。
当所有的检查完成后，最优的分割点将被记录并返回。
# select the best split point for a datasetdef get_split(dataset):class_values = list(set(row[-1] for row in dataset))b_index, b_value, b_score, b_groups = 999, 999, 999, nonefor index in range(len(dataset[0])-1):for row in dataset:groups = test_split(index, row[index], dataset)gini = gini_index(groups, class_values)if gini < b_score:b_index, b_value, b_score, b_groups = index, row[index], gini, groupsreturn {'index':b_index, 'value':b_value, 'groups':b_groups}
我们能在一个小型合成的数据集上来测试这个函数以及整个数据集分割的过程。
x1 x2 y2.771244718 1.784783929 01.728571309 1.169761413 03.678319846 2.81281357 03.961043357 2.61995032 02.999208922 2.209014212 07.497545867 3.162953546 19.00220326 3.339047188 17.444542326 0.476683375 110.12493903 3.234550982 16.642287351 3.319983761 1
同时，我们可以使用不同颜色标记不同的类，将该数据集绘制出来。由图可知，我们可以从 x1 轴（即图中的 x 轴）上挑出一个值来分割该数据集。
范例所有的代码整合如下：
# split a dataset based on an attribute and an attribute valuedef test_split(index, value, dataset):left, right = list(), list()for row in dataset:if row[index] < value:left.append(row)else:right.append(row)return left, right# calculate the gini index for a split datasetdef gini_index(groups, class_values):gini = 0.0for class_value in class_values:for group in groups:size = len(group)if size == 0:continueproportion = [row[-1] for row in group].count(class_value) / float(size)gini += (proportion * (1.0 - proportion))return gini# select the best split point for a datasetdef get_split(dataset):class_values = list(set(row[-1] for row in dataset))b_index, b_value, b_score, b_groups = 999, 999, 999, nonefor index in range(len(dataset[0])-1):for row in dataset:groups = test_split(index, row[index], dataset)gini = gini_index(groups, class_values)print('x%d < %.3f gini=%.3f' % ((index+1), row[index], gini))if gini < b_score:b_index, b_value, b_score, b_groups = index, row[index], gini, groupsreturn {'index':b_index, 'value':b_value, 'groups':b_groups}dataset = [[2.771244718,1.784783929,0],[1.728571309,1.169761413,0],[3.678319846,2.81281357,0],[3.961043357,2.61995032,0],[2.999208922,2.209014212,0],[7.497545867,3.162953546,1],[9.00220326,3.339047188,1],[7.444542326,0.476683375,1],[10.12493903,3.234550982,1],[6.642287351,3.319983761,1]]split = get_split(dataset)print('split: [x%d < %.3f]' % ((split['index']+1), split['value']))
优化后的 get_split() 函数能够输出每个分割点及其对应的基尼系数。
运行如上的代码后，它将 print 所有的基尼系数及其选中的最优分割点。在此范例中，它选中了 x1<6.642 作为最终完美分割点（它对应的基尼系数为 0）。
x1< 2.771 gini=0.494x1 < 1.729 gini=0.500x1 < 3.678 gini=0.408x1 < 3.961 gini=0.278x1 < 2.999 gini=0.469x1 < 7.498 gini=0.408x1 < 9.002 gini=0.469x1 < 7.445 gini=0.278x1 < 10.125 gini=0.494x1 < 6.642 gini=0.000x2 < 1.785 gini=1.000x2 < 1.170 gini=0.494x2 < 2.813 gini=0.640x2 < 2.620 gini=0.819x2 < 2.209 gini=0.934x2 < 3.163 gini=0.278x2 < 3.339 gini=0.494x2 < 0.477 gini=0.500x2 < 3.235 gini=0.408x2 < 3.320 gini=0.469split: [x1 < 6.642]
既然我们现在已经能够找出数据集中最优的分割点，那我们现在就来看看我们能如何应用它来建立一个决策树。
2.3 生成树模型
创建树的根节点（root node）是比较方便的，可以调用 get_split() 函数并传入整个数据集即可达到此目的。但向树中增加更多的节点�...