奇书网

第二节 决策树的ID3算法（第1页）

第二节决策树的ID3算法

有了关于分类问题的基本认识，本节介绍一种简单的分类算法——决策树。决策的意思就是使用训练数据学习分类的决策依据，从而可以据此对需要分类的数据属于哪一类这样的问题给出决策。决策树是人工智能中的经典算法，既适用于输出结果为连续值的回归问题（又叫回归树），也适用于输出结果为离散值的分类问题，它们的基本想法是一致的，理解了决策树的原理，回归树就很容易掌握了，本节只针对离散值的情形讲解决策树算法。

使用决策树进行分类其实模拟了人类决策的过程。例如，小明想约小红明天去看电影，发生了下述对话过程。

小红：明天有好看的电影吗？

小明：有啊，一部新上映的大片。

小红：看几点的？我只有中午有时间。

小明：正好中午12点有一场。

小红：明天天气怎么样？

小明：天气很舒服，不冷不热。

小红：好的，那你明天按时来接我吧。

小明：明天见。

在这个对话中，小红对明天看电影的事情有“看”和“不看”两类安排，做出“看”的决定需要满足如下要求：电影好看、时间合适，并且天气舒服。这个决策的过程可以通过图3-1来描述。

图3-1

上述图示很好地展示了决策树的直观含义。所谓决策树，指的是一个树形结构，其中每个内部节点代表一个特征属性，内部节点的每个分支路径代表了此特征属性的某个可能的属性值，而每个叶子节点代表一个类别。因为每个内部节点都会生长出几个不同的分支，沿分支可以到达其他的内部节点或叶子节点，所以此内部节点对应的特征属性又叫作分裂属性。

决策树是一个用于分类的预测模型，也就是说，它给出了每个待分类对象到类别的一种映射关系。使用决策树进行决策的过程就是从根节点开始，测试待分类对象相应的特征属性，按照属性值选择分支路径，直至到达某个叶子节点，将此叶子节点存放的类别作为决策结果。

可以结合上面的直观例子理解与决策树相关的概念。所谓树形结构，指的是图3-1就像一棵倒置的树。橙色的节点都是内部节点，代表“电影质量”“时间”“天气”三个特征属性，特别地，“电影质量”叫作根节点。存放决策结果“看”或者“不看”的绿色节点就是叶子节点。有了这个树形结构，根据特征属性的不同取值，沿着决策树的不同路径，就可以做出相应的决策了。

在这个直观的例子中，每个特征属性都有两个可能的取值，所以对应两个分支，这样的树叫作二叉树。决策树对特征属性的取值没有个数限制，所以决策过程对应的树形结构可以更复杂。与决策树复杂程度有关的另外一个因素是决策过程中所使用的特征属性的个数，它决定了树的深度。在这个例子中使用了三个特征属性，所以这是一个三层的决策树。

从这个例子看，决策树的道理很简单，对它进行决策的方式也已经了解得很清楚了。那么读者现在是不是可以完整地针对一个分类问题给出相应的决策树呢？如果尝试一下，会发现还有一个最关键的问题没有解决，就是如何构建一棵决策树。具体地说，关于决策树的构建，需要解决如下两个问题。

（1）如何选择分裂属性

这个问题可以分解成两个小问题：一是选择哪个特征属性作为根节点？二是某个内部节点之下应该选择哪个特征属性作为下一层分裂属性？

（2）何时停止树的生长

在决策树生长成什么样子以后，就可以作为最终进行决策时所使用的决策树了？

一个分类问题，通常包含多个特征属性。如果可以随意选择根节点和内部节点，当有m个特征属性时，用不同的顺序安排分裂属性，理论上可以生长出m！棵不同的决策树。所谓选择分裂属性的问题，其实是制订一个合理的量化标准，根据这个标准来比较不同的生长顺序的优劣，从而选择出最佳的生长顺序作为最终的决策树。

为了量化各种分裂属性选择方案的好坏，需要引入一个新的数学概念——熵（Entropy）。熵的概念是由信息论的创始人香农提出的，现在在很多学科中都有重要的用处。为了更容易理解这个概念，这里结合分类问题来描述它的定义。

设某个分类问题X包含n个类别m个特征属性，任意样本C属于第i个类别Xi（1≤i≤n）的概率为pi，则I（Xi）=-log2pi称为Xi的信息（Information），X的熵定义为

在分类问题中，如何简单地理解上述定义呢？显然有如下关系。

进而可以看出，类别Xi的信息是随着概率增加而减少的，也就是说，这个量衡量了Xi的不确定性。例如，概率为1时，它是注定会出现的，所以信息为0，不确定性最小；概率为0时，信息为+∞，不确定性最大。

而熵的概念可以结合概率中的全概率公式来理解，它代表了分类问题X的不确定性的期望（概率平均值），也就是对类别进行预测时的不确定性，或者说是预测的难度。

有了这样的认识，就可以很自然地给出确定分裂属性的原则：选择当前可以最大程度减少预测的不确定性的属性作为分裂属性。

衡量不确定性的减少程度有几种不同的计算方式，根据计算方式的不同，衍生出了不同的决策树算法。例如，使用信息增益的ID3算法，使用信息增益比的C4。5算法，还有使用基尼指数的CART算法。它们的原理是类似的，本教材介绍采用信息增益的ID3算法，其他算法只要把信息增益的计算公式替换成相应的其他计算公式就可以了。

在条件熵的基础上，就可以按如下方式定义信息增益（Gain）的概念了。

Gain（X，A）=H（X）-H（X|A）

信息增益还有一个名称叫作互信息，这是信息论中常用的名称。从熵和条件熵的定义可以看出，信息增益反映的是，选择A作为分裂属性后，分类问题的不确定性减少了多少。按照前面所说的选择分裂属性的原则，只要计算当前可供选择的所有特征属性对应的信息增益，以信息增益最大的属性作为决策树的下一个分裂属性即可。