决策树

决策树（decision tree）是一种基本的机器学习算法

分类决策树模型是表示基于特征对实例进行分类的树形结构；决策树可以转换成一个 if-then 规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布

决策树学习算法包括3部分：

• 特征选择

• 决策树的生成

• 决策树的修剪，常用的算法有 ID3、 C4.5 和 CART

决策树模型与学习

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构，由以下两部分组成：

• 结点（node）：包括

  • 内部节点（internal node）：表示一个特征或属性

  • 叶结点（leaf node）：表示一个类

• 有向边（directed edge）

if-then 规则

可以将决策树看成一个 if-then 规则的集合：

由决策树的根节点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论

if-then 规则要互斥而且完备

决策树学习

假设有训练集

$$D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$$

其中，$x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}}$为输入实例，$n$ 为输入的特征个数，$y_i\in\{1, 2, \cdots, K\}$ 为类标记，$i=1, 2, \cdots, N$，$N$ 为样本容量

决策树学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类

特征选择

特征选择在于选取对训练数据具有分类能力的特征，通常特征选择的准则是信息增益或信息增益比

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设$X$是一个取有限个值的离散随机变量，其概率分布为

$$P(X=x_i)=p_i, \ \ \ \ i=1, 2, \cdots, n$$

则随机变量$X$的熵定义为

$$H(X)=-\sum_{i=1}^n{p_ilog{p_i}}$$

在上式中，若$p_i=0$，则定义$0log0=0$，易知，熵只依赖于$X$的分布，与$X$的取值无关，故也可记为

$$H(p)=-\sum_{i=1}^n{p_ilog{p_i}}$$

通常，式中的对数以$2$或$e$为底，熵的单位分别为比特（bit）或者纳特（nat）

熵越大，随机变量的不确定性就越大，可以验证，

$$0\leq H(p)\leq logn$$