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

一、决策树是什么

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

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

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

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