决策树 | Forgotten Area

基本流程

决策树（decision tree）（判定树）是一类常见的机器学习算法。主要用于对样本的分类。

决策树是基于树的结构进行决策的。

一般的，一颗决策树包含一个根节点、若干个内部节点与若干个叶结点。

叶结点：决策结果。
其他节点：属性测试。

每个结点包含的样本集合根据属性测试的结果被划分到子节点中。
根节点包含样本全集。从根节点到每个叶结点的路径对应了一个判定测试序列。

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

采取策略：分而治之（divide-and-conquer）。

伪代码如下：

输入： 训练集 $D=\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\dots,(\boldsymbol{x}_m,y_m)\};$
属性集 $A=\{a_1,a_2,\dots,a_d\}.$
过程： 函数 $TreeGenerate(D,A)$
1: 生成结点 $node$ ;
2: $\boldsymbol{if}\ \ D$ 中样本全属于同一类别 $C\ \ \boldsymbol{then}$
3: 将 $node$ 标记为 $C$ 类叶结点; $\ \boldsymbol{return}$
4: $\boldsymbol{end \ \ if}$
5: $\boldsymbol{if}\ \ A=\varnothing \ \ \boldsymbol{OR}\ \ D$ 样本在 $A$ 上取值相同 $\ \ \boldsymbol{then}$
6: 将 $node$ 标记为 $C$ 类叶结点,其类别标记为 $D$ 中样本数最多的类; $\ \boldsymbol{return}$
7: $\boldsymbol{end \ \ if}$
8: 从 $A$ 中选择最优划分属性 $a_*$ ;
9: $\boldsymbol{for}\ \ a_*$ 的每一个值 $a_*^v\ \ \boldsymbol{do}$
10: 为 $node$ 生成一个分支;令 $D_v$ 表示 $D$ 中在 $a_*$ 上取值为 $a_*^v$ 的样本子集;
11: $\boldsymbol{if}\ \ D_v$ 为空 $\ \boldsymbol{then}$
12: 将分支结点标记为叶结点,其类别标记为 $D$ 中样本最多的类; $\ \boldsymbol{return}$
13: $\boldsymbol{else}$
14: 以 $Treegenerate(D_v,A \setminus \{ a_* \})$ 为分支结点 $\quad$
15: $\boldsymbol{end \ \ if}$
16: $\boldsymbol{end \ \ for}$
输出： 以 $node$ 为根节点的一棵决策树

三个 $if$ 对应三个终止条件：

$D$ 已经分类完毕，无须继续进行

$D$ 中所有元素在 $A$ 上取值相同，说明没办法区分开来了，无法继续进行，取类别标记为 $D$ 中样本数最多的类（如105个样本，100个A类，5个B类 $\rightarrow$ 标记为A类）

当前结点包含的样本集 $D_v (D_v \sube D)$ 为空，无法划分，取类别标记为 $D$ 中样本数最多的类（如D有105个样本，100个A类，5个B类，没有C类，但根据属性划分出C类子结点的样本数为0 $\rightarrow$ 就把C类子结点类别设定为D所含样本最多的类别A类）（当无样本了就返回分类前情况？）

参考资料：一起啃西瓜书(4)-决策树《机器学习-周志华》

划分选择

决策树学习关键在于选择最优的划分属性，使得决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（purity）越来越高。

熵、信息

*数据 = 噪音 + 信息

熵：一种事物的不确定性

熵的量化

参照一个不确定的事件作为单位
例：抛一次硬币50%正，50%反，记为1bit
抛硬币次数与结果不确定性呈指数关系
等概率均匀分布： $n = \log_2m$
例：8个等概率不确定情况，熵为3bit
若 $m = 10$ ，那么 $10 = 2^n,n = \log_210$
每种情况概率不相等，一般分布

信息增益（information gain）

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,...,|\mathcal{Y}|)$ ，则 $D$ 的信息熵定义为

