【机器学习】决策树（理论+代码）
【声明：本文为个人学习笔记，内容大部分为李航老师《统计学习方法》以及网上其他资料，会尽量做好引用，几乎没有我自己写的东西，只适合作者本人整理思路使用。如有错误，欢迎骂我】
决策树是一种分类和回归的方法。
三个步骤：特征选择、决策树生成、决策树修剪
主要算法：ID3，C4.5，CART
特征选择
特征选择的准则是信息增益（比）
-
熵的定义
熵是表示随机变量不确定性的度量，随机变量
X
X
X是一个取有限值的离散随机变量，则随机变量
X
X
X的熵定义为
H
(
X
)
=
?
∑
i
=
1
n
p
i
l
o
g
p
i
H(X) = -\sum\limits_{i=1}^{n}p_i logp_i
H(X)=?i=1∑n?pi?logpi? -
熵的性质
0
≤
H
(
p
)
≤
l
o
g
(
n
)
0\leq H(p) \leq log(n)
0≤H(p)≤log(n)
证明： 对任何非负实数
a
1
,
…
,
a
n
a_1,…,a_n
a1?,…,an? 和正数 $b
1
,
…
,
b
1,…,b
1,…,bn$ ，并记
a
:
=
∑
i
=
1
n
a
i
a:=\sum_{i=1}^na_i
a:=∑i=1n?ai? 及
b
:
=
∑
i
=
1
n
b
i
b:=\sum_{i=1}^nb_i
b:=∑i=1n?bi?
则有如下的对数求和不等式：
∑
i
=
1
n
a
i
log
?
a
i
b
i
≥
a
log
?
a
b
\sum _{i=1}^{n}a_{i}\log {\frac {a_{i}}{b_{i}}}\geq a\log {\frac {a}{b}}
i=1∑n?ai?logbi?ai??≥alogba?上式中，等号成立的充分必要条件是所有
a
i
b
i
\frac{a_i}{b_i}
bi?ai?? 都相等。
由对数求和不等式易证
香农总结信息熵的三条性质知乎问题：信息熵是什么
单调性，即发生概率越高的事件，其所携带的信息熵越低。极端案例就是“太阳从东方升起”，因为为确定事件，所以不携带任何信息量。从信息论的角度，认为这句话没有消除任何不确定性。
非负性，即信息熵不能为负。这个很好理解，因为负的信息，即你得知了某个信息后，却增加了不确定性是不合逻辑的。
累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。 -
联合熵
H
(
X
,
Y
)
=
?
∑
x
i
∈
X
∑
_
y
i
∈
Y
p
(
x
i
,
y
i
)
l
o
g
p
(
x
i
,
y
i
)
H(X,Y) = -\sum_{x_i \in X}\sum\_{y_i \in Y}p(x_i,y_i)logp(x_i,y_i)
H(X,Y)=?xi?∈X∑?∑_yi?∈Yp(xi?,yi?)logp(xi?,yi?) -
条件熵
类似于条件概率，度量在知道
Y
Y
Y以后，
X
X
X的不确定性：
H
(
X
∣
Y
)
=
?
∑
x
i
∈
X
∑
y
i
∈
Y
p
(
x
i
,
y
i
)
l
o
g
p
(
x
i
∣
y
i
)
=
∑
j
=
1
n
p
(
y
j
)
H
(
X
∣
y
j
)
H(X|Y) = -\sum\limits_{x_i \in X}\sum\limits_{y_i \in Y}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)
H(X∣Y)=?xi?∈X∑?yi?∈Y∑?p(xi?,yi?)logp(xi?∣yi?)=j=1∑n?p(yj?)H(X∣yj?)
一般的，熵
H
(
X
)
H(X)
H(X)与条件熵
H
(
X
∣
Y
)
H(X|Y)
H(X∣Y)只差称为互信息。 -
信息增益
I
(
D
∣
A
)
=
H
(
D
)
?
H
(
D
∣
A
)
I(D|A) = H(D) - H(D|A)
I(D∣A)=H(D)?H(D∣A) -
信息增益比
决策树生成
ID3算法与C4.5算法都很好理解，ID3算法使用的信息增益评价标准倾向于选择取值较多的属性，C4.5使用信息增益比对ID3进行了改进。
决策树剪枝
李航老师的书讲的是后剪枝，即先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。
决策树过拟合的原因是过于追求在训练集上的精度，构造了过于复杂的决策树。因而需要“剪枝”，提高决策树的泛化能力。
决策树的剪枝往往通过极小化决策树整体的损失函数或者代价函数来实现
具体算法简单，看书即可，略。
CART算法(classification and regression tree)
对回归树（输出是连续的）使用平方误差最小化准则，对分类树(输出是离散的)使用基尼指数。
回归树：
使用启发式方法对输入空间进行划分。
（启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。）
对于任意划分特征
A
A
A,选择特征
A
A
A中任一取值
s
s
s将数据集
D
D
D划分为
D
1
D_1
D1?和
D
2
D_2
D2?，*求出使得在
D
1
D_1
D1?和
D
2
D_2
D2?集合中各自样本的均方差最小，同时同时
D
1
D_1
D1?和
D
2
D_2
D2?的均方差之和最小所对应的特征和特征值划分点（这里个人认为写的不好）。表达式为：
m
i
n
?
A
,
s
[
m
i
n
?
c
1
∑
x
i
∈
D
1
(
A
,
s
)
(
y
i
?
c
1
)
2
+
m
i
n
?
c
2
∑
x
i
∈
D
2
(
A
,
s
)
(
y
i
?
c
2
)
2
]
\underbrace{min}_{A,s}\Bigg[\underbrace{min}_{c_1}\sum\limits_{x_i \in D_1(A,s)}(y_i - c_1)^2 + \underbrace{min}_{c_2}\sum\limits_{x_i \in D_2(A,s)}(y_i - c_2)^2\Bigg]
A,s
min??[c1?
min??xi?∈D1?(A,s)∑?(yi??c1?)2+c2?
min??xi?∈D2?(A,s)∑?(yi??c2?)2]
固定
A
A
A，就可以找到最优切分点
s
s
s
分类树
使用基尼系数，省去了计算
l
o
g
log
log
CATR剪枝
剪枝然后交叉验证
未完结
参考资料
博客园刘建平
|