[DM]分类-决策树

一、决策树

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

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

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

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

① 住在农村的客户都买了；

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

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

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)

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

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

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.剪枝

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

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

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

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

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

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

五、matlab实现

更多相关文章

随机推荐