《机器学习：公式推导与代码实践》鲁伟著读书笔记。
决策树（Decision tree）是一种最基础的机器学习方法。决策树的原理是基于特征对数据实例按照条件不同进行不断划分，最终达到分类或者回归的目的。决策树模型的核心概念包括：特征选择方法、决策树构造过程和决策树剪枝。
特征选择从本质上讲就是依据训练集数据从多个特征中选取出具有分类能力的特征。通常情况下，在决策树模型中，我们有三种方式来选取最优特征：信息增益、信息增益比和基尼指数。
信息增益为了更好地解释信息增益的概念，我们需要引入**信息熵（Information entropy）**概念。假设当前样本数据集D中第k个类所占比例为
p
k
,
k
=
1
,
2
,
.
.
.
,
n
p_{k},k=1,2,...,n
pk,k=1,2,...,n，其中n为类别个数那么样本数据集的熵可以定义为：
E
(
D
)
=
−
∑
k
=
1
n
p
k
l
o
g
(
p
k
)
E(D)=-sum_{k=1}^{n}p_{k}log(p_{k})
E(D)=−k=1∑npklog(pk)信息熵越低，样本不确定性越小，相应的纯度就越高。
假设离散随机变量(X,Y)的联合概率分布为：
P
(
X
=
x
i
,
Y
=
y
j
)
=
p
i
j
,
i
=
1
,
2
,
.
.
.
,
m
;
j
=
1
,
2
,
.
.
.
,
n
P(X=x_{i},Y=y_{j})=p_{ij} ,i=1,2,...,m;j=1,2,...,n
P(X=xi,Y=yj)=pij,i=1,2,...,m;j=1,2,...,n条件熵
E
(
Y
∣
X
)
E(Y|X)
E(Y∣X)表示在已知随机变量X的条件下Y的不确定性的度量。
E
(
Y
∣
X
)
E(Y|X)
E(Y∣X)可以定义为在给定X的条件下，Y的条件概率分布的熵对X的数学期望。条件熵可以表示为：
E
(
Y
∣
X
)
=
∑
i
=
1
m
p
i
E
(
Y
∣
X
=
x
i
)
E(Y|X)=sum_{i=1}^{m}p_{i}E(Y|X=x_{i})
E(Y∣X)=i=1∑mpiE(Y∣X=xi)其中
p
i
=
P
(
X
=
x
i
)
,
i
=
1
,
2
,
.
.
.
,
m
p_{i}=P(X=x_{i}),i=1,2,...,m
pi=P(X=xi),i=1,2,...,m。
E
(
Y
∣
X
=
x
i
)
E(Y|X=x_{i})
E(Y∣X=xi)为在
X
=
x
i
X=x_{i}
X=xi的大前提下，Y事件的信息熵。
信息增益定义如下：由于得到特征X的信息而使得类Y的信息不确定性减小的程度。即信息增益是一种描述特征X对特征Y确定性的影响量。特征的信息增益越大，代表对应的特征分类能力越强。在经典决策树中，ID3算法便是基于信息增益进行特征选取的。
假设训练集D的经验熵为E(D)，给定特征A的条件下，D的经验条件熵为E(D|A)，信息增益可以定义为经验熵E(D)与经验条件熵E(D|A)之差。信息增益的公式如下：
g
(
D
∣
A
)
=
E
(
D
)
−
E
(
D
∣
A
)
g(D|A)=E(D)-E(D|A)
g(D∣A)=E(D)−E(D∣A)eg1:
表1 是否打高尔夫
| 是 | 否 |
|---|---|
| 9 | 5 |
计算该数据集的经验熵：
E
(
是
否
打
高
尔
夫
)
=
E
(
5
,
9
)
=
E
(
5
14
,
9
14
)
=
−
5
14
×
l
o
g
2
(
5
14
)
−
9
14
×
l
o
g
2
(
9
14
)
E(是否打高尔夫)=E(5,9)=E(frac {5}{14},frac {9}{14})=-frac {5}{14}times log_{2}(frac {5}{14})-frac {9}{14}times log_{2}(frac {9}{14})
E(是否打高尔夫)=E(5,9)=E(145,149)=−145×log2(145)−149×log2(149)我们给出在天气这个特征的前提下，是否打高尔夫球的情况。
表2 不同天气下是否打高尔夫的情况统计
| 天气 | 是 | 否 | 总计 |
|---|---|---|---|
| 晴 | 2 | 3 | 5 |
| 阴 | 4 | 0 | 4 |
| 雨 | 3 | 2 | 5 |
| 总计 | 14 |
计算在不同天气条件下的条件熵：
E
(
是
否
打
高
尔
夫
∣
天
气
)
=
p
(
晴
)
×
E
(
2
,
3
)
+
p
(
阴
)
×
E
(
4
,
0
)
+
p
(
雨
)
×
E
(
3
,
2
)
=
5
14
×
E
(
2
5
,
3
5
)
+
4
14
×
E
(
1
,
0
)
+
5
14
×
E
(
3
5
,
2
5
)
=
5
14
×
(
−
2
5
×
l
o
g
2
(
2
5
)
−
3
5
×
l
o
g
2
(
3
5
)
)
+
4
14
×
(
−
1
×
l
o
g
2
(
1
)
−
0
×
l
o
g
2
(
0
)
)
+
5
14
×
(
−
3
5
×
l
o
g
2
(
3
5
)
−
2
5
×
l
o
g
2
(
2
5
)
)
=
5
14
×
0.97
+
4
14
×
0
+
5
14
×
0.97
=
0.69
E(是否打高尔夫|天气)=p(晴)times E(2,3)+p(阴)times E(4,0)+p(雨)times E(3,2)=frac {5}{14}times E(frac {2}{5},frac {3}{5})+frac {4}{14}times E(1,0)+frac {5}{14}times E(frac {3}{5},frac {2}{5})=frac {5}{14}times (-frac {2}{5}times log_{2}(frac {2}{5})-frac {3}{5}times log_{2}(frac {3}{5}))+frac {4}{14}times (-1times log_{2}(1)-0times log_{2}(0))+frac {5}{14}times (-frac {3}{5}times log_{2}(frac {3}{5})-frac {2}{5}times log_{2}(frac {2}{5}))=frac {5}{14}times 0.97+frac {4}{14}times 0+frac {5}{14}times 0.97=0.69
E(是否打高尔夫∣天气)=p(晴)×E(2,3)+p(阴)×E(4,0)+p(雨)×E(3,2)=145×E(52,53)+144×E(1,0)+145×E(53,52)=145×(−52×log2(52)−53×log2(53))+144×(−1×log2(1)−0×log2(0))+145×(−53×log2(53)−52×log2(52))=145×0.97+144×0+145×0.97=0.69
天气特征的信息增益为：
g
(
是
否
打
高
尔
夫
∣
天
气
)
=
E
(
是
否
打
高
尔
夫
)
−
E
(
是
否
打
高
尔
夫
∣
天
气
)
=
0.94
−
0.69
=
0.25
g(是否打高尔夫|天气)=E(是否打高尔夫)-E(是否打高尔夫|天气) =0.94-0.69=0.25
g(是否打高尔夫∣天气)=E(是否打高尔夫)−E(是否打高尔夫∣天气)=0.94−0.69=0.25eg2：
计算下图的信息增益：
父辈信息熵为：
E
(
P
a
r
e
n
t
)
=
E
(
70
,
30
)
=
E
(
7
10
,
3
10
)
=
−
7
10
×
l
o
g
2
(
7
10
)
−
3
10
×
l
o
g
2
(
3
10
)
=
0.88129
E(Parent)=E(70,30)=E(frac {7}{10},frac {3}{10})=-frac {7}{10}times log_{2}(frac {7}{10})-frac {3}{10}times log_{2}(frac {3}{10})=0.88129
E(Parent)=E(70,30)=E(107,103)=−107×log2(107)−103×log2(103)=0.88129子辈的条件熵为：
E
(
P
a
r
e
n
t
∣
C
h
i
l
d
)
=
p
(
C
h
i
l
d
1
)
×
E
(
50
,
20
)
+
p
(
C
h
i
l
d
2
)
×
E
(
20
,
10
)
=
7
10
×
E
(
5
7
,
2
7
)
+
3
10
×
E
(
2
3
,
1
3
)
=
7
10
×
(
−
5
7
×
l
o
g
2
(
5
7
)
−
2
7
×
l
o
g
2
(
2
7
)
)
+
3
10
×
(
−
2
3
×
l
o
g
2
(
2
3
)
−
1
3
×
l
o
g
2
(
1
3
)
)
=
0.87967
E(Parent|Child)=p(Child1)times E(50,20)+p(Child2)times E(20,10)=frac {7}{10}times E(frac {5}{7},frac {2}{7})+frac {3}{10}times E(frac {2}{3},frac {1}{3})=frac {7}{10}times (-frac {5}{7}times log_{2}(frac {5}{7})-frac {2}{7}times log_{2}(frac {2}{7}))+frac {3}{10}times (-frac {2}{3}times log_{2}(frac {2}{3})-frac {1}{3}times log_{2}(frac {1}{3}))=0.87967
E(Parent∣Child)=p(Child1)×E(50,20)+p(Child2)×E(20,10)=107×E(75,72)+103×E(32,31)=107×(−75×log2(75)−72×log2(72))+103×(−32×log2(32)−31×log2(31))=0.87967
g
(
P
a
r
e
n
t
∣
C
h
i
l
d
)
=
E
(
P
a
r
e
n
t
)
−
E
(
P
a
r
e
n
t
∣
C
h
i
l
d
)
=
0.00162
g(Parent|Child)=E(Parent)-E(Parent|Child) =0.00162
g(Parent∣Child)=E(Parent)−E(Parent∣Child)=0.00162
信息增益的python实现如下：
