决策树简介

在机器学习中，Decision tree是一个预测模型，他代表的是对象的特征(feature) 与对象标签(label)之间的一种映射关系。树中的每个节点表示某个特征，而每个分叉路径则代表某个特征可能的属性值，而每个叶节点对应从根节点到该叶节点所经历的路径表示对象的表标签。 数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。 决策树是一种常见的分类算法，每一个叶子节点对应一个分类，非叶子节点对应的某个属性的划分。

决策树组成

决策树主要由三部分构成，分别是决策节点、分支和叶子节点。其中决策树的最顶端的节点为根决策点，每一个分支都有一个新的决策节点。决策节点下面是叶子节点。决策的过程从根决策节点开始，从上到下。构造决策树的过程是如何选择合适的属性对样本进行拆分。

划分树的方法

这里主要介绍下ID3算法，ID3算法选取能够得到最大信息增益(information gain)的特征为数据划分归类，直到全部划分结束而不对树的规模进行任何控制 。

信息熵与信息增益

在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。

在认识信息增益之前，先来看看信息熵的定义。

熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵 是对不确定性的度量。

在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

假如一个随机变量X的取值为

每一种取到的概率分别是

那么X的熵定义为

意思是一个变量的变化情况可能越多，那么他携带的信息量就越大。

以上就是信息熵的定义，接下来介绍信息增益。

信息增益是针对一个一个特征而言的，就是看一个特征t，系统有它和没有它时的信息熵各是多少，两者的差就是这个特征给系统带来的信息量，即信息增益

举例说明

比如上图时描述天气的数据表，学习目标是play或者not play

从上表中可以看出，一共有9个yes和5个no。那么当前的信息的熵计算为:

在决策树分类问题中，信息增益就是决策树在进行属性划分前和后信息的差值。

假设现在利用Outlook 来分类，那么如下图

划分之后，数据被分为三部分，那么各分支的信息熵计算如下

那么划分后的信息熵为

Entropy(S|T) 代表在特征属性T的条件下样本的条件熵 。那么最终得到特征属性带来的信息增益为

所以总结下，信息增益的计算公式如下

其中S为全部样本集合，value(T)是属性T所有取值的集合，v是T的其中一个属性值，S_v是S中属性T的值为v的样例集合，|S_v|为S_v中所含样例数。

ID3算法

在决策树中的每一个叶子节点划分之前，先计算每一个属性所带来的信息增益，选择最大的信息增益的属性来划分，因为信息增益越大，区分样本的能力就越强，越具有代表性，这是一种很自然的自顶向下的贪心策略。

其他算法

C4.5：是ID3的一个改进，比ID3准确率高且快，可以处理连续值和有缺失值的feature。
CART：使用基尼指数的划分准则，通过在每个步骤最大限度降低不纯洁度，CART能够处理孤立点以及能够对空缺值进行处理。