走近决策树

easthomeRT

决策树是什么？今天让东方瑞通带你走进决策树吧！

决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系.

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别

一个决策树包含三种类型的节点:

1.决策节点:通常用矩形框来表示

2.机会节点:通常用圆圈来表示

3.终结点:通常用三角形来表示

算法原理:

通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

数据表格:

                               
登录/注册后可看大图

决策树构建:

                               
登录/注册后可看大图

决策树构建的准备工作:

特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的标准是信息增益(information gain)或信息增益比:

特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。

信息量

所谓信息量是指从N个相等可能事件中选出一个事件所需要的信息度量或含量，也就是在辩识N个事件中特定的一个事件的过程中所需要提问"是或否"的最少次数. 如一个汉字的信息量是多少呢？ 假设常用汉字1024个，那么选中每个字概率为1/1024, 信息量为10bit，没错单位就是bit比特，利用二分查找需要询问10次可以定位这个汉字！

计算公式

                               
登录/注册后可看大图

熵的计算

整个概率分布对应的信息量的平均值.这个平均值就叫做随机变量x的熵

熵的计算公式如下： 即信息量的期望值

                               
登录/注册后可看大图

概率x服从正态分布时，对x * log2(x)在(0,1)区间积分，得到香农熵曲线图如下，表明p=0或1时，没有不确定性，此时熵值为0，p=0.5时概率均等，熵最大

                               
登录/注册后可看大图

集合信息的度量方式称为香农熵或者简称为熵(entropy)，这个名字来源于信息论之父克劳德·香农。

熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为

                               
登录/注册后可看大图

通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：

                               
登录/注册后可看大图

经验熵

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为

                               
登录/注册后可看大图

分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

                               
登录/注册后可看大图

如何选择特征，需要看信息增益。

也就是说，信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。

我们还需要明确一个概念，条件熵

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

                               
登录/注册后可看大图

经验条件熵的公式可以写为：

                               
登录/注册后可看大图

计算年龄的信息增益，过程如下：

                               
登录/注册后可看大图

计算其余特征的信息增益g(D,A2)、g(D,A3)和g(D,A4)。分别为：

                               
登录/注册后可看大图

                               
登录/注册后可看大图

                               
登录/注册后可看大图

比较特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大，所以选择A3作为最优特征

依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子结点；最后将测试数据定义为叶子结点所属的类型。在构建决策树的代码，可以看到，有个featLabels参数。它是用来干什么的？它就是用来记录各个分类结点的，在用决策树做预测的时候，我们按顺序输入需要的分类结点的属性值即可。

东方瑞通成立于1998年，总部在北京，分别在上海、广州、天津、武汉、济南、深圳、成都、重庆、杭州和西安建立了直营分部，全国拥有超过40间专业培训教室、40多位专职讲师及180多位签约讲师；作为国内企业级IT高级技术&管理培训的领军机构，为数千家企业客户提供员工外派（公开课）和团体定制培训服务，累计培训专业人才数十万名。