数据挖掘复习笔记---04.分类问题之决策树

栏目: 数据库 · 发布时间: 5年前

内容简介:分类问题之决策树

分类问题之决策树

优点

  • 复杂度较低
  • 效率高
  • 非常适用于简单数据集的分类
  • 抗噪,对噪声鲁棒
  • 选取最优决策树是NP完全问题

划分选择

  • 使结点纯度越来越高
  • 信息熵

    Ent(D) = -Σ (Pk)·log(Pk)

  • 信息增益, Gain

    Gain(D, a) = Ent(D) - Σ (Di/D)·Ent(Di)

    Ent(Di) = -Σ (Pk)·log(Pk)

    ID3 算法使用 Gain 进行划分, 选择信息增益最大的作为划分特征

    缺点:倾向于选择取值更多的特征

    例题

    数据挖掘复习笔记---04.分类问题之决策树

    数据挖掘复习笔记---04.分类问题之决策树

    数据挖掘复习笔记---04.分类问题之决策树

    数据挖掘复习笔记---04.分类问题之决策树

  • 信息增益率, GainRatio

    GainRatio(D, a) = Gain(D, a) / IV(a),

    IV(a) = -Σ (Di/D)log(Di/D), 属性的熵, 属性的固有值, 如果某一特征取值过多,那么它的 IV 就会很大,会被惩罚

    C4.5 算法使用 GainRatio 进行划分, 在信息增益 Gain 高于 Avg 的属性中,选择 GainRatio 最大的属性作为划分属性

    例题(对应上一小节的数据集)

    IV(编号) = -Σ (1/17)·log(1/17) = -log(1/17) = 4.088
    IV(触感) = - [ (5/17)log(5/17) + (12/17)log(12/17) ] = 0.874
  • 基尼指数, Gini

    Gini(D) = 1 - Σp^2

    二路划分时(二叉树), Gini(D) = 2p(1 - p)

    多路划分时, Gini(D) = Σ (Di/D)·Gini(Di)

    CART 算法使用 Gini 指数进行划分, 选择 Gini 指数最小的属性作为划分属性

    注: 多路划分肯定比二路划分更纯,Gini也更小

    例题

    数据挖掘复习笔记---04.分类问题之决策树

    数据挖掘复习笔记---04.分类问题之决策树

    0.393 = (5/10)·(2·0.2·0.8) + (3/10)·(2·0.67·0.33) + (2/10)·(2·0.5·0.5)
  • 分类误差率

    Error(t) = 1 - max P(i|t)

    数据挖掘复习笔记---04.分类问题之决策树

何时停止

  • 同一结点中所有的记录都属于同一类
  • 同一结点所有属性值相近

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

雷军

雷军

蔡艳鹏 / 2012-12 / 29.80元

《雷军:人因梦想而伟大》内容简介:人生充满着期待,梦想连接着未来。雷军一直有个梦,就是建一个受世人尊敬的企业。他不仅建立了属于自己的受人尊敬的企业,也在帮助别人实现心中的梦想。雷军可以说是创业者、职场人奋斗的榜样,从他在金山的不折不挠,在投资界的百投百中,到小米的成功……无不充满传奇,让无数人争相效仿。一起来看看 《雷军》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具