决策树
简介
决策树算法以树状结构表示数据分类的结果。每个决策点实现一个具有离散输出的测试函数，记为分支。
f
(
x
)
=
{
根
结
点
非
叶
子
节
点
（
决
策
点
）
叶
子
节
点
分
支
f(x)=\left\{ \begin{aligned} 根结点 \\ 非叶子节点（决策点） \\ 叶子节点 \\ 分支 \end{aligned} \right.
f(x)=????????????根结点非叶子节点（决策点）叶子节点分支?
熵
P
(
X
,
Y
)
=
P
(
X
)
?
P
(
Y
)
X
P(X, Y)=P(X)^{*} P(Y) \quad X
P(X,Y)=P(X)?P(Y)X 和Y两个事件相互独立
log
?
(
X
Y
)
=
log
?
(
X
)
+
log
?
(
Y
)
\log (X Y)=\log (X)+\log (Y)
log(XY)=log(X)+log(Y)
H
(
X
)
,
H
(
Y
)
\mathrm{H}(\mathrm{X}), \mathrm{H}(\mathrm{Y})
H(X),H(Y) 当成它们发生的不确定性
P
(
\mathrm{P}(
P( 几率越大)-
>
H
(
X
)
>\mathrm{H}(\mathrm{X})
>H(X) 值越小 如：今天正常上课
P
(
\mathrm{P}(
P( 几率越小)
?
>
H
(
X
)
->\mathrm{H}(\mathrm{X})
?>H(X) 值越大 如：今天没翻车
熵
=
?
∑
i
=
1
n
P
i
ln
?
(
P
i
)
=-\sum_{i=1}^{n} P_{i} \ln \left(P_{i}\right)
=?∑i=1n?Pi?ln(Pi?)
Gini系数
=
Gini
?
(
p
)
=
∑
k
=
1
K
p
k
(
1
?
p
k
)
=
1
?
∑
k
=
1
K
p
k
2
=\operatorname{Gini}(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}
=Gini(p)=∑k=1K?pk?(1?pk?)=1?∑k=1K?pk2?
根结点的选取
构造树的基本想法是随着树深度的增加，节点的嫡迅速地降低。嫡降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。
常用算法
ID3：信息增益
一般来讲，如果特征把N个样本划分成了m组，每组Nm个像本，则信息增益（不纯度减少量）为
Δ
I
(
N
)
=
I
(
N
)
?
(
P
1
I
(
N
1
)
+
P
2
I
(
N
2
)
+
?
+
P
m
I
(
N
m
)
)
?其中,?
P
m
=
N
m
/
N
\begin{aligned} &\Delta I(N)=I(N)-\left(P_{1} I\left(N_{1}\right)+P_{2} I\left(N_{2}\right)+\cdots+P_{m} I\left(N_{m}\right)\right) \\ &\text { 其中, } P_{m}=N_{m} / N \end{aligned}
?ΔI(N)=I(N)?(P1?I(N1?)+P2?I(N2?)+?+Pm?I(Nm?))?其中,?Pm?=Nm?/N?
在属性很多，但样本又很少，就会导致信息增益偏大
C4.5: 信息增益率
还要计算信息增益自身的熵值
Δ
I
R
(
N
)
=
Δ
I
(
N
)
I
(
N
)
\Delta I_{R}(N)=\frac{\Delta I(N)}{I(N)}
ΔIR?(N)=I(N)ΔI(N)?
Gini系数：
Gini不纯度度量,也称方差不纯度
I
(
N
)
=
∑
m
≠
n
P
(
ω
m
)
P
(
ω
n
)
=
1
?
∑
j
=
1
k
P
2
(
ω
j
)
I(N)=\sum_{m \neq n} P\left(\omega_{m}\right) P\left(\omega_{n}\right)=1-\sum_{j=1}^{k} P^{2}\left(\omega_{j}\right)
I(N)=m?=n∑?P(ωm?)P(ωn?)=1?j=1∑k?P2(ωj?)
也有人采用所谓误差不纯度
I
(
N
)
=
1
?
max
?
i
P
(
ω
j
)
I(N)=1-\max _{i} P\left(\omega_{j}\right)
I(N)=1?imax?P(ωj?)
能够处理连续型的属性。首先将连续型属性离散化，把连续型属性的值分成不同的区间，依据是比较各个分裂点Gian值的大小。
缺失数据的考虑:在构建决策树时，可以简单地忽略缺失数据，即在计算增益时，仅考虑具有属性值的记录。
评价函数： C ( T ) = ∑ t ∈ ?aaf? N t ? H ( t ) C(T)=\sum_{t \in \text { aaf }} N_{t} \cdot H(t) \quad C(T)=∑t∈?aaf??Nt??H(t) (希望它越小越好,类似损失函数了)
剪枝
评价函数改进： C α ( T ) = C ( T ) + a ∣ T loaf? ∣ ?叶子节点个数越多,?损失越大? C_{\alpha}(T)=C(T)+a\left|T_{\text {loaf }}\right| \text { 叶子节点个数越多, 损失越大 } Cα?(T)=C(T)+a∣Tloaf??∣?叶子节点个数越多,?损失越大?
预剪枝
所谓先剪枝,实际就是控制决策树的生长,在决等树生长讨程中决定某节点是否需要继续分枝还是直接作为叶节点。一日某节点被判断为叶节点以后,则该分枝停止生长。
通常,用于判断决策树何时停止的方法有三种:
(1) 数据划分法。该方法的核心思想是将数据分成训练样本和测试样本,首先基于训练样本对决策树进行生长,直到在测试样本上的分类错误率达到最小时停止生长。此方法只利用了一部分样本进行决策树的生长,没有充分利用数据信息,因此通常采用多次的交叉验证方法(参考第10章)以充分利用数据信息。
(2)阈值法。预先设定一个信息增益阈值,当从某节点往下生长时得到的信息增益小于设定阙值时停止树的生长。但是,实际应用中此阙值往往不容易设定。
(3）信息增益的统计显著性分析。对已有节点获得的所有信息增益统计其分布,如果继续生长得到的信息增益与该分布相比不显著,则停止树的生长,通常可以用卡方检验来考查这个显著性。
后剪枝
顾名思义,后剪枝是指在决策树得到充分生长以后再对其进行修剪。后剪枝的核心想是对一些分枝进行合并,它从叶节点出发,如果消除具有相同父节点的叶节点后不会导到不纯度的明显增加则执行消除,并以其父节点作为新的叶节点。如此不断地从叶节点往上进行回溯,直到合并操作不再适合为止。
常用的剪枝规则也有三种:
(1）减少分类错误修剪法。该方法试图通过独立的剪枝集估计剪枝前后分类错误率的改变,并基于此对是否合并分支进行判断。
(2）最小代价与复杂性的折中。该方法对合并分枝后产生的错误率增加与复杂性减少进行折中考虑,最后得到一个综合指标较优的决策树。
(3）最小描述长度(minimal description length, MDIL)准则。该方法的核心思想是,最简单的树就是最好的树。该方法首先对决策树进行编码,再迪过剪枝得到编码最短的决策树。
随机森林
顾名思义,随机森林就是建立很多决策树,组成一个决策树的“森林”,通过多棵树投票来进行决策。理论和实验研究都表明,这种方法能够有效地提高对新样本的分类准确度即推广能力。这里只给出随机森林方法的三个基本步骤:
首先,随机森林方法对样本数据进行自举重采样,得到多个样本集。所谓自举重采样，就是每次从原来的N个训练样本中有放回地随机抽取N个样本(包括可能的重复样本)。
然后,用每个重采样样本集作为训练样本构造一个决策树。在构造决策树的过程中,每次从所有候选特征中随机地抽取m 个特征,作为当前节点下决策的备选特征,从这些特征中选择最好地划分训练样本的特征。
最后,得到所需数目的决策树后,随机森林方法对这些树的输出进行投票,以得票最多的类作为随机森林的决策。
与之相近的算法还有bagging方法、ADAboost方法等。
MATLAB相关代码
Model = TreeBagger(ntree,train_data,train_label,'Method','classification')
ntree 树的数量
train_data 训练样本数据
train_label 训练样本数据对应的类别标签
[predict_label,scores] = predict(Model, test_data)
test_data 测试数据
predict_label 分类结果
scores 概率分布
view(Model.Trees{n})
或view(Model.Trees{n},‘Mode’,‘graph’)
n 树的编号
可以看到每棵树的决策过程。
以国赛数模2017B第一题为例
根据各个指标来分类完成与未完成。
部分数据截取
MATLAB实现
clc;clear;
load train_label.mat;
load train_data.mat;
ntree=10;
test_data=train_data;
Model = TreeBagger(ntree,train_data,train_label,'Method','classification')
[predict_label,scores] = predict(Model, test_data)
预测结果
为了方便，我直接把训练集当做测试集带入了……
结果如下：
只有少部分错误，相比神经网络、多元线性回归、逻辑回归、SVM等方式，正确率高出了一大截。当然，是否存在过拟合现象有待验证，更加好的做法应该是随机抽取一部分样本作为测试集，其余作为训练集，重复多次可测的正确率。