深入理解决策树算法

2019-11-08 16:12:54 浏览数 (1)

引言

决策树(Decision Tree)是机器学习中一种经典的分类与回归算法。本文主要讨论用于分类的决策树。决策树模型呈树形结构,在分类问题中,决策树模型可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性,分类速度快。决策树学习通常包括3个步骤:特征选择决策树的生成决策树的剪枝

基本原理

模型结构

决策树由结点(Node)和有向边(Directed Edge)组成。结点有两种类型:内部结点(Internal Node)和叶结点(Leaf Node)。内部结点表示特征或属性,叶结点表示一个类别,有向边代表了划分规则。

决策树从根结点到子结点的的有向边代表了一条路径。决策树的路径是互斥并且是完备的。

用决策树分类时,对样本的某个特征进行测试,根据测试结果将样本分配到树的子结点上。此时每个子结点对应该特征的一个取值。递归地对样本测试,直到该样本被划分叶结点。最后将样本分配为叶结点所属的类。

条件概率分布

决策树将特征空间划分为互不相交的单元,在每个单元定义一个类的概率分布,这就构成了一个条件概率分布。

通俗来讲,在训练过程中,我们学习构建的决策树(规则)会将训练样本划分在不同的叶子节点中,每个叶子节点所代表的类别就是该叶子节点中数量最多的样本类别,当然在某些场景下,我们会考虑训练样本的权重,来定义叶子节点代表的类别。

学习过程

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个,也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。

决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这些子集己经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点中去;如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止。最后每个子集都被分到叶结点上,即都有了明确的类。这就生成了一棵决策树。

以上方法生成的决策树可能对训练数据有很好的分类能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好的泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更髙的结点,然后将父结点或更高的结点改为新的叶结点。

如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。

可以看出,决策树学习算法包含特征选择决策树的生成决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。

决策树学习常用的算法有ID3、C4.5与CART,下文结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。

特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提髙决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。

通常特征选择的准则是信息增益信息增益比

信息增益

H(p) = - sum_{i=1}^n p_{i} log p_{i}

熵越大,随机变量的不确定性就越大。从定义可验证:

0 leq H(p) leq log n

当随机变量只取两个值,例如1、0时,即X的分布为:

P(X=1)=p,; ; ; P(X=0)=1-p,; ; ; 0 leq p leq 1

熵为:

H(p)=-plog_{2}p-(1 - p)log_{2}(1-p)

设有随机变量(X, Y),其联合概率分布为:

P(X = x_{i},Y = y_{j}) = p_{ij};,; ; ;i = 1,2,cdots,n;;;j= 1,2,cdots,m

条件熵

(H(Xmid Y))

表示在己知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(Conditional Entropy)

(H(Xmid Y))

,定义为X给定条件下Y的条件概率分布的熵对X的数学期望:

H(Xmid Y)=sum_{i=1}^{n}p_{i}H(Ymid X=X_{i})

这里,

(p_{i}=P(X=x_{i});,; ; ;i=1,2,cdots,n)

当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵与条件熵分别称为经验熵(Empirical Entropy)和经验条件熵(Empirical Conditional Entropy)。此时,如果有0概率,令

(0log0 = 0)

信息增益(Information Gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

0 人点赞