数学建模(七)——决策树

　

决策树模型

数学建模系列(七)——决策树

    在之前看决策树(被一个学长无脑乱讲)的时候，没觉得他有这么强大，被蒙骗了很长时间，直到读了周志华老师的西瓜书，才发现决策树其实相当强大，趁此机会好好整理，弥补当初的无知。本文中用到有关西瓜的例子均来源于周志华老师机器学习那本书。

1." role="presentation" style="position: relative;">1.$1.$ 决策树

    首先介绍下问题背景以及决策树的强大之处。先引入一个问题，第一问：今天天气怎么样？得到一个判断是晴天，也有了第一个决策出去玩。第二问：问问自己有没有女朋友，得到一个判断有，也就产生了第二个决策，要去找她。第三问：问问她想不想去看电影，得到一个回答愿意，也就有了第三个决策，一起看电影。如果说第二个问题的判断是没有女朋友，那么也不用考虑第三个问题，同样这也是一种决策。

    在上面的决策中，判断都分为两种对立事件，有或者没有，去或者不去，这在数据维度是离散的；那么如果是连续值呢？比如说几点约女朋友出去，几点看电影，几点吃饭，时间一点一点流逝，显然是个连续的值，又该怎么决策？不巧的是，决策树对于离散和连续的问题都能处理，看下面的推到。

1.1" role="presentation" style="position: relative;">1.1$1.1$ 信息熵

    先看一眼信息熵的定义

Ent(D)=−∑k=1Kpklog2⁡pk" role="presentation">Ent(D)=−∑k=1Kpklog2pk$$Ent(D)=-\sum _{k=1}^K{p}_k{\log }_2{p}_k$$

    D" role="presentation" style="position: relative;">D$D$表示数据集，K" role="presentation" style="position: relative;">K$K$表示类别个数(比如第一类哺乳动物，第二类爬行动物，第三类昆虫等)，pk" role="presentation" style="position: relative;">pk$p_k$表示第k" role="presentation" style="position: relative;">k$k$类样本所占的比例。当一个数据中某一类占了绝大多数，Ent" role="presentation" style="position: relative;">Ent$Ent$的在负号的作用下会很小，也可以称数据越纯。在数据集D" role="presentation" style="position: relative;">D$D$中，所有在类别a" role="presentation" style="position: relative;">a$a$上取值为av" role="presentation" style="position: relative;">av$a^v$的记为Dv" role="presentation" style="position: relative;">Dv$D^v$，

    但是这玩意在一些情况中不能使用，假设在做一个商品推荐的问题，对用户推广的商品可以五花八门有很多的类，这样就会导致上面提到的权重|Dv|/|D|" role="presentation" style="position: relative;">|Dv|/|D|$|D^v|/|D|$偏大，显然这是符合实际情况的。

1.2" role="presentation" style="position: relative;">1.2$1.2$ 信息增益

    所以提出来一种信息增益的东西，再来看一下公式定义：

Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv)" role="presentation">Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv)$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$

    假设对于一个离散的属性有a" role="presentation" style="position: relative;">a$a$有V" role="presentation" style="position: relative;">V$V$种取值，{a1,a2,...,av}" role="presentation" style="position: relative;">{a1,a2,...,av}$\{a^1,a^2,...,a^v\}$，也就是对于物种分类有哺乳动物、爬行动物、昆虫等分类，考虑到实际情况中某些属性会有缺失值的情况，所以不同分支节点所包含的样本数量也是不同的，给分支节点赋予权重|Dv|/|D|" role="presentation" style="position: relative;">|Dv|/|D|$|D^v|/|D|$，也就是分支节点的数据越多，权重越大，其实这个道理很简单，给出的数据越多，就越能判断你更加详细的信息。对了，分支节点可以理解为不同的类，比如第一类是动物类别，哺乳、爬行等，第二类是饮食习惯，杂食、肉食等，这两个类就是分支节点。来个图形象一下：

    看下面的数据集：

    再来看下计算过程，真的懒得自己写了

    注：在以纹理为基准向下筛选时，比如计算纹理清晰下面的节点，此时的数据集只有纹理清晰，而纹理模糊的数据集不考虑在内。比如纹理清晰下面，根蒂的信息增益最大，纹理模糊下面，触感的信息增益最大。这也就是注明的ID3算法来构造决策树的方法。

1.3" role="presentation" style="position: relative;">1.3$1.3$ 增益率：

    同样信息增益也有个缺点，当某一类的取值很多时，回顾一下信息增益的公式，信息熵的取值会很小，信息增益会变大，也就是会按类别最多的属性进行划分，然而这种效果并不好，比如，在数据集中，如果编号是一个类，显而易见的会以编号进行划分，直接得到哪个编号的瓜好吃哪个不好吃，显然没有任何意义。所以又提出来的增益率，传说中的C4.5构建决策树就是用的增益率。先来看个公式定义。

