[科普中国]-决策树方法

基本概念

决策树是一种从无次序、无规则的样本数据集中推理出决策树表示形式的分类规则方法。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向下的分支．在决策树的叶节点得到结论．因此从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。

分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点和有向边组成。节点有两种类型：内部节点和叶节点。内部节点表示一个特征或属性．叶节点表示一个类。用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直到达到叶节点。最后将实例分到叶节点的类中。决策树学习算法是以实例为基础的归纳学习算法，本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树可能有多个，也可能一个也没有。我们需要的是一个与训练数据集矛盾较小的决策树，同时具有很好的泛化能力。1

表示方法决策树的节点为方块、圆圈、和三角，节点问通过直线段连接，如

□一表示决策节点。从它引出的分支叫方案分支，每支代表一个方案。决策节点上标注的数字是所选方案的期望值。

○一表示方案节点。从它引出的分支叫概率分支。分支数反映可能的自然状态数。分支上注明的数字为该自然状态的概率。

△一表示结果节点。它旁边标注的数字为方案在某种自然状态下的收益值。

应用树状图进行决策的过程，是由右向左逐步前进，计算右端的期望收益值，或损失值，然后对不同方案的期望收益值的大小进行选择。方案的舍弃称为剪支。最后决策节点只留下唯一的一个，就是最优的决策方案。2

关键步骤决策树法的几个关键步骤是：

(1)画出决策树，画决策树的过程也就是对未来可能发生的各种事件进行周密思考、预测的过程，把这些情况用树状图表示出来．先画决策点，再找方案分枝和方案点．最后再画出概率分枝．

(2)由专家估计法或用试验数据推算出概率值．并把概率写在概率分枝的位置上．

(3)计算益损期望值，从树梢开始，由右向左的顺序进行．用期望值法计算．若决策目标是盈利时，比较各分枝，取期望值最大的分枝，其他分枝进行修剪．

用决策树法可以进行多级决策．多级决策(序贯决策)的决策树至少有两个或以上决策点．3

优点决策树法尤其适用于序贯决策(多级决策)，是描述序贯决策的有力工具．用决策树来进行决策。具有分析思路清晰、决策结果形象明确的优点．3

决策树方法简便易学，具有广泛的实用价值。由于多阶段问题由若干单阶段问题构成，所以决策树方法不仅可以解决多阶段问题，也可以解决单阶段问题。但考虑到它在解决多阶段问题上的作用无法被一般方法代替，故将其单独介绍，不过介绍仍然从单阶段问题开始。4

局限性采用传统的决策树进行决策或分类存在着局限性，以变量的某一阈值作为决策或分类的判别条件(如X>Ti)，变量取值在该阈值上下将引起决策或分类的突变(不连续性)，决策或分类结果对于阈值取值很敏感，并且决策树的知识可理解性较差。克服上述局限性的改进方法是，对决策或分类的条件和目标变量的取值进行云离散化表达，基于云理论的决策树既增加了知识的可理解性又确保决策或分类结果的连续性。

应用领域自20世纪60年代以来，决策树方法在分类、预测、规则提取等领域有着广泛应用，特别是在Quilan提出ID3算法以后，在机器学习、知识发现领域得到了进一步应用及发展。决策树的优点在于它的直观和易理解性，但在许多应用中变量值是连续和渐变的，并且在许多情况下，并不要求得到精确的输出预报值，而是能够将输出控制在一定的范围内或作出决策分类。采用传统的决策树进行决策或分类存在着局限性，以变量的某一阈值作为决策或分类的判别条件(如X>正)，变量取值在该阈值上下将引起决策或分类的突变(不连续性)，决策或分类结果对于阈值取值很敏感，并且决策树的知识可理解性较差。克服上述局限性的改进方法是，对决策或分类的条件和目标变量的取值进行云离散化表达，基于云理论的决策树既增加了知识的可理解性又确保决策或分类结果的连续性。5