机器学习和数据挖掘决策树学习

历史地图研究

6年前

决策树学习是一种非常重要的AI算法，因为它非常强大，而且从数据中提取知识也简单而有效。与已经引入的两种学习算法相比，它具有重要的优势。提取的知识不仅可用作黑盒函数，而且可以通过可读决策树的形式轻松地理解，解释和控制。这也使决策树学习成为数据挖掘的重要工具。

我们将讨论使用C4.5算法的决策树学习的功能和应用。C4.5由澳大利亚人Ross Quinlan于1993年推出，是对其前身ID3（Iterative Dichotomiser 3,1986）的改进。它可以免费用于非商业用途[Qui93]。C5.0 [Qui93]是一个进一步发展，它可以更有效地工作，并且可以考虑决策的成本。

由Leo Breiman [BFOS84]开发的CART（Classification and Regression Trees，1984）系统与C4.5类似。它有一个方便的图形用户界面，但非常昂贵。

二十年前，在1964年，J。Sonquist和J. Morgan介绍了可以自动生成决策树的CHAID（卡方自动交互检测器）系统。它具有值得注意的特征，它在树变得太大之前就会停止树的生长，但今天它没有更多的相关性。

表8.4 滑雪分类问题的变量

变量	值	描述
滑雪（球门变量）	是的，没有	我应该开车到最近的滑雪胜地吗？
太阳（功能）	是的，没有	今天有阳光吗？
Snow_Dist （功能）	≤ 100，> 100	距离最近的滑雪胜地有很好的降雪条件（超过/低于100公里）
周末（特色）	是的，没有	今天是周末吗？

同样有趣的是数据挖掘工具KNIME（Konstanz Information
Miner），它具有友好的用户界面，并且使用WEKA Java库，也可以实现决策树的归纳。在Sect。8.8我们将介绍KNIME。

现在我们首先在一个简单的例子中展示如何根据训练数据构建决策树，然后分析算法并将其应用于更复杂的L EXMED医学诊断示例。

1.
一个简单的例子

住在加利福尼亚州加利福尼亚州一个美丽的山脉
– 高山脉附近的一位虔诚的滑雪者想要一棵决策树来帮助他决定是否值得将他的车开到山区的滑雪胜地。因此，基于表8.4中列出的变量，我们有两个问题，即滑雪是/否。

第 186 页的图 8.23 显示了此问题的决策树。决策树是一个树，其内部节点代表特征（属性）。每条边代表一个属性值。在每个叶节点处给出类值。

≥

用于构建决策树的数据显示在第 186 页的表 8.5中。表中的每一行都包含一天的数据，因此代表一个样本。经过仔细研究，我们看到第6行和第7行相互矛盾。因此，没有确定性分类算法可以正确地对所有数据进行分类。因此，错误分类数据的数量必须为1.因此，第 186 页的图 8.23中的树可以最佳地对数据进行分类。

如何根据数据创建这样的树？为了回答这个问题，我们首先将自己局限于具有有限多个值的离散属性。因为属性的数量也是有限的，并且每个属性每个路径最多可以出现一次，所以有许多不同的决策树。用于构造树的简单明显的算法将简单地生成所有树，然后对于每个树计算数据的错误分类的数量，并且最后选择具有最小错误数量的树。因此，我们甚至可以为决策树学习提供最佳算法（在训练数据的错误意义上）。

这种算法的明显缺点是，只要属性数量变得更大，其计算时间就会高得令人无法接受。我们现在将开发一种启发式算法，从根开始递归构建

图8.23滑雪分类问题的决策树。在节点右侧的列表中，给出了相应训练数据的编号。请注意，叶子节点的晴天是只有两三个例子正确

表8.5的数据集

Day Snow_Dist周末太阳滑雪

滑雪分类问题

1.
≤ 100是是是

2.
≤ 100是是是

3.
≤ 100是否是

4.
≤ 100否是是

5.
> 100是是是

6.
> 100是是是

