引言
决策树(Decision Tree)是机器学习中一种经典的分类与回归算法。本文主要讨论用于分类的决策树。决策树模型呈树形结构,在分类问题中,决策树模型可以认为是if-then
规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性,分类速度快。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的剪枝。
基本原理
模型结构
决策树由结点(Node)和有向边(Directed Edge)组成。结点有两种类型:内部结点(Internal Node)和叶结点(Leaf Node)。内部结点表示特征或属性,叶结点表示一个类别,有向边代表了划分规则。
决策树从根结点到子结点的的有向边代表了一条路径。决策树的路径是互斥并且是完备的。
用决策树分类时,对样本的某个特征进行测试,根据测试结果将样本分配到树的子结点上。此时每个子结点对应该特征的一个取值。递归地对样本测试,直到该样本被划分叶结点。最后将样本分配为叶结点所属的类。
条件概率分布
决策树将特征空间划分为互不相交的单元,在每个单元定义一个类的概率分布,这就构成了一个条件概率分布。
通俗来讲,在训练过程中,我们学习构建的决策树(规则)会将训练样本划分在不同的叶子节点中,每个叶子节点所代表的类别就是该叶子节点中数量最多的样本类别,当然在某些场景下,我们会考虑训练样本的权重,来定义叶子节点代表的类别。
学习过程
决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。
决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这些子集己经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点中去;如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶结点上,即都有了明确的类。这就生成了一棵决策树。
以上方法生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更髙的结点,然后将父结点或更高的结点改为新的叶结点。
如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。
可以看出,决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。
决策树学习常用的算法有ID3、C4.5与CART,下文结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。
特征选择
特征选择在于选取对训练数据具有分类能力的特征。这样可以提髙决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。
通常特征选择的准则是信息增益或信息增益比。
信息增益
熵越大,随机变量的不确定性就越大。从定义可验证:
当随机变量只取两个值,例如1、0时,即X
的分布为:
熵为:
设有随机变量(X, Y)
,其联合概率分布为:
条件熵
表示在己知随机变量X
的条件下随机变量Y
的不确定性。随机变量X
给定的条件下随机变量Y
的条件熵(Conditional Entropy)
,定义为X
给定条件下Y
的条件概率分布的熵对X
的数学期望:
这里,
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(Empirical Entropy)和经验条件熵(Empirical Conditional Entropy)。此时,如果有0概率,令
信息增益(Information Gain)表示得知特征X
的信息而使得类Y
的信息的不确定性减少的程度。