1. 决策树

基于树结构来进行决策

1.1. 基本流程

• 测试：决策过程中提出的每个判定问题都是对某个属性的测试

一般的，一颗决策树包含一个根结点、若干个内部结点和若干个叶结点；
叶结点对应于决策结果，其他每个结点则对应于一个属性的测试
每个结点包含的样本集合根据属性测试的结果被划分到子结点中
根结点包含样本全集
从根结点到每个叶结点的路径对应了一个判定测试序列

• 目的：产生一颗泛化能力强，即处理未见示例能力强的决策树
• 基本流程：遵循简单且直观的分而治之策略
  
  决策树的生成是一个递归过程
  三种递归返回
  • 当前结点包含的样本全属于同一类别，无需划分
  • 当前属性集为空，或是所有样本在所有属性上的取值相同，无法划分
  • 当前结点包含的样本集合为空，不能划分

1.2. 划分选择

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高.

1.2.1. ID3决策树

ID3名字中的ID是lterative Dichotomiser(迭代二分器)的简称。
以信息增益为准则来选择划分属性

1.2.1.1. 信息增益

信息熵是对量样本集合纯度最常用的一种指标

• 信息熵
  假定当前样本集合$D$D中第$k$k类样本所占的比例$p_k(k=1,2,3,\ldots,|\mathcal{Y}|)$pk​(k=1,2,3,…,∣Y∣)且$0 \leq p_{k} \leq 1, \sum_{k=1}^{|\mathcal{Y}|} p_{k}=1$0≤pk​≤1,∑k=1∣Y∣​pk​=1,$|\mathcal{Y}|$∣Y∣样本的类别总数，则$D$D的信息熵定义为
  $\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k}$Ent(D)=−k=1∑∣Y∣​pk​log2​pk​
  $\operatorname{Ent}(D)$Ent(D)的值越小，则$D$D的纯度越高

  证明：$0\leq \operatorname{Ent}(D) \leq\log_2|\mathcal{Y}|$0≤Ent(D)≤log2​∣Y∣

  • 求$\operatorname{Ent}(D)$Ent(D)的最大值
    若令$|\mathcal{Y}|=n,p_k=x_k$∣Y∣=n,pk​=xk​,那么信息熵$\operatorname{Ent}(D) $就可以看成$就可以看成n$元实值函数，也即：
    $\operatorname{Ent}(D)=f\left(x_{1}, \ldots, x_{n}\right)=-\sum_{k=1}^{n} x_{k} \log _{2} x_{k}$Ent(D)=f(x1​,…,xn​)=−k=1∑n​xk​log2​xk​
    其中$0 \leq x_{k} \leq 1, \sum_{k=1}^{n} x_{k}=1$0≤xk​≤1,∑k=1n​xk​=1，考虑求该多元函数的最值(约束优化问题)
    仅考虑$\sum_{k=1}^{n} x_{k}=1$∑k=1n​xk​=1对于$f\left(x_{1}, \ldots, x_{n}\right)$f(x1​,…,xn​)求最大值等同于如何最小化
    $\text { min } \sum_{k=1}^{n} x_{k} \log _{2} x_{k},\text { S.t. } \sum_{k=1}^{n} x_{k}=1$ min k=1∑n​xk​log2​xk​, S.t. k=1∑n​xk​=1
    显然，在$0\leq x_k \leq 1$0≤xk​≤1时此问题为凸优化(拆开分析二阶导数大于零，或hessian矩阵)问题，而对于凸优化问题来说，满足KKT条件的点即为最优解。由于此最小化问题仅含等式约束，那么能令其拉格朗日函数的一阶偏导数等于0的点即为满足KKT条件的点。
    根据拉格朗日乘子法可知，该优化问题的拉格朗日函数为
    $L\left(x_{1}, \ldots, x_{n}, \lambda\right)=\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda\left(\sum_{k=1}^{n} x_{k}-1\right)$L(x1​,…,xn​,λ)=k=1∑n​xk​log2​xk​+λ(k=1∑n​xk​−1)
    对于拉格朗日函数分别关于$x_1,\ldots,x_n,\lambda$x1​,…,xn​,λ求一阶偏导数，并令偏导数等于0
    $\begin{aligned} \frac{\partial L\left(x_{1}, \ldots, x_{n}, \lambda\right)}{\partial x_{1}}&=\frac{\partial}{\partial x_{1}}\left[\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda\left(\sum_{k=1}^{n} x_{k}-1\right)\right]=0\\ &=\log _{2} x_{1}+x_{1} \cdot \frac{1}{x_{1} \ln 2}+\lambda=0\\ &=\log _{2} x_{1}+\frac{1}{\ln 2}+\lambda=0\\ &\Rightarrow \lambda=-\log _{2} x_{1}-\frac{1}{\ln 2} \end{aligned}$∂x1​∂L(x1​,…,xn​,λ)​​=∂x1​∂​[k=1∑n​xk​log2​xk​+λ(k=1∑n​xk​−1)]=0=log2​x1​+x1​⋅x1​ln21​+λ=0=log2​x1​+ln21​+λ=0⇒λ=−log2​x1​−ln21​​
    同理可得
    $\lambda=-\log _{2} x_{1}-\frac{1}{\ln 2}=-\log _{2} x_{2}-\frac{1}{\ln 2}=\ldots=-\log _{2} x_{n}-\frac{1}{\ln 2}$λ=−log2​x1​−ln21​=−log2​x2​−ln21​=…=−log2​xn​−ln21​
    又因为
    $\begin{aligned} \frac{\partial L\left(x_{1}, \ldots, x_{n}, \lambda\right)}{\partial \lambda} &=\frac{\partial}{\partial \lambda}\left[\sum_{k=1}^{n} x_{k} \log _{2} x_{k}+\lambda\left(\sum_{k=1}^{n} x_{k}-1\right)\right]=0 \\ & \Rightarrow \sum_{k=1}^{n} x_{k}=1 \end{aligned}$∂λ∂L(x1​,…,xn​,λ)​​=∂λ∂​[k=1∑n​xk​log2​xk​+λ(k=1∑n​xk​−1)]=0⇒k=1∑n​xk​=1​
    所以解的
    $x_{1}=x_{2}=\ldots=x_{n}=\frac{1}{n}$x1​=x2​=…=xn​=n1​
    根据验证满足约束条件，所以未满足所有约束的最优解，也即未当前最小化问题的最小值点，同时也是$f\left(x_{1}, \ldots, x_{n}\right)$f(x1​,…,xn​)的最大值点
    将解带入可得
    $f\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)=-\sum_{k=1}^{n} \frac{1}{n} \log _{2} \frac{1}{n}=-n \cdot \frac{1}{n} \log _{2} \frac{1}{n}=\log _{2} n$f(n1​,…,n1​)=−k=1∑n​n1​log2​n1​=−n⋅n1​log2​n1​=log2​n
    纯度最低是为样本为均匀分布的时候
  • 求$\operatorname{Ent}(D)$Ent(D)的最小值
    仅考虑$0 \leq x_k \leq 1$0≤xk​≤1，$f\left(x_{1}, \ldots, x_{n}\right)$f(x1​,…,xn​)可以看成是$n$n个互不相关的一元函数的加和，即
    $f\left(x_{1}, \ldots, x_{n}\right)=\sum_{k=1}^{n} g\left(x_{k}\right)$f(x1​,…,xn​)=k=1∑n​g(xk​)
    其中$g\left(x_{k}\right)=-x_{k} \log _{2} x_{k}, 0 \leq x_{k} \leq 1$g(xk​)=−xk​log2​xk​,0≤xk​≤1。当各个$g(x_i)$g(xi​)分别取到其最小值时，函数也取到最小值
    • 求$g(x_1)$g(x1​)的最小值
      $\begin{aligned} g^{\prime}\left(x_{1}\right)&=\frac{d\left(-x_{1} \log _{2} x_{1}\right)}{d x_{1}}=-\log _{2} x_{1}-x_{1} \cdot \frac{1}{x_{1} \ln 2}=-\log _{2} x_{1}-\frac{1}{\ln 2}\\ g^{\prime \prime}\left(x_{1}\right)&=\frac{d\left(g^{\prime}\left(x_{1}\right) \right)}{d x_{1}}=\frac{d\left(-\log _{2} x_{1}-\frac{1}{\ln 2}\right)}{d x_{1}}=-\frac{1}{x_{1} \ln 2} \end{aligned}$g′(x1​)g′′(x1​)​=dx1​d(−x1​log2​x1​)​=−log2​x1​−x1​⋅x1​ln21​=−log2​x1​−ln21​=dx1​d(g′(x1​))​=dx1​d(−log2​x1​−ln21​)​=−x1​ln21​​
      $g(x_1)$g(x1​)是一个在其定义域范围内开口向下的凹函数，那么其最小值必然在边界取。所以$g(0)=g(1)=1$g(0)=g(1)=1
      Note:在信息熵中$0\log_2 0=0$0log2​0=0
      