7.
> 100是是否

8.
> 100是否否

9.
> 100否是否

10.
> 100否是否

11.
> 100否否否

≤

决策树。首先，从所有属性的集合中为根节点选择具有最高信息增益（Snow_ Dist）的属性。对于每个属性值（100，

> 100）树中有一个分支。现在，对于每个分支，此过程以递归方式重复。在节点生成期间，始终根据贪婪策略的精神选择尚未使用的属性中信息增益最高的属性。

2.
熵作为信息内容的度量

用于构造决策树的所描述的自上而下算法在每个步骤中选择具有最高信息增益的属性。我们现在介绍一下

熵作为一组训练数据D的信息内容的度量。如果我们只看上面例子中的二元变量滑雪，那么D可以描述为

D = （是，是，是，是，是，是，否，否，否，否，否）具有估计概率

p 1 = P（是）= 6 / 11和 p 2 = P（无）= 5 / 11。

在这里，我们明显地具有的概率分布p（ 6 / 11 ， 5 / 11 ）。一般来说，对于一个n类问题，这就读了

同

p =（p 1，…，pn）

pi = 1。

i = 1

为了介绍分布的信息内容，我们观察了两种极端情况。首先，让我们

p =（1，0，0，…，0）。（8.4）

也就是说，n个事件中的第一个肯定会发生而其他所有事件都不会发生。因此事件结果的不确定性很小。相反，为均匀分布

1 1 1

p ,, ……

NNN

（8.5）

不确定性是最大的，因为没有事件可以与其他事件区分开来。克劳德・香农在这里问自己要编码这样一个事件需要多少比特。在（ 8.4 ）的某些情况下，需要零比特，因为我们知道总是发生i = 1的情况。在（ 8.5 ）的均匀分布的情况下，存在

ñ 同样可能的可能性。对于二进制编码，此处需要log
2 n 位。

p 我

因为所有单个概率都是pi = 1 / n，所以需要log 2
1 比特

编码。

p 我

在一般情况下p（p 1
，…，pn），如果基本事件的概率偏离均匀分布，则计算比特数的期望值H. 为此，我们将权重所有值log 2
1 = – log 2
pi with

他们的概率和获得

H = pi（– log 2 pi）= – pi log 2 pi。

i = 1

我们需要对事件进行编码的位数越多，结果的不确定性就越高。因此我们定义：

图8.24两类情况下的熵函数。我们看到在最大 p 1 / 2和对称相对于交换 p和1 – p

定义8.4
的熵H 为度量的概率分布的不确定性是通过定义7

H（p）= H（p，…，p）：= – p log p。

i = 1

一世

该公式的详细推导见[SW76]。如果我们替换某些事件p = （ 1 ， 0 ， 0 ，…， 0 ），然后0日志2 0，未定义的表达结果。我们通过定义0 log 2 0 ：= 0来解决这个问题（参见第218 页的练习8.9）。

现在，我们可以计算出H（ 1 ， 0 ，…， 0 ）= 0。我们将证明，在熵

i = 1

超立方体[ 0 ， 1 ] Ñ的约束下Ñ PI = 1取在其最大值上

均匀分布

（n，…，n）。如果事件具有两个可能的结果，对应于两个类，则结果为

H（p）= h（第1，第2）= h（第1，1 – p 1）= – （第1个日志2 p 1 +（1 – p 1）日志2（1 – p 1））。

该表达式在图8.24中显示为p 1的函数，其最大值为

p 1 1 / 2中。

因为通过估计类概率为每个分类数据集D分配概率分布p，所以我们可以将熵的概念扩展到数据

7
在第124页的（7.9）中，自然对数而不是log 2
用于熵的定义。因为在这里，并且在MaxEnt方法的情况下，熵只是被比较，这种差异不起作用。（参见第 218 页的练习 8.11 ）。

定义

H（D）= H（p）。

现在，由于数据集D 的信息内容I（D）意味着与不确定性相反。因此我们定义：

