决策树
前面我们讲了线性回归模型和朴素贝叶斯分类模型。前者只能做回归，后者只能做分类。但本文中要讲的决策树模型，却既可以用于回归，又可以用于分类。
什么是决策树:
决策树是一种非常基础又常见的机器学习模型。
一棵决策树是一个树结构，每个非叶节点对应一个特征，该节点的每个分支代表这个特征的一个取值，而每个叶节点存放一个类别或一个回归函数。使用决策树进行决策的过程就是从根节点开始，提取出待分类项中相应的特征，按照其值选择输出分支，依次向下，直到到达叶子节点，将叶子节点存放的类别或者回归函数的运算结果作为输出（决策）结果。
下图是一个决策树的例子：
这棵树的作用，是对要不要接受一个 Offer 做出判断。
我们看到，这棵树一共有7个节点，其中有4个叶子节点和3个非叶子节点。它是一棵分类树，每个叶子节点对应一个类别。从图中我们也可以看出，总共只有2个类别：accept offer（接受）和 decline offer（拒绝）。
以上例而言，拿到一个 Offer 后，要判断三个条件：（1）年薪；（2）通勤时间；（3）免费咖啡。这三个条件的重要程度显然是不一样的，最重要的是根节点，越靠近根节点，也就越重要——如果年薪低于5万美元，也就不用考虑了，直接 say no；当工资足够时，如果通勤时间大于一个小时，也不去那里上班；就算通勤时间不超过一小时，还要看是不是有免费咖啡，没有也不去。
该树按照根节点向下的顺序筛选一个个条件，直到到达叶子为止。到达的叶子所对应的类别就是预测结果。
这三个非叶子节点，统称决策节点，每个节点对应一个条件判断，这个条件判断的条件，我们叫做特征。上例是一个有三个特征的分类树。
构建决策树:
前面我们讲了，获得一种模型的过程叫训练，那么我们如何训练可以得到一棵决策树呢？
简单讲，有以下几步：
- 准备若干的训练数据（假设 m 个样本）；
- 标明每个样本预期的类别；
- 人为选取一些特征（即决策条件）；
- 为每个训练样本对应所有需要的特征生成相应值——数值化特征；
- 将通过上面的1-4步获得的训练数据输入给训练算法，训练算法通过一定的原则，决定各个特征的重要性程度，然后按照决策重要性从高到底，生成决策树。
那么训练算法到底是怎么样的？决定特征重要程度的原则又是什么呢？
常用算法
在讲算法前，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：
其中n代表X的n种不同的离散取值。而pi代表了X取值为i的概率，log为以2或者e为底的对数。
熟悉了一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：
有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下：
现在我们知道H(X)度量了X的不确定性，条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性，那么H(X)-H(X|Y)呢？从上面的描述大家可以看出，它度量了X在知道Y以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为I(X,Y)。在决策树ID3算法中叫做信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。
ID3 算法：
ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D，输出为0或者1。其中有9个输出为1， 6个输出为0。 样本中有个特征A，取值为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中,2个输出为1,3个输出为0， 在取值为A3的样本中，4个输出为1，1个输出为0。
样本D的熵为：
样本D在特征下的条件熵为：
对应的信息增益为：
I(D,A)=H(D)−H(D|A)=0.083
下面我们看看具体算法过程大概是怎么样的。
输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合即为A，输出为决策树T。
- 初始化信息增益的阈值ϵ
- 判断样本是否为同一类输出Di，如果是则返回单节点树T。标记类别为Di
- 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
- 计算A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征Ag
- 如果Ag的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
- 否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
- 对于所有的子节点，令D=Di,A=A−{Ag}递归调用2-6步，得到子树Ti并返回。
ID3 算法的不足：
ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。
- ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
- ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
- ID3算法对于缺失值的情况没有做考虑
- 没有考虑过拟合的问题
可以看出ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。
但是C4.5算法在这几个方面进行了弥补，我们下一节来看看C4.5算法。
