数学建模社区-数学中国

标题: 机器学习笔记之信息熵、信息增益和决策树(ID3算法) [打印本页]
作者: 重光兰衣    时间: 2018-11-2 08:46
标题: 机器学习笔记之信息熵、信息增益和决策树(ID3算法)
机器学习笔记之信息熵、信息增益和决策树(ID3算法)
1 ^% R; C+ N- V3 Y2 K: a决策树算法：
: v% N9 m( [8 Z  r: y$ C7 X, b  C, F2 G1 |3 U: N0 u0 W& f
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关的特征数据。, G, }  z( d7 m- X& V
缺点：可能会产生过度匹配问题。
: J$ T7 u5 I$ A5 X4 m5 a& N6 j适用数据类型：数值型和标称型。6 i, l% I$ c2 x7 X
/ j5 D- i# J3 |
算法原理：
0 V' `6 {/ p* y. x( J决策树是一个简单的为输入值选择标签的流程图。这个流程图由检查特征值的决策节点和分配标签的子叶节点组成。为输入值选择标签，我们以流程图的初始决策节点(即根节点)开始。此节点包含一个条件，检查输入值的特征之一，基于该特征的值选择一个分支。沿着这个描述我们输入值的分支，我们到到了一个新的决策节点，有一个关于输入值的特征的新条件。我们继续沿着每个节点的条件选择的分支，直到到达叶节点，它为输入值提供了一个标签。- C% t) w' ]1 A
7 `. k  c8 D4 C
算法流程：
% @5 N. s) F) n- u/ i( q# Z5 j收集数据：即建立训练测试数据集。
& w7 ^5 L! {6 M1 f3 _准备数据：决策树构造算法只适用于标称型数据，因此数值型数据必须是离散化的。
  [: E+ L# p3 ?; w! e2 @4 s% u7 H分析数据：建立构造数，构造树完成后我们检查图形是否符合预期。! C- v# ?; L4 x2 v0 F& f
训练数据：完善构造树的数据结构。8 H) d% q0 \- R7 q4 E( X
测试数据：使用经验树计算。7 @5 \: O  g' \! Y9 j* G( k: t
使用算法：对实际数据进行预测。9 U( n5 a/ Q- W( P  v, t

* n. d( G& Z9 y' b  o那么问题来了我们是如何确定有多少个树杈节点呢？这里我们采用ID3算法来构造决策树。7 v* p7 {; j% m; f; f

" [& f& c4 h) K# _# z- rID3算法：
/ x4 i, V8 }5 X; A% t  eID3算法(Iterative Dichotomiser 3，迭代二叉树3代)是一种贪心算法，用来构造决策树。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。9 F) f3 ?5 l8 |( y! Z1 M9 k

. Y1 M8 r( O2 Q& |* f8 ^为了实现ID3算法我们还需要了解这个高富帅提出的三个概念：信息、信息熵和信息增益。/ K4 v2 P+ x% @3 q

' t3 p8 _" w8 C那么我们就需要认识认识一下这些概念的提出者美国高(高智商)富帅数学家香农+ T2 |. a9 i' @" x
4 N1 d: U5 F0 a! X' H
克劳德·艾尔伍德·香农（Claude Elwood Shannon ，1916年4月30日—2001年2月24日）是美国数学家、信息论的创始人。
# l# `& D; F1 z9 g) D; w0 `+ F9 |, y$ i# ], X
2 ^; O8 i0 _' C9 g2 a
这个帅哥提出了下面三个概念
/ Y+ t* [+ G- L6 d" u
- V0 A+ h0 W0 O) |$ U$ L2 u4 h( i) [  |# O
并且由上面的公式我们可以看出其实信息熵就是信息的期望值，所以我们可知，信息熵越越小，信息的纯度越高，也就是信息越少，在分类领域来讲就是里面包含的类别越少，所以我们可以得出，与初始信息熵的差越大分类效果越好。
& k9 p: }$ L: N2 M1 L9 G' g
0 O6 Q- G/ O* y4 W) Z   下面我们来举个例子：
/ _, S+ q; O  Q! x    我一般买苹果的时候，从外观上评判一个苹果甜不甜有两个依据：红不红  和  圆不圆 (原谅我浅薄的挑苹果经验吧。。。)
9 p  f% v8 u  f; |" P
. K& Q5 ?9 u) u' @7 ^" H% z, W) q苹果编号    红不红  圆不圆   甜不甜
% @7 q( p6 [: r( X: U6 w1 g               1               1         1           yes
8 h+ |8 j, }& @0 T$ [               2               1         1           yes% j8 ]* A; Z; `9 b9 X. k
               3               1         0           no
