决策树的原理与构建,围绕一个实例展开

1. 什么是决策树:

决策树是一种预测模型,用来进行分类,是一种有监督学习。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值

2 决策树实例(围绕一个例子)

问题1. 基于表1中给出的训练集,给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的“大小”的理解,并按你的理解比较两种方法生成的决策树大小。

问题1. 基于表1中给出的训练集,给出分别使用极小熵和极大熵选择扩展属性所生成的两棵决策树。然后给出你对树的“大小”的理解,并按你的理解比较两种方法生成的决策树大小。

(1) 极小熵生成决策树,设表1给的数据集为D,根据最大信息增益选择最优特征生成极小熵决策树,计算各特征A1、A2、A3、A4、A5对数据D的信息增益,统计结果为

class=1 class=2
D 8 7 H(D)= 0.9968
A1 D1 8 2 6 g(D,A1)=0.2880
D2 7 6 1
A2 D1 5 4 1 g(D,A2)=0.1398
D2 4 1 3
D3 6 3 3
A3 D1 3 1 2 g(D,A3)=0.0292
D2 12 7 5
A4 D1 7 6 1 g(D,A4)=0.2880
D2 8 2 6
A5 D1 6 5 1 g(D,A5)=0.4131
D2 4 0 4
D3 5 3 2

上表中的D1和D2,D3分别表示在各个特征中取值为1、2和3的样本子集,根据计算后统计在表格中的数据可得:

H(D)=-8/15*log2(8/15)—7/15*log2(7/15)=0.9968

g(D,A1)=H(D)-[8/15*H(D1)+7/15*H(D2)]=0.2880

g(D,A2)=H(D)-[5/15*H(D1)+4/15*H(D2)+6/15*H(D3)]=0.1398

g(D,A3)=H(D)-[3/15*H(D1)+12/15*H(D2)]=0.0292

g(D,A4)=H(D)-[7/15*H(D1)+8/15*H(D2)]=0.2880

g(D,A5)=H(D)-[6/15*H(D1)+4/15*H(D2)+5/15*H(D3)]=0.4131

根据上面的计算结果,特征A5的信息增益最大,所以选择A5为根节点。根据A5的取值将样本分成3个结合,S1={2,3,6,8,12,13},S2={1,5,7,14},S3={4,9,10,11,15}其中集合S2已全部属于同一个类,不需要再分,已成为叶子节点。对于集合S1,计算统计结果为:

class=1 class=2
D 5 1 H(D)=0.6500
A1 D1 1 1 0 G(D,A1)=0.0484
D2 5 4 1
A2 D1 3 2 1 G(D,A2)=0.1909
D2 1 1 0
D3 2 2 0
A3 D1 1 1 0 G(D,A3)=0.0484
D2 5 4 1
A4 D1 5 5 0 G(D,A4)=0.6500
D2 1 0 1

H(D)=0.6500 g(D,A1)= 0.0484 g(D,A2)= 0.1909 g(D,A3)= 0.0484 g(D,A4)=0.6500

     根据计算结果,集合S1选择A4为根结点。根据A4的取值,将S1集合划分为S11={3,6,8,12,13}  S12={2},集合S11和集合S12已成为叶节点。对于集合S3,计算统计结果为:

class 1 class 2
D 3 2 H(D)=0.9710
A1 D1 3 1 2 G(D,A1)=0.4200
D2 2 2 0
A2 D1 2 2 0 G(D,A2)=0.5710
D2 1 1 0
D3 2 1 1
A3 D1 0 0 0 G(D,A3)=0
D2 5 3 2
A4 D1 2 1 1 G(D,A4)=0.0200
D2 3 2 1

H(D)=0.9710 g(D,A1)=0.4200 g(D,A2)=0.5710  g(D,A3)=0 g(D,A4)=0.0200

根据计算结果,所以集合S3选择A2作为根结点,根据A2的取值将S3分成集合S31={4,11}集合S32={9}集合S33={10,15} 集合S32和集合S32已为叶子节点。对于集合S33,计算统计结果为

class 1 class 2
D 1 1 H(D)=1
A1 D1 1 0 1 G(D,A1)=1
D2 1 1 0
A3 D1 0 0 0 G(D,A3)=0
D2 2 1 1
A4 D1 2 1 1 G(D,A4)=0
D2 0 0 0

H(D)=1  g(D,A1)=1 g(D,A3)=0  g(D,A4)=0

所以选择A1作为集合S33的根节点。根据A1的取值划分后的集合也都为叶子节点,至此极小熵决策树就建立起来了,如下图所示。

(2) 极大熵生成决策树,同上面的极小熵建立决策树类似,设表1中数据集为D。根据信息增益最小选择特征建立决策树。计算各特征A1、A2、A3、A4、A5对数据D的信息增益,统计结果为

class=1 class=2

D

8

7

H(D)= 0.9968

A1

D1

8

2

6

G(D,A1)= 0.2880

D2

7

6

1

A2

D1

5

4

1

G(D,A2)=0.1398

D2

4

1

3

D3

6

3

3

A3

D1

3

1

2

G(D,A3)= 0.0292

D2

12

7

5

A4

D1

7

6

1

G(D,A4)= 0.2880

D2

8

2

6

A5

D1

6

5

1

G(D,A5)=0.4131

D2

4

0

4

D3

5

3

2

  H(D)=0.9968g(D,A1)=0.2880 g(D,A2)=0.1398 g(D,A3)=0.0292 g(D,A4)=0.2880  g(D,A5)=0.4131

  根据上面计算结果,选择最小增益A3作为根结果。根据A3的取值,将集合划分S1={5,8,14},S2={1,2,3,4,6,7,9,10,11,12,13,15}.对于集合S1,计算统计结果为

