决策树

决策树模型与学习

决策树模型

分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部节点表示一个特征或者属性，叶结点表示一个类。
用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；每一个子节点对应着该特征的一个取值。如此递归分配，直到到达叶结点，最后将实例分到叶结点所在的类中。下图是一个决策树的示意图，圆和方框分别表示内部结点和叶结点。
统计学习方法（机器学习）——5、决策树

决策树模型与if-then规则

将决策树看成一个 $if-then$ 规则的集合：由决策树的根节点到叶结点的每一条路径构建一条规则，而叶结点的类对应着规则的结论。决策树的路径或其对应的 $if-then$ 规则集合有一个重要的性质：互斥且完备，即每一个实例都被一条路径或一条 $if-then$ 规则所覆盖，且只被这一条覆盖。

决策树模型与条件概率分布

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上，将特征空间划分为互不相交的单元或区域，每个单元定义一个类的概率分布，这样就构成了一个条件概率分布。如下图所示，为两个特征时的特征空间的划分：
统计学习方法（机器学习）——5、决策树

决策树学习

        假定给定训练数据集 $D=\{(x_1, y_1), (x_2, y_2), ..., (x_N,y_N)\}$ ，其中 $x_i=(x_i^{(1)}, x_i^{(2)},..., x_i^{(n)})^T$ 为输入特征向量， $n$ 为特征个数， $y_i\in\{1, 2, ..., K\}$ 为类标记， $i=1,2,...,N$ 为样本容量。学习的目标是根据给定的训练集构建一个决策树模型，使其能够对实例进行正确分类。
         决策树学习本质上是从训练集中归纳出一组分类规则。与训练集不相矛盾的决策树可能有多个，也可能一个也没有，我们需要找到一个与训练集矛盾最小的决策树，同时具有良好的泛化能力。
        决策树用损失函数表示这一目标，损失函数通常是正则化的极大似然函数。从所有可能的决策树中选取最优决策树是NP完全问题，现实中决策树的学习算法通常采用启发式的方法，近似求解。
        决策树学习的算法通常是一个递归选择最优特征，并根据该特征对训练集进行分割，使得对各个子数据集也有一个最好分类的过程：

构建根节点，将所有训练数据都放在根节点
选择一个最优特征，按照这一特征将训练集分割成自己，使得各个子集达到当前条件下最好的分类
– 如果这些子集已经能够被基本分类正确，则构建叶结点，并将这些子集分到对应的叶结点中；；
– 如果还有子集不能被基本分类正确，就对这些子集选择新的最优特征，继续分割。

如此递归下去，直到所有训练数据子集都被基本正确分类，或没有合适的特征为止，最后每个子集都被分到叶结点上。
        以上方法可能发生过拟合线性，我们需要对已生成的决策树进行自下而上的剪枝，去掉过于细分的节点，使其回退到父节点甚至更高的结点，然后将父节点改为新的叶结点。
        如果特征数量很多，在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。
        决策树学习算法包含特征选择、决策树的生成与决策树剪枝过程。决策树的生成对应于模型的局部选择，剪枝对应于模型的全局选择。

特征选择——信息增益

熵的概念

        特征选择在于选取对训练数据具有分类能力的特征，即决定用哪个特征来划分特征空间，这样可以提高决策树的学习效率。
        关于信息增益，先给出熵与条件熵的概念。
        熵是表示随机变量不确定性的度量。设 $X$ 是一个取有限个的离散随机变量，其概率分布为
$P(X=x_i)=p_i,\;\;i=i,2,..., n$
则随机变量 $X$ 的熵定义为：
$H(X)=-\sum\limits_{i=1}^np_ilogp_i$
式中的对数通常以2为底或以 $e$ 为底，此时熵的单位分别称为比特或纳特。由定义知，熵只依赖于 $X$ 的分布，与 $X$ 的取值无关，所以也可将 $X$ 的熵记作 $H(p)$ ，即：
$H(p)=-\sum\limits_{i=1}^np_ilogp_i$
        熵越大，随机变量的不确定性越大。

信息增益

        设有随机变量 $(X,Y)$ ，其联合概率分布为
$P(X=x_i,Y=y_j)=p_{ij},\;\;\;\;i=1, 2, ..., n;\;\;j=1, 2, ..., m$
        条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。随机变量 $X$ 给定的条件下随机变量 $Y$ 的条件熵 $H(Y|X)$ 定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$
这里， $p_i=P(X=x_i)， i=1, 2, ..., n$ 。
        当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵与经验条件熵。信息增益表示得知特征 $X$ 的信息而使得类 $Y$ 的信息的不确定性减少的程度。

定义信息增益
特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ 定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即：
$g(D,A)=H(D)-H(D|A)$
一般地，熵与条件熵之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。根据信息增益准则的特征选择方法是：对训练集 $D$ ，计算其每个也在的信息增益，选择信息增益最大的特征。

设训练数据集为 $D$ , $|D|$ 表示其样本容量。
设有 $K$ 个类 $C_k, k=1, 2, ..., K$ ， $|C_k|$ 为属于类 $C_k$ 的样本个数， $\sum\limits_{k=1}^K|C_k|=|D|$ 。
设特征 $A$ 有 $n$ 个不同取值 $\{a_1, a_2, .., a_n\}$ ，根据特征 $A$ 的取值将 $D$ 划分为n个子集 $\{D_1, D_2, .., D_n\}$ ， $|D_i|$ 为 $D_i$ 的样本个数， $\sum\limits_{i=1}^n|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)$

（1）计算数据集 $D$ 的经验熵 $H(D)$
$H(D)=-\sum\limits_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
（2）计算特征 $A$ 对训练数据集 $D$ 的经验条件熵 $H(D|A)$
$H(D|A)=\sum\limits_{i=1}^n\frac{|D_i|}{|D|}H(D)=-\sum\limits_{i=1}^n\frac{|D_i|}{|D|}\sum\limits_{k=1}^K\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$
（3）计算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

当训练集的经验熵大的时候，信息增益偏大，反之偏小。使用信息增益比可以对这一问题进行矫正，也可以作为特征选择的另一个准则。
特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练集 $D$ 的经验熵 $H(D)$ 之比，即：
$g_R(D,A)=\frac{g(D|A)}{H(D)}$

统计学习方法（机器学习）——5、决策树

文章目录

决策树