机器学习04 决策树

前言：简要介绍《机器学习》第四章–决策树，决策树算法主要为三部分：划分选择、树的生成、剪枝。划分选择的准则有信息增益、增益率、基尼指数；生成树的常用算法有ID3、C4.5、CART；剪枝是为了避免过拟合。本章数学公式推导较少，重点在于理解决策树的生成过程。

决策树（decision tree）是一种基本的分类和回归方法，《机器学习》第四章中主要讨论用于分类的决策树。
决策树学习的目的：产生一棵泛化能力强的树
策略：分而治之（divide-and-conquer）

决策树模型

分类决策树模型是一种对样例进行分类属性结构。决策树由结点（node）和有向边（directed edge）组成。结点分为根结点（唯一）、内部结点（internal node）和叶结点（leaf node），叶结点表示一个类对应于决策结果，内部和根结点对应一个属性测试。

停止条件：

1. 当前结点包含的样本全属于同一类别
2. 当前属性集为空，或所有样本在所有属性上取值相同
3. 当前结点包含的样本集合为空

划分选择（特征选择）

划分选择（特征选择）是指选取对训练数据具有分类能力的特征或属性，希望分支结点所包含的样本尽可能属于同一类别，即结点纯度（purity）越高，其准则主要有信息增益、增益率、基尼指数。

熵

熵（entropy）表示随机变量不确定性的度量，熵越大，不确定性越大。

设 $X$ 是一个取有限个值的离散随机变量，概率分布为 $P(X=x_i)=p_i,i=1,2,\mathrm{3...}n$，则随机变量 $X$ 的熵为 $H(X)=-{\sum }_{i=1}^n{p}_i\ast \log p_i$，通常式中对数以 2 或 e 为底数，单位分别为比特（bit）或纳特（nat）。

• 当 $p_i=0$ 时，定义 $0\ast log0=0$
• 熵只依赖于 $X$ 的分布，与 $X$ 取值无关，有时也将熵记为 $H(p)$

信息熵

信息熵（information entropy）为度量样本集合纯度的指标，信息熵越大，则不确定性越大，纯度越低。

假定当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k(k=1,2,3...|y|，|y|为样本集总的类别数)$，则信息熵计算公式：$Ent(D)=-{\sum }_{k=1}^{|y|}{p}_k\ast lo{g}_2{p}_k$。

条件熵

条件熵（conditional entropy）表示在已知随记变量 $X$ 的条件下随机变量 $Y$ 的不确定性，记为 $H(Y|X)={\sum }_{i=1}^n{p}_i\ast H(Y|X=x_i)$

从单个属性（特征）$a$ 的角度来看, 假设其可能取值为 $\left\{a^1,a^2,\dots ,a^V\right\}$，$D^v$ 表示属性 $a$ 取值为 $a^v\in \left\{a^1,a^2,\dots ,a^V\right\}$ 的样本集合，$\frac{\mid D^v}{D}$ 表示占比，那么在已知属性 $a$ 的取值后，样本集合 $D$ 的条件樀为：${\sum }_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Ent}\left(D^v\right)$

信息增益

信息增益（information gain）越大，则是用属性 $a$ 来进行划分所获得的的纯度提升越大。

计算公式：$Gain(D,a)=Ent(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$，可理解为信息熵与条件熵的差值。

信息增益对可取值数目较多的属性有偏好。

增益率

增益率（gain ratio）计算公式：$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

其中，$IV(a)=-{\sum }_{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$ 称为属性 $a$ 的固有值（intrinsic value）。属性 $a$ 取值数目（V 值）越大，则 $IV(a)$ 的值通常越大。

增益率对可取值数目较少的属性有偏好。

基尼指数

基尼指数（Gini index）

数据集 $D$ 的纯度可用基尼值来度量：$Gini(D)={\sum }_{k=1}^{|y|}{\sum }_{k^{\prime }\ne k}{p}_k{p}_k^{{}^{\prime }}$，基尼值越小，数据集 $D$ 的纯度越高。

属性 $a$ 的基尼指数为：$Gini\_index(D,a)={\sum }_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$。

常用决策树模型

多变量决策树

传统的单变量决策树（univariate decision tree）的分类边界是轴平行（axis-parallel）的，即分类边界由若干与坐标轴平行的线或面组成。优点是解释性强，缺点是需要考虑所有属性划分，时间耗费大。

多变量决策树（multivariate decision tree）实现「斜划分」等复杂划分的决策树，每个非叶结点都是一个线性分类器，而不再针对某个属性。

连续与缺失值处理

连续值处理

利用决策树处理连续数据，例如西瓜的含糖率，需要利用二分法（bi-partition）等连续属性离散化技术，

与离散属性不同的是，若当前结点划分属性为连续属性，则该属性还可作为其后代结点的划分属性。如：考试分数=60划分是否及格，分数（>60）=90划分是否优秀。

缺失值处理

解决两个问题：

1. 如何在属性缺失的情况下进行划分属性选择？
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

思想：样本赋权，权重划分。

参考资料：

《机器学习》周志华

《统计学习方法》（第二版）李航

周志华《机器学习》（西瓜书) 视频_bilibili

《机器学习公式详解》（南瓜书）p6