经典机器学习模型——决策树(Decision Tree)

  |   0 评论   |   2,281 浏览

背景知识

信息熵

参考《信息熵

信息增益(information gain)

参考《信息增益

Gini系数

参考《Gini Index

决策树

决策树是一种树型结构,其中每个内部结点表示在一个属性上的测试,每个分支代表一个测试输出,每个叶结点代表一种类别。

基本思路

以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶节点中的实例都属于同一类

以贪心法(greedy strategy)来选择每一个分裂的节点

示例

儿童认识动物的过程

3.png

构建过程

对于打网球问题

image.png

如果我们选择Wind作为分裂的特征

计算不同特征值的分类结果

image.png

计算信息增益

4.png

同理计算出其它特征对应的信息增益

image.png

根据上图,我们可知Gain(S, Outlook)应该作为第一个分支节点

重复上一步,直到收敛

根据不同的特征值,可以将记录划分到下一层级

5.png

依次类推,最终就可以得到下面的决策树

image.png

决策树学习的生成算法

建立决策树的关键,即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数,建立决策树主要有以下三种算法。

一个属性的信息增益(或信息增益率、 Gini系数的降低值)越大,表明属性对样本的熵减少的能力更强,这个属性使得数据由不确定性变成确定性的能力越强

ID3(Iterative Dichotomiser)

直接使用信息增益/互信息g(D,A)作为判断分裂节点的依据

取值多的属性,更容易使数据更纯 ,其信息增益更大。

训练得到的是一棵庞大且深度浅的树:不合理

C4.5

使用信息增益的问题:假如使用样本的序号作为分类依据,则信息增益最大,但样本太多

使用信息增益率作为分裂依据

CART(Classification And Regression Tree)

使用基尼信息作为分裂依据

使用Gini Index指导Split——Gini Split

image.png

Misclassification Error

image.png

计算方法

image.png

二分法的纯净度

image.png

离散化(Discretization)

对于连续的数据,需要先进行离散化,然后再做分裂

离散化成有序的分类属性

image.png

二元决策(Binary Decision)

a < v或者a ≥ v

分裂的依据

基于特征的类型

  • Nominal

  • Ordinal

  • Continuous

基于要分裂的分支数目

  • 二分支

  • 多分支

分裂方法(Splitting)

二分法

例如,对于有三个值的特征,如何分为两类?

image.png

多分法


鸢尾花数据决策树

iris.png


读后有收获可以支付宝请作者喝咖啡