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

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

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

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

让我们开始吧。

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

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

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

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

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

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

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

二、教程 本教程分为五大部分：

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)

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

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

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

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

化简，得：

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. 分割数据集。

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

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

# 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 ] < 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 dataset
def get_split ( dataset ) :
class_values = list ( set ( row [ - 1 ] for row in dataset ) )
b_index , b_value , b_score , b_groups = 999 , 999 , 999 , None
for 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 , groups
return { 'index' : b_index , 'value' : b_value , 'groups' : b_groups }

我们能在一个小型合成的数据集上来测试这个函数以及整个数据集分割的过程。

同时，我们可以使用不同颜色标记不同的类，将该数据集绘制出来。由图可知，我们可以从X1轴（即图中的X轴）上挑出一个值来分割该数据集。

范例所有的代码整合如下：

# 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] < value:

left.append(row)

else:

right.append(row)

return left, right

# 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

# Select the best split point for a dataset

def get_split(dataset):

class_values = list(set(row[-1] for row in dataset))

b_index, b_value, b_score, b_groups = 999, 999, 999, None

for 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, groups

return {'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）。

既然我们现在已经能够找出数据集中最优的分割点，那我们现在就来看看我们能如何应用它来建立一个决策树。
2.3 生成树模型

创建树的根节点（root node）是比较方便的，可以调用 get_split() 函数并传入整个数据集即可达到此目的。但向树中增加更多的节点则比较有趣。
建立树结构主要分为三个步骤：

1. 创建终端节点

2. 递归地分割

3. 建 构整棵树

2.3.1 创建终端节点

我们需要决定何时停止树的「增长」。
我们可以用两个条件进行控制：树的深度和每个节点分割后的数据点个数。
最大树深度：这代表了树中从根结点算起节点数目的上限。一旦树中的节点树达到了这一上界，则算法将会停止分割数据、增加新的节点。更神的树会更为复杂，也更有可能过拟合训练集。
最小节点记录数：这是某节点分割数据后分个部分数据个数的最小值。一旦达到或低于该最小值，则算法将会停止分割数据、增加新的节点。将数据集分为只有很少数据点的两个部分的分割节点被认为太具针对性，并很有可能过拟合训练集。
这两个方法基于用户给定的参数，参与到树模型的构建过程中。
此外，还有一个情况。算法有可能选择一个分割点，分割数据后所有的数据都被分割到同一组内（也就是左叉、右叉只有一个分支上有数据，另一个分支没有）。在这样的情况下，因为在树的另一个分叉没有数据，我们不能继续我们的分割与添加节点的工作。
基于上述内容，我们已经有一些停止树「增长」的判别机制。当树在某一结点停止增长的时候，该节点被称为终端节点，并被用来进行最终预测。
预测的过程是通过选择组表征值进行的。当遍历树进入到最终节点分割后的数据组中，算法将会选择该组中最普遍出现的值作为预测值。
如下是一个名为 to_terminal() 的函数，对每一组收据它都能选择一个表征值。他能够返回一系列数据点中最普遍出现的值。

# Create a terminal node value
def to_terminal ( group ) :
outcomes = [ row [ - 1 ] for row in group ]
return max ( set ( outcomes ) , key = outcomes . count )

2.3.2 递归分割

在了解了如何及何时创建终端节点后，我们现在可以开始建立树模型了。
建立树地模型，需要我们对给定的数据集反复调用如上定义的 get_split() 函数，不断创建树中的节点。
在已有节点下加入的新节点叫做子节点。对树中的任意节点而言，它可能没有子节点（则该节点为终端节点）、一个子节点（则该节点能够直接进行预测）或两个子节点。在程序中，在表示某节点的字典中，我们将一棵树的两子节点命名为 left 和 right。
一旦一个节点被创建，我们就可以递归地对在该节点被分割得到的两个子数据集上调用相同的函数，来分割子数据集并创建新的节点。
如下是一个实现该递归过程的函数。它的输入参数包括：某一节点（node）、最大树深度（max_depth）、最小节点记录数（min_size）及当前树深度（depth）。
显然，一开始运行该函数时，根节点将被传入，当前深度为1。函数的功能分为如下几步：
首先，该节点分割的两部分数据将被提取出来以便使用，同时数据将被在节点中删除（随着分割工作的逐步进行，之前的节点不需要再使用相应的数据）。
然后，我们将会检查该节点的左叉及右叉的数据集是否为空。如果是，则其将会创建一个终端节点。
同时，我们会检查是否到达了最大深度。如果是，则其将会创建一个终端节点。
接着，我们将对左子节点进一步操作。若该组数据个数小于阈值，则会创建一个终端节点并停止进一步操作。否则它将会以一种深度优先的方式创建并添加节点，直到该分叉达到底部。
对右子节点同样进行上述操作，不断增加节点直到达到终端节点。

# Create child splits for a node or make terminal

def split(node, max_depth, min_size, depth):

left, right = node['groups']

del(node['groups'])

# check for a no split

if not left or not right:

node['left'] = node['right'] = to_terminal(left + right)

return

# check for max depth

if depth >= max_depth:

node['left'], node['right'] = to_terminal(left), to_terminal(right)

return

# process left child

if len(left) <= min_size:

node['left'] = to_terminal(left)

else:

node['left'] = get_split(left)

split(node['left'], max_depth, min_size, depth+1)

# process right child

if len(right) <= min_size:

node['right'] = to_terminal(right)

else:

node['right'] = get_split(right)

split(node['right'], max_depth, min_size, depth+1)

# Build a decision tree
def build_tree ( train , max_depth , min_size ) :
root = get_split ( dataset )
split ( root , max_depth , min_size , 1 )
return root

我们可以在如上所述的合成数据集上测试整个过程。如下是完整的案例。
在其中还包括了一个 print_tree() 函数，它能够递归地一行一个地打印出决策树的节点。经过它打印的不是一个明显的树结构，但它能给我们关于树结构的大致印象，并能帮助决策。

# 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 ] < value :
left . append ( row )
else :
right . append ( row )
return left , right
# 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
# Select the best split point for a dataset
def get_split ( dataset ) :
class_values = list ( set ( row [ - 1 ] for row in dataset ) )
b_index , b_value , b_score , b_groups = 999 , 999 , 999 , None
for 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 , groups
return { 'index' : b_index , 'value' : b_value , 'groups' : b_groups }
# Create a terminal node value
def to_terminal ( group ) :
outcomes = [ row [ - 1 ] for row in group ]
return max ( set ( outcomes ) , key = outcomes . count )
# Create child splits for a node or make terminal
def split ( node , max_depth , min_size , depth ) :
left , right = node [ 'groups' ]
del ( node [ 'groups' ] )
# check for a no split
if not left or not right :
node [ 'left' ] = node [ 'right' ] = to_terminal ( left + right )
return
# check for max depth
if depth >= max_depth :
node [ 'left' ] , node [ 'right' ] = to_terminal ( left ) , to_terminal ( right )
return
# process left child
if len ( left ) <= min_size :
node [ 'left' ] = to_terminal ( left )
else :
node [ 'left' ] = get_split ( left )
split ( node [ 'left' ] , max_depth , min_size , depth + 1 )
# process right child
if len ( right ) <= min_size :
node [ 'right' ] = to_terminal ( right )
else :
node [ 'right' ] = get_split ( right )
split ( node [ 'right' ] , max_depth , min_size , depth + 1 )
# Build a decision tree
def build_tree ( train , max_depth , min_size ) :
root = get_split ( dataset )
split ( root , max_depth , min_size , 1 )
return root
# Print a decision tree
def print_tree ( node , depth = 0 ) :
if isinstance ( node , dict ) :
print ( '%s[X%d < %.3f]' % ( ( depth* ' ' , ( node [ 'index' ] + 1 ) , node [ 'value' ] ) ) )
print_tree ( node [ 'left' ] , depth + 1 )
print_tree ( node [ 'right' ] , depth + 1 )
else :
print ( '%s[%s]' % ( ( depth* ' ' , node ) ) )
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 ] ]
tree = build_tree ( dataset , 1 , 1 )
print_tree ( tree )

