淘先锋技术网

首页 1 2 3 4 5 6 7

小白-学决策树

什么是决策树?决策树是一种基本的分类和回归方法。

决策树主要有3种算法结构,ID3决策树-信息增益(Information Gain),C4.5决策树-增益率(gain ratio),CART决策树-基尼指数(gini index)。

首先我们先来介绍ID3决策树,这里要介绍一下“信息熵”。信息熵是判断样本集合纯度的一种指标。

Ent(D) = -\sum_{k=1}^{|y|}p_{k}log_{2}}p_{k}     其中y代表多少个类,Ent(D)的值变小,则D的纯度变高。

Gain(D,a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v}) 其中a代表属性,V代表a有多少个取值。

公式看不懂没关系,看下面的例子你们就懂了。

属性集合{年龄,工作,房子,信用评分}

年龄 {青年:0,中年:1,老年:2}    房子 {有房子:1,没房子:0}

工作 {有工作:1,没工作:0}      信用评分{差:0,良好:1,优:2}

年龄工作房子信用评分是否借贷
 000No
0001No
0101

Yes

01Yes
0000No
1000No
1001No
1111Yes
1012Yes
1012Yes
2012Yes
2011Yes
2101Yes
2102Yes
2000No

其中,Yes(正类)为9个,No(负类)为6个,先算根结点的信息熵为:

 Ent(D) = -\sum_{k=1}^{|y|}p_{k}log_{2}}p_{k}    Ent(D) = -(\frac{6}{15}log_{2}\frac{6}{15}+\frac{9}{15}log_{2}\frac{9}{15})\approx 0.971 

接下来分别计算每个属性的条件熵:

Ent(D|House) = \frac{6}{15}Ent(D|withHouse)+\frac{9}{15}Ent(D|withoutHouse)

Ent(D|withHouse) = -\frac{6}{6}log_{2}\frac{6}{6} = 0 有房子的时候都可以借贷

Ent(D|withoutHouse) = -(\frac{3}{9}log_{2}\frac{3}{9}+\frac{6}{9}log_{2}\frac{6}{9})\approx 0.9183 没房子的有3个可以借贷,6个不可以借贷

Ent(D|House) =\frac{6}{15}\cdot 0+\frac{9}{15}\cdot 0.9183\approx 0.551  

同理,我们可以算出其他3个属性的条件熵,这里就不一一计算了,相信大家都能看懂上面的计算步骤。

Ent(D|Job) \approx 0.647       Ent(D|Age)\approx 0.888     Ent(D|Credit)\approx 0.608

最后我们来计算信息增益

Gain(D|Age) = Ent(D) - Ent(D|Age) = 0.971 - 0.888 = 0.083

Gain(D|Job) = Ent(D) - Ent(D|Job) = 0.971 - 0.647 = 0.324

Gain(D|House) = Ent(D) - Ent(D|House) = 0.971 - 0.551 = 0.420

Gain(D|Credit) = Ent(D) - Ent(D|Credit) = 0.971 - 0.608 = 0.363

我们选择最大的信息增益属性为根结点,这里House就是我们的根结点(最强特征)。

接下来我们把有房子能借贷的数据删掉。

年龄工作房子信用评分是否借贷
 000No
0001No
0101

Yes

0000No
1000No
1001No
2101Yes
2102Yes
2000No

其中,Yes为3个,No为6个,先算根结点的信息熵为:

Ent(D) = -\sum_{k=1}^{|y|}p_{k}log_{2}}p_{k}    Ent(D) = -(\frac{3}{9}log_{2}\frac{3}{9}+\frac{6}{9}log_{2}\frac{6}{9})\approx 0.918

和上面一样,计算每个属性的条件熵,但是这里我们不用计算房子这个属性,因为它已经分过了。

Ent(D|Age) \approx 0.667     Ent(D|Job) = 0.000    Ent(D|Credit) \approx 0.444

同理:这三个属性的信息增益为:

Gain(D|Age) = 0.252    Gain(D|Job) = 0.918    Gain(D|Credit) = 0.474

因此,我们选择Job这个属性作为第二个分类属性,现在我们会发现我们把Yes 和 No 这两类完全分开。

决策树的图如下:

 这里你们可能会问,决策树什么时候才算完全结束:

1. 当前结点包含的样本全属于同一类别,无需划分;

2.当前属性集为空,或是所有样本在所有属性上取值相同,无法划分;

3.当前结点包含的样本集合为空,不能划分。

之后我会把C4.5 和 CART决策树整理一下,也发出来。