1. 决策树算法思想
1.1 概述
决策树算法：是一种分治算法，目的是构建一个基于属性的树形分类器。
- 每个非叶结点代表一个特征属性上的测试（分割）；
- 每个分支代表这个特征属性在某个值域上的输出；
- 每个叶结点代表一个类别。
使用决策树进行决策的过程就是从根结点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到达到叶结点，将叶结点存放的类别作为决策结果。
1.2 决策树构建
决策树构建：分治思想（递归）。
对于当前结点结束递归的条件：
- 当前结点样本均属于同一类别，无需划分；
- 当前属性集为空，无法划分；
- 所有样本在当前属性集上取值相同，无法划分；
- 当前结点包含的样本集合为空，无法划分。
算法伪代码：
注：第2~3行对应于递归结束条件1，第5~6行对应于递归结束条件2和3，第11~12行对应于递归条件4。
9~16行的个人理解：对于最佳划分属性 a ? a_* a??，会为每一个属性值 a ? v a_*^v a?v?生成一个分支。我们现在仅讨论某一个属性值 a ? v a_*^v a?v?，已知通过这个分支后的样本子集为 D v D_v Dv?。如果 D v D_v Dv?为空，这个结点就是叶结点，然后回溯去找 D D D中样本最多的类，作为叶结点的类别；如果 D v D_v Dv?非空，那么就根据样本子集 D v D_v Dv?和属性子集 A ? a ? A-a_* A?a??递归该函数继续划分。
1.3 决策树核心
决策树的核心在于定义最佳划分属性，使得不同类样本被更好的分离。
- 理想情况：划分后每个分支的样本都属于同一类。
- 实际情况：想得美！
根据最佳划分属性的选取方式（准则）的不同，人们提出了不同的算法。
2. 决策树算法
2.1 ID3算法
最佳划分属性选取准则：信息增量越大越好。
目标：提升划分后子集的纯度，降低划分后子集的不纯度。纯度↑=信息量↓=信息熵↓。
什么叫纯？看图！怎么度量信息量？信息熵！
信息熵： E n t ( D ) = ? ∑ k = 1 ∣ y ∣ p k log ? 2 p k Ent(D)=-\sum\limits_{k=1}^{|y|}p_k\log_2p_k Ent(D)=?k=1∑∣y∣?pk?log2?pk?用属性 a a a对数据集 D D D划分后的信息熵： E n t ( D , a ) = ∑ v = 1 ∣ V ∣ ∣ D v ∣ ∣ D ∣ E n t ( D v ) Ent(D,a)=\sum\limits_{v=1}^{|V|}\frac{|D^v|}{|D|}Ent(D^v) Ent(D,a)=v=1∑∣V∣?∣D∣∣Dv∣?Ent(Dv)用属性 a a a对数据集 D D D划分后的信息增益： G a i n ( D , a ) = E n t ( D ) ? E n t ( D , a ) Gain(D,a)=Ent(D)-Ent(D,a) Gain(D,a)=Ent(D)?Ent(D,a)信息增益越大，说明划分效果越好。因此，ID3算法是这样选取最佳划分属性的： a ? = arg?max ? a ∈ A G a i n ( D , a ) a_*=\argmax\limits_{a∈A}Gain(D,a) a??=a∈Aargmax?Gain(D,a)问题：信息增益准则对可取值数目较多的属性有所偏好。例如极端例子为编号属性，由于每个样本的编号都不同，因此每个编号只有一个样本，并对应一个标签，因此纯度很高。
2.2 C4.5算法
最佳划分属性选取准则：信息增益率越大越好。
信息增益率：
G
a
i
n
_
r
a
t
i
o
(
D
,
a
)
=
G
a
i
n
(
D
,
a
)
I
V
(
a
)
Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}
Gain_ratio(D,a)=IV(a)Gain(D,a)?其中
I
V
(
a
)
IV(a)
IV(a)称为属性
a
a
a的固有值，属性
a
a
a的可取值数目越多（也就是
v
v
v越大），
I
V
(
a
)
IV(a)
IV(a)通常就越大。其定义如下：
I
V
(
a
)
=
?
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
log
?
2
∣
D
v
∣
∣
D
∣
IV(a)=-\sum\limits_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}
IV(a)=?v=1∑V?∣D∣∣Dv∣?log2?∣D∣∣Dv∣?问题：增益率准则对可取值数目较少的属性有所偏好。因此，C4.5先从候选属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。
ID3和C4.5都基于信息论的熵模型，涉及大量对数运算。
2.3 CART算法
最佳划分属性选取准则：基尼指数越小越好。
基尼指数：
G
i
n
i
(
D
)
=
∑
k
=
1
∣
y
∣
∑
k
′
≠
k
p
k
p
k
′
=
1
?
∑
k
=
1
∣
y
∣
p
k
2
Gini(D)=\sum\limits_{k=1}^{|y|}\sum\limits_{k'≠k}p_kp_k'=1-\sum\limits_{k=1}^{|y|}p_k^2
Gini(D)=k=1∑∣y∣?k′?=k∑?pk?pk′?=1?k=1∑∣y∣?pk2?基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，基尼指数越小，数据集
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\limits_{v=1}^{|V|}\frac{|D|^v}{|D|}Gini(D^v)
Gini_index(D,a)=v=1∑∣V∣?∣D∣∣D∣v?Gini(Dv)CART算法是这样选取最佳划分属性的：
a
?
=
arg?min
?
a
∈
A
G
i
n
i
_
i
n
d
e
x
(
D
,
a
)
a_*=\argmin\limits_{a∈A}Gini\_index(D,a)
a??=a∈Aargmin?Gini_index(D,a)
3. 决策树剪枝
4. 连续值与缺失值处理
4.1 连续值处理
基本思路：连续属性离散化。
常见方法：二分法。
n
n
n个属性值可形成
n
?
1
n-1
n?1个候选划分，即可当做
n
?
1
n-1
n?1个离散属性值处理。
二分法流程：
- 给定样本集 D D D和连续属性 a a a，假定 a a a在 D D D上出现了 n n n个不同的取值，则将属性值由小到大排序为 { a 1 , a 2 , . . . , a n } \{a^1,a^2,...,a^n\} {a1,a2,...,an}；
- 基于候选划分点集合 T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n ? 1 } T_a=\{\frac{a^i+a^{i+1}}{2}|1≤i≤n-1\} Ta?={2ai+ai+1?∣1≤i≤n?1}中的每个划分点 t t t，将 D D D分为 D ? D^- D?（ ≤ t ≤t ≤t的属性值集合）和 D + D^+ D+（ ≥ t ≥t ≥t的属性值集合）；
- 根据最大化信息增益的规则选取最优划分点，即： G a i n ( D , a ) = max ? t ∈ T a G a i n ( D , a , t ) = max ? t ∈ T a E n t ( D ) ? ∑ λ ∈ { ? , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ ) Gain(D,a)=\max\limits_{t∈T_a}Gain(D,a,t)=\max\limits_{t∈T_a}Ent(D)-\sum\limits_{\lambda∈\{-,+\}}\frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda}) Gain(D,a)=t∈Ta?max?Gain(D,a,t)=t∈Ta?max?Ent(D)?λ∈{?,+}∑?∣D∣∣Dtλ?∣?Ent(Dtλ?)
4.2 缺失值处理
如果简单丢弃有缺失值的样本，无疑是对信息的浪费。
问题：有属性值缺失，如何选择划分属性？给定划分属性，如果样本在该属性上的值缺失，如何进行划分？
基本思路：样本赋权，权重划分。
5. 多变量决策树
对 d d d维样本进行分类等价于在 d d d为空间中寻找不同类样本之间的分类边界。
单变量决策树
单变量决策树：在每个非叶结点仅考虑一个划分属性，因此产生“轴平行”分类面。
问题：当学习任务所对应的分类边界很复杂时，需要非常多段划分才能获得较好的近似。这会导致决策树相当复杂，且时间开销巨大。能否产生“斜”分类面？
多变量决策树
多变量决策树：每个非叶结点不仅考虑一个属性。例如“斜决策树” 不是为每个非叶结点寻找最优划分属性，而是建立一个线性分类器。
