机器学习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)$。

常用决策树模型

	划分属性的准则
ID3	信息增益
C4.5	先从候选划分属性中找出信息增益高于平均水平的属性再从中选择增益率最高的
CART 决策树	基尼指数

多变量决策树

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

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

连续与缺失值处理

连续值处理

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

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

缺失值处理

解决两个问题

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

思想样本赋权权重划分。

---

参考资料

《机器学习》周志华

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

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

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