决策树与随机森林

决策树

决策树概论

决策树算法以树状结构表示数据分类的结果。每个决策点实现一个具有离散输出的测试函数，记为分支。决策树即可有分类，也可以做回归。

比如有这样一个例子，

家里五个人，爷爷奶奶，妈妈，小红小明。只有明想打球，想找到谁想打球，需要一个决策树算法吧小明找出来。

graph TB;
id1[age less than 15?]--yes--->id2[male?]--yes--->Ming
id2--no--->id4[Hong]
id1--No--->id3[grandparents and mom]

所以把每一个值丢进去，总找到一个关于这个值得最终目的地，可能是一个分类值，比如grandparents and mom,也可能是一个精准的预测回归值。

以这个树为例介绍一下相关概念。

根节点(root node)：less than 15（第一层决策点）
非叶子节点(non-leaf node)：male(也就是决策点)
叶子节点(leaf node)：ming,hong(结果值)
分支(branches)：所有的yes no(代表本次决策结果).

决策树构造

训练阶段

从给定的数据集database(DB),构造出一个决策树。例如，我们为什么定less than 15而不是17？以及为什么选年龄做根节点？ blockformula_editorclass=DecisionTree(DB)

分类阶段

从根开始，按照决策树的分类属性逐层往下划分直到叶节点，获得概念（决策、分类）结果。 blockformula_editory=DecisionTree(x)

熵原理

熵原本是化学概念，形容物体内的混乱程度。当前物体是纯还是不纯？在介绍这个概念之前，先复习一下概率论知识。

---xy两个时间相互独立
为xy发生的不确定性。
几率越大，越小反之亦然

熵= 解释：假如有两个集合blockformula_editorA=\{1,2,3,4,5\} ``````blockformula_editorB=\{1,1,1,1,1\} A明显更杂乱一些，B更纯一些。这也就意味着对A来说，,而在B当中。当我们对这个大概率做一个log变化，概率越大，绝对值越小。那么这个熵值得计算就约小。所以可以用熵计算纯度。

为什么这个纯度可以和决策树联系起来呢。因为对于纯度高的集合，决策树分层起来是很快的，可能分一次就可以了，而对于熵值高的，分层起来却很麻烦。

例如基尼系数和熵值得计算方式其实是差不多的。而基尼系数正是用来反应贫富差距，也是类似一种“纯度概念”。

基尼系数:

决策树构造实例(ID3算法)

构造树的基本想法是随着树的深度增加，节点的熵值要迅速减少，熵降低的越快越好，这样我们能得到一个高度最矮的树，也就是一个最简洁的算法。例如：

没有给定任何天气信息，根据历史数据，此时我们能判断打球的概率是9/14，打不了球的概率是5/14，此时的熵为0.94。

我们有了一个14天的样本，对当天的天气有一个判断。样本显示如下。

outlook	temperature	humidity	windy	play
sunny	hot	high	FALSE	yes
sunny	hot	high	FALSE	yes
overcast	hot	high	FALSE	yes
rainy	hot	high	FALSE	yes
rainy	cool	high	FALSE	no
rainy	cool	normal	TRUE	no
rainy	cool	normal	TRUE	no
sunny	cool	normal	TRUE	no
sunny	mild	normal	TRUE	yes
sunny	mild	high	TRUE	yes
rainy	mild	high	FALSE	yes
rainy	mild	high	FALSE	yes
rainy	hot	high	FALSE	yes
rainy	hot	high	FALSE	yes

在历史中看打球与不打球的天数

plays = ['NO','YES']
days_by_play = {}
for this_play in plays:
    num = np.count_nonzero(data['Play'] == this_play)
    days_by_play[this_play] = num
days_by_play
{'NO': 5, 'YES': 9}

那么此时的熵值为

- 9 / 14 l o g_{2} 9 / 14 - 5 / 14 l o g_{2} 5 / 14 = 0.940

然后将上述4个特征注意分析，先从Outlook开始

基于天气的划分

#查看每种天气对应的天数
weathers = ['sunny','overcast','rainy']
days_by_weather = {}
for this_weather in weathers:
    num = np.count_nonzero(data['Outlook'] == this_weather)
    days_by_weather[this_weather] = num
days_by_weather
{'sunny': 5, 'overcast': 4, 'rainy': 5}