$\begin{aligned} Ent(D)=\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2\frac{1}{p_k}\Rightarrow Ent(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k \end{aligned}$

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。

上述公式用于一般分布中

例：4类样本A,B,C,D原本各自所占比例均分， $p_k = 0.25, k = A,B,C,D$ ，计算信息熵 $n = \log_2m, n = 2 bits$ ，后续条件更改，C占比1/2，其余占比均分，为1/6，通过信息熵计算公式计算

$\begin{aligned} Ent(D) = \frac{1}{6}\log_26 +\frac{1}{6}\log_26 +\frac{1}{2}\log_22 +\frac{1}{6}\log_26 = 1.79 \end{aligned}$

假设离散属性 $a$ 有 $V$ 个可能取值 $\{a^1,a^2,\dots,a^V\}$ ，若以 $a$ 对样本进行划分样本集 $D$ 时，会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ ，可计算 $D^v$ 的信息熵，再赋予权重 $\lvert D^v \lvert / \lvert D \lvert$ ，计算信息增益：

$\begin{aligned} Gain(D,a) = Ent(D) - \sum^V_{v=1}\frac{\lvert D^v \lvert}{\lvert D \lvert} Ent(D^v) \end{aligned}$

例：样本集 $D$ 根节点的信息熵为 $Ent(D)$ ，有四个属性 $A,B,C,D$ ，计算它们的信息增益 $Gain(D, ?)(? = A,B,C,D)$ ，取信息增益最大值对应的属性进行划分。假设划分成3部分，随后将3个部分作为根节点继续以属性 $B,C,D$ 进行划分，算出信息增益 $Gain(D^i, ?)(i = 1,2,3; ? = B,C,D)$ 以此类推。

增益率（gain ratio）

由于信息增益准则对可取值数目较多的属性有偏好，为减小这种带来的不利影响，采用增益率来选择划分最优属性。定义：

$\begin{aligned} Gain\_ ratio(D,a) = \frac{Gain(D,a)}{IV(a)} \end{aligned}$

其中

$\begin{aligned} IV(a) = \sum^V_{v=1} \frac{\lvert D^v \lvert}{\lvert D \lvert} \log_2\frac{\lvert D^v \lvert}{\lvert D \lvert} \end{aligned}$

用法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数（Gini index）

数据集 $D$ 的纯度用基尼值度量：

$\begin{aligned} Gini(D) = \sum^{\lvert \mathcal{Y} \lvert}_{k=1}\sum_{k^\prime\neq k}p_kp_{k^\prime} = 1-\sum^{\lvert \mathcal{Y} \lvert}_{k=1}p_k^2 \end{aligned}$

$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本类别标记不一样的概率，因此 $Gini(D)$ 越小，数据集 $D$ 的纯度越高

属性 $a$ 的基尼指数定义(加权平均)：

$\begin{aligned} GiniIndex(D,a)=\sum_{v=1}^V\frac{|D^v|}{D}Gini(D^v) \end{aligned}$

所以以基尼指数选择属性划分时，所选的属性满足： $a_*=\underset{a\in A}{argmin} \ GiniIndex(D, a)$

def gini_index_single(a, b):
    single_gini = 1 - ((a/(a+b))**2) - ((b/(a+b))**2)
    return round(single_gini, 3)

def gini_index(a, b, c, d):
    left = gini_index_single(a, b)
    right = gini_index_single(c, d)
    #加权平均
    gini_index = left*((a+b)/(a+b+c+d)) + right*((c+d)/(a+b+c+d))
    return round(gini_index, 3)

graph TD
  结果.好/坏.

  因素1--是-->1(结果.105/39.);
  因素1--否-->2(结果.34/125.);
  因素2--是-->3(结果.37/127.);
  因素2--否-->4(结果.100/33.);
  因素3--是-->5(结果.92/31.);
  因素3--否-->6(结果.45/129.);

#第一次分支，选择结点，计算GiniIndex，取最小值
gini_index(105,39,34,125) -> 0.364
gini_index(37,127,100,33) -> 0.36
gini_index(92,31,45,129) -> 0.381
#选取因素2

假设第一次分配后现象如下，目前以37/127结点继续选择分支举例

graph TD
  结果.好/坏.

  因素2-->37/127;
  因素2-->100/33;
  37/127-.->因素1
  37/127-.->因素3

  因素1--是-->1(结果.13/98.);
  因素1--否-->2(结果.24/29.);

  因素3--是-->5(结果.24/25.);
  因素3--否-->6(结果.13/102.);

#计算37/127本身的Gini系数
gini_index_single(37, 127) -> 0.349
#再计算因素Gini值，取最小
gini_index(13,98,24,29) -> 0.3
gini_index(24,25,13,102) -> 0.29

#0.29 < 0.349
#选取因素3

graph TD
  结果.好/坏.

  因素2-->因素3;
  因素2-->100/33;

  因素1--是-->1(结果.1/10.);
  因素1--否-->2(结果.12/92.);

  因素3-->24/25;
  因素3-->13/102;
  13/102-.->因素1;

继续计算，以13/102结点举例：

#计算13/102本身的Gini指数
gini_index_single(13, 102) -> 0.201
#再计算因素Gini值，取最小
gini_index(1,10,12,92) -> 0.201

#0.201=0.201
#在13/102结点处终止

graph TD
  结果.好/坏.

  因素2-->因素3;
  因素2-->100/33;

  因素1--是-->1(结果.1/10.);
  因素1--否-->2(结果.12/92.);

  因素3-->24/25;
  因素3-->13/102;

平方误差最小准则（Sum of Squared Residuals SSR）

生成回归树时对于分支条件的选择需要通过SSR来筛选。

对于一个特征的决策树，求取分支条件阈值的流程：

阈值从小到大移动；
每移动一次，计算阈值左右两边的平方误差；
计算后取平方误差最小的阈值作为分支阈值。

对于多个特征的决策树，计算方法类似，不同之处在于需要对多个特征的SSR做比较，随后选择SSR最小的特征作为分支结点。

防止过拟合（分支过多）的举措为设定叶结点的数目上限，视情况而定，一般20个？

剪枝（pruning）

目的：防止过拟合。

策略：预剪枝（prepruning）和后剪枝（postpruning）

预剪枝（能剪则剪）（自上而下？）：选择属性分支，若分支后
验证集精度不大于分支之前的精度，则预剪枝策略禁止该节点划分。

后剪枝（能不剪就不剪）（自下而上？）：从分支后的验证集精度看起，倘若没有该分支的验证集精度更大，则进行剪枝。