当前位置 博文首页 > jcLee95的博客：机器学习 - [源码实现决策树小专题]决策树学习中
JackLee
李俊才
CSDN：jcLee95
邮箱：291148484@163.com
在阅读本文之前，你应该掌握如何去建立一颗决策树。由于不同的决策树存储结构算法的实现细节上存在一定的差异，因此本文源代码实现对决策树的索引是基于我之前的一篇博文【决策树如何分裂以扩展节点】中所建立的决策树而实现的。
通过该博文我给出的源码运行后可以得到类似于这样一颗决策树：
# 训练参数：{features=features, max_depth=3, min_samples_split=1000, impurity_t='entropy',selector_t = 'majority_label'}
{
'depth': 1, # 这里是根节点，深度为1
'the_best_feature': 'blueTowersDestroyed', # 节点对应选出的最佳特征
'bestfeature_values': [0, 1, 2, 3, 4], # 最佳特征的所有取值，也就是'branchs'列表中的分支
'samples': 7903, # 当前节点处剩余的样本数，根节点处的样本数即测试数据集初始样本数
'label': 0, # 节点提前结束分裂（剪枝）时则作为叶节点将使用的标签
'branchs': [ # 分支列表，列表中的每个元素都是一个子节点
{
# 根节点的第 1 个子节点
'branch': 0, # 作为子节点来子父节点的分支（父节点最佳特征的一个取值）
'depth': 2,
'the_best_feature': 'redTowersDestroyed', # 最佳特征
'bestfeature_values': [0, 1, 2], # 最佳特征的所有取值（所有分支名）
'samples': 7533, # 节点处剩余样本数
'label': 0, # 节点提前结束分裂（剪枝）时则作为叶节点将使用的标签
'branchs': [ # 分支列表，列表中的每个元素都是一个子节点
{
'branch': 0,
'depth': 3,
'the_best_feature': 'brTotalGold',
'bestfeature_values': [0, 1, 2, 3, 4],
'samples': 7231,
'label': 0
},
{
'branch': 1,
'depth': 3,
'the_best_feature': 'brTotalGold',
'bestfeature_values': [0, 1, 2, 3, 4],
'samples': 279,
'label': 0
},
{
'branch': 2,
'depth': 3,
'the_best_feature': 'brTotalGold',
'brTotalGold',
'bestfeature_values': [0, 1],
'samples': 23,
'label': 0
}
]
},
{
# 根节点的第 2 个子节点
'branch': 1,
'depth': 2,
'the_best_feature': 'redTowersDestroyed',
'bestfeature_values': [0, 1, 2],
'samples': 340,
'label': 1
},
{
# 根节点的第 3 个子节点
'branch': 2,
'depth': 2,
'the_best_feature': 'redHeralds',
'bestfeature_values': [0, 1],
'samples': 23, 'label': 1
},
{
# 根节点的第 4 个子节点
'branch': 3,
'depth': 2,
'the_best_feature': 'blueWardsPlaced',
'bestfeature_values': [0, 1, 4],
'samples': 6,
'label': 1
},
{
# 根节点的第 5 个子节点
'branch': 4,
'depth': 2,
'the_best_feature': 'blueWardsPlaced',
'bestfeature_values': [1],
'samples': 1,
'label': 1
}
]
}
为了帮助读者理解，我绘制了该决策树的图形结构示意：
可以看到，在一颗树中节点的本质属性是作为父亲的分支。也就是父节点在依据最佳特征不同的特征值分支后，不同分支再次划分数据集的时候也可以选相同的最佳特征，毕竟同一次分支后的子数据集中拥有的特征类型都是一样的。
该树最简单的样子是这样（但是我们并没有记录成这样而是保留了更多信息，为以后可能的剪枝策略提供数据支持）：
[ # root
[0,1,2], # root的分支1
2, # root的分支2
3, # root的分支3
4 # root的分支4
]
即：
★ 先假设有一种情况：
建立决策树没有进行过任何剪枝，并且在每一次分裂中都训练到节点数据集中的所有标签恰好都能一致（只剩下最后一种标签）时。给定一条"测试集"数据并在再次恰好时在训练集中学到过的数据，分类器该如何给出这条数据的标签？
在数据集上做预测，这个数据集在我们的实验项目里也就是所谓的“测试集”，在测试集上做预测的目的是评估我们模型性能的好坏。而在实践项目里就是所谓的未知数据，从哲学上看是将我们的模型用于改造世界的过程。
计算机思维，就是所有事情都要一步一步地来实现，正如古语所云：天下大事必作于细。数据的预测也是如此，在某个数据集上进行预测，本质就是对数据集中的每一条数据逐一预测并依次记录下预测结果。
def predict(tree, test_datas):
'''
预测测试集中数据标签
使用它调用predict_one()对训练集中的每一条数据一次预测获取预测结果
Parameters
----------
tree: 基于字典的树形结构的一组数据，是我们训练好的决策树
test_datas: 测试数据集，包含多条待预测分类标签的数据。
'''
test_datas = np.array([test_datas]) if len(test_datas.shape) == 1 else test_datas
predict_list = [] # 训练结果容器
# 对每一条数据依次调用predict_one()方法预测并以及将结果装入训练结果容器
for one_test_data in test_datas:
one_pre_value = predict_one(tree, one_test_data) # 计算出一条数据的预测标签
predict_list.append(one_pre_value) # 将这一条数据的预测标签插入预测标签列表predict_list中
return np.array(predict_list)
class ClassificationTree(object):
... # 上面的内容请在关联博文中阅读，请尝试文中博文链接
def predict_one(self, tree, one_test_data):
"""
预测测试集中的一条数据
这个过程实际上就是基于节点的递归查询过程，在某个节点:
是否有分支：
- 有分支：必为非叶子节点：
使用测试集该节点对应的特征名索引出测试特征值，决定接下来查询的分支：
如测试数据的特征值在分支列表中，进入特征值决定的分支，递归以上过程。
如测试数据的特征值不在分支列表中，说明是训练时没有遇到过的新情况：
可以用投票器投出一个标签：即可以按照该节点数据集的标签集各标签占比投票一个，
也可以直接选该节点标签集中出现次数最多的标签作为投票结果。
- 无分支：必为叶子节点：
返回叶子节点处的标签值为预测结果。
Parameters
----------
tree： 递归过程中的树（除了根节点是原决策树，其它的节点都是其子树）；
one_test_data： 单条测试数据，本质是单条数据各个特征的取值。
Returns
-------
label, str 或 int、float等，为一条数据的标签
"""
# 先将测试的这单条数据与原始的特征名依次组合成字典以待查询
onetestdata_dict = dict(zip(self.features,list(one_test_data)))
the_best_feature = tree.get('the_best_feature') # 当前的节点（特征名）
branchs = tree.get('branchs') # 当前特征节点下树的所有分支，是一个包含分支的列表
if branchs == None: # 没有分支时，时叶子节点
return tree.get('label') # 返回叶子节点处的标签
else: # 否则是非叶子节点
node_values = tree['bestfeature_values'] # 获取该非叶子节点所有分支值
feature_value = onetestdata_dict.get(the_best_feature) # 这条数据中当前特征对应的标签值
if feature_value not in node_values: # 这条来自测试集的特征值没有在训练时出现过（未学习到的样本）
return tree.get('label') # 不得不终止递归预测，返回本节点处的预测标签
else: # 仍然在学习到的分支中
for i in range(len(branchs)):
if branchs[i].get('branch') == feature_value:
subtree = branchs[i] # 进入该分支（获取子节点）
return self.predict_one(subtree, one_features_data) # 递归预测之
def predict(self, test_datas):
assert len(test_datas.shape) == 1 or len(test_datas.shape) == 2 # 只能是1维或2维
'''
预测测试集中数据标签
使用它调用self.predict_one()对训练集中的每一条数据一次预测获取预测结果
'''
if len(test_datas.shape) == 1:
test_datas= np.array([test_datas])
tree = self.tree # 准备决策树
predict_list = []
