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

zh
zh
zh
26
文章
0
评论
2020-04-1809:05:00 评论 379 3025字
摘要

决策树归纳是从有类标号的训练元组中学习决策模型。常用的决策树算法有ID3,C4.5和CART。它们都是采用贪心(即非回溯的)方法,自顶向下递归的分治方法构造。

一、决策树原理

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

二、算法优点

1.算法比较简单;

2.理论易于理解;

3.对噪声数据有很好的健壮性。

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

三、算法一般流程

1.收集数据:任意方法和途径。

2.准备数据:书构造算法只适用于标称型数据,因此数据必须离散化。

3.分析数据:构造树完成后,检查图形是否符合预测。

4.训练算法:决策树的数据构造。

5.测试算法:一般将决策树用于分类,可以用错误率衡量,而错误率使用经验率计算。

6.使用算法:决策树可以用于任何监督学习算法。

四、实例分析

1.信息熵

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

(1)熵(Entropy)的计算公式

熵定义为信息的期望值。先看看信息的定义:l(xi)=−log2p(xi)l(xi)=−log2p(xi)

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

Entropy=H(D)=E(I(D))=−∑inpilog2(pi),pi是D中任意元组属于类Ci非零概率。Entropy=H(D)=E(I(D))=−∑inpilog2(pi),pi是D中任意元组属于类Ci非零概率。

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

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

(2)信息增益计算

首先计算特征A对数据集D的经验条件熵H(D|A)H(D|A),在数学上就是条件概率分布(Condition Probability).H(D|A)=∑j|Dj||D|×H(Dj),项|Di||D|充当第j个分区的权重H(D|A)=∑j|Dj||D|×H(Dj),项|Di||D|充当第j个分区的权重引入条件熵,在信息论中主要是为了消除结果的不确定性。然后计算信息增益Gain(A)=H(D)−H(D|A)Gain(A)=H(D)−H(D|A)其中,Gain(A)Gain(A)即为所求的信息增益。下面来应用一个实例,训练元组数据D

在这里

H(D)=−914log2914−514log2514=0.940位H(D)=−914log2914−514log2514=0.940位

H(D|age)=514×(−25log225−35log235)+414×(−44log204−04log204)+514×(−35log235−25log225)=0.694位

H(D|age)=514×(−25log225−35log235)+414×(−44log204−04log204)+514×(−35log235−25log225)=0.694位

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

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

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

Gain(income)=0.029位,Gain(student)=0.151位,Gain(creditrating)=0.048位Gain(income)=0.029位,Gain(student)=0.151位,Gain(creditrating)=0.048位

2.使用信息熵计算

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

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

(1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;

(2)在树构造过程中进行剪枝;

(3)能够完成对连续属性的离散化处理;

(4)能够对不完整数据进行处理。

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

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

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

SplitH(D|A)=−∑|Dj||D|×log2(|Dj||D|)SplitH(D|A)=−∑|Dj||D|×log2(|Dj||D|)

信息增益率定义为:

GainRate(A)=Gain(A)SplitH(D|A)GainRate(A)=Gain(A)SplitH(D|A)

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

3.基尼系数Gini index

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

Gini(D)=1−∑p2i,其中,pi是D中元组数以Ci类的概率,对m个类计算和。Gini(D)=1−∑pi2,其中,pi是D中元组数以Ci类的概率,对m个类计算和。Gini指数越大,不纯度越大,越不容易区分。假设A有v个不同的值出现在特征D中,它的二元划分有2v−22v−2种(除去自己和空集)。当考虑二元划分裂时,计算每个结果分区的不纯度加权和。比如A有两个值,则特征D被划分成D1和D2,这时Gini指数为:

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

End.

作者:拾毅者

来源:『刘帝伟』维护的个人技术博客

本文均已和作者授权,如转载请与作者联系。

  • 我的微信公众号
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: