决策树算法

1.先举一个简单的栗子

如果想要判断一个人是否去打篮球，假设我们可以从天气情况、温度高低和此人心情三个方面去判断此人是否去打篮球，我们该如何做？

我们已知历史数据如下表，通过这些数据，我们可以预测出某个给定数据的结果。

 

数据编号	Feature1(weather)	Feature2(temp)	Feature3(pleasure)	label
01	s	h	g	y
02	s	h	b	n
03	s	m	g	y
04	r	h	b	n
05	c	m	g	y
06	r	l	g	n
07	c	l	b	n

 

 

假设判断是否去打篮球的流程如下：

那么，对于天气情况、温度高低、此人心情的优先顺序怎样确定呢？（引入问题：①如何选取最优特征？②如何构造这样一颗树？）此时，我们就应该引入”熵”的概念----香农熵：表示的是事物的混合程度。

2.了解基本概念

（1）熵---描述事物的混乱程度

熵表示的是事物的混乱程度，例如在某一堆事物中，其种类越多就越混乱，其种类越单一，其混乱程度就越低（熵值越低）。

了解熵的概念以后，下来了解一下熵如何计算？

（其中：N表示当前数据集标签个数，q表示当前标签的所占总个数的比率）

对于当前栗子而言： (Py = 3/7   Pn = 4/7)

（2）条件熵--经过某一个特征划分后，数据集的混乱程度

了解熵之后，我们来了解一下条件熵。

我对条件熵的理解是，在经过某一个特征划分之后，当前数据集的熵，表示的也是一种混乱程度。假设一个数据集经过特征F1划分过后的成为两个数据集D1和D2,D1和D2分别占比P(d1)和P(d2)

H(D|F1) = p(d1)*H(D1)+p(d2)*H(D2)

（3）信息增益

顾名思义，信息增益就是熵的改变量。在此就是H(D)-H(D|F1)

ID3决策树是通过信息增益来选择最优特征的，选择原则为信息增益最大的（即混乱程度改变最大的）就是最优特征。

但是其存在一个缺陷，对于特征值较多但每个特征值对应样本数量相对较少的特征，用其作为特征进行划分时，会出现信息增益特别大的情况，会出现误差。所以通过改进，产生了C4.5决策树---通过增益率来选取最优特征。

（4）信息增益率

在计算信息增益率之前，先了解特征熵的概念，很简单,就是当前所选特征列所对应的熵值，就拿前面的栗子来说：

 

3.算法基本流程

3.1选择最优特征：划分数据集

对每个特征，计算其对应的信息增益率，选取增益率最大的特征为最优特征。

对于某个数据集，我们应该做如下统计：

     1）统计每个类别标签所对应的LabelCount<label,Count>; ------>初始熵

     2）统计某个特征所含特征值的FeatureCount<feature,count>-->特征熵

     3）根据某个特征的不同特征值划分数据集，统计出每个特征值对应的数据集，求取该数据集的LabelCount<label,Count>--------->条件熵

    4）根据1）,2）,3）所求的数据,可得某个特征的信息增益率======>计算每个特征所对应的信息增益率=======>最优特征

3.2构造决策树：递归选择最优特征，递归构造。

（1）递归出口

1)当前节点所包含的数据集全部属于同一类===>节点类型

2)特征集合已经遍历完（无可用特征），当前节点数据集还未完全分类=======>统计出当前节点数据集的分类LabelCount,投票得出分类====>投票结果为节点类型

（2）递归过程

如果节点类型还未全部确定并且特征集合中还存在未使用特征，则递归选取剩余特征集合中的最优特征,并对未分类节点进行递归划分。

3.3测试决策树算法:输入测试数据进行测试，输出正确率。