选自MachineLearningMastery作者：JasonBrownlee机器之心编译参与：沈泽江、吴攀
决策树算法是一个强大的预测方法，它非常流行。因为它们的模型能够让新手轻而易举地理解得和专家一样好，所以它们比较流行。同时，最终生成的决策树能够解释做出特定预测的确切原因，这使它们在实际运用中倍受亲睐。
同时，决策树算法也为更高级的集成模型（如bagging、随机森林及gradientboosting）提供了基础。
在这篇教程中，你将会从零开始，学习如何用Python实现《ClassificationAndRegressionTreealgorithm》中所说的内容。
在学完该教程之后，你将会知道：
如何计算并评价数据集中地候选分割点（CandidateSplitPoint）如何在决策树结构中排分配这些分割点如何在实际问题中应用这些分类和回归算法
一、概要
本节简要介绍了关于分类及回归树（ClassificationandRegressionTrees）算法的一些内容，并给出了将在本教程中使用的钞票数据集（BanknoteDataset）。
1.1分类及回归树
分类及回归树（CART）是由LeoBreiman提出的一个术语，用来描述一种能被用于分类或者回归预测模型问题的回归树算法。
我们将在本教程中主要讨论CART在分类问题上的应用。
二叉树（BinaryTree）是CART模型的代表之一。这里所说的二叉树，与数据结构和算法里面所说的二叉树别无二致，没有什么特别之处（每个节点可以有0、1或2个子节点）。
每个节点代表在节点处有一个输入变量被传入，并根据某些变量被分类（我们假定该变量是数值型的）。树的叶节点（又叫做终端节点，TerminalNode）由输出变量构成，它被用于进行预测。
在树被创建完成之后，每个新的数据样本都将按照每个节点的分割条件，沿着该树从顶部往下，直到输出一个最终决策。
创建一个二元分类树实际上是一个分割输入空间的过程。递归二元分类（RecursiveBinarySplitting）是一个被用于分割空间的贪心算法。这实际上是一个数值过程：当一系列的输入值被排列好后，它将尝试一系列的分割点，测试它们分类完后成本函数（CostFunction）的值。
有最优成本函数（通常是最小的成本函数，因为我们往往希望该值最小）的分割点将会被选择。根据贪心法（greedyapproach）原则，所有的输入变量和所有可能的分割点都将被测试，并会基于它们成本函数的表现被评估。（译者注：下面简述对回归问题和分类问题常用的成本函数。）
回归问题：对落在分割点确定区域内所有的样本取误差平方和（SumSquaredError）。分类问题：一般采用基尼成本函数（GiniCostFunction），它能够表明被分割之后每个节点的纯净度（NodePurity）如何。其中，节点纯净度是一种表明每个节点分类后训练数据混杂程度的指标。
分割将一直进行，直到每个节点（分类后）都只含有最小数量的训练样本或者树的深度达到了最大值。
1.2Banknote数据集
Banknote数据集，需要我们根据对纸币照片某些性质的分析，来预测该钞票的真伪。
该数据集中含有个样本，每个样本由5个数值型变量构成。这是一个二元分类问题。如下列举5个变量的含义及数据性质：
1.图像经小波变换后的方差（Variance）（连续值）
2.图像经小波变换后的偏度（Skewness）（连续值）
3.图像经小波变换后的峰度（Kurtosis）（连续值）
4.图像的熵（Entropy）（连续值）
5.钞票所属类别（整数，离散值）
如下是数据集前五行数据的样本。
3.,8.,-2.,-0.,0
4.,8.,-2.,-1.,0
3.,-2.,1.,0.,0
3.,9.,-4.,-3.,0
0.,-4.,4.,-0.,0
4.,9.,-3.,-3.,0
使用零规则算法（ZeroRuleAlgorithm）来预测最常出现类别的情况（译者注：也就是找到最常出现的一类样本，然后预测所有的样本都是这个类别），对该问的基准准确大概是50%。
你可以在这里下载并了解更多关于这个数据集的内容：UCIMachineLearningRepository。
请下载该数据集，放到你当前的工作目录，并重命名该文件为data_banknote_authentication.csv。
二、教程
本教程分为五大部分：
1.对基尼系数（GiniIndex）的介绍
2.（如何）创建分割点
3.（如何）生成树模型
4.（如何）利用模型进行预测
5.对钞票数据集的案例研究
这些步骤能帮你打好基础，让你能够从零实现CART算法，并能将它应用到你子集的预测模型问题中。
2.1基尼系数
基尼系数是一种评估数据集分割点优劣的成本函数。
数据集的分割点是关于输入中某个属性的分割。对数据集中某个样本而言，分割点会根据某阈值对该样本对应属性的值进行分类。他能根据训练集中出现的模式将数据分为两类。
基尼系数通过计算分割点创建的两个类别中数据类别的混杂程度，来表现分割点的好坏。一个完美的分割点对应的基尼系数为0（译者注：即在一类中不会出现另一类的数据，每个类都是「纯」的），而最差的分割点的基尼系数则为1.0（对于二分问题，每一类中出现另一类数据的比例都为50%，也就是数据完全没能被根据类别不同区分开）。
下面我们通过一个具体的例子来说明如何计算基尼系数。
我们有两组数据，每组有两行。第一组数据中所有行都属于类别0（Class0），第二组数据中所有的行都属于类别1（Class1）。这是一个完美的分割点。
首先我们要按照下式计算每组数据中各类别数据的比例：
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的情况。
#CalculatetheGiniindexforasplitdatasetdefgini_index(groups,class_values):gini=0.0forclass_valueinclass_values:forgroupingroups:size=len(group)ifsize==0:continueproportion=[row[-1]forrowingroup].count(class_value)/float(size)gini+=(proportion*(1.0-proportion))returngini
我们可以根据上例来测试该函数的运行情况，也可以测试最差分割点的情况。完整的代码如下：
#CalculatetheGiniindexforasplitdatasetdefgini_index(groups,class_values):gini=0.0forclass_valueinclass_values:forgroupingroups:size=len(group)ifsize==0:continueproportion=[row[-1]forrowingroup].count(class_value)/float(size)gini+=(proportion*(1.0-proportion))returngini#testGinivaluesprint(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()的函数，它能实现上述功能：
#Splitadatasetbasedonanattributeandanattributevaluedeftest_split(index,value,dataset):left,right=list(),list()forrowindataset:ifrow[index]value:left.append(row)else:right.append(row)returnleft,right
代码还是很简单的。
注意，在代码中，属性值大于或等于阈值的数据点被分类到了右组中。
2.2.2评价所有分割点
在基尼函数gini_index()和分类函数test_split()的帮助下，我们可以开始进行评估分割点的流程。
对给定的数据集，对每一个属性，我们都要检查所有的可能的阈值使之作为候选分割点。然后，我们将根据这些分割点的成本（cost）对其进行评估，最终挑选出最优的分割点。
当最优分割点被找到之后，我们就能用它作为我们决策树中的一个节点。
而这也就是所谓的穷举型贪心算法。
在该例中，我们将使用一个词典来代表决策树中的一个节点，它能够按照变量名储存数据。当选择了最优分割点并使用它作为树的新节点时，我们存下对应属性的下标、对应分割值及根据分割值分割后的两部分数据。
分割后地每一组数据都是一个更小规模地数据集（可以继续进行分割操作），它实际上就是原始数据集中地数据按照分割点被分到了左叉或右叉的数据集。你可以想象我们可以进一步将每一组数据再分割，不断循环直到建构出整个决策树。
如下是一个名为get_split()的函数，它能实现上述的步骤。你会发现，它遍历了每一个属性（除了类别值）以及属性对应的每一个值，在每次迭代中它都会分割数据并评估该分割点。
当所有的检查完成后，最优的分割点将被记录并返回。
#Selectthebestsplitpointforadatasetdefget_split(dataset):class_values=list(set(row[-1]forrowindataset))b_index,b_value,b_score,b_groups=,,,Noneforindexinrange(len(dataset[0])-1):forrowindataset:groups=test_split(index,row[index],dataset)gini=gini_index(groups,class_values)ifginib_score:b_index,b_value,b_score,b_groups=index,row[index],gini,groupsreturn{index:b_index,value:b_value,groups:b_groups}
我们能在一个小型合成的数据集上来测试这个函数以及整个数据集分割的过程。
X1X2Y2.........2089222..497573.........
同时，我们可以使用不同颜色标记不同的类，将该数据集绘制出来。由图可知，我们可以从X1轴（即图中的X轴）上挑出一个值来分割该数据集。
范例所有的代码整合如下：
#Splitadatasetbasedonanattributeandanattributevaluedeftest_split(index,value,dataset):left,right=list(),list()forrowindataset:ifrow[index]value:left.append(row)else:right.append(row)returnleft,right#CalculatetheGiniindexforasplitdatasetdefgini_index(groups,class_values):gini=0.0forclass_valueinclass_values:forgroupingroups:size=len(group)ifsize==0:continueproportion=[row[-1]forrowingroup].count(class_value)/float(size)gini+=(proportion*(1.0-proportion))returngini#Selectthebestsplitpointforadatasetdefget_split(dataset):class_values=list(set(row[-1]forrowindataset))b_index,b_value,b_score,b_groups=,,,Noneforindexinrange(len(dataset[0])-1):forrowindataset:groups=test_split(index,row[index],dataset)gini=gini_index(groups,class_values)print(X%d%.3fGini=%.3f%((index+1),row[index],gini))ifginib_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.,1.,0],[1.,1.,0],[3.,2.,0],[3.,2.,0],[2.208922,2.,0],[7.49757,3.,1],[9.,3.,1],[7.,0.,1],[10.,3.,1],[6.,3.,1]]split=get_split(dataset)print(Split:[X%d%.3f]%((split[index]+1),split[value]))
优化后的get_split()函数能够输出每个分割点及其对应的基尼系数。
运行如上的代码后，它将print所有的基尼系数及其选中的最优分割点。在此范例中，它选中了X16.作为最终完美分割点（它对应的基尼系数为0）。
X12.Gini=0.X11.Gini=0.X13.Gini=0.X13.Gini=0.X12.Gini=0.X17.Gini=0.X19.Gini=0.X17.Gini=0.X.Gini=0.X16.Gini=0.X21.Gini=1.X21.Gini=0.X22.Gini=0.X22.Gini=0.X22.Gini=0.X23.Gini=0.X23.Gini=0.X20.Gini=0.X23.Gini=0.X23.Gini=0.Split:[X16.]
既然我们现在已经能够找出数据集中最优的分割点，那我们现在就来看看我们能如何应用它来建立一个决策树。
2.3生成树模型
创建树的根节点（rootnode）是比较方便的，可以调用get_split()函数并传入整个数据集即可达到此目的。但向树中增加更多的节点则比较有趣。
建立树结构主要分为三个步骤：
1.创建终端节点
2.递归地分割
3.建构整棵树
2.3.1创建终端节点
我们需要决定何时停止树的「增长」。
我们可以用两个条件进行控制：树的深度和每个节点分割后的数据点个数。
最大树深度：这代表了树中从根结点算起节点数目的上限。一旦树中的节点树达到了这一上界，则算法将会停止分割数据、增加新的节点。更神的树会更为复杂，也更有可能过拟合训练集。
最小节点记录数：这是某节点分割数据后分个部分数据个数的最小值。一旦达到或低于该最小值，则算法将会停止分割数据、增加新的节点。将数据集分为只有很少数据点的两个部分的分割节点被认为太具针对性，并很有可能过拟合训练集。
这两个方法基于用户给定的参数，参与到树模型的构建过程中。
此外，还有一个情况。算法有可能选择一个分割点，分割数据后所有的数据都被分割到同一组内（也就是左叉、右叉只有一个分支上有数据，另一个分支没有）。在这样的情况下，因为在树的另一个分叉没有数据，我们不能继续我们的分割与添加节点的工作。
基于上述内容，我们已经有一些停止树「增长」的判别机制。当树在某一结点停止增长的时候，该节点被称为终端节点，并被用来进行最终预测。
预测的过程是通过选择组表征值进行的。当遍历树进入到最终节点分割后的数据组中，算法将会选择该组中最普遍出现的值作为预测值。
如下是一个名为to_terminal()的函数，对每一组收据它都能选择一个表征值。他能够返回一系列数据点中最普遍出现的值。
#Createaterminalnodevaluedefto_terminal(group):out