定义8.5 数据集的信息内容定义为

I（D）：= 1 – H（D）。

（8.6）

3.
信息增益

如果我们将熵公式应用于示例，则结果为

H（6 / 11，5 / 11）= 0。994

产生的未分割数据集的信息内容I（D）

在构建决策树期间，数据集进一步细分为每个新属性。属性越多，通过划分数据来提升分布的信息内容，属性越好。我们相应地定义：

定义8.6的信息增益G（d，A）通过使用属性的

A 由平均信息内容的差异决定

数据集 d = d 1 ∪ d 2 ∪…∪ DN 由分割 Ñ -value属性甲和

G（D，A）=

i
= 1 | D |

我（迪）–我（D）。

一世

D |

用（ 8.6 ）我们从中获得

G（D，A） = | D i | 我（D） – 我（D） = | D i
| （1 – H（D）） – （1 – H（D））

一世

i =
1 | D |

一世

= 1 – | D i
| H（D） – 1 + H（D）

i
= 1 | D |

| D | = H（d） – H（d）。（8.7）

一世

i
= 1 | D |

图8.25 各种属性的计算增益反映了各个属性对数据的划分是否导致更好的类划分。属性生成的分布越偏离均匀分布，信息增益越高

应用于我们的属性Snow_Dist的示例，这会产生

G（d，Snow_Dist）= H（d）– 4 H（d ≤ 100）+ 7 H（d 100）

= 0 。994 – 4 ・ 0 + 7 ・ 0 。863 = 0 。445 。

类似地我们获得

和

G（D，Weekend）= 0。150

G（D，Sun）= 0。049。

Snow_Dist属性现在成为决策树的根节点。在图8.25中再次阐明了该属性选择的情况。

的两个属性值≤ 100和> 100生成在树的两个边缘，其对应于所述子集ð ≤ 100和d> 100对于子集d ≤ 100中的分类

显然是的。因此树终止于此。在另一个分支D> 100中没有明确的结果。因此，算法递归地重复。从仍然可用的两个属性，Sun和Weekend，必须选择更好的属性。我们计算

G（D> 100，Weekend）= 0。292

和

G（D> 100，太阳）= 0。170。

因此节点获得Weekend赋值属性。对于周末，没有树与决定滑雪号决定终止。此处增益的计算返回值0.对于周末是，Sun 获得0.171的增益。然后树的构造终止，因为没有其他属性可用，尽管示例编号7被错误地分类。已完成的树已在第186 页的图8.23中熟悉。

4. C4.5的应用

我们刚刚生成的决策树也可以由C4.5生成。训练数据以以下格式保存在数据文件ski.data中：

<= 100，	是，	是，	是
<= 100，	是，	是，	是
<= 100，	是，	没有，	是
<= 100，	没有，	是，	是
> 100，	是，	是，	是
> 100，	是，	是，	是
> 100，	是，	是，	没有
> 100，	是，	没有，	没有
> 100，	没有，	是，	没有
> 100，	没有，	是，	没有
> 100，	没有，	没有，	没有

有关属性和类的信息存储在ski.names文件中

（以“ | ” 开头的行是注释）：

|课程：不：不滑雪，是的：去滑雪

| 没有，是的。

|属性

Snow_Dist：<= 100，> 100。

周末：不，是的。

太阳：不，是的。

然后从Unix命令行调用C4.5并生成如下所示的决策树，该树使用缩进格式化。选项-f用于输入文件的名称，选项-m指定在树中生成新分支所需的最小训练数据点数。因为在这个例子中训练数据点的数量非常小，所以-m 1在这里是明智的。对于较大的数据集，应使用至少-m 10的值。

unixprompt> c4.5 -f ski -m 1

C4.5 [release 8]决策树生成器

2010年8月23日星期三10:44:49

—————————————-

选项：

文件干<ski>

合理的测试需要2个分支> = 1个案例从ski.data读取11个案例（3个属性）

决策树：

Snow_Dist = <= 100：ja（4.0）

