决策树

<统计学习>李航

信息论一些概念:

熵entropy

• 定义:表示对随机变量(X)不确定性的度量
• 熵只依赖于X的分布,与X取值无关
• 从公式可看出,熵与X的不确定性成正比

决策树算法3要素

• 特征选择
• 决策树生成
• 决策树剪枝

特征选择**key

特征分类准则:有3种

• 信息增益（ID3）

  • 定义： 以某特征划分数据集前后的熵的差值

      在熵的理解那部分提到了，熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以**使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏**。
    
      划分前样本集合D的熵是一定的 ，entroy\(前\)，
    
      使用某个特征A划分数据集D，计算划分后的数据子集的熵 entroy\(后\)
    

    信息增益 = entroy(前) - entroy(后)

    书中公式:

    

    做法：

    计算使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

    信息增益的理解：

    对于待划分的数据集D，其 entroy(前)是一定的，但是划分之后的熵 entroy(后)是不定的，entroy(后)越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因此 entroy(前) - entroy(后)差异越大，说明使用当前特征划分数据集D的话，其纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的集合，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

    缺点

    ：信息增益偏向取值较多的特征

    原因

    ：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。

• 信息增益比(C4.5)

• Gini系数(CART - 分类树)

决策树常用算法

ID3

C4.5/C5.0

CART