周志华西瓜书学习笔记
2023.12 二周目补充版
加粗和高亮是重点和我自己的理解
二周目心得：不好好学习贪图一时享乐欠下的债以后都是要还的
基本流程
一棵决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。示意图如下
生成是一个递归过程，四种情况会导致递归返回：
- 当前结点包含的样本全属于同一类别，无需划分 => 比如现在的样本类别都是好瓜
- 当前属性集为空，无法划分 => 没有属性 => 标记为叶结点，并将其类别设定为该结点所含样本最多的类别（当前结点的后验分布 ）
- 所有样本在所有属性上取值相同，无法划分 => 当前node所包含的样本集在所有属性 $a_i \in A $ 上的值都相同，比如色泽、根蒂、敲声 三个属性值都一样 => 标记为叶结点，并将其类别设定为该结点所含样本最多的类别（当前结点的后验分布 ）
- 当前结点包含的样本集合为空，不能划分 => 标记为叶结点，将其类别设定为其父结点所含样本最多的类别（把父节点的样本分布作为当前结点的先验分布）
划分选择
随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高。
本章节记录了几种选择最优化分属性 $a^{*}$ （纯度）的方法
信息增益 => ID3决策树
定义
用信息熵来衡量样本集合纯度。若当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k (k = 1, 2, …, \mid \mathcal{Y} \mid)$，对于上面西瓜的例子 $|\mathcal{Y}| = 2$（好瓜和坏瓜两种），则：
$$Ent(D) = - \sum \limits _ {k=1} ^ {|\mathcal{Y}|} p_k log_2 p_k$$
$Ent(D)$ 的值越小，则 $D$ 的纯度越高，最小值为0，最大值为 $log_2|\mathcal{Y}|$
当每个类别出现的概率相等时，即 $p_k = \frac{1}{|\mathcal{Y}|}$时，$Ent(D) = -\sum \frac{1}{|\mathcal{Y}|} log_2(\frac{1}{|\mathcal{Y}|}) = - |\mathcal{Y}| \times (\frac{1}{|\mathcal{Y}|} log_2(\frac{1}{|\mathcal{Y}|})) = -log_2(\frac{1}{|\mathcal{Y}|}) = log_2|\mathcal{Y}|$
假设离散属性 $a$ 有 $V$ 个取值 ${a _1, a_2, …, a_V}$ ，使用其来对样本进行划分，则会产生 $V$ 个结点，其中第 $V$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a_v$ 的样本，记 为 $D_v$，给每个子节点赋予权重 $\frac{|D_v|}{|D|}$ （即样本数越多的分支结点的影响越大）。因此属性 $a$ 对样本集 $D$ 进行划分所获得的“信息增益”为：
$$Gain(D,a) = Ent(D) - \sum \limits _{v=1} ^{V} \frac{|D_v|}{|D|} Ent(D_v)$$
为当前的每个划分离散值对应的样本子集信息熵，划分得到的信息熵和越小，划分后的纯度越大，原来的值减去新的划分和得到的值越大
取 $a_* = arg _{a \in A} max(Gain(D,a))$ 作为标准来挑选最优划分属性 => ID3决策树学习算法
举例
这是书上举的例子，很好理解且一定要理解：
增益率 => C4.5决策树
信息增益准则对可取值数目较多的属性有所偏好
增益率准则对可取值数目较少的属性有所偏好
增益率定义：
$$Gain_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}$$
$$IV(a) = -\sum \limits _{v=1} ^{V} \frac{|D_v|}{|D|} log_2 \frac{|D_v|}{|D|}$$
$IV(a)$ 为属性a的固有值，属性a的可能取值数目越多(即V越大)，则 IV(a)的值通常会越大。
基尼指数 => CART决策树
纯度用基尼值来度量
$$Gini(D) = \sum \limits _{k=1} ^{|\mathcal{Y}|} \sum \limits _{k’≠k} p _k p _{k’} = 1 - \sum \limits _{k=1} ^{|\mathcal{Y}|} p _k ^2$$
$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此 $Gini(D)$ 越小，则数据集 $D$ 的纯度越高。
基尼指数定义：
$$Gini _ index(D, a) = \sum \limits _{v=1} ^{V} \frac{|D_v|}{|D|} Gini(D_v)$$
在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性
$$a _* = arg _{a \in A} min(Gini(D, a))$$
剪枝处理
为了应付过拟合，提升泛化能力。基本策略有 “预剪枝” (prepruning)和 “后剪枝” (postpruning)
预剪枝
在每次划分前验证划分后精度是否会下降，若会下降则不进行此次划分。
有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；还可能会带来欠拟合的风险
后剪枝
先生成一颗完整的树再进行剪枝，能够保留更多的分支，欠拟合的风险比较小，泛化性能往往优于预剪枝决策树。
但存在的问题是要自顶向下生成一棵树，再自底向上进行剪枝，开销会特别大。
连续与缺失值
连续属性的可取值数目不再有限，不能直接根据连续属性的可取值来对结点进行划分 => 连续属性离散化技术
二分法 => C4.5决策树
定义
给定样本集 $D$ 和连续属性 $a$，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为 ${ a^1, a^2,\dots,a^n }$。基于划分点 $t$ 可以将 $D$ 分为子集 $D _{t} ^{-}$ 和 $D _{t} ^{+}$，表示不大于和大于 $t$，左闭右开。因此在区间 $[a^{i}, a^{i+1})$ 中取任意值所产生的划分结果相同，对连续属性 $a$ ，我们可以考察包含 $n-1$ 个元素的候选划分点集合，把该区间的中点作为候选划分点，然后像离散属性值一样来考察划分点，选取最优的划分
$$T_a = { \frac{a^{i} + a^{i+1}}{2} | i \leq i \leq n-1 }$$
找出（一个个算）使得 $Gain(D, a)$ 取得最大值的划分点 $t$：
$$Gain(D,a) = \max \limits _{t \in T_a} Gain(D, a, t) \ = \max \limits _{t \in T_a} Ent(D) - \sum \limits _{\lambda \in { -, + }} \frac{|D _{\lambda} ^{t}|}{|D|} Ent(D _{\lambda} ^{t})$$
举例
同样上个例子：
缺失值处理
定义
符号说明（看得明白）：
- $\widetilde{D}$ 表示 $D$ 在属性 $a$ 上 没有缺失值的样本子集，意思就是对于某个属性 $a$ 我们把这一列没有缺失值的拿出来打包成一个集合
- 属性 $a$ 有 $V$ 个取值，${ a_1, a_2, \dots , a_V }$ ，$\widetilde{D} ^v$ 表示在属性a上取值为 $a ^v$的样本子集，属性a有6个取值，从小到大排序，第五个的值为3.78，把所有在a上取值为3.78的样本都取出来，这样的集合就叫做 $\widetilde{D} ^5$，它们在a上的取值都是 $a ^5 = 3.78$
- $\widetilde{D} _k$ 表示 $\widetilde{D}$ 中属于第 $k$ 类 $(k=1,2, \dots, |\mathcal{Y}|)$ 的样本子集，第一类是好瓜，第二类是坏瓜诸如此类
- $\widetilde{D} = \bigcup ^{|\mathcal{Y}|} _{k=1} \widetilde{D} _k$，$\widetilde{D} = \bigcup ^{V} _{v=1} \widetilde{D} ^v$
从上面内容可以进行新的定义（注意各自的分母），对于每个样本 $x$ 我们赋予一个权重$\omega _x$：
$$\rho = \frac{\sum _{x \in \widetilde{D}} \omega _x}{\sum _{x \in D} \omega _x}$$
$$\widetilde{p} _k = \frac{\sum _{x \in \widetilde{D} _k} \omega _x}{\sum _{x \in \widetilde{D}} \omega _x} \space (1 \leq k \leq |\mathcal{Y}|)$$
$$\widetilde{r} _v = \frac{\sum _{x \in \widetilde{D} ^v} \omega _x}{\sum _{x \in \widetilde{D}} \omega _x} \space (1 \leq v \leq V)$$
$\rho$ 表示无缺失值样本所占的比例，$\widetilde{p} _k$ 表示无缺失值样本中
第 $k$ 类所占的比例，$\widetilde{r} _v$ 则表示无缺失值样本中在属性a上取值为 $a ^v$ 的样本所占的比例。
根据信息熵公式：
$$Ent(\widetilde{D}) = - \sum \limits _{k=1} ^{|\mathcal{Y}|} \widetilde{p} _k log _2 \widetilde{p} _k$$
可以得到信息增益：
$$Gain(D, a) = \rho \times Gain(\widetilde{D}, a) \ = \rho \times (Ent(\widetilde{D}) - \sum \limits _{v=1} ^{V} \widetilde{r} _v Ent(\widetilde{D} ^v))$$
算出每个属性的信息增益，然后选择信息增益最大的属性作为划分属性
举例
同样上个例子
多变量决策树
把每个属性视为坐标空间中的一个坐标轴，则 d 个属性描述的样本就对应了 d 维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界
多变量决策树希望做的事情是把平行的轴变成倾斜的轴，非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试，每个非叶结点是一个形如 $\sum _{i=1} ^{d} w _i a _i = t$ 的线性分类器，$w_i$ 是属性 $a _i$ 的权重，$w _i$ 和 $t$ 可以在该结点所含的样本集和属性集上学得。=> 建立一个线性分类器而不是进行最优属性划分
