机器学习基础篇(十一)：决策树算法

type

status

date

slug

summary

一、基本概念

待补充

二、信息熵与条件熵

待补充

三、学习案例

3.1 ID3算法

3.1 基于西瓜数据集的ID3算法详细计算过程

根据图中的数据集逐步计算每个特征的信息增益，并选择最佳划分特征。

1. 计算初始信息熵

首先计算整个数据集的信息熵Ent(D)：

总样本数|D| = 17

正例("是")数量 = 8

反例("否")数量 = 9

Ent(D) = - (8/17)log₂(8/17) - (9/17)log₂(9/17)= -0.4706(-1.117) - 0.5294(-0.918)≈ 0.5255 + 0.4861≈ 0.998

2. 计算各特征的信息增益

(1) 特征"色泽"

"色泽"有三个取值：青绿、乌黑、浅白

青绿(D₁): 6个样本(3是,3否)

乌黑(D₂): 6个样本(4是,2否)

浅白(D₃): 5个样本(1是,4否)

计算各子集熵值：

Ent(D₁) = - (3/6)*log₂(3/6) - (3/6)*log₂(3/6) = 1

Ent(D₂) = - (4/6)*log₂(4/6) - (2/6)*log₂(2/6) ≈ 0.918

Ent(D₃) = - (1/5)*log₂(1/5) - (4/5)*log₂(4/5) ≈ 0.722

信息增益：

Gain(D,色泽) = Ent(D) - [ (6/17)*1 + (6/17)*0.918 + (5/17)*0.722 ]

≈ 0.998 - [ 0.3529 + 0.324 + 0.2124 ]

≈ 0.998 - 0.8893

≈ 0.109

(2) 特征"根蒂"

"根蒂"有三个取值：蜷缩、稍蜷、硬挺

蜷缩(D₁): 8个样本(5是,3否)

稍蜷(D₂): 7个样本(3是,4否)

硬挺(D₃): 2个样本(0是,2否)

计算各子集熵值：

Ent(D₁) = - (5/8)*log₂(5/8) - (3/8)*log₂(3/8) ≈ 0.954

Ent(D₂) = - (3/7)*log₂(3/7) - (4/7)*log₂(4/7) ≈ 0.985

Ent(D₃) = 0 (因为所有样本都属于同一类)

信息增益：

Gain(D,根蒂) = Ent(D) - [ (8/17)*0.954 + (7/17)*0.985 + (2/17)*0 ]

≈ 0.998 - [ 0.449 + 0.4056 + 0 ]

≈ 0.998 - 0.8546

≈ 0.143

(3) 特征"敲声"

"敲声"有三个取值：浊响、沉闷、清脆

浊响(D₁): 10个样本(6是,4否)

沉闷(D₂): 5个样本(1是,4否)

清脆(D₃): 2个样本(1是,1否)

计算各子集熵值：

Ent(D₁) = - (6/10)*log₂(6/10) - (4/10)*log₂(4/10) ≈ 0.971

Ent(D₂) = - (1/5)*log₂(1/5) - (4/5)*log₂(4/5) ≈ 0.722

Ent(D₃) = 1

信息增益：

Gain(D,敲声) = Ent(D) - [ (10/17)*0.971 + (5/17)*0.722 + (2/17)*1 ]

≈ 0.998 - [ 0.5712 + 0.2124 + 0.1176 ]

≈ 0.998 - 0.9012

≈ 0.097

(4) 特征"纹理"

"纹理"有三个取值：清晰、稍糊、模糊

清晰(D₁): 9个样本(7是,2否)

稍糊(D₂): 5个样本(1是,4否)

模糊(D₃): 3个样本(0是,3否)

计算各子集熵值：

Ent(D₁) = - (7/9)*log₂(7/9) - (2/9)*log₂(2/9) ≈ 0.764

Ent(D₂) = - (1/5)*log₂(1/5) - (4/5)*log₂(4/5) ≈ 0.722

Ent(D₃) = 0

信息增益：

Gain(D,纹理) = Ent(D) - [ (9/17)*0.764 + (5/17)*0.722 + (3/17)*0 ]

≈ 0.998 - [ 0.4045 + 0.2124 + 0 ]

≈ 0.998 - 0.6169

≈ 0.381

(5) 特征"脐部"

"脐部"有三个取值：凹陷、稍凹、平坦

凹陷(D₁): 7个样本(5是,2否)

稍凹(D₂): 6个样本(3是,3否)

平坦(D₃): 4个样本(0是,4否)

计算各子集熵值：

Ent(D₁) = - (5/7)*log₂(5/7) - (2/7)*log₂(2/7) ≈ 0.863

