决策树的构造
我的微信公众号： s406205391; 欢迎大家一起学习，一起进步！！！
有一个二十个问题的小游戏，游戏规则很简单：参与游戏的一方在脑海了想某个事物，其他参与者向他提出问题，只允许提问20个问题，问题的答案也只能用对和错来回答。问问题的人通过推断分解，逐步缩小猜测事物的范围。决策树的工作原理与20个问题类似，用户输入一系列数据，然后给出游戏的答案。
我们经常使用决策树处理分类问题，近来的调查表明决策树也是最经常使用的数据挖掘算法。决策树流行的很重要的原因就是他的工作很简单，不需要了解机器学习的知识。下图所示的流程图就是一个决策树。图中构造了一个假象的邮件分类系统，它首先检测发送邮件的域名地址。如果地址为：myEmployer.com，则将其放在“无聊时需要阅读的邮件”中，如果邮件不是来自这个域名，则检查邮件内容里是否包含单词曲棍球，如果包含则将邮件归类到“需要及时处理的朋友邮件”，如果不包含，则将邮件归类到“无需阅读的垃圾邮件”。
决策树的主要优势再与数据形式非常容易理解。决策树的一个重要任务是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，这些机器根据数据集创建规则的过程，就是机器学习的过程。专家系统中经常使用决策树，而且决策树给出的结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。
决策树的一般流程
决策树的优点是计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相干特征数据。缺点是可能会产生过度匹配问题。适用数据为数值型和标称型。
在构造决策树时，首先需要解决的问题是，当前数据集上，哪个特征在划分数据集中起决定性作用。为了找到决定性特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。
决策树构建的伪代码如下：
检测数据集中的每个子项是否属于同一分类：
if so return 类标签
else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
递归调用本函数，并增加返回结果到分支节点中
return 分支节点
为了解决寻找划分数据集的最好特征问题，就需要引入信息增益的概念。
信息增益
划分数据的最大原则是：将无序的数据变得更加有序。在划分数据集之前之后信息发生的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。这就得引入熵的概念。
集合信息的度量方式成为香农熵或者简称为熵。熵定义为信息的期望值。如果待分类的事物可能划分在多个分类之中，则符号xi的信息定义为：
其中p(xi)是选择该分类的概率。那么其所有类别所有可能值包含的信息期望值的计算公式就为：
其中，n是分类数目。
我们首先定义一个函数，来计算数据集的香农熵
from math import log
def calc_shannon(data_set):
"""calculation shannon entropy"""
# 默认数据集的最后一列是标签列
feat_vec = [f[-1] for f in data_set]
label_counts = Counter(feat_vec)
# 使用信息期望值的计算公式，计算香农熵
prob_list = [value / len(data_set) for key, value in label_counts.items()]
shannon_ent = sum([-(prob * log(prob, 2)) for prob in prob_list])
return shannon_ent
熵越高，则混合的数据也越多。在得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集。
另一个度量集合无需程度的方法是基尼不纯度（Gini impurity），简单地说就是冲一个数据集中随机选取子项，度量其被错误风雷刀其他分组的概率。
划分数据集
分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以便判断当前是否正确地划分了数据集。下面的函数将对每个特征划分数据集的结果计算一次信息熵， 然后判断按照那个特征划分数据集是最好的方式。
def split_data_set(data_set, axis, value):
"""按照给定特征划分数据集
从待划分的数据集中，返回特征值列为value的数据集
:param data_set: 待划分的数据集
:param axis: 划分数据集的特征所在列的索引
:param value: 需要返回的特征值
"""
ret_data_set = [feat_vec[: axis] + feat_vec[axis+1:] for feat_vec in data_set if feat_vec[axis] == value]
return ret_data_set
选择最好的数据集划分方式
在了解了如何划分数据集合求信息熵之后，就可以通过信息增益来选择最好的数据集划分方式了。首先，我们会求整个数据集的原始信息熵，然后遍历没一个特征值，对特征值下的所有特征求一遍信息熵，其和就是该特征值的信息熵。原始信息熵与该特征值的信息熵的差就是该特征值的信息增益。信息增益越大，则该特征值越好划分。
def choose_best_feature_to_split(data_set):
"""选择最好的数据划分方式
函数调用需要满足要求：
1. 数据必须是由一种列表元素组成的列表，且所有的列表元素都具有相同的数据长度
2. 数据的最后一列或者每个实例的最后一个元素时当前实例的类别标签
"""
num_feature = len(data_set[0]) - 1 # 确定特征的数量
base_ent = calc_shannon(data_set) # 计算原始的信息熵
# 遍历所有的特征以及特征值，确定最好的划分数据集的特征
best_info_gain = 0
best_feature = -1
for i in range(num_feature):
new_ent = 0
# 计算该特征的信息熵
for value in set([ex[i] for ex in data_set]):
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set) / len(data_set)
new_ent += prob * calc_shannon(sub_data_set)
# 计算信息增益，确定最好的特征
info_gain = base_ent - new_ent
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature
递归构建决策树
现在，我们可以通过前面的函数，来构建决策树了。其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。如果遍历完所有属性，但是类标签仍然不是唯一的，那么就采用多数表决的方法，决定该叶子节点的分类。
def create_tree(data_set, labels):
"""构建决策树
递归函数终止条件：
1. 遍历完所有的特征，返回数量最多的标签作为叶子节点
2. 所有的类标签完全相同，直接返回包含唯一类别的分组
"""
# 递归函数终止条件
class_list = [ex[-1] for ex in data_set]
if len(set(class_list)) == 1:
return class_list[0]
if len(data_set[0]) == 1:
return Counter(class_list).most_common(1)[0][0]
# 寻找最好的特征属性
best_feat = choose_best_feature_to_split(data_set)
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
del(labels[best_feat])
# 递归构建决策树
for value in set([ex[best_feat] for ex in data_set]):
sub_labels = labels[:]
my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
return my_tree
使用决策树执行分类
依靠训练数据构造了决策树之后，就可以将它用于实际数据的分类了。下面的函数，可以根据输入的测试数据集构建决策树，并预测测试向量的所属分类
def classify(input_tree, feat_labels, test_vec):
"""使用决策树进行分类"""
first_str = list(input_tree.keys())[0]
second_dict = input_tree[first_str]
feat_index = feat_labels.index(first_str)
class_label = "unknown"
for key in second_dict.keys():
if test_vec[feat_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_label = classify(second_dict[key], feat_labels, test_vec)
else:
class_label = second_dict[key]
return class_label
示例： 使用决策树预测隐形眼镜类型
接下来，我们通过一个例子讲解如何预测患者需要佩戴的隐形眼镜类型。数据集见lenses.txt(提取码为：uhww)。数据一共分为五列，前四列为特征列，最后一列是分类标签。
#!/usr/bin/env python3
# coding: utf-8
# Author：Shen Yi
# Date ：2020/2/15 2:35
"""机器学习实战 决策树的python实现"""
from collections import Counter
from math import log
def calc_shannon(data_set):
"""计算香农熵"""
feat_vec = [f[-1] for f in data_set]
label_counts = Counter(feat_vec)
prob_list = [value / len(data_set) for key, value in label_counts.items()]
shannon_ent = sum([-(prob * log(prob, 2)) for prob in prob_list])
return shannon_ent
def split_data_set(data_set, axis, value):
"""按照给定特征划分数据集"""
ret_data_set = [feat_vec[: axis] + feat_vec[axis+1:] for feat_vec in data_set if feat_vec[axis] == value]
return ret_data_set
def choose_best_feature_to_split(data_set):
"""选择最好的数据划分方式"""
num_feature = len(data_set[0]) - 1
base_ent = calc_shannon(data_set)
best_info_gain = 0
best_feature = -1
for i in range(num_feature):
new_ent = 0
for value in set([ex[i] for ex in data_set]):
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set) / len(data_set)
new_ent += prob * calc_shannon(sub_data_set)
info_gain = base_ent - new_ent
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature
def create_tree(data_set, labels):
"""构建决策树"""
class_list = [ex[-1] for ex in data_set]
if len(set(class_list)) == 1:
return class_list[0]
if len(data_set[0]) == 1:
return Counter(class_list).most_common(1)[0][0]
best_feat = choose_best_feature_to_split(data_set)
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
del(labels[best_feat])
for value in set([ex[best_feat] for ex in data_set]):
sub_labels = labels[:]
my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), sub_labels)
return my_tree
def classify(input_tree, feat_labels, test_vec):
"""使用决策树进行分类"""
first_str = list(input_tree.keys())[0]
second_dict = input_tree[first_str]
feat_index = feat_labels.index(first_str)
class_label = "unknown"
for key in second_dict.keys():
if test_vec[feat_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_label = classify(second_dict[key], feat_labels, test_vec)
else:
class_label = second_dict[key]
return class_label
def demo_predict_glass():
fr = open('data\\Ch03\\lenses.txt')
lenses = list(map(lambda line: line.strip().split('\t'), fr))
lenses_label = ['age', 'prescript', 'astigmatic', 'tearRate']
lenses_tree = create_tree(lenses, lenses_label)
test_age = input("age: ")
test_prescript = input("prescript: ")
test_astigmatic = input("astigmatic: ")
test_tear_rate = input("tearRate: ")
lenses_label = ['age', 'prescript', 'astigmatic', 'tearRate']
class_label = classify(lenses_tree, lenses_label, [test_age, test_prescript, test_astigmatic, test_tear_rate])
print(class_label)
if __name__ == '__main__':
demo_predict_glass()
