算法篇之决策树

算法概述

决策树是一种类似于流程图的树结构，其中每个节点代表一个特征，每个分支表示满足该特征的一个输出，而每个叶子节点代表一个分类编号，树的最顶层节点是根节点。是最为广泛的归纳推理算法之一，处理类别型或连续型变量的分类预测问题。

关键词解读

熵

熵最初概念来源于热力学，在信息论中代表随机变量不确定度的度量。一个离散型随机变量 X的熵 H(X)定义为：

从概念上理解比较抽象，我们通俗一点的说，熵就是指一个事件的不确定性，不确定性（或者说信息量）越大，那么我们说他的熵越大，同理他的不确定越小，熵值就越小。举个简单例子：

在我们上面的对话中，很明显葡小萄说的话信息量最小，因为他的不确定性最小，用熵的概念来说我们就说他的熵值最小，相信通过这个例子对于熵的概念应该有了一个初步的理解。

信息增益

理解了熵的概念，信息增益就很好理解了，通俗点讲信息增益就是两个熵做差后的值，比如说我们计算了特征A的信息熵为a，在特征A作为父节点的前提下，我们计算了其所有子节点的信息熵为b，那a-b我们就称之为信息增益。

过拟合

理解过拟合我们先来说一说拟合，所谓拟合是指已知某函数的若干离散函数值，通过调整该函数中若干待定系数f(λ1, λ2,…,λn)，使得该函数与已知点集的差别(最小二乘意义)最小。那么何为过拟合呢，就是我们的函数刻意的去拟合每一个样本，比如说我们的样本有100个，函数去尽可能的拟合了这一百个样本，生成了100个类别，这就是过度拟合，在训练数据上来说过度拟合看起来是一个最优拟合，但是对于测试数据来说会使得样本点之外的函数值远远偏离期望的目标，反而降低分类器的性能。像下图中的第三种情况，就是典型的过拟合。

算法原理讲解

举例

如图是一棵结构简单的决策树，用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性：是否拥有房产，是否结婚，平均月收入。每一个内部节点都表示一个属性条件判断，叶子节点表示贷款用户是否具有偿还能力。例如：用户甲没有房产，没有结婚，月收入 5K。通过决策树的根节点判断，用户甲符合右边分支 (拥有房产为“否”)；再判断是否结婚，用户甲符合左边分支 (是否结婚为否)；然后判断月收入是否大于 4k，用户甲符合左边分支 (月收入大于 4K)，该用户落在“可以偿还”的叶子节点上。所以预测用户甲具备偿还贷款能力。

决策树构建

要构建一颗决策树，我们首先要确定他的根节点，也就是以哪个特征作为跟节点，这里我选用比较基本的ID3算法来实现，ID3算法求根节点的整体思路就是通过遍历每一个特征属性，计算出其每一个作为根节点时对应的信息增益，最后选择信息增益最大的一个作为根节点，依次循环确定根节点，第二级节点，等等直到达到我们的分类预期。

决策树优化

剪枝：即剪掉一些节点，避免过拟合的发生。而常见的剪枝方法有前剪枝、后剪枝。前剪枝即在决策树生成的过程中边生成边剪枝，后剪枝是指在整个决策树构建完成后，再进行剪枝。

总结

决策树的概念整体上比较简单，重在实践，今天我们只介绍了决策树的一些基本概念，之后我们会选取一个基本的例子，用python来实现一次决策树的完整构建。敬请关注。