摘 要：本文探讨了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）最大。……