DecisionTree的原理

摘 要：本文探讨了decision treee的设计原理，分析了Decision tree的核心分类思想，并给出了决策树的分值构建的伪码。

关键词：决策树;分类算法;信息熵;信息增益

一、 研究背景

给定A一个问题Q1，我们列出其诸多答案选项B。比如，B={B1，B2，…，Bn}。其中，n标示共有n个子选项，每个选项都是潜在的答案。然后，我们让A根据我们的提供的答案B，告诉我们B中的哪个答案是正确的，比如Bi是A给我们的反馈。若答案Bi并非问题的最终解，我们更进一步的根据B的特点提问，设问题是Q2，根据Q2，我们设定答案选项C。同样，不是一般性，我们假定C={C1，C2，…，Cp}。其中，p表示C中共有p个答案选项。如果A告诉我们Ci是正确答案，那么，我们就得到了更进一步地对问题的收敛解。以此类推，我们可以一直以这种操作延续下去，则最终肯定能够得到一组满足要求的解。这个过程就是普通树的生成过程，同时，也是决策树的研究背景。

二、 信息论基础

n分之一份信息量（定义1）：若存在n个相同概率的消息，则每个消息的概率p是1/n，一个消息传递的信息量为-log2（1/n）。

熵（定义2）：熵是体系混乱程度的度量，即信息的信息量大小和它的不确定性有直接的关系。对于任意一个随机变量X，若有n个消息，其给定概率分布为P=（p1，p2，…，pn），则由该分布传递的信息量称为P的熵，它的熵定义为：

H（X）=-∑xP（x）log2[P（x）]

由图可见，离散信源的信息熵具有：

①非负性：即收到一个信源符号所获得的信息量应为正值，H（X）≥0

②对称性：即P=0.5

③确定性：H（1，0）=0，即P=0或P=1已是确定状态，所得信息量为零

④极值性：因H（U）是P上是凸的，且一阶导数在P=0.5 时等于0，所以当P=0.5时，H（U）最大。

信息增益（定义）：设关于变量X的划分P，在做划分之前的信息为H（Xi），做划分之后的信息为H（Xi），则系统的增益为△=H（Xi）-H（Xi+δ）。其中δ表示相对Xi的该变量。

注意，这里的Xi是向量。我们称Xi为特征向量。显然信息的增益指的是变化前后系统中信息的变化量。若某个Xi，使得△最大，则这样的Xi是最好的，因为使用这个特征向量引起的操作增益是系统敏感的。

三、 基于ID3分类的Decision tree

决策树由node、branch和leaf组成。和普通的树一样，决策树的最上面的结点为根结点，递归地，每个branch是一个新的决策node，或者是树的leaf。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。决策树的分类的思想是：沿决策树从上到下遍历的过程中，在每个结点处都会生成一次询问测试，对每个checking node上的不同问题对应的不同的询问测试结果产生不同的后续分支，以此类推，直到最后到达某个叶子结点。前述增益的特性时，已经明确了，ID3算法计算每个属性的信息增益，对于关于使用某个特征值后系统的增益，越大越好。故使用作为具有最高增益的属性作为给定checking node的询问（query）测试属性。且以此询问测试属性构作一个node，并以该节点的属性标记，对该属性的每个值创建一个分支据此partition样本。

下面给出递归调用如下的CreateBranch函数创建决策树分支的方法创建决策树的伪代码，以结束本文的讨论：

CreateBrach（…）{

检测数据集中的每个子项是否属于同一类：

If yes

Return label of class

Else

通过计算信息熵获得的信息增益寻找划分数据集的最好特征

Partition data set

创建分支节点

For 每个划分的subset

Call CreateBranch（…），并增加返回结果到分支节点中

Return 分支结点

}

参考文献：

[1]周志华，王珏.机器学习及其应用2009[M].北京：清华大学出版社，2009.

[2]周志华.机器学习[J].航空港，2018（2）：94.

[3]崔伟东，周志华，李星，等.支持向量机研究[J].计算机工程与应用，2001（1）.

[4]姜远，黎铭，周志华.一種基于半监督学习的多模态Web查询精化方法[J].计算机学报，2009（10）：217-224.

[5]李楠，姜远，周志华.基于模型似然的超1-依赖贝叶斯分类器集成方法[J].模式识别与人工智能，2016，20（6）.

[6]曲开社，成文丽，王俊红.ID3算法的一种改进算法[J].计算机工程与应用，2003，39（25）：104-107.

作者简介：

智岩，广东省广州市，广州工商学院。