Outlook = sunny时，计算熵值为 $- \frac{3}{5} l o g_{2} \frac{3}{5} - \frac{2}{5} l o g_{2} \frac{2}{5} = 0.971$ Outlook=overcast时，熵值为0(因为已经划分好了，全部都是yes) Outlook = rainy时，熵值为0.971 其余特征分类后的每个子类的熵值计算也是类似根据统计Outlook取值分别为sunny,overcast,rainy的概率分别为$5/14 , 4/14 , 5/14 $ 那么整体分类后的熵值为，就是分类后的加权熵值为

5 / 14 * 0.971 + 4 / 14 * 0 + 5 / 14 * 0.971 = 0.693

基于温度的划分

Temperatures = ['hot','cool','mild']
days_by_temperature = {}
for this_Temperature in Temperatures:
    num = np.count_nonzero(data['Temperature'] == this_Temperature)
    days_by_temperature[this_Temperature] = num
days_by_temperature

那么我们现在还是不知道应该如何构建树，应该以天气？温度？湿度还是有风为根节点呢？方法就是计算每个划分之后的熵值然后跟原本的无背景信息时的熵值作比较。

基于天气划分，sunny是5/14，overcast是4/14，rainy是5/14.可以计算相应的熵值为0.693。
基于温度划分....
基于湿度划分....
基于有风划分....

到这里可以引入信息增溢的概念，比如，利用天气outlook进行划分之后的熵值为0.693，比原来下降了0.247，那么信息增溢就是0.247，这也是反应我们建立节点的指标。相应的我们也可以计算出温度划分、湿度划分、有无风的划分等等，这个数字我们希望越大越好，因为越大代表着熵值经过算法降低越快，样本划分的更好。

所以，之前的例子当中，为什么首先是less than 15 years?原因就是信息增溢最大

经过计算，按照天气划分信息增溢最大，所以我们按照天气分类第一层，那么怎么划分第二层呢？也是一样的逻辑，类似于一个递归问题。

c4.5算法

用信息增益来进行计算是存在bug的比如，我们新加一行id,只代表index,没有任何实际意义。但是当我们以id为划分，会发现熵值直接变成0了，也就是信息增溢最大化了，但是id这个划分明显是没有意义的。算法与之前类似，具体可以参考cdsn-机器学习. 这种情况经常发生在分类很多而每个分类下个体很少的情况。这也就是“过拟合”情况，为了追求拟合效果过分追求划分细致。所以我们引入ID3算法，通过信息增溢率来决定。