在运行过程中，我们能修改树的最大深度，并在打印的树上观察其影响。
当最大深度为1时（即调用 build_tree() 函数时第二个参数），我们可以发现该树使用了我们之前发现的完美分割点（作为树的唯一分割点）。该树只有一个节点，也被称为决策树桩。

[X1 < 6.642]

[0]

[1]

当最大深度加到2时，我们迫使输算法不需要分割的情况下强行分割。结果是，X1 属性在左右叉上被使用了两次来分割这个本已经完美分割的数据。

[X1 < 6.642]

[X1 < 2.771]

[0]

[0]

[X1 < 7.498]

[1]

[1]

最后，我们可以试试最大深度为3的情况：

[X1 < 6.642]

[X1 < 2.771]

[0]

[X1 < 2.771]

[0]

[0]

[X1 < 7.498]

[X1 < 7.445]

[1]

[1]

[X1 < 7.498]

[1]

[1]

这些测试表明，我们可以优化代码来避免不必要的分割。请参见延伸章节的相关内容。
现在我们已经可以（完整地）创建一棵决策树了，那么我们来看看如何用它来在新数据上做出预测吧。
2.4 利用模型进行预测
使用决策树模型进行决策，需要我们根据给出的数据遍历整棵决策树。
与前面相同，我们仍需要使用一个递归函数来实现该过程。其中，基于某分割点对给出数据的影响，相同的预测规则被应用到左子节点或右子节点上。
我们需要检查对某子节点而言，它是否是一个可以被作为预测结果返回的终端节点，又或是他是否含有下一层的分割节点需要被考虑。
如下是实现上述过程的名为 predict() 函数，你可以看到它是如何处理给定节点的下标与数值的。

