西瓜书读书笔记

chapter4-决策树

4.1基本概念

​ 决策树是一种常见的机器学习分类方法，在分类任务为例，在若干轮决策过程后对样本进行分类，这是一种非常自然的思考过程，以树结构来进行决策、判定。如下图所示：

​ 其中，非叶节点为属性测试，叶节点为样本分类，决策树训练的目的是为了产生一一棵泛化能力强，对未见过样本分类能力强的决策树。

4.2划分选择

4.2.1信息增益

​ 我们现有的信息熵公式$Ent(D)=-\sum_\limits{k=1}^\limits{|y|}p_klog_2{p_k}$，其中y定义为样本分类的种类。

​ 对于信息增益的示意是：对某个离散属性$a$在样本集合$D$上进行划分，产生$V$个分支节点，我们可以算出在$a$下进行划分的样本$D^v$的信息熵，并且根据分支节点中所包含样本数的不同给分支节点赋予权重$|D^v|/|D|$，样本数越多分支结点影响权重越大，于是计算出“信息增益”:
$$
Gain(D,a)=Ent(D)-\sum_\limits{v=1}^\limits{V}Ent{D^v} \tag{4.2}
$$
​ 一般来说，信息增益越大，说明使用属性$a$来进行划分获得的纯度提升更大(purity)，也即为分类属性的区分度高。例如著名的ID3决策树学习算法就是以信息增益为准则划分属性。

​ 值得注意的是决策树每层划分都要基于不同的分类节点重新计算信息增益。

4.2.2增益率

​ 我们时常忽略样本编号这一属性，是因为该属性不具有泛化能力，无法对新样本提供有效预测。

​ 实际上信息增益会具有某些属性的“偏好性”，为了减少这种影响，C4.5决策树算法采用增益率来选择最优划分属性。
$$
Gain_ratio(D,a)=\frac{Gain(D,a)}{IV{a}}\tag{4.3}
$$
其中
$$
IV(a)=-\sum_\limits{v=1}^\limits{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} \tag{4.4}
$$
$IV(a)$称为$a$属性的固有值，属性a，可能取值数目越多，则$IV(a)$值会增大。增益率准则(未完待续)