Ent(D₂) = 1

Ent(D₃) = 0

信息增益：

Gain(D,脐部) = Ent(D) - [ (7/17)*0.863 + (6/17)*1 + (4/17)*0 ]

≈ 0.998 - [ 0.3554 + 0.3529 + 0 ]

≈ 0.998 - 0.7083

≈ 0.290

(6) 特征"触感"

"触感"有两个取值：硬滑、软粘

硬滑(D₁): 10个样本(5是,5否)

软粘(D₂): 7个样本(3是,4否)

计算各子集熵值：

Ent(D₁) = 1

Ent(D₂) = - (3/7)*log₂(3/7) - (4/7)*log₂(4/7) ≈ 0.985

信息增益：

Gain(D,触感) = Ent(D) - [ (10/17)*1 + (7/17)*0.985 ]

≈ 0.998 - [ 0.5882 + 0.4056 ]

≈ 0.998 - 0.9938

≈ 0.004

3. 选择最佳划分特征

比较各特征的信息增益：

色泽: 0.109

根蒂: 0.143

敲声: 0.097

纹理: 0.381

脐部: 0.290

触感: 0.004

"纹理"的信息增益最大(0.381)，因此选择"纹理"作为根节点。

4. 递归构建决策树

第一层划分：纹理

纹理=清晰分支(9个样本:7是,2否)

计算剩余特征的信息增益

发现纯度已经较高，可以停止划分或继续细分

纹理=稍糊分支(5个样本:1是,4否)

继续选择最佳划分特征

纹理=模糊分支(3个样本:0是,3否)

已经纯了(全是"否")，作为叶节点

纹理=清晰分支的进一步划分

计算剩余特征的信息增益(仅使用纹理=清晰的9个样本):

色泽:

青绿:3(2是,1否), 乌黑:4(4是,0否), 浅白:2(1是,1否)

Gain ≈ 0.764 - [ (3/9)*0.918 + (4/9)*0 + (2/9)*1 ] ≈ 0.764 - 0.417 ≈ 0.347

根蒂:

蜷缩:5(4是,1否), 稍蜷:4(3是,1否)

Gain ≈ 0.764 - [ (5/9)*0.722 + (4/9)*0.811 ] ≈ 0.764 - 0.760 ≈ 0.004

敲声:

浊响:7(6是,1否), 沉闷:1(0是,1否), 清脆:1(1是,0否)

Gain ≈ 0.764 - [ (7/9)*0.592 + (1/9)*0 + (1/9)*0 ] ≈ 0.764 - 0.461 ≈ 0.303

脐部:

凹陷:5(4是,1否), 稍凹:3(3是,0否), 平坦:1(0是,1否)

Gain ≈ 0.764 - [ (5/9)*0.722 + (3/9)*0 + (1/9)*0 ] ≈ 0.764 - 0.401 ≈ 0.363

触感:

硬滑:5(4是,1否), 软粘:4(3是,1否)

Gain ≈ 0.764 - [ (5/9)*0.722 + (4/9)*0.811 ] ≈ 0.764 - 0.760 ≈ 0.004

选择"脐部"作为下一划分特征(Gain=0.363)

纹理=稍糊分支的进一步划分

计算剩余特征的信息增益(仅使用纹理=稍糊的5个样本):

色泽:

青绿:2(0是,2否), 乌黑:2(1是,1否), 浅白:1(0是,1否)

Gain ≈ 0.722 - [ (2/5)*0 + (2/5)*1 + (1/5)*0 ] ≈ 0.722 - 0.4 ≈ 0.322

根蒂:

蜷缩:1(0是,1否), 稍蜷:4(1是,3否)

Gain ≈ 0.722 - [ (1/5)*0 + (4/5)*0.811 ] ≈ 0.722 - 0.649 ≈ 0.073

敲声:

浊响:3(1是,2否), 沉闷:2(0是,2否)

Gain ≈ 0.722 - [ (3/5)*0.918 + (2/5)*0 ] ≈ 0.722 - 0.551 ≈ 0.171

脐部:

凹陷:2(0是,2否), 稍凹:3(1是,2否)

Gain ≈ 0.722 - [ (2/5)*0 + (3/5)*0.918 ] ≈ 0.722 - 0.551 ≈ 0.171

触感:

硬滑:3(0是,3否), 软粘:2(1是,1否)

Gain ≈ 0.722 - [ (3/5)*0 + (2/5)*1 ] ≈ 0.722 - 0.4 ≈ 0.322

选择"色泽"或"触感"作为下一划分特征(Gain=0.322)

5. 最终决策树结构

基于以上计算，构建的决策树大致如下：