• 条件熵
  在已知样本属性$a$a的取值情况下，度量样本集合纯度的一种指标
  假定离散属性$a$a有$V$V个可能的取值$\{a^1,a^2,\ldots,a^V\}${a1,a2,…,aV},若使用$a$a来对样本集$D$D进行划分，则会产生$V$V个分支结点，其中第$v$v个分支结点包含了$D$D中所有在属性$a$a上取值为$a^v$av的样本，记为$D^v$Dv
  $H(D | a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)$H(D∣a)=v=1∑V​∣D∣∣Dv∣​Ent(Dv)
  $H(D | a)$H(D∣a)值越小，纯度越高

• 信息增益
  属性$a$a对样本集$D$D进行划分所获得的信息增益
  $\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)=\operatorname{Ent}(D)-H(D | a)$Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)=Ent(D)−H(D∣a)
  其中$|D^v|/|D|$∣Dv∣/∣D∣为分支结点赋予权重，即样本数越多的分支结点的影响越大

  一般而言信息增益越大，则意味着使用属性$a$a来进行划分所获得的纯度提升越大

最优化分属性
$a_{*}=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a)$a∗​=a∈Aargmax​Gain(D,a)

• 缺点
  信息增益对对可取数值数目较多的属性有所偏好
  $\begin{aligned} \operatorname{Gain}(D, a) &=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) \\ &=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|}\left(-\sum_{k=1}^{|y|} p_{k} \log _{2} p_{k}\right) \\ &=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|}\left(-\sum_{k=1}^{|y|} \frac{\left|D_{k}^{v}\right|}{\left|D^{v}\right|} \log _{2} \frac{\left|D_{k}^{v}\right|}{\left|D^{v}\right|}\right) \end{aligned}$Gain(D,a)​=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)=Ent(D)−v=1∑V​∣D∣∣Dv∣​⎝⎛​−k=1∑∣y∣​pk​log2​pk​⎠⎞​=Ent(D)−v=1∑V​∣D∣∣Dv∣​⎝⎛​−k=1∑∣y∣​∣Dv∣∣Dkv​∣​log2​∣Dv∣∣Dkv​∣​⎠⎞​​

