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

一、决策树原理

决策树原理很简单，通俗易懂，最简单的就是二元划分，类似于二叉树。例如只考虑某一层某个节点的划分，如果年龄大于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指数的自己作为它的分裂信息。

End.

作者：拾毅者

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

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