【ML】决策树

一、决策树初识

决策树感性的理解就是通过构建一系列的规则把满足一定条件的数据划分到同一节点。
贷款申请表

ID	年龄	有工作	有房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

二、特征选择

特征选择在于选择对训练数据具有分类能力的特征来划分特征空间，通常特征选择的准则是信息增益或信息增益比。

• 熵

在信息论中，熵是表示随机变量不确定性的量，假设随机变量X概率分布为：
则随机变量X的熵可以表示为： 熵越大则随机变量所包含的不确定性越大。对于伯努利分布随机变量只有两个取值，则其熵可以表示为： 所以以扔硬币问题为例，出现正面和反面的概率都为0.5，则其熵为1，如果对于一个造假的硬币每次投掷都只会出现正面的话那它的熵就是0，因为其不存在不确定性。
H(Y|X)为在已知随机变量X的条件下随机变量Y的不确定性或条件熵 其中

• 信息增益

信息增益表示在知道特征X的信息以后而使得类Y的信息不确定性减少的程度。用公式表示的话就是：

上式的含义是在以特征A对进行数据集和D进行划分时，划分前数据集D的信息熵为H(D)，而H(D,A)为划分后数据集D的条件熵，他们的差即为信息增益（互信息），也是特征A对数据集D不确定性的减少量。所以一个特征如果他的信息增益越大则改特征的分类能力也越强。

这里我们以贷款数据为例计算各个特征的信息增益，数据集D的信息熵为： （1）年龄

(2) 工作

(3)房子

(3)信贷

所以比较上面计算的所有特征在信贷中信息增益，有没有房子的信息增益最大所以选择有没有房子作为划分特征

• 信息增益率

由于信息增益对于可取值数目较多的属性有所偏好，比如我们如果以信贷数据中的ID作为特征的话则其对应的信息增益为0.97，远大于其它划分属性，但是它对于新样本无法进行有效的预测。信息增益率可以有效的解决这一问题。

其中G(D,A)为信息增益,H_A(D)数据集D关于特征A的信息熵

n为特征A取值的个数 。

三、经典决策树算法

1、ID3

ID3算法根据信息增益准则进行特征的选择
—————————————————————————————
Input：训练数据D={(x1,y1),(x2,y2),....,(xn,yn)}
特征集A={a1,a2,...,an}
Output：决策树T
Algorithm:
(1) 生成节点node
(2) 如果D中样本属于同一个类，将node标识为C类也节点
(3) 如果A为空
(4)计算所有特征的信息增益，选择信息增益最大的特征a作为划分属性
(5)按照
—————————————————————————————

2、C4.5

3、CART

四、剪枝

参考资料

• 1.统计学习方法(李航)
• 2.机器学习(周志华)