1.2.2. C4.5决策树

解决信息增益的确定，不直接使用信息增益，而是使用增益率来选择最优化分属性

1.2.2.1. 增益率

• 增益率准则对可取数目较少的属性有所偏好

定义：
$\text { Gain ratio }(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}$ Gain ratio (D,a)=IV(a)Gain(D,a)​
其中
$\mathrm{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|}$IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​称为属性$a$a的固有值

属性$a$a的可能取值数目越多(即V越大)，则$\mathrm{IV}(a)$IV(a)的值通常会越大

算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的.

1.2.3. CART

CART是Classification and Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。

1.2.3.1. 基尼指数

• 基尼值
  $\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned}$Gini(D)​=k=1∑∣Y∣​k′​=k∑​pk​pk′​=1−k=1∑∣Y∣​pk2​​
  直观来说，$Gini(D)$Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率.因此，$Gini(D)$Gini(D)越小，则数据集D的纯度越高.
• 基尼指数
  属性$a$a的基尼指数
  $\text { Gini index }(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)$ Gini index (D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

最优化分属性
$a_{*}=\underset{a \in A}{\arg \min } \operatorname{Gini}_{\text {index }}(D, a)$a∗​=a∈Aargmin​Giniindex ​(D,a)

1.2.3.2. 算法

• 分类
  
• 回归