统计学习方法 CHAPTER5 决策树

韩好学

742人浏览 · 2022-02-27 16:31:42

韩好学 · 2022-02-27 16:31:42 发布

开始入门机器学习有关知识，在这里发文的目的一是来记录主要的知识点，二是熟悉一下CSDN的发文操作，方便后续的更新。

信息增益：

熵（entropy）：是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：

$P\left ( X = x_{i}\right ) = p_{i} , i = 1,2,3,...,n$

则随机变量X的熵定义为：

$H\left ( X \right ) = -\sum_{i = 1}^{n}p_{i}logp_{i}$

熵越大，随机变量的不确定性越大。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望

$H(Y|X) = \sum_{i=1}^{n}p_{i}H(Y|X=x_{i}),p_{i}=P(X = x_{i}),i=1,2,...,n$

H(Y|X=xi)表示Y对于X等于特定的数值的情况下取熵。

当熵和条件熵中的概率由数据估计得到是，所对应的熵与条件熵分别称为经验熵(empirical entrop)和条件经验熵(empirical conditional entropy)。此时，如果有概率0，令0log0=0.

信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D) 与特征A给定条件下D的经验条件熵H(D|A)之差，即：

$g(D,A) = H(D)-H(D|A)$

一般地，熵与条件熵的差称为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益依赖于特征，不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。根据信息增益准则选取特征的方法是：对训练数据集D，计算其每个特征的信息增益，并且比较他们的大小，选择信息增益最大的特征。

信息增益的算法：

输入：训练数据集D和特征A；

输出：特征A对训练数据集D的信息增益g(D,A)。

信息增益比(information gain ratio)：

特征A对训练数据集D的信息增益比定义为其信息增益与训练数据集D关于特征A的值的熵之比，即：

$g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D))}$

其中

$H_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}log_{2}\frac{|D_{i}|}{|D|}$

n是特征A取值的个数。

ID3算法：

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点（root node）开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树。但是ID3算法仅有树地生成，所以该算法生成的树容易产生过拟合。

输入：训练数据集D，特征值A阈值；

输出：决策树T。

C4.5算法：

C4.5算法跟ID3算法类似，其对ID3算法进行了改进。C4.5算法在树的生成过程中，用信息增益比来选择特征。

输入：训练数据集D，特征值A阈值；

输出：决策树T。

决策树的剪枝：

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设树的叶结点个数为|T|，t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个，k=1,2,...,K,Ht(T)为叶结点的经验熵，α≥0为参数，则决策树学习的损失函数定义为：

$C_{\alpha }(T)=\sum_{t=1}^{|T|}N_{t}H_{t}(T)+\alpha|T|$