QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4626|回复: 1
打印 上一主题 下一主题

机器学习笔记之信息熵、信息增益和决策树(ID3算法)

[复制链接]
字体大小: 正常 放大

600

主题

29

听众

6868

积分

  • TA的每日心情
    奋斗
    2023-5-24 09:14
  • 签到天数: 119 天

    [LV.6]常住居民II

    群组2018高中组美赛 课堂

    群组2018国赛冲刺

    群组2018 夏令营面授课堂

    群组2016美赛交流群组

    跳转到指定楼层
    1#
    发表于 2018-11-2 08:46 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    机器学习笔记之信息熵、信息增益和决策树(ID3算法)5 r3 `+ i$ i5 Q# [" w4 k4 b
    决策树算法:" C* A1 `, n+ G9 r( L! v6 ]' T. o
    $ ?( ?* p- s$ E- O5 o
    优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关的特征数据。
    5 ?, E; [* u: y0 [& [! g$ r缺点:可能会产生过度匹配问题。
    & q& q8 I& b3 L# g" m* U0 b适用数据类型:数值型和标称型。
    6 v. [. K7 x2 I% d( i6 y* d" K
    & A. X' }4 G/ n& x' l算法原理:
    * d# c: [: b$ f$ e1 P9 K9 x决策树是一个简单的为输入值选择标签的流程图。这个流程图由检查特征值的决策节点和分配标签的子叶节点组成。为输入值选择标签,我们以流程图的初始决策节点(即根节点)开始。此节点包含一个条件,检查输入值的特征之一,基于该特征的值选择一个分支。沿着这个描述我们输入值的分支,我们到到了一个新的决策节点,有一个关于输入值的特征的新条件。我们继续沿着每个节点的条件选择的分支,直到到达叶节点,它为输入值提供了一个标签。
    ; l$ e! N3 _. Z% @8 A
    + a. c3 ]3 Y0 U3 G算法流程:% O$ T% S+ j+ S
    收集数据:即建立训练测试数据集。) l% E4 D; F# _- O$ R9 I" ^6 ^
    准备数据:决策树构造算法只适用于标称型数据,因此数值型数据必须是离散化的。
    . U; p3 E+ }* i* N/ |  k分析数据:建立构造数,构造树完成后我们检查图形是否符合预期。
    " v& Y, a+ ?: ~& U训练数据:完善构造树的数据结构。/ _+ d0 C3 U2 W
    测试数据:使用经验树计算。
    $ r; a! Q$ b" \: Y* ]! @使用算法:对实际数据进行预测。
    $ `  M! j4 \" E, Z, A, Q/ N! B5 [8 n8 f: L% M. X7 v! X) T5 @: U5 J
    那么问题来了我们是如何确定有多少个树杈节点呢?这里我们采用ID3算法来构造决策树。7 U5 M; E+ P% M9 O
    / x8 U. Z8 |  a, T* K' ^4 l4 e0 [
    ID3算法:
    . [9 D$ t4 O6 U1 R) o6 J! w) ZID3算法(Iterative Dichotomiser 3,迭代二叉树3代)是一种贪心算法,用来构造决策树。ID3算法起源于概念学习系统(CLS),以信息熵的下降速度为选取测试属性的标准,即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准,然后继续这个过程,直到生成的决策树能完美分类训练样例。0 o" u3 y4 l2 O/ [. c

    9 J. F, G* f* _2 u( |为了实现ID3算法我们还需要了解这个高富帅提出的三个概念:信息、信息熵和信息增益。( Q1 x0 f3 D2 _0 L9 F( q9 x

    3 ]* k2 d8 K: B6 J0 B那么我们就需要认识认识一下这些概念的提出者美国高(高智商)富帅数学家香农. b& I$ r( c5 H% U1 k( ?: H
    : c5 ?: C- p7 V. J
    克劳德·艾尔伍德·香农(Claude Elwood Shannon ,1916年4月30日—2001年2月24日)是美国数学家、信息论的创始人。0 ~8 H8 y5 Y; t# K& \4 g/ L2 x

    7 ]5 w4 G4 Q) L2 p4 [* b' a- `" n
    3 u  G0 \  d4 B, K& s这个帅哥提出了下面三个概念
    0 `1 w4 P) m7 j2 T' H  Z9 y& b9 [5 f  A
    0 [! q5 ^0 f  t& e3 s& f
    并且由上面的公式我们可以看出其实信息熵就是信息的期望值,所以我们可知,信息熵越越小,信息的纯度越高,也就是信息越少,在分类领域来讲就是里面包含的类别越少,所以我们可以得出,与初始信息熵的差越大分类效果越好。
    5 F6 w* B5 ?3 k- M5 Q8 m9 a
    * b1 Z$ x7 ~9 j" u) V5 x   下面我们来举个例子:. l+ s- J- O' w2 O" d7 b
        我一般买苹果的时候,从外观上评判一个苹果甜不甜有两个依据:红不红  和  圆不圆 (原谅我浅薄的挑苹果经验吧。。。)
    ' J% C6 @$ ~6 V+ ~: H6 E
    8 k: q) I7 Z, H: d: A苹果编号    红不红  圆不圆   甜不甜
    2 r( x/ d) v* F               1               1         1           yes
    7 F3 h) ^4 e9 e               2               1         1           yes
    0 p) J1 q5 M! p5 Y$ p               3               1         0           no
    ! q4 i) J, Y! r  x" g               4               0         1           no4 I% ~) Q& P5 \8 K: l
                   5               0         1           no' {8 y# I8 S$ {+ N! p9 N) j

    * O- i% e% P$ D$ E4 k' v下面我来算一下啊这5个苹果是不是好苹果的信息熵:
    # q: B% ?6 w& U0 S- Z# Q! f( g, P, Z% B% f, g
    9 x2 S/ h, z4 D4 d3 ^) y1 N1 z/ N
    下面给出python求信息熵的代码  L) m6 {! `. O; t5 {5 I! k8 F

    ) a$ l9 w3 `; b- l1 | 捕获.PNG ( N5 k( U4 q7 z
    我们来用程序求一下我们这个小例子的结果:! I5 p. P4 `9 o3 y' P+ I8 ]4 o6 b9 \

    5 D$ }  M" i( c4 @8 y, e! q" p& r8 P# r

    , u1 G+ A% X3 q" |2 u& T7 n
    ! G3 g. V# x- g6 L2 w5 J
    . \) z' ?6 w( V( x& E1 M
    5 w/ k# J2 S* B: `

    * B/ q6 C  R& V  d3 S- P. n; U和我们的笔算结果完全一致。。。
    . d9 f0 q3 n0 H3 ~! R" V1 k7 h: c  C+ ]' l0 b

    ; p5 A/ H* U- p) B) A' n接下来我们要寻找怎么分类比较好也就是决策树的叉,我们的例子中可以按两个方式分类,红不红和圆不圆。。到的按哪个分更好一点呢,这下就用到信息增益了:6 D' z/ B1 |( X0 Q" U9 W+ U

    1 n5 i/ y! U4 c7 M% g% Y 捕获.PNG , b2 g, s7 F" J2 V% w) j( ~/ H

    8 v7 M( P& {* M# K% n我们可以看出,这种分类的信息熵是0.5509775,它的信息增益是0.419973
    % x0 o3 W7 m; s; q0 y' j: `
    8 I8 v# ~. f& N  J- \2 y4 b
    " }5 L( w! t3 _9 o6 ]; b( ^* e5 O
    如果按照圆不圆来分类:
    2 O2 ]( U- W( n) h2 Q$ [; B6 s* ~7 Q0 t  w5 {
    我们可以看出,这种分类的信息熵是0.8,它的信息增益是0.17095
    $ Q- b  E9 h8 J

    % v& w/ s4 F! m( b( `显然第一种分类的信息增益较大4 @  P7 N% P' U$ \2 ?* }% R

    ! b/ q* U- M0 H$ y( @5 t

    " F1 a* d$ H3 w我们来看一下啊两个划分的结果集:
    6 l- z$ ~0 v. H! ~  v! w" x( T; X9 D- a) x6 U& T4 ]! ]& j0 @2 j4 U
    - |8 z" W2 \! n& b" L4 C% b  A
    确实第一种方法划分的较好。1 k4 U8 ~+ M* P: m! |7 z; j
    这样我们的决策树也就构建好了:
    8 ^4 _  b5 ]& X. w' C, g) o! a6 M7 r" R8 Z3 }3 i

      Q2 s) \% [, Q' E" z
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    0

    主题

    2

    听众

    22

    积分

    升级  17.89%

  • TA的每日心情
    郁闷
    2019-1-25 20:15
  • 签到天数: 1 天

    [LV.1]初来乍到

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-14 19:13 , Processed in 0.446729 second(s), 59 queries .

    回顶部