机器学习-分类算法[1]决策树

核心概念:

特征、信息增益、信息熵

决策树的核心思路

看过《七龙珠》的朋友肯定对那个小悟空分不清男女的梗印象很深。因为在深山中的他从没见过其他人,更别说女孩。所以当他第一次见到布玛时各种惊讶(也占尽便宜啊,虽然他自己不觉得:) 那么在现实中我们怎样判断一个人是男是女呢?第一步肯定是要接触足够多的男男女女(虽然你可能忘了,但是你也曾经有过跟悟空一样男女不分的小时候)。然后你会根据每个人的一些特征,结合其中的一些来区分男女,某种程度上说这就是一个决策树判断的过程。

辣么,男女之间存在什么特征呢?先来温习下漫画——



从上面我们可以收集到以下几个特征:

  1. 是否柔弱
  2. 是否长尾巴
  3. 是否有胸部

将他们结合悟空和布玛的性别进行整理我们得到这样一张性别判定表:

柔弱?长尾巴?有胸部?男女?
101
010

我们拿着这样一张表进行决策,判断一个人是男是女,会发现其中有一些特点是比较有用的(比如:柔弱,胸),有一些其实对问题并没有多大的帮助(比如:尾巴)。这也正是决策树算法和核心问题:选择特征。

要解决的主要问题

为了更方便地说明问题,我们添加一些样本到判定表当中:

柔弱?长尾巴?有胸部?男女?
101
010
001女 (比如女汉子)
100女 (比如… 李宇春)
100男 (比如现在的小鲜肉明星)
001男 (比如胖子)
000

选择信息增益最大的特征

怎样看待这些属性?其中有的属性对我们的判断相对有用,有的则几乎没有帮助(比如是否长尾巴)。算法上通过“信息增益”来描述一个特征对判断的帮助有多大。

在我们这个例子当中,如果我们用是否长尾巴来区分男女。会得到这样一个结果:

长尾巴的:1男

不长尾巴的:3男3女

很明显尾巴不是判断男女的好特征。如何量化地判断一个特征的好坏?香农给出了这样的一个公式:

H又被称作信息熵,其中p(i)的意义是在n种可能的特征选择中,第i种出现的概率。将尾巴这个特征代入公式可得:

而“柔弱”这个特征对应的H为:

可见“柔弱”是一个比“长尾巴”更理想的区分男女的特征。

根据特征划分数据集

接下来,我们可以得到两组根据是否柔弱划分的子数据集合。

柔弱组:

长尾巴?有胸部?男女?
01
00女 (比如… 李宇春)
00男 (比如现在的小鲜肉明星)

非柔弱组:

长尾巴?有胸部?男女?
10
01女 (比如女汉子)
01男 (比如胖子)
00

根据信息熵公式可以计算出在两个子集中各自剩余属性对应的H值,胸部成为下一个有用的判断特征(H值大)。

拿非柔弱组的数据来看,没有胸部的都是男的,所以可以得出一个结论,只要非柔弱且没有胸部的都是男生。这就根据两个特征判定一个人为男生。决策树就是这样工作的。

但是!有个问题:

非柔弱且有胸部的却不一定是男或女!!

同样,非柔弱没有胸部的也不确定其性别!!

这也正是这种简单ID3决策树算法存在的问题:

ID3算法的缺陷

  1. 不支持数值型数据。例如胸部我们可以具体到胸围罩杯,这会让特征更为明显。
  2. 特征太多导致过度匹配。这里的尾巴虽然是一个特征,但是对性别判断提供的信息量太少。

发表评论

电子邮件地址不会被公开。

31 + = 34