Snow_Dist => 100：

| 周末=否：否（3.0）

| 周末=是：

| | 太阳=否：否（1.0）

| | Sun =是：是（3.0 / 1.0）简化决策树：

Snow_Dist = <= 100：是（4.0 / 1.2）Snow_Dist
=> 100：否（7.0 / 3.4）

培训数据评估（11项）：

在修剪之前

—————-

修剪后

—————————

大小错误大小错误估计

1（9.1％）

2（18.2％）（41.7％）<<

另外，给出了仅具有一个属性的简化树。这棵树是通过修剪（参见第8.4.7节）创建的，对于越来越多的训练数据非常重要。在这个小例子中它还没有多大意义。还给出了训练数据上两棵树的错误率。决策后括号中的数字给出了基础数据集的大小和错误数。例如，顶部树中的行Sun = yes：yes（3.0 / 1.0）表示对于该叶节点Sun =是，存在三个训练示例，其中一个被错误地分类。因此，用户可以从中读取该决定是否在统计上是基于和/或确定的。

在第 193 页的图 8.26中，我们现在可以给出用于生成决策树的学习算法的模式。

我们现在熟悉自动生成决策树的基础。然而，对于实际应用，需要重要的扩展。我们将使用已经熟悉的L EXMED应用程序介绍这些。

G ENERATE D ECISION T REE（数据，节点）

Amax =具有最大信息增益的属性

然后 Node 成为 Data 节点中频率最高的叶子节点

否则将属性Amax分配给Node

对于每一个值一 1 ，…，一个的λ最大，生成

后继节点：K 1 ，…，Kn

然后生成的叶节点的Ki类的次

其他 G ENERATE D ECISION T REE（D i
，K i）

如果所有的 X ∈迪属于同一类词

划分数据成 d 1，…，DN 与狄= { X ∈数据| Amax（x）= ai }

对于所有我∈{ 1，…，N }

如果G（Amax）= 0

图8.26 构建决策树的算法

5.
学习阑尾炎的诊断

在研究项目L EXMED中，在患者数据数据库[ES99，SE00]的基础上开发了阑尾炎诊断专家系统。该系统采用最大熵方法，在Sect。7.3

我们现在使用L EXMED数据库生成用C4.5诊断阑尾炎的决策树。用作属性的症状在app.names文件中定义：

|类和属性的定义

| 0级=阑尾炎阴性

| 1 =阑尾炎阳性0,1。

|属性

年龄：持续。性别（1 = m 2 = w）：1,2。

Pain_Quadrant1_（0 =没有 1 =是）：0,1。

Pain_Quadrant2_（0 =没有 1 =是）：0,1。

Pain_Quadrant3_（0 =没有 1 =是）：0,1。

Pain_Quadrant4_（0 =没有 1 =是）：0,1。

Local_guarding_（0 = no 1 = yes）：0,1。

Generalized_guarding_（0 = no 1 = yes）：0,1。

Rebound_tenderness_（0 =无 1 =是）：0,1。

Pain_on_tapping_（0 =没有 1 =是）：0,1。

Pain_during_rectal_examination_（0 =没有 1 =是）：0,1。Temp_axial：连续的。

Temp_rectal：连续的。白细胞：连续的。

Diabetes_mellitus_（0 =没有 1 =是）：0,1

我们看到，除了诸如各种疼痛症状之类的许多二元属性之外，还会出现诸如年龄和发烧温度的连续症状。在下面的训练数据文件app.data中，每行描述一个案例。第一行是一名19岁男性患者，第三象限疼痛（右下方，阑尾位置），两个发热值分别为36.2和37.8摄氏度，白细胞值为13400，阳性诊断为是，发炎的阑尾。

19,1,0,0,1,0,1,0,1,1,0,362,378,13400,0,1

13,1,0,0,1,0,1,0,1,1,1,383,385,18100,0,1

32,2,0,0,1,0,1,0,1,1,0,364,374,11800,0,1

