机器学习-决策树(ID3)

小白-学决策树

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

决策树主要有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}

年龄	工作	房子	信用评分	是否借贷
0	0	0	0	No
0	0	0	1	No
0	1	0	1	Yes
0	1	1	0	Yes
0	0	0	0	No
1	0	0	0	No
1	0	0	1	No
1	1	1	1	Yes
1	0	1	2	Yes
1	0	1	2	Yes
2	0	1	2	Yes
2	0	1	1	Yes
2	1	0	1	Yes
2	1	0	2	Yes
2	0	0	0	No

其中，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就是我们的根结点(最强特征)。

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

年龄	工作	房子	信用评分	是否借贷
0	0	0	0	No
0	0	0	1	No
0	1	0	1	Yes
0	0	0	0	No
1	0	0	0	No
1	0	0	1	No
2	1	0	1	Yes
2	1	0	2	Yes
2	0	0	0	No

其中，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|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决策树整理一下，也发出来。