2019-05-07

数据挖掘|决策树

数据挖掘|决策树和相关算法

数据挖掘笔记

记录：氦核最后编辑时间：20190508

前排简介，本文不涉及实战，仅仅举例。文章中间夹杂很多个人思考与经验，如有错误，请在下方评论区指出，欢迎讨论。

预测数据集

年龄、性别、家庭所得、是否购买

目标：用前面三列的数据预测是否购买

>
root node根节点
non-leaf node：非叶结点
branches：分支
leaf node：叶子节点

注：树不一定对称。很多时候会有一个偏态
树分为两种，一种是分类树（离散变量），一种是回归树（连续变量）。

对每一个变量进行大致分类：

1.年龄-小于35、大于等于35
2.家庭所得：低、高、小康
3.性别：男、女

此时，只有年龄是我们希望看到的根节点分类。

如何分节点呢？最常见的方式是计算信息增益

信息增益的计算

方法1：ID3

$I = -(P_1*log_2(p_1) + ... + P_k*log_2(p_k)) = - \sum_{i = 1}^{k}{P_i*log_2(p_i)}$ $Gain(X) = I(n,n_1) - E(X) $

注：

$I(n,n_1) = -(n_1/n)*log_2(n_1/n) + (n-n_1)/n *log_2((n-n_1)/n)$ $E(X) = m_1 /n * I(m_1,m_{11}) + m_2 /n * I(m_2,m_{21}) +...+ m_k /n * I(m_k,m_{k1})$

节点分开后，对另外的变量进行信息增益的计算

一棵树，三个节点

总结一下：信息增益——基于熵的概念（搞信息的人常用）

做分支前后熵的差值

方法2：GINI INDEX

$i(t) = \sum_{i≠j}p(i/t)p(j/t)$ $gini_{split}(T) = \frac{N_1}{N} gini(T_1) + \frac{N_2}{N} gini(T_2)$

将基尼系数最小的作为划分属性

做统计的常用，比较简便

注：ID3（信息增益）

当ID3确定根节点以及后续节点后，当满足一下条件该分支可以结束：

1.该群数据的每一个数据都已经归类到同一类别中

2.该群数据已经没办法找到新的属性进行节点分割

3.该群数据已经没有尚未处理的数据

过度拟合问题

并不一定是好事，有可能发生过度拟合，在推广模型时产生较大误差。

两种过度拟合：

1.噪声导致的过度拟合，如错误的分类，或者属性值

2.缺乏代表性的样本导致，如数据有偏

出现过度拟合时处理方式：剪枝

剪枝

预剪枝：提前停止树的构建

1.定义一个高度，到达时停止生长

2.达到某个节点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这个方法对于处理数据的数据冲突问题比较有效

3.定义一个阈值，当达到某个节点的实例个数小于阈值时，停止生长（常用）

4.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止生长

思考：有没有什么不太好的地方

第二个比较特别，特殊情况特殊考虑。第四个更容易接受，理由是比较客观。因为阈值不好设置，需要经验。

因此预剪枝的方式好理解，但是多采用后剪枝的方式。但是要求计算量和计算速度。

后剪枝

首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。

相比于预剪枝，这种方法更常用。

其他剪枝方法

Minimal cost-complexity pruning
CCP代价复杂度剪枝

$R_\alpha(T) = R(T) + \alpha |T| $ $R_\alpha(T(\alpha)) = min_{T <= T_(max) } R_\alpha (T) $

该算法为子树 $T_t$ 定义了代价和复杂度以及一个可由用户设置的衡量代价与复杂度之间关系的参数 $\alpha$

代价指在剪枝过程中因子树 $T_t$ 被叶节点替代而增加的错分样本

复杂度表示剪枝后子树 $T_t$ 减少的叶结点数

$\alpha$$ 则表示剪枝后树的复杂度降低程度与代价间的关系 $$ \alpha = \frac{R(t) - R(T_t)}{|N_1| - 1} $

|N1|：子树 $T_t$ 中的叶节点数，衡量树的复杂度

R(t) ：结点t的错误代价

R(t) = r(t) ∗p(t) ， r(t)为结点t的错分样本率 p(t)为落入结点t的样本占所有样本的比例

R( $T_t$ )：子树Tt错误代价

R( $T_t$ )=$\sum$R(i)，i为子树 $T_t$ 的叶节点

步骤：

1.对于完全决策树T的每个非叶结点计算α值，循环剪掉具有最小α值的子树，直到剩下根节点。在该步可得到一系列的剪枝树｛T0，T1，T2……Tm｝,其中T0为原有的完全决策树，Tm为根结点，$T_{i+1}$为对$T_i$进行剪枝的结果；