class=1 class=2

D

1

2

H(D)=0.9183

A1

D1

2

0

2

G(D,A1)=0.9183

D2

1

1

0

A2

D1

1

1

0

G(D,A2)=0.9183

D2

1

0

1

D3

1

0

1

A4

D1

1

1

0

G(D,A4)= 0.9183

D2

2

0

2

A5

D1

1

1

0

G(D,A5)=0.9183

D2

2

0

2

D3

0

0

0

H(D)=0.9183 g(D,A1)=0.9183 g(D,A2)=0.9183 g(D,A4)=0.9183 g(D,A5)=0.9183

根据计算结果,选择A1或A2或A4或A5都可以作为集合S1的根节点,这里不妨选择A1作为根节点,根据A1的取值将S1划分成S11={5,14} ,S12={8},此时S11和S12已经为叶节点不需要在划分。

对于集合S2,计算统计结果为

class=1 class=2

D

7

5

H(D)=0.9799

A1

D1

6

2

4

G(D,A1)= 0.1957

D2

6

5

1

A2

D1

4

3

1

G(D,A2)=0.0753

D2

3

1

2

D3

5

3

2

A4

D1

6

5

1

G(D,A4)=0.1957

D2

6

2

4

A5

D1

5

4

1

G(D,A5)= 0.2745

D2

2

0

2

D3

5

3

2

H(D)=0.9799 g(D,A1)=0.1957 g(D,A2)=0.0753 g(D,A4)=0.1957 g(D,A5)=0.2745

根据计算结果,选择A2作为集合S2的根节点,根据A2的取值将集合S2划分为S21={2,4,6,11},S22={7,9,12},S23={1,3,10,13,15},对于集合S21,计算统计结果为

class=1 class=2

D

3

1

H(D)=0.8113

A1

D1

1

1

0

G(D,A1)=0.1226

D2

3

2

1

A4

D1

1

1

0

G(D,A4)=0.1226

D2

3

2

1

A5

D1

2

1

1

G(D,A5)=0.3113

D2

0

0

0

D3

2

2

0

H(D)=0.8113  g(D,A1)=0.1226  g(D,A4)=0.1226  g(D,A5)=0.3113

根据计算结果,选择A1和A4作为S21的根节点都可以,这里不妨选A1为S21的根节点。根据A1的取值将S21划分为S211={11},S212={2,4,6},其中S211已为叶节点。对于集合S212,计算统计结果为

class=1 class=2

D

2

1

H(D)=0.9183

A4

D1

1

1

0

G(D,A4)=0.2516

D2

2

1

1

A5

D1

2

1

1

G(D,A5)=0.2516

D2

0

0

0

D3

1

1

0

H(D)=0.9183  g(D,A4)=0.2516  g(D,A5)=0.2516

根据计算结果,选择A4和A5作为S212的根节点都可以,这里不妨选A4作为根节点。根据A4的取值将集合S212划分为S2121={6}  S2122={2,4};对于集合S2122选择A5作为根节点,根据A5的取值将集合S2122划分为S21221={2}  S21223={4};此时集合S2121和集合S21221,S21223都为叶节点,对于集合S22,计算统计结果为

class=1 class=2

D

1

2

H(D)= 0.9183

A1

D1

2

0

2

G(D,A1)=0.9183

D2

1

1

0

A4

D1

1

1

0

G(D,A4)=0.9183

D2

2

0

2

A5

D1

1

1

0

G(D,A5)=0.9183

D2

1

0

1

D3

1

0

1

H(D)=0.9183  g(D,A1)=0.9183  g(D,A4)=0.9183  g(D,A5)=0.9183

根据计算结果,选择A1或A4或A5作为根节点都可以,这里选择A1作为根节点。根据A1的取值将集合S22划分为S221={12},S222={7,9} 此时,S221和S222已为叶节点。对于集合S23,计算统计结果为

class=1 class=2

D

3

2

H(D)=0.9710

A1

D1

3

1

2

G(D,A1)=0.4200

D2

2

2

0

A4

D1

4

3

1

G(D,A4)=0.3220

D2

1

0

1

A5

D1

2

2

0

G(D,A5)=0.5710

D2

1

0

1

D3

2

1

1

H(D)=0.9710  g(D,A1)=0.4200  g(D,A4)=0.3220  g(D,A5)=0.5710

根据计算结果,选择A4作为根节点。根据A4的取值将S23划分为S231={3,10,13,15},S232={1}.对集合S231,计算统计结果为

class=1 class=2

D

3

1

H(D)=0.8113

A1

D1

2

1

1

G(D,A1)= 0.3113

D2

2

2

0

A5

D1

2

2

0

G(D,A5)= 0.3113

D2

0

0

0

D3

2

1

1

H(D)=0.8113  g(D,A1)=0.3113  g(D,A5)=0.3113

根据计算结果,选择A1或A5作为S231的根节点都可以,这里选择A1作为其根节点,根据A1的取值将集合S231划分为S2311={3,10},S2312={13,15}。集合S2311选择A5作为根节点,将集合S2311划分为S23111={3} , S23113={10}。至此极大熵决策树就可以建立起来了,如下图所示

3.  拓展

利用极小熵生成的决策树不一定是“最小决策树”。因为用极小熵生成的决策树可能存在过拟合,对训练数据分类很好,但对测试数据不一定好。一般需要对生成的决策树做剪枝处理,减掉过于细分的叶节点。使其退回到父节点,然后将父节点改为新的叶节点。

1 5 收藏 评论

关于作者:YONGMING0915

小冰一枚,专注于数据挖掘,玩原汁原昧的工业数据,分享有趣有料的topic 个人主页 · 我的文章 · 1 ·   

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部