小白-学决策树

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

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

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

     其中y代表多少个类，Ent(D)的值变小，则D的纯度变高。

 其中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个，先算根结点的信息熵为：

      

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

 有房子的时候都可以借贷

 没房子的有3个可以借贷，6个不可以借贷

  

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

            

最后我们来计算信息增益

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个，先算根结点的信息熵为：

    

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

         

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

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

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

决策树的图如下：

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

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

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

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

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