Decision Tree
- 是一种基本的分类与回归方法
- 决策树由节点和有向边组成
- 内部节点表示一个特征/属性
- 叶子节点表示一个分类
- 有向边表示一个划分规则
- 决策树从根节点到子节点的有向边代表了一条路径(一条分类规则)
- 决策树的路径是互斥的且是完备的
- 互斥：每一个样本不会同时匹配上两条分类规则
- 完备：每一个样本都能在决策树中匹配上一条规则
- 决策树学习通常包括3个步骤：
- 特征选择
- 决策树生成
- 决策树剪枝
- 决策树表示给定特征条件下类的条件概率分布
决策树的组成：
- 根节点：第一个选择点
- 非叶子节点与分支：中间过程
- 叶子节点：最终的决策结果
原理
特征选择
特征选择指选择最大化所定义目标函数的特征。
为了衡量类别分布概率的倾斜程度，定义决策树节点node的不纯度（impurity）
- 不纯度越小，则类别的分布概率越倾斜
不纯度的三种度量：
- 熵（Entropy）
$$\mathrm{Entropy}(\mathrm{node})=-\sum_{k=1}^Kp_k\log{p_k}$$ - 基尼不纯度（Gini Impurity）
$$\mathrm{Gini}(\mathrm{node})=\sum_{k=1}^K p_k(1-p_k)$$ - 分类误差率
$$\mathrm{Classification_error}(\mathrm{node})=1-\max_k\ p_k$$
其中$p_k$表示样本中类别$k$的占比；共有$K$个类别。
其中
- 为了更好地反映变量关系，曲线中的熵除以2
- 横轴是$p$
- $p$为0或1时，熵、基尼不纯度、分类误差率都为0，表示不存在不确定性
- 当$p=0.5$时，熵、基尼不纯度、分类误差率最大，表示不确定性最大
信息增益
信息增益（Information Gain）：表示已知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。
定义：特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为数据集$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差。即
$$g(D,A)=H(D)-H(D|A)$$
一般地，熵$H(Y)$与条件熵$H(Y|X)$之差称为Post not found: Machine-Learning-熵 互信息（Mutual Information）。
- 决策树学习中的信息增益等价于训练数据集中类与特征的互信息
- 给定训练数据集$D$和特征$A$，经验熵$H(D)$表示对数据集$D$进行分类的不确定性
- $g(D,A)$表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度
- 对于数据集$D$而言，信息增益依赖于特征
- 不同的特征往往具有不同的信息增益
- 信息增益大的特征具有更强的分类能力
考虑训练数据集$D$，$n=|D|$为样本容量。
- 有$K$个类$C_k,\ (k=1,\cdots,K)$
- $|C_k|$为属于类$C_k$的样本个数
$$\sum_{k=1}^K|C_k|=n$$ - 设特征$A$有$m$个不同的取值$a_1,\cdots,a_m$
- 根据特征$A$的取值将$D$划分为$m$个子集$D_1,\cdots,D_m$
- $|D_i|$为$D_i$的样本个数
$$\sum_{i=1}^m|D_i|=|D|$$ - 记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$
$$D_{ik}=D_i\cap C_k$$
$|D_{ik}|$为$D_{ik}$的样本个数
信息增益算法
输入：训练数据集$D$和特征$A$
输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$
- 计算训练集$D$的经验熵$H(D)$
$$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log{\frac{|C_k|}{|D|} }$$ - 计算特征$A$对数据集$D$的经验条件熵$H(D|A)$
$$\begin{aligned} H(D|A)&=\sum_{i=1}^m\frac{|D_i|}{|D|}H(D_i)\
&=-\sum_{i=1}m\frac{|D_i|}{|D|}\sum_{k=1}K\frac{|D_{ik}|}{|D_i|}\log{\frac{|D_{ik}|}{|D_i|} }\
&= -\sum_{i=1}m\sum_{k=1}K\frac{|D_{ik}|}{|D|}\log{\frac{|D_{ik}|}{|D_i|} }
\end{aligned}$$ - 计算信息增益
$$g(D,A)=H(D)-H(D|A)$$
- 可用信息增益来进行决策树的划分属性选择
$$a^*=\arg\max_{a\in A} g(D,a)$$
ID3决策树学习算法就是以信息增益为准则来选择划分属性
决策树算法
包括
- ID3
- C4.5
- CART
ID3
- 以信息增益为准则来划分属性
示例：
数据来源
共4个特征：
- 天气
- 温度
- 湿度
- 风
| 特征 | 特征的不同取值 | 样本数 | `yes`样本数 | `no`样本数 |
|---|---|---|---|---|
| outlook | sunny | 5 | 2 | 3 |
| overcast | 4 | 4 | 0 | |
| rainy | 5 | 3 | 2 | |
| temperature | hot | 4 | 2 | 2 |
| mild | 6 | 4 | 2 | |
| cool | 4 | 3 | 1 | |
| humidity | high | 7 | 3 | 4 |
| normal | 7 | 6 | 1 | |
| windy | false | 8 | 6 | 2 |
| true | 6 | 3 | 3 | |
标签为“打球”yes或“不打球”no，原始数据共有14个样本，其中9个为yes、5个为no，原始数据集的熵为
$$H(D)=-\frac{9}{14}\log_2{\frac{9}{14} }-\frac{5}{14}\log_2{\frac{5}{14} }=0.940286$$
接着计算经验条件熵：
- 天气：
\begin{aligned}
H(sunny)&=-\frac{2}{5}\log_2{\frac{2}{5} }-\frac{3}{5}\log_2{\frac{3}{5} }=0.970951\
H(overcast)&=0\
H(rainy)&=-\frac{3}{5}\log_2{\frac{3}{5} }-\frac{2}{5}\log_2{\frac{2}{5} }=0.970951\
H(D|outlook)&=\frac{5}{14}H(sunny)+\frac{4}{14}H(overcast)+\frac{5}{14}H(rainy)=0.693536
\end{aligned} - 温度
\begin{aligned}
H(hot)&=-\frac{2}{4}\log_2{\frac{2}{4} }-\frac{2}{4}\log_2{\frac{2}{4} }=1\
H(mild)&=-\frac{4}{6}\log_2{\frac{4}{6} }-\frac{2}{6}\log_2{\frac{2}{6} }=0.918296\
H(cool)&=-\frac{3}{4}\log_2{\frac{3}{4} }-\frac{1}{4}\log_2{\frac{1}{4} }=0.811278\
H(D|temperture)&=\frac{4}{14}H(hot)+\frac{6}{14}H(mild)+\frac{4}{14}H(cool)=0.911063
\end{aligned} - 湿度
\begin{aligned}
H(high)&=\cdots=0.985228\
H(normal)&=\cdots=0.591673\
H(D|humidity)&=\frac{7}{14}H(high)+\frac{7}{14}H(normal)=0.788451
\end{aligned} - 风
\begin{aligned}
H(false)&=\cdots=0.811278\
H(true)&=\cdots=1\
H(D|windy)&=\frac{8}{14}H(false)+\frac{6}{14}H(true)=0.892159
\end{aligned}
接着计算信息增益：
\begin{aligned}
H(D,outlook)&=0.940286-0.693536=0.24675\
H(D,temperature)&=0.940286-0.911063=0.029223\
H(D,humidity)&=0.940286-0.788451=0.151835\
H(D,windy)&=0.940286-0.892159=0.048127
\end{aligned}
其中outlook的信息增益最大，所以应选择特征outlook为根节点。
ID4
C4.5
- 基于ID3
- ID3使用的是信息增益，而C4.5使用的是信息增益比
CART
Classification and Regression Tree / Regression Tree
分类和回归树
- 与C4.5不同，CART的决策树由二元逻辑问题生成，每个树节点只有两个分支
regression tree is a function that maps the attributes to the score. —— from Tianqi Chen - Introduction to Boosted Tree
CHAID
Chi-squared Automatic Interaction Detector
MARS
条件推断树
过拟合
当训练误差（training error）很小，泛化误差（generalization error / test error）较大时，说明决策树模型发生了过拟合。
发生过拟合的根本原因是决策树模型过于复杂，可能的原因有：
- 训练数据集中有异常点（噪音样本点），异常点影响了模型的分类效果
- 决策树的叶节点中缺乏有分类价值的样本记录（需要进行剪枝）
如何避免决策树过拟合？
- 限制树的深度max_depth
- 剪枝prune
- 限制叶子节点数量
- 正则化项
- 增加样本数据
- bagging（subsample、subfeature、低维空间投影）
- 数据增加（加入有噪声的数据）
- early stopping
总结
优点
决策树的优点：
- 可读性强
- 分类速度快
- 推理过程完全依赖于属性变量的取值特点
- 可自动忽略对目标变量没有贡献的属性变量
缺点
笔试题目
当在一个决策树中划分一个节点时，以下关于“信息增益”的论述正确的是（2、3）
1.较不纯的节点需要更多的信息来描述总体
2.信息增益可以通过熵来推导
3.信息增益偏向于选择大量值的属性
[来自：牛客试题广场]
- 不纯度指的是基尼系数
- 不需要归一化处理的模型：决策树、随机森林
- 因为它们不关心变量的值，而是关心变量的分布和变量之间的条件概率