18,2,0,0,1,1,0,0,0,0,0,362,370,09300,0,0

73,2,1,0,1,1,1,0,1,1,1,376,380,13600,1,1

30,1,1,1,1,1,0,1,1,1,1,377,387,21100,0,1

56,1,1,1,1,1,0,1,1,1,0,390，？，14100,0,1

36,1,0,0,1,0,1,0,1,1,0,372,382,11300,0,1

36,2,0,0,1,0,0,0,1,1,1,370,379,15300,0,1

33,1,0,0,1,0,1,0,1,1,0,367,376,17400,0,1

19,1,0,0,1,0,0,0,1,1,0,361,375,17600,0,1

12,1,0,0,1,0,1,0,1,1,0,364,370,12900,0,0

…

在没有详细说明数据库的情况下，重要的是要提到只有在到达医院时被怀疑患有阑尾炎并随后进行手术的患者才被包括在数据库中。我们在第七行看到C4.5也可以处理缺失值。该数据包含9764个案例。

unixprompt> c4.5 -f app -u -m 100

C4.5 [release 8]决策树生成器

2006年8月23日星期三13:13:15

—————————————-

从app.data决策树中读取9764个案例（15个属性）：

白细胞<= 11030：

| Rebound_tenderness = 0：

| | Temp_rectal> 381：1（135.9 / 54.2）

| | Temp_rectal <= 381：

| | | Local_guarding = 0：0（1453.3 / 358.9）

| | | Local_guarding = 1：

| | | | 性别（1 = m 2 = w）= 1：1（160.1 / 74.9）

| | | | 性别（1 = m 2 = w）= 2：0（286.3 / 97.6）

| Rebound_tenderness = 1：

| | 白细胞<= 8600：

| | | Temp_rectal> 378：1（176.0 / 59.4）

| | | Temp_rectal <= 378：

| | | | Sex_（1 = m 2 = w）= 1：

| | | | Sex_（1 = m 2 = w）= 2：

| | | | | 年龄<= 14：1（131.1 /
63.1）

| | | | | 年龄> 14：0（398.3 /
137.6）

| | 白细胞> 8600：

| | | 性别（1 = m 2 = w）= 1：1（429.9 / 91.0）

| | | Sex_（1 = m 2 = w）= 2：

| | | | Local_guarding = 1：1（311.2 / 103.0）

| | | | Local_guarding = 0：

| | | | | Temp_rectal> 375：0（118.3 / 56.1）白细胞> 11030：

| Rebound_tenderness = 1：1（4300.0 / 519.9）

| Rebound_tenderness = 0：

| | 白细胞> 14040：1（826.6 /
163.8）

| | 白细胞<= 14040：

| | | Pain_on_tapping = 1：1（260.6 / 83.7）

| | | Pain_on_tapping = 0：

| | | | Local_guarding = 1：1（117.5 / 44.4）

| | | | Local_guarding = 0：

白细胞> 11030：1（5767.0 / 964.1）白细胞<= 11030：

| Rebound_tenderness = 0：

| | Temp_rectal> 381：1（135.9 / 58.7）

| | Temp_rectal <= 381：

| | | Local_guarding = 0：0（1453.3 / 370.9）

| | | Local_guarding = 1：

| | | | 性别（1 = m 2 = w）= 1：1（160.1 / 79.7）

| | | | 性别（1 = m 2 = w）= 2：0（286.3 / 103.7）

| Rebound_tenderness = 1：

| | 白细胞> 8600：1（984.7 /
322.6）

| | 白细胞<= 8600：

| | | Temp_rectal> 378：1（176.0 / 64.3）

| | | Temp_rectal <= 378：

| | | | Sex_（1 = m 2 = w）= 1：

| | | | Sex_（1 = m 2 = w）= 2：

| | | | | 年龄<= 14：1（131.1 /
67.6）

在修剪之前修剪之前

—————- —————————

大小错误大小错误估计

37 2197（22.5％）21 2223（22.8％）（23.6％）<<

