ID3 决策树算法 - 第 1 部分

引言

迭代二分器3 (Iterative Dichotomiser 3) 或 ID3 是一种用于生成决策树的算法，关于 ID3 算法的详细信息可以在这里找到。ID3 算法有许多用途，特别是在机器学习领域。在本文中，我们将了解 ID3 算法中使用的属性选择过程。属性选择部分分为与数据集相关的基本信息，讨论了熵和信息增益，并使用了一些示例来展示如何使用示例数据计算熵和信息增益。

属性选择

属性选择是构建决策树的基本步骤。熵和信息增益这两个术语用于处理属性选择，通过属性选择，ID3 算法选择哪个属性将成为决策树的节点，依此类推。深入探讨之前需要介绍一些属性选择过程中使用的术语，

Outlook（展望）	温度	湿度	风	打球
晴朗	热	高	弱	否
晴朗	热	高	强	否
阴天	热	高	弱	是
雨	温和	高	弱	是
雨	凉爽	正常	弱	是
雨	凉爽	正常	强	否
阴天	凉爽	正常	强	是
晴朗	温和	高	弱	否
晴朗	凉爽	正常	弱	是
雨	温和	正常	弱	是
晴朗	温和	正常	强	是
阴天	温和	高	强	是
阴天	热	正常	弱	是
雨	温和	高	强	否
			总计	14

属性

在上面的表格中，Day、Outlook、Temperature、Humidity、Wind、Play ball 都表示为属性，

类别(C) 或 分类器

在这些属性中，Play ball 被称为类别(C)或分类器。因为我们需要根据 Outlook、Temperature、Humidity 和 Wind 来决定是否可以打球，所以 Play ball 是一个用于做出决策的分类器。

集合 (S)

表格中的所有记录都称为集合 (S)。

熵计算

熵是信息论中的一种度量方法，关于熵的详细信息在这里。在这里，我们将看到如何计算给定数据集的熵。这里使用的测试数据是图1的数据，

熵(S) = ∑_n=1-p(I)log₂p(I)

p(I) 指的是 S 属于类别 I 的比例，即在上面的表格中，我们有两种类别 {否, 是}，分别有 {5, 9} 个（这里 5 是否的总数，9 是是的总数），集合大小 S=14。因此，整个集合中 C 的 p(I) 分别是 否 (5/14) 和 是 (9/14)。

log₂p(I)，指的是 C 中 log₂(5/14) 和 log₂(9/14)。

∑ 是对 c 的求和，即所有分类器项的总和。在这种情况下，-p(否/S)log₂p(否/S) 和 -p(是/S)log₂p(是/S) 的总和 = -p(否/S)log₂p(否/S) + -p(是/S)log₂p(是/S)

所以，

熵(S) = ∑-p(I)log₂p(I)

=) 熵(S) = -p(否/S)log₂p(否/S) + -p(是/S)log₂p(是/S)

=) 熵(S) = ((-(5/14)log₂(5/14)) + (-(9/14)log₂(9/14)) )

=) 熵(S) = (-0.64285 x -0.63743) + (-0.35714 x -1.485427)

=) 熵(S) = 0.40977 + 0.5305096 = 0.940

所以 S 的熵是 0.940

信息增益 G(S,A)

信息增益是选择特定属性作为决策树决策节点的过程。有关信息增益的详细信息，请参阅此处。

信息增益是 G(S,A)

其中 S 是数据集中数据的集合，A 是将在集合 S 上计算信息增益的属性。因此，如果 Gain(S, Wind)，则指 Wind 在 S 上的增益。

Gain(S, A) = 熵(S) - ∑( ( |S_v|/|S| ) x 熵(S_v) )

其中，

S 是记录的总集合。

A 是将计算增益的属性。

v 是属性 A 的所有可能值，例如在本例中，如果我们考虑 Windy 属性，则 v 的集合是 { 弱, 强 }。

S_v 是每个 v 的元素数量，例如 S_弱 = 8，S_强 = 6。

∑ 是对 v 集合中所有项的 ( ( |S_v|/|S| ) x 熵(S_v) ) 的求和，即 ( ( |S_弱|/|S| ) x 熵(S_弱) ) + ( ( |S_强|/|S| ) x 熵(S_强) )

因此，如果我们想使用以下公式计算 Wind 在集合 S 上的信息增益，

Gain(S, A) = 熵(S) - ∑( ( |S_v|/|S| ) x 熵(S_v) )

那么它将如下所示，

=) Gain(S, Wind) = 熵(S) - ( ( |S_弱|/|S| ) x 熵(S_弱) ) - ( ( |S_强|/|S| ) x 熵(S_强) )

从上表中可知，对于 Wind 属性，有两种类型的数据（弱，强），因此新的数据集将分为以下两个子集，如下所示，

Outlook（展望）	温度	湿度	风	打球
晴朗	热	高	弱	否
阴天	热	高	弱	是
雨	温和	高	弱	是
雨	凉爽	正常	弱	是
晴朗	温和	高	弱	否
晴朗	凉爽	正常	弱	是
雨	温和	正常	弱	是
阴天	热	正常	弱	是
			总计	8

Outlook（展望）	温度	湿度	风	打球
晴朗	热	高	强	否
雨	凉爽	正常	强	否
阴天	凉爽	正常	强	是
晴朗	温和	正常	强	是
阴天	温和	高	强	是
雨	温和	高	强	否
			总计	6

