[DM]分类-决策树

一、决策树

所谓决策树,就是自顶而下树形的结构每一个节点都是一个属性。用决策树解决问题就是根据数据属性一层一层做决策的过程

好处:结构清晰,模仿人类思考的流程。

以下为某商品经过推销后,收集回来的客户信息,包括居住地区、住房类型、收入、是否老客户四种属性,最后一列代表该客户买没买。

[DM]分类-决策树

1.用树状的结构表示上面的信息表格,我们能分析出那些规律?

[DM]分类-决策树

①   住在农村的客户都买了

②   住在郊区的低收入人群比高收入人群更喜欢本商品

③   住在城里的客户,买过一次就不会再买了。

2.换一种属性顺序来划分,决策树也可以像下面这样:

决策树不唯一。

我们可以看到根据不同属性先后划分时,树有不同的形态,所以我们的目标时选取能表现样本数据规律,且最简单的树。

3.奥卡姆的剃刀

现在有两个理论或者两个模型,性能是一样的,我们通常会选择比较简单的那个。越复杂的模型,参数和假设就会越多。

奥卡姆的剃刀认为这些多余参数设置和假设是不必要的,如果不影响做判断,剃刀就把参数、假设剃掉


二、信息熵增益

1.信息熵

信息熵用于衡量系统的不确定性,用下面的式子表示。

14条商品信息,9条商品被买走了,5条没买,那么此时样本集S的信息熵为

当样本被分为50%和50%时信息熵最大,信息熵最大值为1,表示该样本集最不确定

2.信息熵增益

当用一个属性A对样本进行划分时,用属性A划分样本集S后所得的信息增益为

结合上表根据“居住地区“划分,样本集S的信息熵增益为:

根据“收入“划分,样本集S的信息熵增益:

0.247>0.152,说明属性“居住地区“对于分类提供的信息越大


三、ID3算法

ID3算法的目的是基于已知数据建立一个最简单的决策树

ID3的基本思想强大的属性先分,也就是对信息熵增益大的属性优先对样本进行划分。

ID3算法流程

以如下数据为例,介绍ID3算法流程。

ID3 matlab方法:

function [ tree ] = id3( examples, attributes, activeAttributes )

examples:树杈,id3方法就是对examples分叉。

attributes:属性标签:“天气“,”是否周末”,”是否促销“,”销量“

activeAttributes:激活属性标签,该开始“天气“,”是否周末“,”是否促销“都为激活属性标签

1.对当前样本的集合,计算当前样本信息熵计算所有属性的信息增益

本例中,样本集中销量“高“的记录为18个,销量”低“的记录为16个

天气属性的信息熵计算

天气“好“中:销量”高“11条,销量”低“6条。(11,6)

天气“不好“中:销量”高“7条,销量”低“10条。(7,10)

[DM]分类-决策树

[DM]分类-决策树

[DM]分类-决策树

计算“天气“属性的信息熵增量

[DM]分类-决策树

同理,“是否周末“、”是否促销“的信息熵增量

[DM]分类-决策树

[DM]分类-决策树

2.选择信息增益最大的属性作为测试属性,把测试属性取值相同的样本划分为同一个子样本集

根据上一步计算结果知,“是否周末”属性的信息增益最大(0.139394)所以决策树第一层用“是否周末“划分,example划分结果为

example_0(不是周末):(销量低,销量高)(7,13)

example_1(是周末):(销量高,销量低)(11,3)

在以后的分类中,我们就不再用“是否周末“属性进行划分。“是否周末”也就不是activeAttributes了

3.若子样本集的类别属性只含有单个属性,则分支为叶子节点,判断其属性值并标上响应的符号;

叶子节点为决策树最末端的节点,本例中,如果叶子节点销量低的个体多,叶子节点value设为false,反之设为true

否则对子样本集递归调用本算法。

决策树是按属性一层一层往下划分的,经常会用到递归的思想

tree.left= id3(examples_0, attributes, activeAttributes);

tree.right= id3(examples_1, attributes, activeAttributes);


四、Overfitting

过学习是指:两个分类器A、B,在训练集时,A的误差小于B。在测试集时,B的误差反而小于A。那么我们就说A过学习了

比如,在学校念书的时候A的学习成绩比B好,在社会上工作时候B的业绩反而比A好。

在决策树“生长“时,为了不让它长的太长,我们可以设置生长限制,让他长到一定层数就停下来,或者等决策树生长完毕再剪枝

1.剪枝

决策树中剪枝并不是把数据剪掉,而是把末端的树叶往上合并,如下图

[DM]分类-决策树

把末端的紫叶和红叶合并为一个红叶。

2.给信息增益添加惩罚项

如果某种属性把数据分的过细,虽然样本在该划分规则的信息增益很大,但对目标属性的划分的实际意义也特别差。

所以在根据属性A对样本集S划分时,我们在公式中加入一个惩罚量,来实现信息熵增益指标的改进。

[DM]分类-决策树

A属性对样本划分的越细,惩罚量值越大,信息增益也就越小。

[DM]分类-决策树


五、matlab实现

[DM]分类-决策树


上一篇:设计模式C++学习笔记之五(Factory Method工厂方法模式)


下一篇:网络通信异常