评估测试数据（4882项）：

在修剪之前修剪之前

—————- —————————

大小错误大小错误估计

37 1148（23.5％）21 1153（23.6％）（23.6％）<<

（a）（b）< – 分类为

—- —-

758 885（a）：0级

268 2971（b）：第1类

6.
连续属性

在为阑尾炎诊断产生的树中，存在节点白细胞

> 11030，其通过将阈值设定为值11030 而明显来自连续属性白细胞。因此，C4.5 从连续属性白细胞产生二元属性白细胞> 11030。属性A的阈值ΘD，A由以下算法确定：对于在训练数据D中出现的所有值v，生成二进制属性A> v并计算其信息增益。然后将阈值ΘD，A设置为具有最大信息增益的值v，即：

ΘD，A = argmax v { G（D，A> v） } 。

对于诸如白细胞值或患者年龄的属性，基于二元离散化的决定可能过于不精确。然而，不需要更精细地离散化，因为在每个新生成的节点上测试每个连续属性，并且因此可以在具有不同阈值ΘD，A的一个树中重复出现。因此，我们最终获得了非常好的离散化，其细度适合于问题。

图8.27 关于阑尾炎数据的C4.5学习曲线。我们清楚地看到超过55个节点的树的过度拟合

7. 修剪，切割树

自亚里士多德时代以来，已经规定了同样适用于同一情况的两种科学理论，更为简单的理论。这种经济法，现在也被称为奥卡姆剃刀，对于机器学习和数据挖掘非常重要。

决策树是用于描述训练数据的理论。描述数据的不同理论是数据本身。如果树对所有数据进行了分类而没有任何错误，但是更加紧凑，因此人们更容易理解，那么根据奥卡姆剃刀更好。两个不同大小的决策树也是如此。因此，用于生成决策树的每个算法的目标必须是针对给定的错误率生成最小可能的决策树。在具有固定错误率的所有树中，应始终选择最小的树。

到目前为止，我们尚未准确定义术语错误率。正如已经多次提到的那样，重要的是学习树不仅要记住训练数据，而应该很好地概括。为了测试树概括的能力，我们将可用数据分成一组训练数据和一组测试数据。测试数据对学习算法隐藏，仅用于测试。如果有大型数据集，例如阑尾炎数据，那么我们可以使用三分之二的数据进行学习，剩下的三分之一进行测试。

除了更好的理解之外，奥卡姆的剃刀还有另一个重要的理由：泛化能力。模型越复杂（这里是决策树），表示的细节越多，但在相同程度上，可转换为新数据的模型越少。这种关系如图8.27 所示。针对阑尾炎数据训练各种大小的决策树。在图中，给出了训练数据和测试数据的分类错误。训练数据的错误率随着树的大小单调减小。最多55个节点的树大小，测试数据的错误率也会降低。然而，如果树进一步增长，则错误率再次开始增加！我们已经在最近邻方法中看到过这种效应过度拟合。

我们将给出这个对几乎所有学习过程都很重要的概念，这个概念取自[Mit97]：

定义8.7让我们给出一个特定的学习算法，即学习代理。我们称一个代理一个过度拟合训练数据，如果有另一个代理一个训练数据，其误差比的较大一个，但对数据的整体分布，其误差比的误差较小的一个。

我们现在怎样才能在测试数据上找到这一最小误差点？最明显的算法称为交叉验证。在构造树期间，并行测量测试数据的误差。一旦错误显着上升，就会保存具有最小错误的树。该算法由前面提到的CART系统使用。

C4.5的工作方式略有不同。首先，使用第193 页的图8.26中的算法G ENERATE D ECI – SION T REE，它生成一个通常过度拟合的树。然后，使用修剪，它试图切除树的节点，直到由训练数据的误差估计的测试数据上的错误开始上升。8就像树的构造一样，这也是一种贪婪的算法。这意味着一旦节点被修剪，它就无法重新插入，即使后来证明更好。