机器学习算法-决策树理论

源码下载:https://github.com/csuldw/MachineLearning/tree/master/DecisionTree

在决策树理论中,有这样一句话,“用较少的东西,照样可以做很好的事情。越是小的决策树,越优于大的决策树”。数据分类是一个两阶段过程,包括模型学习阶段(构建分类模型)和分类预测阶段(使用模型预测给定数据的类标号)。决策树分类算法属于监督学习(Supervised learning),即样本数据中有类别标号。下面是两个阶段的简单描述:

  • 第一阶段(以分类为例),可以看做是根据样本来学习一个映射或函数y=f(x)表达式,能够使用它预测给定元组X的类标号y。
  • 第二阶段,使用第一阶段学习得到的模型进行分类。首先评估分类器的预测准确率。这个过程要尽量减少过拟合(为什么是尽量减少?因为过拟合是避免不了的,再好的模型也会有过拟合的情况的)。

简介

决策树归纳是从有类标号的训练元组中学习决策模型。常用的决策树算法有ID3,C4.5和CART。它们都是采用贪心(即非回溯的)方法,自顶向下递归的分治方法构造。这几个算法选择属性划分的方法各不相同,ID3使用的是信息增益,C4.5使用的是信息增益率,而CART使用的是Gini基尼指数。下面来简单介绍下决策树的理论知识。内容包含信息增益信息增益率以及Gini指数的概念及公式。


决策树原理

决策树原理很简单,通俗易懂,最简单的就是二元划分,类似于二叉树。例如只考虑某一层某个节点的划分,如果年龄大于18,就表示成年人,如果年龄小于18就表示未成年人。

算法优点

决策树算法的优点如下:

  • 算法比较简单;
  • 理论易于理解;
  • 对噪声数据有很好的健壮性。

目前,决策树是应用最为广泛的归纳推理算法之一,在数据挖掘中受到研究者的广泛关注。衍生出很多出色的集成算法,如random forest、adaboost、gradient tree boosting都是基于决策树的模型。

算法一般流程

  1. 收集数据:任意方法和途径。
  2. 准备数据:书构造算法只适用于标称型数据,因此数据必须离散化。
  3. 分析数据:构造树完成后,检查图形是否符合预测。
  4. 训练算法:决策树的数据构造。
  5. 测试算法:一般将决策树用于分类,可以用错误率衡量,而错误率使用经验率计算。
  6. 使用算法:决策树可以用于任何监督学习算法。

实例分析

信息增益和熵(克劳德.香农提出)

1.使用信息增益作为划分属性

信息增益度量属性选择

熵被用来衡量一个随机变量出现的期望值。熵越大,一个变量的不确定性就越大(也就是可取的值很多),把它搞清楚所需要的信息量也就越大,熵是整个系统的平均消息量。 信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序,信息熵就越低;反之,一个系统越是混乱,信息熵就越高。所以,信息熵也可以说是系统有序化程度的一个度量。

熵(Entropy)的计算公式

熵定义为信息的期望值。先看看信息的定义:

$$l(x_i)=-log_2p(x_i)$$

其中,$p(x_i)$是选择该分类的概率。对$D$中的元组所有分类所有可能值的信息期望,即熵,计算公式如下:

$$Entropy=H(D)=E(I(D))=-\sum_i^{n} p_ilog_2(p_i),p_i是D中任意元组属于类C_i非零概率。$$

熵越大,说明系统越混乱,携带的信息就越少。熵越小,说明系统越有序,携带的信息就越多。信息的作用就是在于消除不确定性。

ID3划分特征使用的就是信息增益IG。一个属性的信息增益越大,表明属性对样本的熵减少的能力就更强,该属性使得数据所属类别的不确定性变为确定性的能力越强。信息增益在统计学中称为互信息,互信息是条件概率与后验概率的比值,化简之后就可以得到信息增益。所以说互信息其实就是信息增益。计算方法【互信息=熵-条件熵】。熵描述的是不确定性。熵越大,不确定性就越大,条件熵H(B|A)描述的是在A给定的条件下B的不确定性,如果条件熵越小,表示不确定性就越小,那么B就越容易确定结果。所以使用熵减去条件熵,就得到了信息增益,他描述的不确定性的降低程度,可以用来度量两个变量的相关性。比如,在给定一个变量的条件下,另一个变量它的不确定性能够降低多少,如果不确定性降低得越多,那么它的确定性就越大,就越容易区分,两者就越相关。注:期望信息越小,分区的纯度越高。

