决策树
历史
决策树是机器学习和数据挖掘领域最火爆并且研究最深入的方法. 有好多决策树的算法. 其中最有影响力的算法是在机器学习领域开发的ID3, C4.5算法(由悉尼大学Ross Quinlan开发), 在统计学领域开发的CART算法(由Breiman等人开发). 其中最广泛应用的是C4.5算法.
定义
决策树, decision tree, 是一个树形结构(可以是二叉树或者非二叉树). 其每个非叶节点表示一个特征属性上的测试, 每个分支代表这个特征属性在某个值域上的输出, 而每个叶节点存放一个类别.
使用决策树进行决策的过程就是从根节点开始, 测试待分类项目中相应的特征属性, 并按照其值选择输出分支, 直到到达叶子节点, 将叶子节点存放的类别作为决策结果.
信息增益
详见不确定性和熵.
信息熵代表的是随机变量的不确定性程度, 条件熵代表某一条件下, 不确定性减少的程度. 在决策树算法中, 我们的关键就是每次选择一个特征, 特征有多个, 那么到底按照什么标准来选择哪一个特征. 这个问题就可以用信息增益来度量. 如果选择一个特征之后, 信息增益最大, 那么我们就选择这个特征.
例子
| 帅？ | 性格好？ | 身高？ | 上进？ | 嫁与否 |
|---|---|---|---|---|
| 帅 | 不好 | 矮 | 不上进 | 不嫁 |
| 不帅 | 好 | 矮 | 上进 | 不嫁 |
| 帅 | 好 | 矮 | 上进 | 嫁 |
| 不帅 | 爆好 | 高 | 上进 | 嫁 |
| 帅 | 不好 | 矮 | 上进 | 不嫁 |
| 帅 | 不好 | 矮 | 上进 | 不嫁 |
| 帅 | 好 | 高 | 不上进 | 嫁 |
| 不帅 | 好 | 中 | 上进 | 嫁 |
| 帅 | 爆好 | 中 | 上进 | 嫁 |
| 不帅 | 不好 | 高 | 上进 | 嫁 |
| 帅 | 好 | 矮 | 不上进 | 不嫁 |
| 帅 | 好 | 矮 | 不上进 | 不嫁 |
可以求得嫁与不嫁的信息熵为: \(-\frac{1}{2}\log \frac{1}{2}-\frac{1}{2}\log \frac{1}{2}\simeq 0.301\). 假如现在我已经知道了一个男生的身高信息, 求直到这个信息之后的信息增益.
身高的可能取值有三个, 即随机变量的取值可能有三个: 矮, 中, 高.
- 矮的个数为7个, 对应的嫁的数量是1个, 不嫁的数量是6个
- 中的个数是2个, 对应的嫁的数量是2个, 不嫁的数量是0个
- 高的个数是3个, 对应的嫁的数量是3个, 不嫁的数量是0个
条件熵的计算公式为: \(H(Y|X)=\sum_{x\in X}p(x)H(Y|X=x)\).
- \(H(Y|X=矮)=-\frac{1}{7}\log\frac{1}{7}-\frac{6}{7}\log\frac{6}{7}\simeq 0.178\), \(p(X=矮)=\frac{7}{12}\)
- \(H(Y|X=中)=-1\log1-0=0\), \(p(X=中)=\frac{2}{12}\)
- \(H(Y|X=高)=-1\log1-0=0\), \(p(X=低)=\frac{3}{12}\)
由此可以计算出条件熵为\(\frac{7}{12}*0.178+\frac{2}{12}*0+\frac{3}{12}*0=0.103\).
所以信息增益就是\(0.301-0.103=0.198\). 也就是说, 本来如果我对一个男生什么都不知道的话, 作为他的女朋友决定是否嫁给他的不确定性有\(0.301\)这么大. 当我们直到男朋友的身高信息之后, 不确定性减少了\(0.198\), 也就是说, 身高这个特征对于我们广大女生同学来说, 决定加不加给自己的男朋友是很重要的.
构建决策树
决策树学习的一种常见的策略是使用递归, 自顶向下的递归分治.
- 从根节点开始, 我们需要选择一个最优的属性, 通常基于信息增益或者基尼指数来衡量. 选择好属性后, 根据属性不同的取值, 创建相应的分支. 每个分支代表一种可能的选择
- 一旦根节点及其分支确定下来, 数据就会被划分到各个子集中, 每个子集对应于一个分支, 这个分支的属性值和子集中相应的属性值保持一致
- 对每个子集递归地重复上述过程, 重复选择最优的属性, 划分数据
- 直到子集中所有的样本都属于同一个类, 终止递归, 创建一个叶节点, 这个叶节点属于这个类
如何选择最优属性
从决策树的构建过程可以看出, 递归终止的条件是子集中所有的样本属于同一个类. 我们需要递归尽快终止, 这样可以得到一棵较小的决策树, 为什么要小树:
- 避免过拟合: 过度复杂的树往往会对训练数据进行过度拟合. 这样的树可能会非常准确地分类训练数据, 但是对新数据表现不佳. 这是因为深树可能学到了训练数据中的噪音或者异常模式, 而不是一般性规律. 通过生成较小的树, 可以获得更加简洁, 更具有概括能力的模型, 从而提高模型对新数据的泛化能力. 较小的树意味着较高的偏差, 但是较低的方差, 关于什么是偏差和方差, 请见这里
- 提高可解释性: 小而简单的树更容易理解和解释. 如果树非常复杂, 包括许多分支和节点, 人们可能难以理解决策过程, 小树可以更加清晰地展示分类的决策过程, 从而提高人们理解和引用
- 减少计算开销: 较小的树意味着更少的节点/计算但是获得同等程度的表现, 这在处理大规模数据和实时应用中非常重要. 较小的树可以更快地进行预测, 在内存和计算资源上更加节省
- 降低数据需求: 较大的树需要更多的数据来可靠地估计每个节点的分类规则. 如果数据不足, 深树可能在小样本上做出不可靠的决策. 较小的树更容易在有限的数据上表现出良好的性能
那么我们怎么获得较小的决策树呢? 较小的决策树意味着我们要尽快获得"纯度"较高的子集. 当一个子集中的所有样本都属于同一个类的时候, 那么这个子集被认为是"纯"的. 如果一个子集中的样本属于的类别越多, 通常纯度就越低. 这个其实就是熵的概念, 即表示一个子集中数据的不确定性/混乱程度. 我们的目标就是选取最有的属性, 使得产生的子集的纯度更高, 也就是信息增益更大.
熵, 信息增益, 互信息..等等知识请见什么是信息, 不确定性和熵.
例子
给出下面的一张表, 计算这个集合的熵, 并计算如果我们选择shape属性获得的信息增益.
| shape | color | class |
|---|---|---|
| circle | blue | + |
| circle | blue | + |
| square | blue | - |
| triangle | blue | - |
| square | red | + |
| square | blue | + |
| square | red | + |
| circle | red | + |
-
计算这个集合的熵
\(H(S)=-5/8\log_2(5/8)-3/8\log_2(3/8)=0.95\) bits.
-
计算选择\(shape\)属性产生的信息增益
- \(H(S_{shape=cicle})=-3/3\log_2(3/3)-0/3\log_2(0/3)=0\) bits
- \(H(S_{shape=square})=-2/4\log_2(2/4)-2/4\log_2(2/4)=1\) bits
- \(H(S_{shape=triangle})=-0/1\log_2(0/1)-1/1\log_2(1/1)=0\) bits
\(H(S|shape)=3/8*0+4/8*1+1/8*0=0.5\) bits \(\Rightarrow\) 信息增益\(=H(S)-H(S|shape)=0.45\) bits.
修剪决策树
如果我们将决策树生长到能够完美分类训练集的程度, 树可能会变得过于具体并导致对数据的过拟合.
当出现以下情况时, 往往会出现过拟合:
- 训练样本太少: 无法收集到具有代表性的样本构建模型使得在新数据上表现良好
- 训练样本中有噪音: 如不正确的标签
修剪决策树就是一个避免过拟合的过程. 主要有两种方式修剪决策树, 那就是预剪枝和后剪枝. 预剪枝就是在初始阶段防止决策树过度生长, 后剪枝就是在决策树全部生长完毕后修剪. 在实际训练过程中, 往往使用的是后剪枝.
后剪枝
后剪枝的具体实现有多种方法, 如:
- 子树替换
- 子树提升
- 将树转换为规则, 然后再修剪
如何确定剪枝的程度呢? 可以使用验证集测试.
子树替换
这种方法的剪枝过程是从决策树的叶节点向根节点进行的. 这意味着你先检查那些最靠近叶节点的非叶节点, 然后逐渐向上移动到根节点. 每个非叶节点都有可能成为剪枝的目标.
对于每个非叶节点, 执行以下步骤:
- 移除以该节点为根的子树
- 将其替换为一个叶子节点: 将移除后的节点变为叶节点, 这个叶节点的类别标签是基于之前所有沿着这个节点路径的数据样本中的多数类
- 使用验证集计算新树的准度, 和旧树比较
- 如果新树的准度比旧树好或相同, 则保留新树