2.从子树序列中，根据真实的误差估计选择最佳决策树。

即：几个分对了，几个分错了

一倍标准差规则

有一个cp（复杂度参量）取不同值的table，

展示每个样本的CP，nsplit，rel error，xerror，xstd

原则首先保证一定的预测误差（通过交叉验证获得，训练模型放进预测模型验证，k轮交叉验证后获得误差的平均xerror）尽量小，但不一定要取最小值，而是允许它在“最小的误差+或-一个相应标准差”的范围内，然后再此范围内选取尽量小的复杂性参量，进而以它为依据进行剪枝。

CP值越大模型越精简（小的时候需要剪枝），CP不断减小时，xerror先变小后变大（树预测结果先变好，后过拟合）。我们要找xerror最小的行，同时也要综合CP值，选一个较大的。

连续型变量的树处理

自变量连续条件可以由树处理

甚至因变量连续也可以（决策树回归）

如何处理？也得分支，建树

利用大于小于分支

部分代码实现（R)

fit <- rpart(Species~., data=iris,method="class")
    #建立分类树的模型
fit2 <-rpart(Species~.,data=iris,control=rpart.control(cp=.05))

print(fit)                      #展示分类树的主要输出结果
path.rpart(fit, node=c(1,2,3))  #展示前四个节点的分枝情况

plot(fit, asp=4, compress=T)
text(fit, cex=1,use.n=T)        #画出分类树的图

method参数：class“离散型”，anova“连续型”，poisson”计数型“，exp“生存分析型”

control：用来控制每个节点的最小样本量、交叉验证的次数、复杂性参量（cp）。这个参数意味着对每一步拆分，模型的拟合优度必须提高的程度

其他实操要注意的（其实是讲代码时候突然提到的，没地方记了）

混淆矩阵再两分类比较好分析，错分情况的概率好解释。但如果维数较高，就不好解释了。实际含义与二维相比可能有所不同。

决策树方法不好的地方

鸢尾花数据，抽选部分数据做模型，“建一棵树”的方法用在不同的数据集上时，结果会一样吗？

决策树方法很不稳定

如何评价树的好坏？

1.K 折交叉验证

2.留1验证

3.oob估计

k折交叉验证是以前讲过的方法，做很多轮。k取很大或很小都不好：k取很大时即留1验证；k取很小时测试得到的误差太不稳定。

留1验证即每次只留一个作为测试样本

几个处理决策树精度的方法

boostrap（自助法）

最重要特点：从n个样品中，等概率地有放回地抽样。

抽出n个，抽多轮。称为bootstrap抽样集。

对训练集L进行bootstrap抽样(样本量为n)获得新的训练集，从训练集中等概率、有放回的重新抽取样本，得到bootstrap抽样数据集。

对于一个样本点i来说，它出现在bootstrap抽样数据集$Z^∗$中的概率

$P(x_i,y_i )∈Z^∗)=1-(1-1/N)^N≈0.632$

换句话说，由于bootstrap抽样的性质，L中大约每次约有37%的样本点不在$L_m$中。

可以将bootstrap抽样理解成从数据Z的经验分布中的抽样。即可以将训练集和bootstrap抽样训练集理解为来自同一分布的。

每一轮抽取时，未被bootstrap抽中的（37%），当作测试集。

Out Of Bag

对训练集L进行bootstrap抽样(样本量为N)获得新的训练集${ L_m,m = 1,2,…,M}$时，由于bootstrap抽样的性质，L中大约每次有37%的样本点不在$L_m$中，这些样本点对于应用$L_m$构建的预测器$H_m(x,L_m)$来说，可以看作是未被使用的测试样本。

假设M=100，则某一个固定的样本点$(x_n,y_n)$，大概有37个$H_m(x,L_m) $没有使用该样本点。我们称这些样本点为“out-of-bag”样本点.

对这些样本点的预测可以用来准确估计某些重要指标:

–比如在分类树中，可以用“out-of-bag”估计每个样本点属于第j类的概率，也可以用来估计节点概率；

–应用到回归树中，可以用来估计节点均方误差；

–应用“out-of-bag”的预测值可以用来构建更准确的回归树；

–也可以用来估计组合预测器的推广误差(generalization error)。

Bagging方法

Bagging 是bootstrap aggregating的缩写

它指的是利用bootstrap 抽样的方法对训练集抽样，得到一系列新的训练集，对每个训练集构建一个预测器，最后组合所有的预测器得到最终的预测模型。

对于分类问题，最终的预测模型是所有基预测器“投票”的结果。

对于回归问题，最终的预测模型是所有基预测器“平均”的结果。

基预测器：我的理解是第一次预测产生的模型，称为最初的预测器