所以，Wind 属性的集合是 (Weak, Strong)，元素总数集合是 (8,6)。

=) Gain(S, Wind) = 0.940 - ( (8/14 ) x 熵(S_弱) ) - ( ( 6/14 ) x 熵(S_强) )

如前所述，如何计算熵，现在我们将计算“弱”的熵，有两个分类器“否”和“是”，对于“弱”，分类器集合是（否，是），元素数量集合是（2,6），“强”的（否，是）集合是（3,3）。

熵(S_弱) = ∑-p(I)log₂p(I) = ( - ( (2/8)xlog₂(2/8) ) ) + ( - ( (6/8)xlog₂(6/8) ) )

=) 熵(S_弱) = 使用前面提到的熵计算过程计算得出的 S_弱 值。

和

熵(S_强) = ∑-p(I)log₂p(I) = ( - ( (3/6)xlog₂(3/6) ) ) + ( - ( (3/6)xlog₂(3/6) ) )

=) 熵(S_强) = 使用前面提到的熵计算过程计算得出的 S_强 值。

因此 Gain(S, Wind) 将如下所示，

=) Gain(S, Wind) = 0.940 - ( (8/14 ) x 熵(S_弱) ) - ( ( 6/14 ) x 熵(S_强) )

=) Gain(S,Wind) = 0.940 - S_弱 的值 - S_强 的值

=) Gain(S, Wind) = 0.048

所以 Wind 在 S 上的信息增益是 0.048。使用相同的过程，可以计算 Outlook、Temperature 和 Humidity 的信息增益。根据 ID3 算法，将选择增益最高的作为决策节点，这里是 Outlook，因此，图 1 所示的数据集将按以下方式划分：

Outlook（展望）	温度	湿度	风	打球
晴朗	热	高	弱	否
晴朗	热	高	强	否
晴朗	温和	高	弱	否
晴朗	凉爽	正常	弱	是
晴朗	温和	正常	强	是
			总计	5

Outlook（展望）	温度	湿度	风	打球
阴天	热	高	弱	是
阴天	凉爽	正常	强	是
阴天	温和	高	强	是
阴天	热	正常	弱	是
			总计	4

Outlook（展望）	温度	湿度	风	打球
雨	温和	高	弱	是
雨	凉爽	正常	弱	是
雨	凉爽	正常	强	否
雨	温和	正常	弱	是
雨	温和	高	强	否
			总计	5

Outlook 有三个不同的值：Sunny、Overcast、Rain，这些值将用作决策节点。

因此，使用上述三个新集合，将计算 Temperature、Humidity 和 Wind 的信息增益，并根据计算出的信息增益值进一步选择节点以生成决策树节点。例如，如果我们想计算 Humidity 相对于 Sunny 的信息增益，那么：

Gain(S, A) = 熵(S) - ∑( ( |S_v|/|S| ) x 熵(S_v) )

=) Gain(S, A) = ∑-p(I)log₂p(I) - ∑( ( |S_v|/|S| ) x 熵(S_v) ) =) Gain(S_晴朗, 湿度) = (- 3/5log₂3/5 - 2/5log₂₂/5) - ( ( 3/5 ) x 熵(S_高) ) - ( ( 2/5 ) x 熵(S_低) )

其中，
3/5 指的是“否”的总数/“否”和“是”的总数
2/5 指的是“是”的总数/“否”和“是”的总数（从“晴朗”集合中）

=) Gain(S_晴朗, 湿度) = (0.4421 +0.528 ) - ( ( 3/5 ) x ∑-p(I)log₂p(I) ) - ( ( 2/5 ) x ∑-p(I)log₂p(I) ) )

=) Gain(S_晴朗, 湿度) = (0.9708 ) - ( ( 3/5 ) x (- (3/3log₂ 3/3) - ( 0/3log₂ 0/3 ) ) ) - ( ( 2/5 ) x ( -(0/2)log₂ 0/2 - (2/2log₂2/2) ) ) )

其中，
3/3 指的是“高”集合中“否”的总数/“否”和“是”的总数
0/3 指的是“高”集合中“是”的总数/“否”和“是”的总数
0/2 指的是“低”集合中“否”的总数/“否”和“是”的总数
2/2 指的是“低”集合中“是”的总数/“否”和“是”的总数

=) Gain(S_晴朗, 湿度) = 0.9708 - 3/5 x (-1 x 0 ) - 2/5 x ( 0 - ( 1x 0))

=) Gain(S_晴朗, 湿度) = 0.9708

所以湿度对于 S_晴朗集合的信息增益是 0.9708。同样地，我们可以计算温度、风对于 S_晴朗的信息增益。

参考文献

在撰写本文期间，使用了以下网站作为参考：

• http://en.wikipedia.org/wiki/ID3_algorithm
• http://en.wikipedia.org/wiki/Entropy_(information_theory)
• http://en.wikipedia.org/wiki/Information_gain_in_decision_trees
• http://en.wikipedia.org/wiki/Machine_learning
• http://en.wikipedia.org/wiki/Decision_tree_learning
• http://chem-eng.utoronto.ca/~datamining/dmc/decision_tree.htm
• http://mrthin.blogspot.com/2010/09/id3-algorithm.html
• http://logbase2.blogspot.com/2008/08/log-calculator.html

历史

版本 1.0