+ ~4 }4 I1 F) F- t. I( U' Q               4               0         1           no+ W% o+ @% A9 h  i  J
               5               0         1           no/ A; f5 M  O! {# q" G
% R) ~" n. H* _! Y7 h
下面我来算一下啊这5个苹果是不是好苹果的信息熵：# M; Q( I3 M. q! E: Q& e6 c

7 N! r8 @: W% w% O  ^/ v8 g  c4 {6 Z
1 r+ z; S+ N2 R8 H! m6 ]下面给出python求信息熵的代码
& O3 R( _+ _, g8 u+ t0 q9 {. D! D8 r; x+ \0 z  V: l4 e
捕获.PNG
* p6 e# e6 O, B5 @! N4 O/ R" @7 T我们来用程序求一下我们这个小例子的结果：
- w' c5 h+ c/ O! I: `" z9 A1 u

& Q* E# @% K. E! L" W% ^2 x% ?
+ |/ e; R- w5 v; A3 T% K9 v% e' ]
0 t$ B, i: |  |+ v0 m4 V7 W: D" Y/ {
% x' c3 d+ ]0 c$ g: }8 ^

! c4 t9 e1 R2 O6 o0 l9 `和我们的笔算结果完全一致。。。
. O# j' ?" h& [" d
2 Q+ w" U; t; M; p
+ Q" V3 ]8 S" [" D9 B接下来我们要寻找怎么分类比较好也就是决策树的叉，我们的例子中可以按两个方式分类，红不红和圆不圆。。到的按哪个分更好一点呢，这下就用到信息增益了：3 S" D! a* ]- q8 i$ c$ U' f
3 _3 T! p2 G! G5 u
捕获.PNG ! ^! d; P7 _: k9 J
  X6 N% v9 M" b' {
我们可以看出，这种分类的信息熵是0.5509775，它的信息增益是0.419973) L* l/ {* \9 f- F2 V6 d& A" x
6 v  K: O: O) ?: H9 ?4 N

! D6 ^! j9 n# f8 `4 K3 n2 Z2 @如果按照圆不圆来分类：4 T8 X9 J% j( x" J" N3 {

9 v4 {  }) _- f. h我们可以看出，这种分类的信息熵是0.8，它的信息增益是0.17095& F4 H8 G  T9 M+ b% ]8 B
( Z. B) t3 E! J" s% k
显然第一种分类的信息增益较大
* }" t# j; g9 K1 t, e' n1 V8 s( c* w# s5 o7 r: J3 s

3 z' F+ e7 W1 z( z$ W8 [( k4 H我们来看一下啊两个划分的结果集：' N: b' v. x: e1 z% w
- S. A# u  S( c

8 G5 s$ {/ G7 k$ s% Q# x5 v1 {确实第一种方法划分的较好。# f; L, k! p1 d7 f2 V! p8 X8 v
这样我们的决策树也就构建好了：+ B# y7 h+ X/ I" J' ^. z

9 ~  y* p4 ~: \+ b: P* Q+ R+ b  s
& U3 b: v4 X2 u0 R" s1 P
作者: 3234139512    时间: 2019-1-23 16:12
帮助很大，谢谢分享
, @/ _9 W4 I3 [) R" O4 l8 l; @



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5