例如组合的是一棵树（基预测器），那么得到最终的预测模型会变比开始要稳定；如果基预测器组合的是k近邻方法（自身本来就相对稳定的方法），那么得到最终的预测模型提升肯定不会高。

分类问题的bagging方法

设训练样本集合L为$((x_n,y_n),n = 1,2,…,N)$其中$x_n$为p 维向量，是预测变量；$y_n$为因变量，是取值$(1,2,…,J)$的分类变量。

对此数据集，我们可以构建一棵决策树$H_B(x,L)$(也可以使用其它基分类器)来预测y。

假设我们有一系列与L有同样分布的训练集${ L_m,m = 1,2,…,M}$，每个训练集$L_m$都包含N个独立样本。因此我们可以构建M棵决策树$H_m(x,L_m)$，我们的目的是组合这M棵树得到最终分类器$H_{agg}$，以提高预测精度。

一种自然而然可以想到的组合方法是“投票”(voting)。令 $N_j = \sum_{m=1}^{M}(I(H_m(x,L_m) = j))$

其中$I(.)$为示性函数，在$H_m(x,L_m) = j$时取值为1，其它情况取值为0。那么$N_j$表示所有M棵树预测x属于类$j$的总个数；则$H_{agg}(x) = arg max_jN_j$，即最终组合的分类器$H_{agg}$预测x属于使得$N_j$取最大值的$j$ 。

通常我们只有一个训练样本集合L，我们如何得到与其具有相同分布的训练集$L_m$呢？答案是对L进行Bootstrap 抽样。即对$((x_n,y_n),n = 1,2,…,N)$中N个样本点进行概率为1/N的等概率有放回的抽样，样本量为N。通过这样的抽样方法得到的最终组合分类器$H_{agg}$记为$H_B$，该预测方法称为bagging预测方法。

综上所述，分类问题的Bagging算法如下：

(1) $m = 1,2,…,M$

对L进行Bootstrap 抽样，得到样本量为N的训练样本集$L_m$，对$L_m$构建分类器(决策树)$H_m(x,L_m)$

(2) 组合M棵决策树得到最终分类器$H_B$，$H_B$对x的预测为：$argmax_jN_j$，即使得$N_j$取最大值的$j$。

其中 $N_j = \sum_{m=1}^{M}(I(H_m(x,L_m) = j))$ ，$I(.)$为示性函数。

注：回归问题的Bagging算法如下：

(1) $m = 1,2,…,M$

对L进行Bootstrap 抽样，得到样本量为N的训练样本集$L_m$，对$L_m$构建回归(回归树)$f_m(x,L_m)$

(2) 组合M棵决策树得到最终分类器$F_B$，$F_B$对x的预测为：

$F_B(x) = \sum_{m=1}^{M}(f_m(x,L_m))/M$

一些讨论

可以看到，对于不稳定的基预测器(比如说决策树)，使用bagging算法虽然我们失去了一个简单的可解释的树型结构，但是却大大提高了预测的准确度。

但是它也有局限性，我们在应用该算法的时候应该注意以下几点。如果预测结果很糟，那么bagging方法还能将结果变好吗？

如分类的结果都在0~0.5附近时，bagging甚至会让结果更加糟糕。

Bagging算法对于基预测器不稳定的情况很有作用，对于稳定的基预测器，bagging并不有效。

在分类问题的bagging 算法中我们进行bootstrap抽样50次，即M=50，在回归问题中M=25。这并不表示25或者50是充分的，也不表示其是必要的，只是比较合理的。

对于waveform数据集我们分别对M=10,25, 50和100进行了计算。可以看到在M=25之后，分类误差的提高已经并不明显。且M过大时，会将原始训练集的数据过多得使用在分类器上，产生过拟合问题（不确定是不是这个原因），总之不好。

	CART	Bagging M=10	M=25	M=50	M=100
错分率	29.5	23.1	21.8	20.7	21.1

Breiman建议对于回归问题的M值可以取得小一些，对于分类问题，尤其是y的类别比较多的时候，M的取值应该相应的大一些。

M取值的大小对于bagging CART影响并不明显，因为相对来讲构建CART决策树的时间比较快。但是对于神经网络算法，因为其耗时较长，所以如果M取值很大的话，通常需要很久才能得到结果。

注：M在实战中就多做几个，看看，选合适的。

每次进行bootstrap抽样的时候，我们选择的样本量相等于原始训练集的样本量。因为bootstrap是有放回的重复抽样，所以有些样本点被抽中的次数超过一次，有些样本点没有被抽中。

