一、决策树简介

在介绍决策树之前，先了解一下决策树的处理流程。如下图所示，有三个属性值，分别为Outlook、Humidity、Wind，对应的最终分类为Yes和No。当一条新数据过来时，根据新数据中Outlook、Humidity和Wind就能确定该数据的输出结果是Yes还是No。而Outlook、Humidity、Wind这三个属性值的选择，需要从已标记好的训练数据集中选择。

决策树

二、构建决策树

决策树是一层层构建的，在每一层就要选择一个属性，然后根据它的属性值将数据集进行分裂。如何选择属性作为节点以测试实例是最为关键的一步。不同的算法采取了不同的方法，主要的决策树算法有这样几个：

ID3
C4.5 （数据挖掘十大算法之一，也是ID3算法的改进）
C5.0 （C4.5的改进，适用于处理大数据集，采用Boosting方式提高模型准确率，因而又称BoostingTrees。）
CART（数据挖掘十大算法之一）

三、ID3

ID3算法的核心就是要选取分类能力最好的属性，那么怎么去确定哪个属性是分类能力最好的呢？ID3算法中，使用信息增益作为评判标准。

1. 信息熵

信息熵又称为香农熵，简称熵。信息熵简单说就是信息不确定性的大小。
若用xi，i=1,2,…,n来表示数据集所包含的分类结果，那么这个数据集的熵为：

熵公式（1）
其中，p(xi)表示选取xi作为分类的最终类别的概率；l(xi)为xi的信息，定义为：l(xi)=−log2p(xi)

2. 信息增益

简单来说，一个属性的信息增益就是：使用这个属性分割样例集合进一步导致熵值降低。那么要选取分类能力最好的属性，就是要选取使得信息增益最大的那个属性。
假设数据集D，按照属性A将数据进行分割，分割成v类，则分割后的信息熵为：

分割后的信息熵（2）

其中|D|为样本的总数，|Dj|为A属性值为j类的总样本数，info(Dj)为以Dj为数据集的信息熵，顾名思义，就是样本数据集D按照属性A进行分割成V类，将所有类别的信息熵求和，即可。那么数据集D按照A属性进行分割后的信息增益为：

数据D按照A属性进行分割后的信息增益（3）
依次计算数据D按照各个属性的分割后的信息增益，选择信息增益最大的作为分割属性，依次进行。

3. 简单例子

ID3例子(来自Jacky)

4. 信息增益的理解

一般说来，对于一个具有多个属性的元组，用一个属性就将它们完全分开几乎不可能，否则的话，决策树的深度就只能是2了。从这里可以看出，一旦我们选择一个属性A，假设将元组分成了两个部分A1和A2，由于A1和A2还可以用其它属性接着再分，所以又引出一个新的问题：接下来我们要选择哪个属性来分类？对D中元组分类所需的期望信息(信息熵)是Info(D) ,那么同理，当我们通过A将D划分成v个子集Dj(j=1,2,…,v)之后，我们要对Dj的元组进行分类，需要的期望信息就是Info(Dj),而一共有v个类，所以对v个集合再分类，需要的信息就是公式（2）了。由此可知，如果公式（2）越小，是不是意味着我们接下来对A分出来的几个集合再进行分类所需要的信息就越小？而对于给定的训练集，实际上Info(D)已经固定了，所以选择信息增益最大的属性作为分裂点。

但是，使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性。什么意思呢？就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性。例如一个训练集中有10个元组，对于某一个属相A，它分别取1-10这十个数，如果对A进行分裂将会分成10个类，那么对于每一个类Info(Dj)=0，从而式（2）为0，该属性划分所得到的信息增益（3）最大，但是很显然，这种划分没有意义