Walt You - 知行合一

机器学习入门(十) -- 决策树




定义

决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。

使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

算法步骤

在数据挖掘中决策树训练是一个常用的方法。目标是创建一个模型来预测样本的目标值。

一棵树的训练过程为:根据一个指标,分裂训练集为几个子集。这个过程不断的在产生的子集里重复递归进行,即递归分割。当一个训练子集的类标都相同时递归停止。这种决策树的自顶向下归纳 (TDITD) 是 贪心算法的一种, 也是目前为止最为常用的一种训练方法,但不是唯一的方法。

常用算法

ID3

ID3算法是最基本的模型,简单实用,但是在某些场合下也有缺陷。

这个算法的思想是:在每次分裂的时候,贪心选择信息增益最大的属性,作为本次分裂属性。

那么什么是增益最大呢?

首先它定义了一个公式来表示熵增益,然后算出每个属性所对应的熵增益,挑出最大的那个,然后用对应的属性作为分裂属性,接着,对各个子集,进行类似操纵。

存在的问题

ID3在选择的时候容易选择一些比较容易分纯净的属性做分裂,尤其在具有像ID值这样的属性,因为每个ID都对应一个类别,所以分的很纯净。但是这对于结果是毫无意义的。

C4.5

C4.5 在 ID3 的基础上,抛弃了比较熵增益,转而比较增益率

增益率引入了一个分裂熵,来表示属性分裂的熵,分的越多就越混乱,熵越大。

最后得出增益率 = 熵增益 / 分裂熵。

这样子就抑制了ID3算法的缺陷。

注意点

停止条件

决策树的构建过程是一个递归的过程,所以需要确定停止条件,否则过程将不会结束。一种最直观的方式是当每个子节点只有一种类型的记录时停止,但是这样往往会使得树的节点过多,导致过拟合问题(Overfitting)。另一种可行的方法是当前节点中的记录数低于一个最小的阀值,那么就停止分割,将max(P(i))对应的分类作为当前叶节点的分类。

过度拟合

  • 噪音数据:训练数据中存在噪音数据,决策树的某些节点有噪音数据作为分割标准,导致决策树无法代表真实数据。
  • 缺少代表性数据:训练数据没有包含所有具有代表性的数据,导致某一类数据无法很好的匹配。
  • 多重比较

属性用完了怎么办

在决策树构造过程中可能会出现这种情况:所有属性都作为分裂属性用光了,但有的子集还不是纯净集,即集合内的元素不属于同一类别。在这种情况下,由于没有更多信息可以使用了,一般对这些子集进行“多数表决”,即使用此子集中出现次数最多的类别作为此节点类别,然后将此节点作为叶子节点。

优化方案

修剪枝叶

前置裁剪:在构建决策树的过程时,提前停止。那么,会将切分节点的条件设置的很苛刻,导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。

后置裁剪:决策树构建好后,然后才开始裁剪。采用两种方法:1)用单一叶节点代替整个子树,叶节点的分类采用子树中最主要的分类;2)将一棵子树完全替代另外一棵子树。后置裁剪有个问题就是计算效率,有些节点计算后就被裁剪了,导致有点浪费。

K-Fold Cross Validation

首先计算出整体的决策树T,叶节点个数记作N,设i属于[1,N]。对每个i,使用K-Fold Validataion方法计算决策树,并裁剪到i个节点,计算错误率,最后求出平均错误率。(意思是说对每一个可能的i,都做K次,然后取K次的平均错误率。)这样可以用具有最小错误率对应的i作为最终决策树的大小,对原始决策树进行裁剪,得到最优决策树。

Random Forest

Random Forest是用训练数据随机的计算出许多决策树,形成了一个森林。然后用这个森林对未知数据进行预测,选取投票最多的分类。

优缺点

优点

  • 易于理解和解释,人们很容易理解决策树的意义。

  • 只需很少的数据准备,其他技术往往需要数据归一化。

  • 即可以处理数值型数据也可以处理类别型数据。其他技术往往只能处理一种数据类型。例如关联规则只能处理类别型的而神经网络只能处理数值型的数据。
  • 使用白箱模型.。输出结果容易通过模型的结构来解释。而神经网络是黑箱模型,很难解释输出的结果。

  • 可以通过测试集来验证模型的性能 。可以考虑模型的稳定性。

  • 强健控制. 对噪声处理有好的强健性。

  • 可以很好的处理大规模数据 。

缺点

  • 只能采用启发式搜索算法(例如 贪心算法)来达到局部最优,但却没办法得到全局最优。
  • 决策树创建的过度复杂会导致无法很好的预测训练集之外的数据。这称作过拟合。剪枝机制可以避免这种问题。
  • 有些问题决策树没办法很好的解决,例如 异或问题。

参考

  1. 决策树学习-维基百科
  2. 机器学习方法(四):决策树Decision Tree原理与实现技巧
  3. 算法杂货铺——分类算法之决策树(Decision tree)

Content