Drainradio(D,a)=Gain(D,a)IV(a)" role="presentation">Drainradio(D,a)=Gain(D,a)IV(a)$$Drai{n}_{r}adio(D,a)=\frac{Gain(D,a)}{IV(a)}$$

，

IV(a)=−∑v=1V|Dv||D|log2⁡|Dv||D|" role="presentation">IV(a)=−∑v=1V|Dv||D|log2|Dv||D|$$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$

IV(a)" role="presentation" style="position: relative;">IV(a)$IV(a)$称为属性a" role="presentation" style="position: relative;">a$a$的固有值，属性a" role="presentation" style="position: relative;">a$a$的取值种类越多，IV(a)" role="presentation" style="position: relative;">IV(a)$IV(a)$的值就越大，

    上面那个增益率的鬼公式就是在信息增益的基础上除以固有属性来消除类别特别多的影响。类别越多，固有属性会偏大，也就是，增益率这个东西会对一个属性中取值少的有所偏向，所以增益率不会直接选择最大的属性直接划分，而是先选择信息增益高于平均水平的，在选择增益率最大的进行划分，分两步完成。第一步信息增益选择出合适的，但可能有类别特别多的，第二部增益率把类别特别多但不是最好的给筛除掉。

1.4" role="presentation" style="position: relative;">1.4$1.4$ 基尼指数：

    基尼指数可以用于选择划分特征，公式表示为

Gini(D)=∑k=1K∑k′≠kpkpk′=1−∑k=1Kpk2" role="presentation">Gini(D)=∑k=1K∑k′≠kpkp′k=1−∑k=1Kp2k$$Gini(D)=\sum _{k=1}^K\sum _{k^{\prime }\ne k}{p}_k{p}_k^{\prime }=1-\sum _{k=1}^K{p}_k^2$$

它反映了随机从数据集中抽取两个样本，其类别标记不一致的概率，也就是基尼指数越小，数据集的纯度越高，属性a" role="presentation" style="position: relative;">a$a$的基尼指数的定义为

Gini_index(D,a)=∑v=1V|Dv||D|Gini(Dv)" role="presentation">Gini_index(D,a)=∑v=1V|Dv||D|Gini(Dv)$$Gini\mathrm{\_}index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$

    因此在数据集中，选择基尼指数最小的属性进行划分。在sklearn的官网中，只提供了基尼指数的决策树实现，并没有ID3和C4.5的实现。sklearn有关决策树回归与分类的实现

    对了，前面一直说的分类，回归问题是预测输出值是0.1，是0.2还是0.3的那种，解决回归问题也是用的类似损失函数的东西，使用了均方误差函数或者平均误差函数，让这个函数最小来达到划分决策树的目的。Nm" role="presentation" style="position: relative;">Nm$N_m$是样本，H(Xm)" role="presentation" style="position: relative;">H(Xm)$H(X_m)$是误差函数。

    均方误差：cm=1Nm∑i∈NmyiH(Xm)=1Nm∑i∈Nm(yi−cm)2" role="presentation" style="position: relative;">cm=1Nm∑i∈NmyiH(Xm)=1Nm∑i∈Nm(yi−cm)2$c_m=\frac{1}{N_m}\sum _{i\in N_m}{y}_{i}H(X_m)=\frac{1}{N_m}\sum _{i\in N_m}(y_i-c_m{)}^2$

    平均误差：ym¯=1Nm∑i∈NmyiH(Xm)=1Nm∑i∈Nm|yi−ym¯|" role="presentation" style="position: relative;">ym¯=1Nm∑i∈NmyiH(Xm)=1Nm∑i∈Nm|yi−ym¯|$\overline{y_m}=\frac{1}{N_m}\sum _{i\in N_m}{y}_{i}H(X_m)=\frac{1}{N_m}\sum _{i\in N_m}|y_i-\overline{y_m}|$

1.5" role="presentation" style="position: relative;">1.5$1.5$ 剪枝处理：

    首先剪枝的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，也就导致了过拟合。决策树的剪枝策略最基本的有两种：预剪枝和后剪枝。

1.5.1" role="presentation" style="position: relative;">1.5.1$\mathrm{1.5.1}$ 预剪枝处理：

    预剪枝：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点，来个图形象一下，精度是怎么计算的呢，很简单，划分对的个数除以总个数，比如划分了10个，有5个是对的，精度就是50%。

1.5.2" role="presentation" style="position: relative;">1.5.2$\mathrm{1.5.2}$ 后剪枝处理：

    后剪枝：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点，再来个图形象一下，精度计算同上。

    总结一下，对于两种剪枝方式，后剪枝更像是全局寻优，全部的路线都有了，看看哪个更好，预剪枝更像是局部寻优，一步一步的走，可能为了局优而屏蔽了全优，所以预剪枝欠拟合的风险大，但是后剪枝的计算量更大。

    下面可能及时决策树的强大之处，不管数据是连续还是离散还是缺失，都能处理，前面介绍的都是离散值的处理，下面介绍连续值和缺失值的处理。