# Make a prediction with a decision tree

def predict(node, row):

if row[node['index']] < node['value']:

if isinstance(node['left'], dict):

return predict(node['left'], row)

else:

return node['left']

else:

if isinstance(node['right'], dict):

return predict(node['right'], row)

else:

return node['right']

接着，我们使用合成的数据集来测试该函数。如下是一个使用仅有一个节点的硬编码树（即决策树桩）的案例。该案例中对数据集中的每个数据进行了预测。

# Make a prediction with a decision tree
def predict ( node , row ) :
if row [ node [ 'index' ] ] < node [ 'value' ] :
if isinstance ( node [ 'left' ] , dict ) :
return predict ( node [ 'left' ] , row )
else :
return node [ 'left' ]
else :
if isinstance ( node [ 'right' ] , dict ) :
return predict ( node [ 'right' ] , row )
else :
return node [ 'right' ]
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 ] ]
# predict with a stump
stump = { 'index' : 0 , 'right' : 1 , 'value' : 6.642287351 , 'left' : 0 }
for row in dataset :
prediction = predict ( stump , row )
print ( 'Expected=%d, Got=%d' % ( row [ - 1 ] , prediction ) )

运行该例子，它将按照预期打印出每个数据的预测结果。

现在，我们不仅掌握了如何创建一棵决策树，同时还知道如何用它进行预测。那么，我们就来试试在实际数据集上来应用该算法吧。
2.5 对钞票数据集的案例研究

该节描述了在钞票数据集上使用了 CART 算法的流程。
第一步是导入数据，并转换载入的数据到数值形式，使得我们能够用它来计算分割点。对此，我们使用了辅助函数 load_csv() 载入数据及 str_column_to_float() 以转换字符串数据到浮点数。
我们将会使用5折交叉验证法（5-fold cross validation）来评估该算法的表现。这也就意味着，对一个记录，将会有1273/5=274.4 即270个数据点。我们将会使用辅助函数 evaluate_algorithm() 来评估算法在交叉验证集上的表现，用 accuracy_metric() 来计算预测的准确率。
完成的代码如下：

# CART on the Bank Note dataset

from random import seed

from random import randrange

from csv import reader

# Load a CSV file

def load_csv(filename):

file = open(filename, "rb")

lines = reader(file)

dataset = list(lines)

return dataset

# Convert string column to float

def str_column_to_float(dataset, column):

for row in dataset:

row[column] = float(row[column].strip())

# Split a dataset into k folds

def cross_validation_split(dataset, n_folds):

dataset_split = list()

dataset_copy = list(dataset)

fold_size = len(dataset) / n_folds

for i in range(n_folds):

fold = list()

while len(fold) < fold_size:

index = randrange(len(dataset_copy))

fold.append(dataset_copy.pop(index))

dataset_split.append(fold)

return dataset_split

# Calculate accuracy percentage

def accuracy_metric(actual, predicted):

correct = 0

for i in range(len(actual)):

if actual[i] == predicted[i]:

correct += 1

return correct / float(len(actual)) * 100.0

# Evaluate an algorithm using a cross validation split

def evaluate_algorithm(dataset, algorithm, n_folds, *args):

folds = cross_validation_split(dataset, n_folds)

scores = list()

for fold in folds:

train_set = list(folds)

train_set.remove(fold)

train_set = sum(train_set, [])

test_set = list()

for row in fold:

row_copy = list(row)

