吃瓜教程|Datawhale-10月（3）

决策树

基本流程

基于树结构来进行决策。

一般一颗决策树只包含一个根结点、若干个内部结点和若干个叶结点。

其中叶结点对应决策结果，其他的每个结点对应一个属性测试，从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一颗泛化能力强，即处理未见实例能力强的决策树。

逻辑角度：一堆 if else 语句的组合

几何角度：根据某种准则划分特征空间

最终目的：将样本越分越“纯”

#输入：训练集D = {(x_1,y_1),(x_1,y_1),...,(x_m,y_m)};
#	  属性集A = {a_1,a_2,...,a_d}.
#过程：（递归过程）
'''
TreeGenerate(D,A):
	生成结点node
    if D中样本全属于C:
        node标记为C类叶结点
        return
    if A = NULL or D在A上取值相同:
    	node标记为叶结点，类别为D中样本最多的类
    	return
    else:
    	从A中选择最优划分属性a_*
    	for a_*的每一个值a_*_v:
    		为node生成一个分支
    		令Dv表示在a_*上取值为a_*_v的样本子集
    		if Dv = NULL:
    			将分支结点记为叶结点，类别为D中样本最多的类
    			return
    		else：
    			以TreeGenerate(Dv,A/{a_*})为分支结点
    return
'''

划分选择

自信息：

\[I(X)=-\log_{b}{p(x)} \]

当 b = 2 时单位为 bit ，当 b = e 时单位为 nat

配合下边的式子，也可写成：

\[I(D)=-\log_{b}{p_{k}} \]

信息熵（自信息的期望）：度量样本集合纯度最常用的一种指标。

假设当前样本 D 中的第 k 类样本所占比例为 \(p_{k}(k=1,2,...,|\mathcal{Y}|)\) ，则 D 的信息熵定义为：

\[H(D)=E[I(D)]=\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k} \]

\(\operatorname{Ent}(D)\) 的值越小，则 D 的纯度越高。

计算信息樀时约定：若 \(p_{k}=0\) ，则 \(p_{k} \log _{b} p_{k}=0\) 。当 \(X\) 的某个取值的概率为 1 时信息熵最小（最确定，样本集合纯度最高），其值为 0 ；当 \(X\) 的各个取值的概率均等时信息樀最大（最不确定），其值为 \(\log _{b}|D|\) ， 其中 \(|D|\) 表示 \(D\) 可能取值的个数。

条件熵： Y 的信息熵关于概率分布 X 的期望

在已知 X 后 Y 的不确定性

\[H(Y|X)=\sum_{x}p(x)H(Y|X=x) \]

从单个属性（特征） a 的角度来看，假设其可能取值为 \(\{a^{1},a^{2},...,a^{V}\}\) ， \(D^{v}\) 表示属性 a 取值为 \(a^{v}\in\{a^{1},a^{2},...,a^{V}\}\) 的样本集合， \(\frac{|D^{v}|}{D}\) 表示占比，那么在已知属性 a 的取值后，样本集合 D 的条件熵为

\[\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) \]

信息增益：在已知属性（特征）a 的取值后 y 的不确定性减少的量, 也即纯度的提升（信息熵 - 条件熵）

\[\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) \]

ID3决策树

以信息增益为准则来选择划分属性的决策树（以信息增益最大的属性作为划分属性）

\[a_{*}=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a) \]

C4.5决策树

信息增益准则对可能取值数目过多的属性有所偏好（如标号，但是这个是因为每个取值所包含的样本太少），为了减少这种偏好带来的不利影响，C4.5决策树使用增益率代替信息增益。

增益率

\[\operatorname{Gain_{-}\operatorname{ratio}}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)} \]

其中

\[\operatorname{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|} \]

称为属性 \(a\) 的”固有值”， \(a\) 的可能取值个数 \(V\) 越大，通常其固有值 \(\operatorname{IV}(a)\) 也越大。但是, 增益率对可能取值数目较少的属性有所偏好。

因此，C4.5并未完全使用增益率代替信息增益，而是先选出信息增益高于平均水平的属性，在从中选择增益率最高的。

CART决策树

基尼值

从样本集合 \(D\) 中随机抽取两个样本, 其类别标记不一致的概率。因此, 基尼值越小，碰到异类的概率就越小, 纯度自然就越高。

\[\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=\sum_{k=1}^{|\mathcal{Y}|} p_{k}\left(1-p_{k}\right) \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned} \]

基尼指数

属性 a 的基尼指数：

\[\operatorname{Gini_{-}\operatorname{index}}(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right) \]

CART决策树选择基尼指数最小的属性作为最优化分属性

