决策树(Decision Tree)
决策树算法是干什么的?
什么叫信息熵
信息熵可以描述为未知事件(可以看做概率中的事件)可能含有的信息量。香浓给出信息熵的计算公式:
对于一个系统变量X={x1,x2,x3,,,,,xn},(x1,x2,,,,,xn可以看做是这个系统的所有类别信息),系统的计算公式为(单位为:比特-bit):
信息的增益:假设一个保持稳定的时候其信息熵为T1,增加了一个变量,信息熵变为T2,那么信息增益就可以表示为T2-T1。
1、决策树的定义
首先,它是一个树形结构,用二叉树或者多叉树来表示都可以。这个树的叶子节点(没有子节点的节点)就表示类别信息,每个非叶子节点就表示特征属性。通过不同的特征属性的判断,最终找到由这些特征决定的类别信息。
2、决策树的构造
一个决策树构造的例子
决策树生成算法中著名的是ID3算法。用一个例子来说明如何用ID3算法构造决策树。
假设一个样本数据集如下表所示(摘自网络):
在这个表中可以看到,:
(1)数据集分成了两个类:类1和类2;
(2)类1的个数为9,类2的个数为5;
(3)未做决策树分类时的总信息熵为:
(4)现在来计算信息的增益
(4.1)假设只用属性1来做分类,那么样本集被分成了三个分支(A,B,C),
那么各个分支的信息熵为:
那么按照此属性做划分后的信息熵需要乘以每个分支的权重,就得到在此属性情况下的信息熵:
那么信息的增益为
(4.2)假设只用属性3来做分类,那么样本集被分成了两个分支(真,假),
那么信息增益的计算过程如下:
(4.3)由于属性2的值不同于属性1和属性3,其在一个连续的区间段内取值,如果对于每个取值都计算一次熵,当取值很多的时候,必然会导致计算量很大。一个解决办法是对区间进行二分类,例如大于某个值的分到一边,小于这个值的分到另外一边。然后根据这个值计算属性的熵。例如,对于本例,属性2的取值包括{65,70,75,78,80,85,90,95,96},一个典型的做法是采用贪心算法(会在另外一篇文章中介绍!)。这里我们只列出两个可能的取值,不如说取80或者取75,到底取哪个呢?
如果取80,那么就把样本集分成两个分支:
那么信息增益的计算过程如下:
同理,取75的时候,信息增益的计算过程如下:
通过比较两个信息增益,可以发现,当取80的时候是合适的,因为增益大。
(4.4)通过比较(4.1)、(4.2)、(4.3)的结果发现,将属性1作为根节点,那么就得到如下的初始树
从这个树种可以看到,中间的一个,当判断属性1是B的时候,直接输出类1,那么这个就确定了,但是对于另外两个分支却不行,还要分别对每一个分支选择合适的节点做分类。例如,对于最左边的分支,分别计算属性2和属性3的增益,其结果为:
所以选择属性2作为节点,那么就得到如下的树
(4.5)同理,对最右边的分支做计算,得到如下的分类树
3、分类
假设突然来了两个新的样本
(属性1=A,属性2=75,属性3=假)
(属性1=C,属性2=90,属性3=真)
那么很显然,根据上面的树,第一个属于类1,第二个属于类2
我只是理解一个皮毛,如果正真想玩玩整整的写一写来龙去脉,会占用很多时间,这个是引子。
其中(4.1)-(4.5)是一个递归的过程。