这里开始机器学习的笔记记录。今天的这篇是一个分类方法--决策树。

决策树
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过拟合的问题。
适用数据类型：数值型和标称型

本文内容大部分来自于《统计学习方法》。

先来看看决策树是什么？

决策树模型就是个树形结构。由结点（node）和有向边（directed edge）组成。结点分内部结点和叶结点。内部结点是一个特征，叶结点是类别。如图5-1：

决策树模型

决策树可以看做一个if-then规则的集合，即如上图的由根结点到叶结点的每一条路径构建一条规则，特征对应规则的条件，叶结点就是结论。每个实例都被一条路径或规则所覆盖，而且只被一条路径或规则覆盖。即实例的特征与那条路径上的特征表现一致。

决策树叶可以看成给定特征条件下类的条件概率分布。将特征空间进行划分成很多个单元，每个单元定义一个类的概率分布。

决策树的本质上是从训练样本中归纳出一组分类规则，也是估计条件概率模型。（所以说是判别模型）

先看书上的一道例题：

在用决策树做分类的过程中，我们需要一步一步的选取特征来划分。可是，比如说在例题当中，有4个特征，选择任意一个都能进行决策树的划分，比如年龄和是否有工作两个特征，分别选取都可以让决策树进行下去：

特征选择不同，分支不同

那么我们首先选择哪个特征来进行划分呢？

当然是该选择一个好的特征。怎样才算好呢？直观上，如果一个特征具有更好的分类能力（能将训练集分割成子类，使得各个子类在当前条件下有更好的分类），那么这个特征就可以当做好特征。

那么如何评判某特征是个好特征呢？

书上给出的是一种叫信息增益和基尼系数的指标。下面就分别来看看。

1.信息增益

什么是信息增益呢？这与信息论中的熵和条件熵有关。也就是通过信息论的一套来划分数据集。

首先一个概念：信息熵是表示随机变不确定性的度量。熵越大，信息量越大，也就是越不确定。

熵的定义如下：

熵的定义

p(x)表示的是概率分布，对数可以以2或者e为底都可以，这时只是熵的单位不同，并没有什么区别。（以2为底叫比特，以e为底叫纳特）

不过熵为什么要这样定义呢？
可以试着解释下，先看看“越不确定”是什么意思？可以看成发生的概率越小。因此事件发生的概率越小，信息量就越大。比如说本来认为不可能的事发生了，给人的信息量就很大。

如果两个事件是独立的，则

如果在这里设置表示两个事件信息量的函数为h(x1)和h(x2),那么二者同时发生的信息量可以这样表示:

(因为用加法更直观方便)

如何把概率和信息量联系起来呢？看公式的话，可以看到乘法取个对数就能变成加法，因此我们可以假定h(x)=log(p(x))，但p(x)是小于1的，这样取出来是负数，为了让它是正数形式上好看些，那就取个负吧。这样，信息量的表示就成了：

单个事件的信息量就这样表示了出来。。而熵呢？熵就是所有信息量相加了:

为什么要乘以概率，因为熵应该表示总事件的信息期望（平均），因此要乘以单独事件发生的概率。

那么条件熵又是什么呢？
条件熵是表示在已知随机变量X的条件下随机变量Y的不确定性。

而信息增益就是在集合D的经验熵H(D)与特征A给定条件下D的经验条件熵之差：

在决策树中，经验熵H(D)表示对数据集D进行分类的不确定性；而H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性；它们的差就表示由于特征A而使对数据集D的分类的不确定性减少的程度，即信息增益。（就是划分数据之前之后信息熵发生的变化叫信息增益。）

如此定义后，我们就认为信息增益大的那个特征是好特征了。信息增益大的那个特征就是在划分数据时起决定性作用的那个特征。

那么如何计算信息增益？在书上给了公式（简书不支持Latex，公式真的挺难弄，只能截图了）:

看到信息增益的公式，其实信息增益就是互信息。

另外，在信息增益的基础上，还可以使用信息增益比来表示特征选择的准则。

信息增益比

2.基尼系数

前面说了除信息增益外，还可以用基尼系数来表示特征选择的准则。

