决策树

ryluo 2020-08-22 20:18:50

熵和条件熵

决策树是机器学习算法中非常经典的一个算法,既可以用来分类也可以用来回归,经常被作为基学习器用于集成学习,下面总结一下决策树的基本原理,包括ID3,C4.5算法。

由于决策树中节点特征的选择使用到了信息论中的一些基本概念,先复习一下熵的基本概念。

熵,度量了事件的不确定性,熵越大说明事件越不确定,对于随机变量$X$的熵可以定义为:

其中$n$表示了事件$X$有$n$种不同的离散取值,$p_i$表示$X$取值为$i$的概率。条件熵$H(Y|X)$表示已知随机变量$X$的情况下随机变量$Y$的不确定性,定义为$X$给定的条件下条件概率分布的熵对$X$的数学期望:

这里的$p_i=P(X=x_i), i=1,2,…,n$。


信息增益及ID3

$H(X)$度量了事件$X$的不确定性,$H(Y|X)$度量了已知$X$之后剩下的不确定性,那么$H(X)-H(X|Y)$表示$X$在知道$Y$之后不确定性的减少,这个表达式被叫做信息增益,而ID3算法的核心思想就是通过计算每个特征的信息增益确定最终以哪一个特征对节点上的样本进行划分,首先对信息增益进行表示:

为了更好的理解信息增益,下面举一个具体的例子进行理解:

image-20200822205525030

上图中是某个数据集中的某个特征的信息增益,其实数据中的特征数量可能很多,需要通过统计每个特征的每个取值的一些概率值计算每个特征的信息增益,进而选择信息增益最大的特征对数据进行划分

实际上直接使用信息增益最大的特征来分割数据是不妥的,因为使用这种方法进行分割会使得每次都是偏向取值较多的特征,所以对于这个C4.5算法使用信息增益比来优化ID3算法的一个缺陷。


C4.5算法

特征A对数据D的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练集D中特征A的熵$H_A(D)$之比即:

其中,$g(D,A)$表示的是信息增益,$H_A(D)=\sum_{i=1}^n \frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$, $n$表示的是特征$A$的取值,$|D_i|$表示特征的第i个取值的样本个数,$|D|$表示样本总数。由于特征值越多的特征其熵值越大,所以在信息增益的基础上除以该特征的熵值可以一定程度上矫正信息增益偏向特征值多的特征上。

C4.5就是使用上述定义的信息增益比来选择用来划分的特征。


决策树的生成

上面介绍了ID3和C4.5选择分裂特征分别是使用信息增益和信息增益比,下面主要来介绍一下这两种算法如何生成一棵决策树。

ID3

  1. 若D中所有实例属于同一类$C_k$,则T为单节点数,并将类$C_k$作为该节点的类标记,返回T
  2. 若$A=\emptyset$,则T为单节点树,并将D中实例数最大的类$C_K$作为该节点的类标,返回T
  3. 否则,使用信息增益公式计算每个特征的信息增益,选择信息增益最大的特征$A_g$
  4. 如果$A_g$的信息增益小于阈值$\epsilon$,则置T为单节点树,并将D中实例数最大的类$C_K$作为该节点的类标,返回T
  5. 否则,对$A_g$的每一个可能值$a_i$,按照$A_g=a_i$将D分割为若干非空子集$D_i$将D中实例数最大的类作为标记构建子节点,由节点及其子结构构成树T,返回T
  6. 对于第i个子节点,以$D_i$为训练集,以$A-\{A_g\}$为特征集递归的调用1-5步骤,得到子树$T_i$,返回$T_i$。

C4.5

  1. 若D中所有实例属于同一类$C_k$,则T为单节点数,并将类$C_k$作为该节点的类标记,返回T
  2. 若$A=\emptyset$,则T为单节点树,并将D中实例数最大的类$C_K$作为该节点的类标,返回T
  3. 否则,使用信息增益比公式计算每个特征的信息增益比,选择信息增益比最大的特征$A_g$
  4. 如果$A_g$的信息增益比小于阈值$\epsilon$,则置T为单节点树,并将D中实例数最大的类$C_K$作为该节点的类标,返回T
  5. 否则,对$A_g$的每一个可能值$a_i$,按照$A_g=a_i$将D分割为若干非空子集$D_i$将D中实例数最大的类作为标记构建子节点,由节点及其子结构构成树T,返回T
  6. 对于第i个子节点,以$D_i$为训练集,以$A-\{A_g\}$为特征集递归的调用1-5步骤,得到子树$T_i$,返回$T_i$。


由于CART算法用的更加的广泛,打算对于CART算法的分类与回归单独写一次笔记。

参考文献:
刘建平博客(非常推荐):https://www.cnblogs.com/pinard/p/6050306.html

《统计学习方法》