决策树的构建设计并用Graphviz实现决策树的可视化

最近打算系统学习下机器学习的基础算法，避免眼高手低，决定把常用的机器学习基础算法都实现一遍以便加深印象。本文为这系列博客的第一篇，关于决策树(Decision Tree)的算法实现，文中我将对决策树种涉及到的算法进行总结并附上自己相关的实现代码。所有算法代码以及用于相应模型的训练的数据都会放到GitHub上。

本文中我将一步步通过MLiA的隐形眼镜处方数集构建决策树并使用Graphviz将决策树可视化。

决策树学习

决策树学习是根据数据的属性采用树状结构建立的一种决策模型，可以用此模型解决分类和回归问题。常见的算法包括 CART, ID3, C4.5等。我们往往根据数据集来构建一棵决策树，他的一个重要任务就是为了数据中所蕴含的知识信息，并提取出一系列的规则，这些规则也就是树结构的创建过程就是机器学习的过程。

决策树的结构

以下面一个简单的用于是否买电脑预测的决策树为例子，树中的内部节点表示某个属性，节点引出的分支表示此属性的所有可能的值，叶子节点表示最终的判断结果也就是类型。

借助可视化工具例如Graphviz，matplotlib的注解等等都可以讲我们创建的决策树模型可视化并直接被人理解，这是贝叶斯神经网络等算法没有的特性。

决策树算法

决策树算法主要是指决策树进行创建中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯. 最大的原则就是: 将无序的数据变得更加有序。

这里总结下三个常用的方法:
1.信息增益
2.增益比率
3.基尼不纯度

信息增益

这里涉及到了信息论中的一些概念：某个事件的信息量，信息熵，信息增益等, 关于事件信息的通俗解释可以看知乎上的一个回答

某个事件 i 的信息量: 这个事件发生的概率的负对数

信息熵就是平均而言一个事件发生得到的信息量大小，也就是信息量的期望值

任何一个序列都可以获取这个序列的信息熵，也就是将此序列分类后统计每个类型的概率，再用上述公式计算，使用Python实现如下:
def get_shanno_entropy(self, values):
''' 根据给定列表中的值计算其Shanno Entropy
'''
uniq_vals = set(values)
val_nums = {key: values.count(key) for key in uniq_vals}
probs = [v/len(values) for k, v in val_nums.items()]
entropy = sum([-prob*log2(prob) for prob in probs])
return entropy

信息增益

我们将一组数据集进行划分后，数据的信息熵会发生改变，我们可以通过使用信息熵的计算公式分别计算被划分的子数据集的信息熵并计算他们的平均值(期望值)来作为分割后的数据集的信息熵。新的信息熵的相比未划分数据的信息熵的减小值便是信息增益了. 这里我在最初就理解错了，于是写出的代码并不能创建正确的决策树。

假设我们将数据集D划分成kk 份D1,D2,…,Dk，则划分后的信息熵为:

信息增益便是两个信息熵的差值

在这里我主要使用信息增益来进行属性选择，具体的实现代码如下:
def choose_best_split_feature(self, dataset, classes):
''' 根据信息增益确定最好的划分数据的特征

:param dataset: 待划分的数据集
:param classes: 数据集对应的类型

:return: 划分数据的增益最大的属性索引
'''
base_entropy = self.get_shanno_entropy(classes)

feat_num = len(dataset[0])
entropy_gains = []
for i in range(feat_num):
splited_dict = self.split_dataset(dataset, classes, i)
new_entropy = sum([
len(sub_classes)/len(classes)*self.get_shanno_entropy(sub_classes)
for _, (_, sub_classes) in splited_dict.items()
])
entropy_gains.append(base_entropy - new_entropy)

return entropy_gains.index(max(entropy_gains))

增益比率