前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >机器学习实战 - 读书笔记(03) - 决策树

机器学习实战 - 读书笔记(03) - 决策树

作者头像
绿巨人
发布2018-05-17 13:44:10
7440
发布2018-05-17 13:44:10
举报
文章被收录于专栏:绿巨人专栏

机器学习实战读书笔记 - 03 - 决策树

解决的问题

一个经典的例子是猜人游戏。参与游戏的一方默想一个人名,另一方向他提问题,最终猜出这个人名。 决策树属于监督学习,可以处理上面的分类问题。这个问题的特点是:

  • 训练数据全面,计算数据被训练数据覆盖了。
  • 训练数据是标称型数据,数值型数据必须离散化。

决策树算法是找到一个优化的决策路径(决策树),使得每次分类尽可能过滤更多的数据,或者说问的问题尽量少。 决策树算法可以用来优化一些知识系统,帮助用户快速找到答案。

优势

  • 使用决策树可以更好地理解数据的内在含义。

基本概念

  • 属性(Feature): 训练数据中每列都是一个属性。
  • 标签(Label):训练数据中的分类结果。

决策树的一般流程

  1. 收集数据:可以使用任何方法。
  2. 准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。
  3. 分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。
  4. 训练算法:构造树的数据结构。
  5. 测试算法:使用经验树计算错误率。
  6. 使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

如何构造决策树

这里,要解决的问题是采用哪些数据属性作为分类条件,最佳次序是什么?

  • 方法一:采用二分法,或者按照训练数据中的属性依次构造。
  • 方法二:使用香农熵计算公式。这是书中使用的方法。
  • 方法三:使用基尼不纯度2 (Gini impurity)。
  • 流行的算法: C4.5和CART

香农熵(Shannon Entropy)简介

  • 熵的定义 在信息论中,熵是接收的每条消息中包含的信息的平均量,又被称为信息熵、信源熵、平均自信息量。 熵定义为信息的期望值。 熵实际是对随机变量的比特量和顺次发生概率相乘再总和的数学期望。 熵的单位通常为比特, bit 或者sh(annon) (基于2),但也用nat(基于自然对数)、Hart(基于10)计量,取决于定义用到对数的底。 熵值是一个>=0的值。 如果为0,则表明结果可以准确预测。从下面的公式可以看出,其概率为1. 因此,熵值越大,越不容易被准确预测。
  • 期望值 在概率论和统计学中,一个离散性随机变量的期望值(或数学期望、或均值,亦简称期望,物理学中称为期待值)是试验中每次可能结果的概率乘以其结果的总和。 比如掷骰子, 其点数的期望值是3.5: E(x) = 1 * 1 / 6 + 1 * 2 / 6 + 1 * 3 / 6 + 1 * 4 / 6 + 1 * 5 / 6 + 1 * 6 / 6 = 3.5

核心公式

  • 数据集的信息熵的计算公式

H(X) = \sum\limits_{i=1}^n P(x_i)I(x_i) = - \sum\limits_{i=1}^n P(x_i)\log_2 P(x_i) \\ where \\ \qquad H(X) : 数据集合X的信息熵值。 \\ \qquad X : 数据集合X。 \\ \qquad x_i : 数据集合X的标签的一个枚举值。 \\ \qquad I(x_i) :x_i的资讯量 (information self). I(x_i) = -ln(P(x_i)) \\ \qquad P(x_i) : 发生x_i的概率。x的机率质量函数(probability mass function)。 P(x_i) = count(x_i)/len(X).

  • 数据集合X在属性F上的信息熵的计算公式

H(F, X) = \sum\limits_{i=1}^n P(f_i)H(X_fi) \\ where \\ \qquad H(F, X) : 数据集合X在属性F上的信息熵值。 \\ \qquad F : Feature F。 \\ \qquad X : 数据集合X。 \\ \qquad f_i : Feature F的一个枚举值。 \\ \qquad H(X_fi) :集合X_fi的信息熵。 \\ \qquad X_fi :数据集合X中属性F为f_i的子集。 \\ \qquad P(f_i) : 发生f_i的概率。f_i的机率质量函数(probability mass function)。 P(f_i) = count(f_i)/len(X).

构造决策树

  • 输入
    • 数据集
  • 输出
    • 决策树 建造一个决策树。决策树的json表示如下:

'no surfacing'和'flippers'是数据的属性名。 0, 1是标称数据。 'yes', 'no'是决策结果。

  • 逻辑过程
    • createTree

\text{(jsonTree) createTree(dateset)} = \\ \{ \\ \qquad \text{if (the value of the dateset labels are same)} \\ \qquad \{ \\ \qquad \qquad return\ dataset.lables[0] \\ \qquad \} \\ \qquad \\ \qquad \text{if (dataset.features.length = 1)} \\ \qquad \{ \\ \qquad \qquad return\ mostAppeard(dataset.lables) \\ \qquad \} \\ \qquad \\ \qquad feature = findBestFeature(dateset) \\ \qquad jsonTree = \{feature.label:\{\}\} \\ \qquad \textstyle {foreach}_\text{value}^\text{feature.values} \\ \qquad \{ \\ \qquad \qquad jsonTree[feature.label][value] = createTree(dateset.subset(feature, value)) \\ \qquad \} \\ \} * findBestFeature

\text{(feature) findBestFeature(dateset)} = \\ \{ \\ \qquad baseFeatureEntroy = infinite \\ \qquad \text{foreach}_\text{current_feature}^\text{dataset.features} \\ \qquad \{ \\ \qquad \qquad featureEntroy = calculateFeatureEntroy(dateset, feature) \\ \qquad \qquad \text{if (featureEntroy < baseFeatureEntroy)} \\ \qquad \qquad \{ \\ \qquad \qquad \qquad baseFeatureEntroy = featureEntroy \\ \qquad \qquad \qquad feature = current_feature \\ \qquad \qquad \} \\ \qquad \} \\ \}

使用Matplotlib注解绘制树形图

见原书。

测试和存储分类器

见原书。

个人总结

决策树对数据质量要求比较高。那猜人名的游戏来说,需要收集大量的人名和人名对应的数据。

参考:

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-08-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 机器学习实战读书笔记 - 03 - 决策树
  • 解决的问题
    • 优势
    • 基本概念
    • 决策树的一般流程
    • 如何构造决策树
      • 香农熵(Shannon Entropy)简介
      • 核心公式
        • 构造决策树
          • 使用Matplotlib注解绘制树形图
            • 测试和存储分类器
              • 个人总结
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档