那基尼系数又表示的是什么呢？

基尼系数同样可以表示样本集合的不确定性。

在分类问题中，假设有K个类，样本点属于第k类的概率是P_k，则概率分布的基尼系数定义为:

基尼指数

从公式看就是被分对的概率乘以被分错的概率，然后整个的和就是基尼系数。

其实和熵比起来似乎就是定义概念不一样，公式感觉是差不多的啊:

熵

都是概率乘以一个东西，然后求和。也就是求期望。基尼系数也就是把log(p)改为了1-p。熵前面加个负号只是为了让值成为正数而已。

如果是二分类的话(概率p₁=(1-p₂))，那么基尼系数化简就是：

二分类基尼系数公式

在特征A的条件下，集合D的基尼系数表示法也和条件熵的表示法蛮像的，也就是条件基尼系数。如果都以二分类来做对比的话，公式分别如下：

看上去形式简直就是一模一样啊。这里书上介绍基尼指数值越大，就表示不确定性越大，所以应选择基尼系数最小的特征及对应切分点作为最优特征。

那么为什么基尼系数和熵一样能够表示不确定性呢？《统计学习方法》书上有这样一幅图：

基尼系数和熵之半(也就是熵的一半值)的曲线比较近似。

曾经看到过一个解释，熵的公式中有一个log对数，而f(x)=-lnx在x=1处一阶泰勒展开，忽略掉高次项，可以得到f(x)≈1-x。这样p_klogp_k≈p_k(1-p_k)了，就更可以看到基尼指数与熵很近似了。

决策树的生成

算好了信息增益后，就可以进行决策树的生成了。通过应用信息增益准则来选取特征的这一种方法而进行决策树的构建叫ID3算法。

ID3算法的核心是在决策树各个结点上应用信息增益准则来选择特征，递归的构建决策树。

具体方法如下:

从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值来建立子结点；再对子结点递归的调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。

ID3算法步骤：

另外，还可以用信息增益比的形式来选择特征，这样的算法叫做C4.5算法。

C4.5算法的步骤：

最后还有一种是通过样本集合D的基尼系数来进行特征选取，而依据这样一种准则的树生成算法叫CART算法。

CART全称叫分类与回归树（classification and regression tree），因此可以看到决策树不仅可以做分类，还可以用于回归呢。

CART假设决策树是二叉树，左边的分支取值为“是”，右边的分支取值为“否”。

CART生成算法步骤：

决策树的剪枝

决策树容易产生过拟合现象，这样的话虽然对已知的训练数据分类很准确，但对于未知的测试数据就没那么准确了。过拟合的原因是在学习时过多的考虑如何提高对训练样本的正确分类，从而构建了过于复杂的决策树。因此，为了解决过拟合现象，可以对已生成的决策树进行简化，这就是剪枝。

上面所介绍的三种决策树的剪枝过程是相同的，不同的仅仅是对于当前树所用的评价标准不同，也就是上面说过的信息增益、信息增益比或基尼系数。

剪枝的总体思路如下：

由完全树T₀开始，剪枝部分结点得到T₁，再次剪枝部分结点得到T₂，直到剪枝到仅剩下树根的那棵树T_k。当然这些树都要保留{T₁,T₂,....,T_k}；

接着通过交叉验证法在验证数据集上对这k棵树分别进行测试评价，选择损失函数最小的数T_α作为最优子树。

那么来看看决策树的损失函数定义：

其中|T|为树T的叶节点个数，t是数T的叶节点，该叶节点上有N_t个样本，其中k类的样本有N_tk个。H_t(T)就是叶节点t上的经验熵：

将公式简化一下表示：

其中：

这样，C(T)就表示模型对训练数据的预测误差，|T|就表示模型复杂度，也就是说叶结点越多，决策树越复杂，损失就越大。α就是那个控制值了，其实后面就相当于正则化的存在。当α=0时，未剪枝的决策树损失最小；当α=+∞时，单根结点的决策树损失最小。α越小，选择的树越复杂。因此，才说模型选择就是用正则化的极大似然估计。