test_set.append(row_copy)

row_copy[-1] = None

predicted = algorithm(train_set, test_set, *args)

actual = [row[-1] for row in fold]

accuracy = accuracy_metric(actual, predicted)

scores.append(accuracy)

return scores

# 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] < value:

left.append(row)

else:

right.append(row)

return left, right

# 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

# Select the best split point for a dataset

def get_split(dataset):

class_values = list(set(row[-1] for row in dataset))

b_index, b_value, b_score, b_groups = 999, 999, 999, None

for 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, groups

return {'index':b_index, 'value':b_value, 'groups':b_groups}

# Create a terminal node value

def to_terminal(group):

outcomes = [row[-1] for row in group]

return max(set(outcomes), key=outcomes.count)

# Create child splits for a node or make terminal

def split(node, max_depth, min_size, depth):

left, right = node['groups']

del(node['groups'])

# check for a no split

if not left or not right:

node['left'] = node['right'] = to_terminal(left + right)

return

# check for max depth

if depth >= max_depth:

node['left'], node['right'] = to_terminal(left), to_terminal(right)

return

# process left child

if len(left) <= min_size:

node['left'] = to_terminal(left)

else:

node['left'] = get_split(left)

split(node['left'], max_depth, min_size, depth+1)

# process right child

if len(right) <= min_size:

node['right'] = to_terminal(right)

else:

node['right'] = get_split(right)

split(node['right'], max_depth, min_size, depth+1)

# Build a decision tree

def build_tree(train, max_depth, min_size):

root = get_split(dataset)

split(root, max_depth, min_size, 1)

return root

# Make a prediction with a decision tree

def predict(node, row):

if row[node['index']] < node['value']:

if isinstance(node['left'], dict):

return predict(node['left'], row)

else:

return node['left']

else:

if isinstance(node['right'], dict):

return predict(node['right'], row)

else:

return node['right']

# Classification and Regression Tree Algorithm

def decision_tree(train, test, max_depth, min_size):

tree = build_tree(train, max_depth, min_size)

predictions = list()

for row in test:

prediction = predict(tree, row)

predictions.append(prediction)

return(predictions)

# Test CART on Bank Note dataset

seed(1)

# load and prepare data

filename = 'data_banknote_authentication.csv'

dataset = load_csv(filename)

# convert string attributes to integers

for i in range(len(dataset[0])):

str_column_to_float(dataset, i)

# evaluate algorithm

n_folds = 5

max_depth = 5

min_size = 10

scores = evaluate_algorithm(dataset, decision_tree, n_folds, max_depth, min_size)

print('Scores: %s' % scores)

print('Mean Accuracy: %.3f%%' % (sum(scores)/float(len(scores))))

上述使用的参数包括：max_depth 为 5，min_size 为 10。经过了一些实现后，我们确定了上述 CART 算法的使用的参数，但这不代表所使用的参数就是最优的。
运行该案例，它将会print出对每一部分数据的平均分类准确度及对所有部分数据的平均表现。
从数据中你可以发现，CART 算法选择的分类设置，达到了大约 83% 的平均分类准确率。其表现远远好于只有约 50% 正确率的零规则算法（ Zero Rule algorithm）。

1. 算法调参（Algorithm Tuning）：在钞票数据集上使用的 CART 算法未被调参。你可以尝试不同的参数数值以获取更好的更优的结果。

2. 交叉熵（Cross Entropy）：另一个用来评估分割点的成本函数是交叉熵函数（对数损失）。你能够尝试使用该成本函数作为替代。

3. 剪枝（Tree Pruning）：另一个减少在训练过程中过拟合程度的重要方法是剪枝。你可以研究并尝试实现一些剪枝的方法。

4. 类数据集（Categorical Dataset）：在上述例子中，其树模型被设计用于解决数值型或有序数据。你可以尝试修改树模型（主要修改分割的属性，用等式而非排序的形式），使之能够应对分类型的数据。

5. 回归问题（Regression）：可以通过使用不同的成本函数及不同的创建终端节点的方法，来让该模型能够解决一个回归问题。

6. 更多数据集：你可以尝试将该算法用于 UCI Machine Learning Repository 上其他的数据集。

四、回顾
在该教程中，你学会了如何从零开始在Python中实现决策树算法。
具体而言，你学会了：

1. 如何对训练集选择分割点并做出评价。

2. 如何递归地建立一个分割点决策树。

3. 如何应用 CART 算法到一个实际分类预测建模问题。