\[a_{*}=\underset{a \in A}{\arg \text { min }} \operatorname{Gini_{-}\operatorname{index}}(D, a) \]

CART决策树的实际构造算法如下:

• 首先，对每个属性 \(a\) 的每个可能取值 \(v\) ，将数据集 \(D\) 分为 \(a=v\) 和 \(a \neq v\) 两部分来计算基尼指数，即

  \[\operatorname{Gini_{-}\operatorname{index}}(D, a)=\frac{\left|D^{a=v}\right|}{|D|} \operatorname{Gini}\left(D^{a=v}\right)+\frac{\left|D^{a \neq v}\right|}{|D|} \operatorname{Gini}\left(D^{a \neq v}\right) \]

• 然后，选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点

• 最后，重复以上两步，直至满足停止条件

剪枝处理

为了防止过拟合，主要有预剪枝和后剪枝。

• 预剪枝：在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
• 后剪枝：先生成一棵完整的决策树，再自底向上地对叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则替换。

判断泛化性能提升地方法：留出法。即预留一部分数据作为验证集进行评估。

后剪枝欠拟合风险很小，泛化性一般优于预剪枝，但是时间开销大。

连续与缺失值

连续值处理

目前我们在讨论的都是离散型属性，当遇到连续属性时，可对其进行离散化处理。

最简单的是使用二分法。就是以每两个相邻取值的中点作为划分点

例子参见南瓜书

缺失值处理

第一种情况，属性值缺失。

给定训练集 \(D\) 和属性 a ，令 \(\tilde{D}\) 表示 \(D\) 中属性 a 上没有缺失值的样本子集。

假设属性 a 有 V 个可取值 \(\{a^{1},a^{2},...,a^{V}\}\) ，令 \(\tilde{D}^{v}\) 表示 \(\tilde{D}\) 中在属性 a 上取值为 \(a^{v}\) 地样本子集， \(\tilde{D}_{k}\) 表示 \(\tilde{D}\) 中属于第 k 类的样本子集。假定我们为每个样本 x 赋予一个权重 \(w_{x}\) ，并定义：

\[\rho=\frac{\sum_{x \in \tilde{D}} w_{x}}{\sum_{x \in D} w_{x}} \]

\[\tilde{p}_{k}=\frac{\sum_{x \in \tilde{D}_{k}} w_{x}}{\sum_{x \in \widetilde{D}} w_{x}} \quad(1 \leq \mathrm{k} \leq|y|) \\ \]

\[\tilde{r}_{v}=\frac{\sum_{x \in \tilde{D}}^{v} w_{x}}{\sum_{x \in \widetilde{D}} w_{x}} \quad(1 \leq \mathrm{v} \leq \mathrm{V}) \]

对于属性 a， \(\rho\) 表示无缺失值样本所占的比例， \(\tilde{p}_{k}\) 表示无缺失值样本中第 k 类所占的比例， \(\tilde{r}_{v}\) 则表示无缺失值样本中在属性 a 上取值为 \(a^{v}\) 的样本所占的比例。

因此，我们将信息增益计算式推广为：

\[\begin{array}{l} \operatorname{Gain}(D, a)=\rho \times \operatorname{Gain}(\tilde{D}, a)=\rho \times\left(\operatorname{Ent}(\tilde{D})-\sum_{v=1}^{V} \tilde{r}_{v} \operatorname{Ent}\left(\tilde{D}^{v}\right)\right) \\ \operatorname{Ent}(\tilde{D})=-\sum_{k=1}^{|y|} \tilde{p}_{k} \log _{2} \tilde{p}_{k} \end{array} \]

第二种情况，给定划分属性，样本在该属性上的值缺失。

• 若样本 \(\boldsymbol{x}\) 在划分属性 \(a\) 上的取值已知, 则将 \(\boldsymbol{x}\) 划入与其取值对应的子结 点, 且样本权值在子结点中保持为 \(w_{x}\)
• 若样本 \(\boldsymbol{x}\) 在划分属性 \(a\) 上的取值末知, 则将 \(\boldsymbol{x}\) 同时划入所有子结点, 且样本权值在与属性值 \(a^{v}\) 对应的子结点中调整为 \(\tilde{r}_{v} \cdot w_{x}\) (直观来看, 相 当于让同一个样本以不同概率划入不同的子结点中去)

多变量决策树

决策树生成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得更好的近似。

有很多时候，斜着划分能让模型更加简化，多变量决策树便是如此。

在多变量决策树中非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试。这使得在学习过程中不是为每个非叶结点寻找一个最优划分属性，二是试图建立一个合适的线性分类器。