机器学习之决策树算法简介

一、决策树是什么

我们生活中往往会碰到各种各样的决策,每一个不同的决策最后的结局都会不一样。举个简单的例子,例如我们在进行银行贷款审批的时候,银行怎么判断我们这一笔贷款是否应该发放?以下图为例,首先会根据是否拥有房产,其次根据个人年收入状况,最后再根据婚姻状况判断,由此就构成了一个决策树,当然现实生活中银行贷款审批流程肯定不止这么一点信息。

二、信息熵、条件熵及信息增益

从上图的这颗树中可以看到房产位于树的根节点,优先级最高,其次是年收入,最后才是婚姻,这些顺序是怎么确定的呢?那就是通过信息熵和信息增益来衡量的。信息是我们现实世界中的一切事物,一个事物中含有多少信息是个很抽象的概念,那信息是否可以量化从中知道事物含有的信息量有多少呢?

1948年香农提出了信息熵的概念用来描述事物的不确定度,一个事物发生的概率越大,则它所蕴含的信息量就越少,甚至是不含有任何信息量,例如太阳每天东方升起西方落下,这是地球上生物每天见到永恒不变的真理,因此不含有任何的信息量。香农给出的信息熵公式如下,公式(1)中P(x)代表x事件各种可能的概率:

H(x)=−∑P(x)logP(x) (1)

那什么是条件熵呢?在给定x事件所有情况下,y的信息熵平均值就是条件熵,条件熵的公式如下:

H(y|x)=∑P(x=i)H(y|x=i)(2)

如上图所示,H(x)代表黄色圆圈,H(y)代表白色圆圈,H(x,y)代表x和y都发生的信息熵,条件熵还可以使用公式(3)表示:

H(y|x)=H(x,y)-H(x)(3)

信息增益是ID3算法中用来度量特征重要程度的重要指标,信息增益越大那么说明这个特征对决策的影响越大,应该放在决策树的上层,信息增益用Gain表示,信息增益公式如下:

Gain=H(D)-H(D|A) (4)

三、使用Python来计算信息增益

以下图数据为例,来计算信息熵及信息增益,检测下房产、年收入及婚姻对是否可以贷款的决策影响力。

1.导入Python科学计算库

2.定义信息熵计算函数,传入的是事件发生的概率list,使用公式(1)计算

3.定义事件概率计算函数

4.定义信息增益计算函数,使用上面的公式(4)计算信息增益,首先计算出H(y),再根据公式(2)计算出H(y|x)

5.构造初始化上面的数据

6.计算信息增益

由上图计算结果可以看出年收入的信息增益最大,其次是房产,最后是婚姻,信息增益越大则应该处于决策树的最上层。信息增益是决策树ID3算法的评价指标,还有其它决策树算法例如C4.5算法使用的是信息增益率,CART算法使用的是基尼系数作为评价指标。

四、使用sklearn的决策树分类算法来求解

决策树是一种贪心算法,只考虑在当前情况下最好的决策条件,不能回溯。决策树的构建一般都是使用递归,递归需要有停止条件,一般使用当前节点数小于某个阈值的时候停止。在sklearn中定义了很多参数来作为停止条件,还是以上面的数据为例。

1.导入sklearn决策树算法所需的库

2.定义构建表格中的数据的方法

3.训练集和测试机数据分割

4.使用网格搜索调优获得最优解

这里的使用到的GridSearchCV是用来参数调优时候使用的,给模型一堆训练参数,从中组合每个参数,从而训练出最优的参数。决策树的树深度参数是一个重要的影响指标,数深度过小或者过大都容易造成模型欠拟合或者过拟合,决策树还有一个剪枝过程,下一次再写一篇说明。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180624G0X3UO00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券