信息增益计算

首先计算特征A对数据集D的经验条件熵$H(D|A)$,在数学上就是条件概率分布(Condition Probability).

$$H(D|A)=\sum_j\dfrac{|D_j|}{|D|}\times H(D_j),项\dfrac{|D_i|}{|D|}充当第j个分区的权重$$

引入条件熵,在信息论中主要是为了消除结果的不确定性。然后计算信息增益

$$Gain(A) = H(D) - H(D|A)$$

其中,$Gain(A)$即为所求的信息增益。下面来应用一个实例,训练元组数据D

这里写图片描述

在这里

$$H(D)=-\dfrac{9}{14}log_2\dfrac{9}{14}-\dfrac{5}{14}log_2\dfrac{5}{14}=0.940位$$

$$H(D|age)=\dfrac{5}{14}\times(-\dfrac{2}{5}log_2\dfrac{2}{5}-\dfrac{3}{5}log_2 \dfrac{3}{5})+\dfrac{4}{14}\times(-\dfrac{4}{4}log_2\dfrac{0}{4}-\dfrac{0}{4}log_2 \dfrac{0}{4})+\dfrac{5}{14}\times(-\dfrac{3}{5}log_2\dfrac{3}{5}-\dfrac{2}{5}log_2 \dfrac{2}{5})=0.694位$$

根据计算出来的条件熵,计算按$age$划分的信息增益,计算方法如下:

$$Gain(age)=H(D)-H(D|age)=0.940-0.964=0.246位$$

类似的可以计算出其它属性的信息增益:

$$ Gain(income)=0.029位,
Gain(student)=0.151位,Gain(credit_rating)=0.048位 $$

由于$age$在属性中具有最高的信息增益,所以它被选作分裂特征。下面再进行递归计算信息增益,在此就不展示了。ID3采用的就是就是IG,算法步骤如下:


这里写图片描述
这里写图片描述

2.使用增益率计算

在决策树中,ID3属性划分标准使用的是信息增益,C4.5使用的是信息增益率。

C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:

  • 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
  • 在树构造过程中进行剪枝;
  • 能够完成对连续属性的离散化处理;
  • 能够对不完整数据进行处理。

C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。另外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

另外,无论是ID3还是C4.5最好在小数据集上使用,决策树分类一般只试用于小数据。当属性取值很多时最好选择C4.5算法,ID3得出的效果会非常差,因为使用信息增益划分时它倾向于取值多的属性。

计算信息增益率时,用到了分裂信息计算公式:

$$Split_H(D|A)=-∑\dfrac{|D_j|}{|D|}\times log_2(\dfrac{|D_j|}{|D|})$$

信息增益率定义为:

$$Gain_Rate(A)=\dfrac{Gain(A)}{Split_H(D|A)}$$

选择具有最大增益率的特征作为分裂特征。

3.基尼指数Gini index

基尼指数主要在CART算法中用到,随机森林中用到的属性划分标准也是它。Gini index划分是二元的,它度量的是数据分区或训练元组集D的不纯度,表示的是一个随机选中的样本在子集中被分错的可能性。计算方式如下:

$$Gini(D)=1-\sum p^{2}_i ,其中,p_i 是D中元组数以C_i 类的概率,对m个类计算和。$$

Gini指数越大,不纯度越大,越不容易区分。假设A有v个不同的值出现在特征D中,它的二元划分有$2^v - 2$种(除去自己和空集)。当考虑二元划分裂时,计算每个结果分区的不纯度加权和。比如A有两个值,则特征D被划分成D1和D2,这时Gini指数为:

$$Gini_A(D) = \frac{D_1}{D} Gini(D_1) + \frac{D_2}{D} Gini(D_2)$$

上面的式子表示的是不确定性的大小。对于每个属性,考虑每种可能的二元划分,对于离散值属性,选择该属性产生最小Gini指数的自己作为它的分裂信息


学习推介

Andrew W. Moore PPT DTree
决策树Python实现,单独成文,网址:决策树实现
Wikipedia维基百科-Decision Tree决策树

最后,附一张决策树的优点和缺点图:


这里写图片描述

参考文献

  • [1]数据挖掘概念与技术 Third Edition,韩家伟.
  • [2]机器学习实战 ,Peter Harrington.