根据bootstrap抽样的理论，当样本量为时，大约有37%的样本点没有被抽中。增加bootstrap抽样样本量的个数(我们知道，按照bootstrap抽样技术，一般是按照等于原始数据集的样本量进行抽样，但从理论上讲，bootstrap抽样的样本量既可以大于又可以小于)，是否可以提高bagging算法的精度呢？

对这个问题的经验回答是否定的，当提高bootstrap抽样样本量的个数至2后，大约有14%的样本点没有被抽中，但是bagging算法的精度并没有提高。

如果从偏差方差分解的角度理解bagging算法，它可以提高不稳定基预测器的预测精度，实质上是减小了预测的方差(variance)，但并没有降低偏差(bias)。

从这个角度出发，Breiman(2001)提出了迭代(iterated) bagging算法同时减小预测的偏差及方差。

Breiman, Leo (2001a), Using Iterated Bagging to Debias Regressions, Machine Learning, 45, 261-277

Buhlmann 和 Yu (2002)进一步从理论上探讨了bagging方法对偏差及方差的降低，提出了subbagging算法，与bagging方法相比，它有相同的预测精度，但却可以大大节省计算时间。这人厉害。

Adaboost算法

相较于bagging，更加精细，更好。

具体步骤如下：

(1) m=1，以bootstrap方法(即等概率$p_1(n)=1/N$有放回重复抽样)对训练样本集$L{(x_n,y_n), n=1,…,N}$抽样得到新的训练集$L_1$，样本量为N。

对$L_1$构建决策树$H_1(x,L_1)$。应用$H_1(x,L_1)$预测训练集L中所有样本点$(x_n,y_n), n=1,…,N$，如果$H_1$对$(x_n,y_n)$预测错误，

令$d_1(n)=1$，否则$d_1(n)=0$。d_1(n)就是预测正误标记，对了就是0，错了就是1.

计算:

$\epsilon_1 = \sum_{n}p_1(n)d_1(n);$ $\beta_1 = (1-\epsilon_1)/\epsilon_1;$$ 先理解为正确和错误的比重 $$C_1 = log(\beta_1)$

(2) 对于m=2,…,M

更新第m次抽样概率为

$p_m(n) = p_{m-1}(n)\beta_{m-1}^{d_{m-1}(n)}/\sum_{n}p_{m-1}(n) \beta_{m-1}^{d_{m-1}(n)}$

以概率$p_m(n)$对训练集L进行有放回重复抽样得到新的训练集$L_m$，并对$L_m$构建决策树$H_m(x,L_m)$

应用$H_m(x,L_m)$预测训练集L中所有样本点$(x_n,y_n), n=1,…,N$，如果$H_m$对$(x_n,y_n)$预测错误，令$d_m(n)=1$，否则$d_m(n)=0$。

计算:

$\epsilon_m = \sum_{n}p_m(n)d_m(n);$ $\beta_m = (1-\epsilon_m)/\epsilon_m;$$ 先理解为正确和错误的比重 $$C_m = log(\beta_m)$

(3) 计算$W_m=C_m/\sum_{m}C_m$，（类似权重）

组合M棵决策树得到最终分类器$H_A (x)$ ，使得

$H_A (x) = arg max_{y∈(1,2,...,K)}(\sum_{m=1}^{M}W_mI(h_B(x,L_m)=y))$

其中$I(.) $为示性函数。

这个判别是一个递进的过程，是统计可加模型。

现在最流行的是XGBboost

关于决策树的一些说明

1.二叉树还是多叉树

多叉树经常导致数据被分到每个节点，没有足够的数据进行后续的分枝。多叉树可以通过多层二叉树实现，建议使用二叉树。

多个水平如何二分叉：有一些专门的方法进行选择。自变量多水平，有时也可以当作连续变化（ordered var）

2.单棵树构建的探讨

ID3是最早的，后来又经历商业包装，出现了其他算法C4.0、C5.0等

3.缺失值的处理

删除、替代、保留：保留方法很重要，在决策树这里有很好的效果。

4.算法的稳定性

如果生成基预测器的算法是不稳定的(unstable)，通过bagging得到的最终预测模型的预测精度往往会大大高于单个基预测器的预测精度。

“不稳定” ：当训练样本集合有很小的变动，由此生成的预测器有很大的变化。

不稳定的算法: 决策树，神经网络，MARS (multivariate splines)，和子集回归(subset regression)等等；

稳定的算法:岭回归(ridge regression)，最近邻方法(K-nearest neighbor)，和线性判别方法(Linear discriminate)等等。

（未完

本文链接： https://konelane.github.io/2019/05/07/190507decisiontree/

-- EOF --

转载请注明出处署名-非商业性使用-禁止演绎 3.0 国际（CC BY-NC-ND 3.0）

￥^￥请氦核牛饮一盒奶~suki

打赏