首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >机器学习与决策树简介

机器学习与决策树简介

作者头像
花落花飞去
发布2018-02-05 10:05:14
1.2K0
发布2018-02-05 10:05:14
举报
文章被收录于专栏:人工智能人工智能

机器学习是计算机科学的一个分支,它使计算机能够学习而不需要明确的编程。” ——Arthur Samuel,1959年

机器学习现在是技术界的流行语。如果你相信机器人总有一天会偷走我们的工作并统治世界,那你可能会觉得有趣,充满挑战,令人困惑,甚至有点可怕。无论我们喜不喜欢,我们身边有很多有适应能力的智能事物,这些智能事物能够在瞬间解决我们日常生活中最常见的问题。

电影“终结者“中的“天网”被宣称使用了机器学习技术有些人害怕”天网“变成现实,而有些人则为人工智能领域的全新机遇感到兴奋。当然,这个未来的人工智能可能想要消灭整个人类......但现在,我们可以使用AI(人工智能)做到比我们所能想象的还要多得多的事情。

所以,这是对ML(机器学习)的简要介绍。现在,让我们看看一个机器学习技术——决策树。

什么是决策树?

简而言之,决策树是一种树,其每个分支节点代表选择了一个方案,每个叶节点代表一个决策。

决策树是一种监督学习算法(具有预定义的目标变量),主要用于分类问题,也适用于不同类别而且连续的输入和输出变量。它是归纳推理中使用最广泛也最实用的方法之一。(归纳推断是从具体例子得出一个普遍结论的过程。)

决策树从给定的例子中学习和训练自己,并预测未知的情况。

一个决策树的例子用图形可以表示为:

决策树算法:ID3

ID3代表Iterative Dichotomizer 3。ID3算法是由Ross Quinlan发明的。它从一组固定的例子构建决策树,并使用结果树对未来的样本进行分类。

其基本思想是通过对给定集合进行自顶向下的贪婪搜索来构造决策树,以测试每个树节点上的每个属性。

听起来很简单,但我们应该选择哪个节点来构建正确和最精确的决策树?我们将如何决定?

当然,我们有一些措施可以帮助我们做出最好的选择!

在信息论中,是衡量消息来源不确定性的指标。它告诉我们数据的混乱程度。

给定一个包含一些目标概念的正反样本的集合S,相对于这个布尔分类的集合S的熵是:

Entropy(S)\equiv-p_\oplus log_2p_\oplus-p_\ominus log_2p_\ominus

这里,p+和p-是S中正反样本的比例。

考虑这个相对于布尔分类的熵函数,因为正样本p+的比例在0和1之间变化。

我们注意到,如果集合S的所有成员属于同一个类别,则熵是0。例如,如果所有成员都是正数(p+ = 1),则p-为0,Entropy(S) = -1。log2(1) - 0.log2(0) = -1。0 - 0. log2(0) = 0。

当集合包含相同数量的正负样本时,熵是1。

如果集合包含不等数量的正负样本,则熵在0和1之间。

信息增益

它衡量熵的预期减少量。它决定哪个属性进入决策节点。为了最小化决策树深度,减少熵最大的属性是最好的选择!

更确切地说,属性A相对于样本集合S的信息增益Gain(S,A)被定义为:

Gain(S,A)=\underbrace {Entropy(S)}_\text{S的原始熵}-\underbrace{\sum_{v\in values(A)}\frac {|S_v|}{|S|}\cdot Entropy(S_v)}_\text{S的相对熵}

  • S = 属性A的所有可能值v的集合
  • Sv = 集合S中属性A具有值v的子集合
  • |Sv| = Sv中的元素数量
  • |S| = S中的元素数量

让我们看看这些措施如何起作用!

假设我们想让ID3决定天气是否适合打棒球。在两周的时间里,收集数据以帮助ID3构建决策树。目标分类是“我们应该打棒球吗?”可以应该或不应该。

见下表。

第几天

前景

温度

湿度

我应该打棒球吗?

D1

晴朗

不应该

D2

晴朗

不应该

D3

多云

应该

D4

应该

D5

正常

应该

D6

正常

不应该

D7

多云

正常

应该

D8

晴朗

不应该

D9

晴朗

正常

应该

D10

正常

应该

D11

晴朗

正常

应该

D12

多云

应该

D13

多云

正常

应该

D14

不应该

天气属性有前景,温度,湿度和风速。他们可以有以下值:

  • 前景 = { 晴朗,多云,雨}
  • 温度 = {高,中,低}
  • 湿度 = { 高,正常}
  • 风 = { 小,大 }

我们需要找到哪个属性是我们决策树中的根节点。

  • Entropy(S) = – (9/14) Log2 (9/14) – (5/14) Log2 (5/14) = 0.940
  • Gain(S,风) = Entropy(S) – (8/14)*Entropy(S_小) – (6/14)*Entropy(S_大)
  • = 0.940 – (8/14)*0.811 – (6/14)*1.00
  • = 0.048
  • Entropy(S_小) = - (6/8)*log2(6/8) – (2/8)*log2(2/8) = 0.811
  • Entropy(S_大) = - (3/6)*log2(3/6) – (3/6)*log2(3/6) = 1.00

对于每个属性,计算增益并在决策中使用最高增益。

  • Gain(S, 前景) = 0.246
  • Gain(S, 温度) = 0.029
  • Gain(S, 湿度) = 0.151

显然,前景属性的增益最高。因此,它被用作根节点中的决策属性。

由于前景有三个可能的值,根节点有三个分支(晴朗,多云,雨)。接下来的问题是,什么属性应该在晴朗的分支节点测试?由于我们已经在根节点上使用了前景,所以我们只决定剩下的三个属性:湿度,温度还是风。

  • S_{晴朗} = \{D1, D2, D8, D9, D11\} = 有5个样本的前景 = 晴朗
  • Gain(S_{晴朗}, 湿度) = 0.970
  • Gain(S_{晴朗}, 温度) = 0.570
  • Gain(S_{晴朗}, 风) = 0.019

湿度的增益最高。因此,它被用作决策节点。这个过程继续下去,直到所有的数据被完美的分类或者我们用完了属性。

决策树也可以用规则表示为:

  • 如果前景 = 晴朗并且湿度 = 高,那么玩棒球 = 不应该
  • 如果前景 = 雨并且湿度 = 高,那么玩棒球 = 不应该
  • 如果前景 = 雨并且风 = 大,那么玩棒球 = 应该
  • 如果前景 = 多云,那么玩棒球 = 应该
  • 如果前景 = 雨并且风 = 小,那么玩棒球 = 应该

所以,这是对决策树的一个非常快速的介绍。决策树和上面描述的一样简单。我希望这篇文章能帮助你!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 什么是决策树?
  • 决策树算法:ID3
      • 信息增益
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档