Gain\_ratio（D，a)=\frac{Gain(G,a)}{IV(a)

I V (a) = - v = 1 \sum v = V \frac{∣ D ^{v} ∣}{∣ D ∣} l o g_{2} \frac{∣ D ^{v} ∣}{∣ D ∣}

这就是C4.5算法：解决了ID3算法的问题，考虑到了自身熵。以上面的例子说明。原本以id为划分，信息增益应该是0.971，我们要计算信息增溢率，就要除以原本他自己的熵。即： $- \sum_{i = 1}^{i = 14} (- \frac{1}{1 4}) l o g \frac{1}{1 4}$ . 这个数一定是非常大的，除以它以后得到的信息增溢率一定是很小的。

评价函数

现在我们已经知道了如何构建出一颗树，但是如何评价这棵树的好坏呢，我们构建这样一个评价函数：

C (T) = t \in l e a f \sum N_{t} . H (t)

我们希望他越小越好，类似于损失函数。 t是指叶子节点，不能往下再分的节点。关于这些节点的熵值（H（t））我们是可以计算的。 $N_{t}$ 是当前叶子节点内的元素个数，也就是叶子结点的权重值。

离散化

C4.5是ID3的延伸，可以处理离散值也可以处理连续值，只要进行一个离散化处理（less than 15？）离散化区间的确定依据就是熵值大小。

决策树剪枝

我们知道了决策树如何构建，也知道了决策树的评价函数，但是我们真的按照评价函数这样做了吗？其实是没有的，因为我们想要的是一颗矮树，但是按照熵最小的思想构建出来的决策树肯定是很大的树。决策树的过拟合的风险很大，因为理论上来说可以将数据完全分的开，如果树足够大，每个叶子节点就剩下了一个数据。那么，这就会造成模型在训练集上的拟合效果很好，但是泛化能力很差，对新样本的适应能力不足。所以，对决策树进行剪枝，可以降低过拟合的风险。尤其考虑到我们的数据集本身就会因为各种原因存在各种异常值。所以剪枝是必要的。常见的剪枝方法有两个

预剪枝
后剪枝

预剪枝

在构建决策树的过程时，提前停止。变构建边剪枝。概念：预剪枝就是边建立决策时边进行剪枝的操作。在决策树生成的过程中，对每个节点在划分前向首先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶子节点 预剪枝的实现方式：限制树的深度，叶子节点个数，叶子节点的样本数，信息增益量等。

后剪枝

决策树构建好之后再进行裁剪。概念：当建立完决策树后再进行剪枝操作。后剪枝是先从训练集生成一棵完整的决策树，然后自底向上地对非叶子节点进行考察，若将该节点对应的子树替换为叶子节点能够带来决策树泛化性能的提升，将该子树替换为叶子节点。 后剪枝的实现方式：CART算法的后剪枝方法---代价复杂度算法，即CCP算法。 $T$ 表示树 $C (T)$ 表示当前损失 $α \geq 0$ 为参数或者剪枝系数，由自己确定，不同大小代表着对于剪枝与否的倾向。 $C_{α} (T)$ 表示损失函数的正则化 $α ∣ T_{l e a f} ∣$ 实际上是损失函数的正则项代价函数的基本思想：

C_{α} (T) = C (T) + α ∣ T_{l e a f} ∣

$C (T)$ 表示当前损失,实际上就是求分类后叶子节点的经验熵期望，计算方式为当前叶节点的样本数与当前叶结点的熵值的乘积。也就是说，叶子节点含有的样本数越多，那么这个分类效果就越混乱，损失值越大。参考评价函数

$α∣T_{leaf}| $是修正项，它是基于复杂度的考虑。当叶节点分裂后与不分裂的熵值相等，实际上没有进行任何分类，但是我们认为不分类的情况更好，因为，分类后树的复杂度会更高。加了修正项后，如果$ \alpha=0 $表示未剪枝的树损失更小，也就是熵更小，如果$ \alpha \to \infty $表示剪枝到根节点更好，因为叶结点的个数占了主导地位。修正项$ \alpha|T_{leaf}| $可以避免过拟合。$ \alpha$值的设置可以更好的避免出现完全树和根节点这种极短情况，所以可以避免过拟合。

随机森林 Random Forest

随机森林是决策树的延伸。决策树相当于一个大师，通过自己在数据集中学到的知识对于新的数据进行分类。随机森林就是希望构建多个决策树，希望最终的分类效果能够超过单个大师的一种算法。森林是什么呢？是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。那随机体现在哪里呢？或者随机森林具体如何构建呢？有两个方面：数据的随机性选取，以及待选特征的随机选取。

数据的随机性选取

首先，从原始的数据集中采取有放回的抽样 $（ b o o t s t r a p p i n g)$ ^[1]，构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。第二，利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果的投票，得到随机森林的输出结果了。如图，假设随机森林中有3棵子决策树，2棵子树的分类结果是A类，1棵子树的分类结果是B类，那么随机森林的分类结果就是A类。

待选特征的随机选取

就比如开头的例子，天气，湿度，是否刮风等等特征，我们怎么知道这些特征都是好特征呢？或许也像数据集一样也有“异常”值呢？与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选取最优的特征。这样能够使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。图4中，蓝色的方块代表所有可以被选择的特征，也就是待选特征。黄色的方块是分裂特征。左边是一棵决策树的特征选取过程，通过在待选特征中选取最优的分裂特征（别忘了前文提到的ID3算法，C4.5算法，CART算法等等），完成分裂。右边是一个随机森林中的子树的特征选取过程。

结合这两重随机性之后的整个过程被称为bagging.^[2]

Bootstrapping is any test or metric that uses random sampling with replacement (e.g. mimicking the sampling process), and falls under the broader class of resampling methods. Bootstrapping assigns measures of accuracy (bias, variance, confidence intervals, prediction error, etc.) to sample estimates. This technique allows estimation of the sampling distribution of almost any statistic using random sampling methods.与之相对的 ↩︎
Bagging is an approach to ensemble learning that is based on bootstrapping. Shortly, given a training set, we produce multiple different training sets (called bootstrap samples), by sampling with replacement from the original dataset. Then, for each bootstrap sample, we build a model. The results in an ensemble of models, where each model votes with the equal weight. Typically, the goal of this procedure is to reduce the variance of the model of interest (e.g. decision trees). ↩︎

本文章使用limfx的vscode插件快速发布