关键词：
前言
最近打算系统学习下机器学习的基础算法，避免眼高手低，决定把常用的机器学习基础算法都实现一遍以便加深印象。本文为这系列博客的第一篇，关于决策树(Decision Tree)的算法实现，文中我将对决策树种涉及到的
算法进行总结并附上自己相关的实现代码。所有算法代码以及用于相应模型的训练的数据都会放到GitHub上(https://github.com/PytLab/MLBox).
本文中我将一步步通过MLiA的隐形眼镜处方数集构建决策树并使用Graphviz将决策树可视化。
决策树学习
决策树学习是根据数据的属性采用树状结构建立的一种决策模型，可以用此模型解决分类和回归问题。常见的算法包括 CART(Classification And Regression Tree), ID3, C4.5等。我们往往根据数据集来构建一棵决策树，
他的一个重要任务就是为了数据中所蕴含的知识信息，并提取出一系列的规则，这些规则也就是树结构的创建过程就是机器学习的过程。
决策树的结构
以下面一个简单的用于是否买电脑预测的决策树为例子，树中的内部节点表示某个属性，节点引出的分支表示此属性的所有可能的值，叶子节点表示最终的判断结果也就是类型。
借助可视化工具例如Graphviz，matplotlib的注解等等都可以讲我们创建的决策树模型可视化并直接被人理解，这是贝叶斯神经网络等算法没有的特性。
决策树算法
决策树算法主要是指决策树进行创建中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯. 最大的原则就是: 将无序的数据变得更加有序
这里总结下三个常用的方法:
1、信息增益(information gain)
2、增益比率(gain ratio)
3、基尼不纯度(Gini impurity)
信息增益 (Information gain)
这里涉及到了信息论中的一些概念：某个事件的信息量，信息熵，信息增益等, 关于事件信息的通俗解释可以看知乎上的一个回答
1、某个事件 i 的信息量: 这个事件发生的概率的负对数
2、信息熵就是平均而言一个事件发生得到的信息量大小，也就是信息量的期望值
任何一个序列都可以获取这个序列的信息熵，也就是将此序列分类后统计每个类型的概率，再用上述公式计算，使用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))
增益比率
增益比率是信息增益方法的一种扩展，是为了克服信息增益带来的弱泛化的缺陷。因为按照信息增益选择，总是会倾向于选择分支多的属性，这样会是的每个子集的信息熵最小。例如给每个数据添加一个
第一无二的id值特征，则按照这个id值进行分类是获得信息增益最大的，这样每个子集中的信息熵都为0，但是这样的分类便没有任何意义，没有任何泛化能力，类似过拟合。
因此我们可以通过引入一个分裂信息来找到一个更合适的衡量数据划分的标准，即增益比率。
分裂信息的公式表示为:
当然SplitInfo有可能趋近于0，这个时候增益比率就会变得非常大而不可信，因此有时还需在分母上添加一个平滑函数，具体的可以参考参考部分列出的文章
基尼不纯度(Gini impurity)
基尼不纯度的定义:
其中m 表示数据集D 中类别的个数, pi 表示某种类型出现的概率。可见当只有一种类型的时候基尼不纯度的值为0，此时不纯度最低。
针对划分成k个子数据集的数据集的基尼不纯度可以通过如下式子计算:
由此我们可以根据不纯度的变化来选取最有的树分裂属性
树分裂
有了选取最佳分裂属性的算法，下面我们就需要根据选择的属性来将树进一步的分裂。所谓树分裂只不过是根据选择的属性将数据集划分，然后在总划分出来的数据集中再次调用选取属性的
方法选取子数据集的中属性。实现的最好方式就是递归了.
关于用什么数据结构来表示决策树，在Python中可以使用字典很方便的表示决策树的嵌套，一个树的根节点便是属性，属性对应的值又是一个新的字典，其中key为属性的可能值，value为新的子树。
下面是我使用Python实现的根据数据集创建决策树：
def create_tree(self, dataset, classes, feat_names): ''' 根据当前数据集递归创建决策树 :param dataset: 数据集 :param feat_names: 数据集中数据相应的特征名称 :param classes: 数据集中数据相应的类型 :param tree: 以字典形式返回决策树 ''' # 如果数据集中只有一种类型停止树分裂 if len(set(classes)) == 1: return classes[0] # 如果遍历完所有特征，返回比例最多的类型 if len(feat_names) == 0: return get_majority(classes) # 分裂创建新的子树 tree = {} best_feat_idx = self.choose_best_split_feature(dataset, classes) feature = feat_names[best_feat_idx] tree[feature] = {} # 创建用于递归创建子树的子数据集 sub_feat_names = feat_names[:] sub_feat_names.pop(best_feat_idx) splited_dict = self.split_dataset(dataset, classes, best_feat_idx) for feat_val, (sub_dataset, sub_classes) in splited_dict.items(): tree[feature][feat_val] = self.create_tree(sub_dataset, sub_classes, sub_feat_names) self.tree = tree self.feat_names = feat_names return tree
树分裂的终止条件有两个
1、一个是遍历完所有的属性
可以看到，在进行树分裂的时候，我们的数据集中的数据向量的长度是不断缩短的，当缩短到0时，说明数据集已经将所有的属性用尽，便也分裂不下去了, 这时我们选取最终子数据集中的众数作为最终的分类结果放到叶子节点上.
2、另一个是新划分的数据集中只有一个类型。
若某个节点所指向的数据集都是同一种类型，那自然没有必要在分裂下去了即使属性还没有遍历完.
构建一棵决策树
这我用了一下MLiA书上附带的隐形眼镜的数据来生成一棵决策树，数据中包含了患者眼部状况以及医生推荐的隐形眼镜类型.
首先先导入数据并将数据特征同类型分开作为训练数据用于生成决策树
from trees import DecisionTreeClassifier lense_labels = ['age', 'prescript', 'astigmatic', 'tearRate'] X = [] Y = [] with open('lenses.txt', 'r') as f: for line in f: comps = line.strip().split('\t') X.append(comps[: -1]) Y.append(comps[-1])
生成决策树:
clf = DecisionTreeClassifier()
clf.create_tree(X, Y, lense_labels)
查看生成的决策树:
In [2]: clf.tree
Out[2]:
{'tearRate': {'normal': {'astigmatic': {'no': {'age': {'pre': 'soft',
'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}},
'young': 'soft'}},
'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses',
'presbyopic': 'no lenses',
'young': 'hard'}},
'myope': 'hard'}}}},
'reduced': 'no lenses'}}
可视化决策树
直接通过嵌套字典表示决策树对人来说不好理解，我们需要借助可视化工具可视化树结构，这里我将使用Graphviz来可视化树结构。为此实现了讲字典表示的树生成Graphviz Dot文件内容的函数，
大致思想就是递归获取整棵树的所有节点和连接节点的边然后将这些节点和边生成Dot格式的字符串写入文件中并绘图。
递归获取树的节点和边，其中使用了uuid给每个节点添加了id属性以便将相同属性的节点区分开.
def get_nodes_edges(self, tree=None, root_node=None): ''' 返回树中所有节点和边 ''' Node = namedtuple('Node', ['id', 'label']) Edge = namedtuple('Edge', ['start', 'end', 'label']) if tree is None: tree = self.tree if type(tree) is not dict: return [], [] nodes, edges = [], [] if root_node is None: label = list(tree.keys())[0] root_node = Node._make([uuid.uuid4(), label]) nodes.append(root_node) for edge_label, sub_tree in tree[root_node.label].items(): node_label = list(sub_tree.keys())[0] if type(sub_tree) is dict else sub_tree sub_node = Node._make([uuid.uuid4(), node_label]) nodes.append(sub_node) edge = Edge._make([root_node, sub_node, edge_label]) edges.append(edge) sub_nodes, sub_edges = self.get_nodes_edges(sub_tree, root_node=sub_node) nodes.extend(sub_nodes) edges.extend(sub_edges) return nodes, edges
生成dot文件内容
def dotify(self, tree=None): ''' 获取树的Graphviz Dot文件的内容 ''' if tree is None: tree = self.tree content = 'digraph decision_tree {\n' nodes, edges = self.get_nodes_edges(tree) for node in nodes: content += ' "{}" [label="{}"];\n'.format(node.id, node.label) for edge in edges: start, label, end = edge.start, edge.label, edge.end content += ' "{}" -> "{}" [label="{}"];\n'.format(start.id, end.id, label) content += '}' return content
隐形眼镜数据生成Dot文件内容如下:
digraph decision_tree {
"959b4c0c-1821-446d-94a1-c619c2decfcd" [label="call"];
"18665160-b058-437f-9b2e-05df2eb55661" [label="to"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [label="your"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [label="areyouunique"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" [label="02073162414"];
"aac20872-1aac-499d-b2b5-caf0ef56eff3" [label="ham"];
"18aa8685-a6e8-4d76-bad5-ccea922bb14d" [label="spam"];
"3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [label="spam"];
"44d1f972-cd97-4636-b6e6-a389bf560656" [label="spam"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [label="i"];
"a6f22325-8841-4a81-bc04-4e7485117aa1" [label="spam"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" [label="ldn"];
"51b9477a-0326-4774-8622-24d1d869a283" [label="ham"];
"16f6aecd-c675-4291-867c-6c64d27eb3fc" [label="spam"];
"adb05303-813a-4fe0-bf98-c319eb70be48" [label="spam"];
"959b4c0c-1821-446d-94a1-c619c2decfcd" -> "18665160-b058-437f-9b2e-05df2eb55661" [label="0"];
"18665160-b058-437f-9b2e-05df2eb55661" -> "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [label="0"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [label="0"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "ca091fc7-8a4e-4970-9ec3-485a4628ad29" [label="0"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "aac20872-1aac-499d-b2b5-caf0ef56eff3" [label="0"];
"ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "18aa8685-a6e8-4d76-bad5-ccea922bb14d" [label="1"];
"bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [label="1"];
"2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "44d1f972-cd97-4636-b6e6-a389bf560656" [label="1"];
"18665160-b058-437f-9b2e-05df2eb55661" -> "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [label="1"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "a6f22325-8841-4a81-bc04-4e7485117aa1" [label="0"];
"7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "c181fe42-fd3c-48db-968a-502f8dd462a4" [label="1"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" -> "51b9477a-0326-4774-8622-24d1d869a283" [label="0"];
"c181fe42-fd3c-48db-968a-502f8dd462a4" -> "16f6aecd-c675-4291-867c-6c64d27eb3fc" [label="1"];
"959b4c0c-1821-446d-94a1-c619c2decfcd" -> "adb05303-813a-4fe0-bf98-c319eb70be48" [label="1"];
}
这样我们便可以使用Graphviz将决策树绘制出来
with open('lenses.dot', 'w') as f:
dot = clf.tree.dotify()
f.write(dot)
dot -Tgif lenses.dot -o lenses.gif
效果如下:
使用生成的决策树进行分类
对未知数据进行预测，主要是根据树中的节点递归的找到叶子节点即可。z这里可以通过为递归进行优化，代码实现如下:
def classify(self, data_vect, feat_names=None, tree=None): ''' 根据构建的决策树对数据进行分类 ''' if tree is None: tree = self.tree if feat_names is None: feat_names = self.feat_names # Recursive base case. if type(tree) is not dict: return tree feature = list(tree.keys())[0] value = data_vect[feat_names.index(feature)] sub_tree = tree[feature][value] return self.classify(feat_names, data_vect, sub_tree)
决策树的存储
通过字典表示决策树，这样我们可以通过内置的pickle或者json模块将其存储到硬盘上，同时也可以从硬盘中读取树结构，这样在数据集很大的时候可以节省构建决策树的时间.
def dump_tree(self, filename, tree=None): ''' 存储决策树 ''' if tree is None: tree = self.tree with open(filename, 'w') as f: pickle.dump(tree, f) def load_tree(self, filename): ''' 加载树结构 ''' with open(filename, 'r') as f: tree = pickle.load(f) self.tree = tree return tree
总结
本文一步步实现了决策树的实现, 其中使用了ID3算法确定最佳划分属性，并通过Graphviz可视化了构建的决策树。本文相关的代码链接: https://github.com/PytLab/MLBox/tree/master/decision_tree
参考:
-
《Machine Learning in Action》
-
数据挖掘系列（6）决策树分类算法
机器学习-决策树(decisiontree)算法
学习彭亮《深度学习基础介绍：机器学习》课程[toc]决策树概念决策树是一种用于监督学习的层次模型，由此，局部区域通过少数几步递归分裂决定。决策树是一个类似流程图的树结构：其中每个结点表示在一个... 查看详情
机器学习sklearn监督学习分类算法决策树decisiontree(代码片段)
#导入鸢尾花数据集、决策树分类器、计算交叉验证值的函数cross_val_scorefromsklearn.datasetsimportload_irisfromsklearn.treeimportDecisionTreeClassifierfromsklearn.model_selectionimportcross_val_score#使用默认参数，创建一颗基于基尼系数的决策树&# 查看详情
机器学习实战之第三章决策树（decisiontree）
...st/MathJax.js?config=default"></script>决策树概述决策树（DecisionTree）算法主要用来处理分类问题，是最经常使用的数据挖掘算法之一。决策树场景一个叫做"二十个问题"的游戏，游戏的 查看详情
机器学习：决策树(decisiontree)--id3算法(代码片段)
决策树的主要算法构建决策树的关键：按照什么样的次序来选择变量（属性/特征）作为分类依据。根据不同的目标函数，建立决策树主要有以下三种算法ID3(J.RossQuinlan-1975)核心：信息熵，信息增益C4.5——ID... 查看详情
机器学习sklearn监督学习分类算法决策树decisiontree(代码片段)
...数cross_val_scorefromsklearn.datasetsimportload_irisfromsklearn.treeimportDecisionTreeClassifierfromsklearn.model_selectionimportcross_val_score#使用默认参数，创建一颗基于基尼系数的决策树，并将该决策树分类器赋值给变量clfclf=DecisionTreeClassifier()i... 查看详情
机器学习方法：决策树decisiontree原理与实现技巧
欢迎转载，转载请注明：本文出自Bin的专栏blog.csdn.net/xbinworld。技术交流QQ群：433250724，欢迎对算法、技术、应用感兴趣的同学加入。前面三篇写了线性回归，lasso，和LARS的一些内容，这篇写一下决策树... 查看详情
机器学习入门-1.介绍与决策树(decisiontree)
机器学习(MachineLearning)介绍与决策树(DecisionTree)机器学习入门系列是个人学习过程中的一些记录与心得。其主要以要点形式呈现，简洁明了。1.什么是机器学习？一个比较概括的理解是:根据现有的数据，预测未来2.核心思想：Genera... 查看详情
机器学习--决策树分类算法及应用
1.决策树分类算法原理1.1概述决策树（decisiontree）——是一种被广泛使用的分类算法。相比贝叶斯算法，决策树的优势在于构造过程不需要任何领域知识或参数设置在实际应用中，对于探测式的知识发现，决策树更加适用1.2算法... 查看详情
鹅厂优文|决策树及id3算法学习
...的方式，是机器学习中的一种基本的分类方法。决策树(DecisionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概... 查看详情
机器学习实践之决策树算法学习
...37608890/article/details/78731169）。 本文根据最近学习机器学习书籍网络文章的情况,特将一些学习思路做了归纳整理,详情如下.如有不当之处 查看详情
机器学习入门之决策树算法
1、什么是决策树（DecisionTree） 决策树是一个类似于流程图的树结构，其中每一个树节点表示一个属性上的测试，每一个分支代表一个属性的输出，每一个树叶节点代表一个类或者类的分布，树的... 查看详情
机器学习——决策树（下）算法实现
Decisiontree在机器学习（5）——决策树（上）原理中介绍了决策树的生成和剪枝原理。介绍了CART,ID3，C4.5等算法的算法流程，其中CART算法可以实现回归和分类，是基于基尼不纯度实现的，这里并未实... 查看详情
machinelearning01_decisiontree(决策树)
分类树（决策树）是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象... 查看详情
常见机器学习算法原理+实践系列4（决策树）
决策树分类决策树算法借助于树的分支结构实现分类，决策树在选择分裂点的时候，总是选择最好的属性作为分类属性，即让每个分支的记录的类别尽可能纯。常用的属性选择方法有信息增益（InformationGain），增益比例（gainratio... 查看详情
机器学习--决策树
决策树（DecisionTree）决策树是监督学习(supervisedlearning)的一种。机器学习中分类和预测算法的评估：1.准确率2.速度3.强壮型4.可规模性5.可解释性什么是决策树？决策树是一个类似于流程图的树结构：其中，每个内部节点表示在一... 查看详情
机器学习——决策树（上）原理
Decisiontree决策树是机器学习中一种基本的分类和回归算法，是依托于策略抉择而建立起来的树。其主要优点是模型具有可读性，分类速度快，易于理解。决策树的思想主要来源于Quinlan在1986年提出的ID3算法和1993年提出... 查看详情
机器学习决策树
决策树(DecisionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图... 查看详情
机器学习——决策树
决策树一、了解决策树 决策树(DecisionTree)是一类常见的机器学习算法，属于非参数的监督学习方法，主要用于分类和回归，也可以用于特征提取。 决策树就是一棵树（很像流程图），其内包含一个... 查看详情