1.6" role="presentation" style="position: relative;">1.6$1.6$ 连续值处理：

    看上面数据集中的密度和含糖率，显然无法直接划分为具体的类。如何把这些连续值给离散化呢，介绍下C4.5中的处理方法。首先对连续值进行排序，选取两个连续的属性值ai,ai+1" role="presentation" style="position: relative;">ai,ai+1$a^i,a^{i+1}$，以其中点作为划分点，小于的化为一类，大于的化为另一类，对信息增益的公式稍加改造，

Gain(D,a,t)=maxEnt(D)−∑|Dt|DEnt(Dt)" role="presentation">Gain(D,a,t)=maxEnt(D)−∑|Dt|DEnt(Dt)$$Gain(D,a,t)=\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{E}\mathrm{n}\mathrm{t}(D)-\sum \frac{|D_t|}{D}\mathrm{E}\mathrm{n}\mathrm{t}(D_t)$$

，t" role="presentation" style="position: relative;">t$t$为划分点。也就是找到最大的划分点即可，然后进行分类，比如下图的密度。

1.7" role="presentation" style="position: relative;">1.7$1.7$ 缺失值处理：

    再看一个数据集，可以看图中红框的位置，数据没了，又该怎么处理呢？

    首先对数据集进行划分，分为没有缺失数据的数据集D~" role="presentation" style="position: relative;">D˜$\tilde{D}$，对每一个样本x" role="presentation" style="position: relative;">x$x$赋予权重wx" role="presentation" style="position: relative;">wx$w_x$，定义三个参数：

ρ=∑x∈D~wx∑x∈Dwx" role="presentation">ρ=∑x∈D˜wx∑x∈Dwx$$\rho =\frac{\sum _{x\in \tilde{D}}{w}_x}{\sum _{x\in D}{w}_x}$$

p~k=∑x∈D~kwx∑x∈D~wx" role="presentation">p˜k=∑x∈D˜kwx∑x∈D˜wx$${\tilde{p}}_k=\frac{\sum _{x\in {\tilde{D}}_k}{w}_x}{\sum _{x\in \tilde{D}}{w}_x}$$

r~v=∑x∈D~vwx∑x∈D~wx" role="presentation">r˜v=∑x∈D˜vwx∑x∈D˜wx$${\tilde{r}}_v=\frac{\sum _{x\in {\tilde{D}}^v}{w}_x}{\sum _{x\in \tilde{D}}{w}_x}$$

" role="presentation">$$$$

    直观的看这三个参数，对于属性a" role="presentation" style="position: relative;">a$a$，ρ" role="presentation" style="position: relative;">ρ$\rho$表示无确实样本所占比例，p~l" role="presentation" style="position: relative;">p˜l${\tilde{p}}_l$表示无确实样本中k" role="presentation" style="position: relative;">k$k$类所占的比例，最后那个参数表示属性a" role="presentation" style="position: relative;">a$a$中某一取值所占的比例。再将信息增益的公式推广一下：

Gain(D,a)=ρ×Gain(D~,a)" role="presentation">Gain(D,a)=ρ×Gain(D˜,a)$$Gain(D,a)=\rho \times Gain(\tilde{D},a)$$

Ent(D~)=−∑k=1|γ|p~klog2⁡p~k" role="presentation">Ent(D˜)=−∑k=1|γ|p˜klog2p˜k$$Ent(\tilde{D})=-\sum _{k=1}^{|\gamma |}{\tilde{p}}_k{\log }_2{\tilde{p}}_k$$

γ" role="presentation" style="position: relative;">γ$\gamma$表示属性的个数，同理，信息率的公式同样进行更改。好了，问题解决了。

1.8" role="presentation" style="position: relative;">1.8$1.8$ 问题推广：多变量决策树

    看一个sklearn的图。

    用决策树做的鸢尾花的分类，可见分类的边界相当明显，也很好解释，一段分类对应了某个属性的取值；但在比较复杂的分类中，这种直线线段的分类效果并不很好，需要学习一个线性分类器来进行分类，这就是多变量决策树，效果如下图所示。

    实现的效果看这里。

1.9" role="presentation" style="position: relative;">1.9$1.9$ Code Time：

    目前代码只能处理类别，连续值，分类和回归，暂时不能处理缺失值，等写好程序再来贴上。

相关阅读

决策树到底是什么？

本文思想及知识来源于对李航老师的统计学习方法的拜读，加上一些自己的理解整理，感谢李航老师伟大的著作：《统计学习方法》！ 决策树是

AI产品经理必懂算法：决策树

决策树（Decision Tree）是一种以树形数据结构来展示决策规则和分类结果的模型，它是将看似无序、杂乱的已知实例，通过某种技术手段将它