本文为博主学习机器学习决策树部分的一些笔记和思考，以及python编程实现算法的具体步骤
决策树(decision tree) 是一类常见的机器学习方法. 在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法. 在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系.
对于决策树的原理和概念以及信息增益的计算部分不再赘述，对此部分感兴趣或者希望了解的朋友可以翻阅周志华《机器学习》P73～P78
本文重点介绍CART决策树
一、基本概念
CART决策树[Breiman et al., 1984] 使用“基尼指数”来选择划分属性. 这是西瓜书上给出的定义. 通过大量文章的阅读将CART决策树关键点整理如下：
- CART决策树既能是分类树，也能是回归树
- 当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据
-
CART是一颗二叉树 (关于这一点其实我存在疑惑，准备去问问老师或者同学。因为在我编程实现的过程中忽略了这一点，因为西瓜树上并没有指明CART算法必须生成二叉树. 而其中西瓜数据集中的离散属性取值
N
≥
3
N\geq3
N≥3，因此我在编程过程中生成的是多叉树. 所以是否考虑在属性取值较少的情况下，CART算法不用一定生成二叉树)
二、选择划分属性
目标取值为一个有限集合的树模型称为分类树，而目标值是连续值(典型的真实数值)的树模型称为回归树。分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么CART是如何评价节点的纯度呢？如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度. 节点越不纯，节点分类或者预测的效果就越差.
1、CART决策树作为分类树
CART决策树作为分类树时，特征属性可以是连续类型也可以是离散类型，但观察属性(即标签属性或者分类属性)必须是离散类型。
划分的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。
如果是分类树，CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可以用基尼值来度量：
G
i
n
i
(
D
)
=
∑
k
=
1
∣
Y
∣
∑
k
′
≠
k
p
k
p
k
′
Gini(D)=\sum_{k=1}^{\vert \mathcal Y\vert}\sum_{k'\neq k}p_kp_{k'}
Gini(D)=k=1∑∣Y∣k′=k∑pkpk′
=
1
−
∑
k
=
1
∣
Y
∣
p
k
2
=1-\sum_{k=1}^{\vert \mathcal Y\vert}p_k^2
=1−k=1∑∣Y∣pk2
直观来说，
G
i
n
i
(
D
)
Gini(D)
Gini(D)反映了从数据集
D
D
D中随机抽取两个样本，其类别标记不一致的概率。因此，
G
i
n
i
(
D
)
Gini(D)
Gini(D)越小，则数据集
D
D
D的纯度越高.
属性
a
a
a的基尼指数定义为
G
i
n
i
_
i
n
d
e
x
(
D
,
a
)
=
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
G
i
n
i
(
D
v
)
.
Gini\_ index(D,a)={\sum_{v=1}^V \frac{\vert D^v\vert}{\vert D\vert}}Gini(D^v).
Gini_index(D,a)=v=1∑V∣D∣∣Dv∣Gini(Dv).
所以我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即
a
∗
=
a
r
g
a
∈
A
m
i
n
G
i
n
i
_
i
n
d
e
x
(
D
,
a
)
a_*={arg}_{a \in A}min\ Gini\_ index(D,a)
a∗=arga∈Amin Gini_index(D,a).
2、CART作为回归树
而如果是回归树，其建立算法同CART分类树大部分是类似的。除了上述中提到的两者样本输出的不同，CART回归树和CART分类树的建立和预测主要有以下两点不同：
- 连续值的处理方法不同
- 决策树建立后做预测的方式不同
回归树对于连续值的处理使用了常见的和方差的度量方式，即：
σ
=
∑
i
∈
I
(
x
i
−
μ
)
2
=
∑
i
∈
I
x
i
2
−
n
μ
2
.
\sigma=\sqrt {\sum_{i\in I}(x_i-\mu )^2}=\sqrt {\sum_{i\in I}{x_i}^2-n\mu ^2}.
σ=i∈I∑(xi−μ)2=i∈I∑xi2−nμ2.
方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据都相同，那么方差就为0，此时可以很肯定得认为该节点的输出值；如果节点的数据相差很大，那么输出的值有很大的可能与实际值相差较大。
因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者回归方差最小的属性作为分裂的方案。
即最小化分类树:
G
a
i
n
=
∑
i
∈
I
p
i
⋅
G
i
n
i
i
Gain=\sum_{i\in I}p_i\cdot Gini_i
Gain=i∈I∑pi⋅Ginii
或者回归树：
G
a
i
n
=
∑
i
∈
I
σ
i
.
Gain=\sum _{i\in I}\ \sigma _i.
Gain=i∈I∑ σi.
三、剪枝处理
剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段. 决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(post-pruning). 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点; 后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.
预剪枝使得决策树很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销. 但另一方面，预剪枝由于基于“贪心”本质将某些禁止展开的分支的后续划分也一并禁止，而其中某些后续划分有可能会导致泛化性能显著提高，给预剪枝决策树带来了欠拟合的风险.
后剪枝决策树通常比预剪枝决策树保留了更多的分支，且在一般情况下欠拟合风险很小，泛化性能往往也能优于预剪枝决策树。但由于其是在生成完全决策树之后进行的，并且要自底向上考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大很多.
四、连续值处理
由于现实学习任务中常会遇到连续属性，由于连续属性的可取值树木不再有限，此时连续属性离散化技术可派上用场. 最简单的策略是采用**二分法(bi-partion)**对连续属性进行处理，这正是C4.5决策树算法中采用的机制.
给定样本集合
D
D
D和连续属性
a
a
a，假定
a
a
a在
D
D
D上出现了n个不同的取值，将这些值从小到大进行排序，记为{
a
1
,
a
2
,
.
.
.
,
a
n
a^1,a^2,... ,a^n
a1,a2,...,an}. 基于划分点
t
t
t可将子集
D
t
−
D^-_t
Dt−和
D
t
+
D^+_t
Dt+，其中
D
t
−
D^-_t
Dt−包含那些在属性
a
a
a上取值不大于
t
t
t的样本，而
D
t
+
D^+_t
Dt+则包含那些在属性
a
a
a上取值大于
t
t
t的样本. 所以对连续属性
a
a
a，我们可考察包含
n
−
1
n-1
n−1个元素的候选划分点集合
T
a
=
{
a
i
=
a
i
+
1
2
∣
1
≤
i
≤
n
−
1
}
T_a= \left\{ \frac {a^i=a^{i+1}}{2} \vert1 \leq i \leq n-1 \right\}
Ta={2ai=ai+1∣1≤i≤n−1}
即把区间
[
a
i
,
a
i
+
1
)
\left[a^i,a^{i+1} \right)
[ai,ai+1)的中位点
a
i
+
a
i
+
1
2
\frac{a^i+a^{i+1}}{2}
- 文章目录
- 繁
