机器学习1：决策树

机器学习

人工智能

发布日期: 2022-07-12

文章字数: 9.6k

一、决策树的描述

决策树（decision tree）

“信息熵”是度量样本级和纯度最常用的一种指标。

热力学里有一个熵的概念，熵就是来形容系统混乱程度的，系统越混乱，熵就越大。信息熵也具有同样的意义，不过它描述的是随机变量的不确定性（也就是混乱程度）。

假定当前样本集合D中第K类样本所占的比例记作： $p_{k} (k = 1, 2, . . ., | y |)$
则它的信息熵计算公式为：
　　　　　　　　　　 $H (D) = - \sum_{i = 0}^{| y |} p_{k} l o g p_{k}$
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　因而可计算出例子中的信息熵：

从上面的计算结果中可以看出，信息熵越大，纯度越低。当集合中所有样本均匀混合时，信息熵越大，纯度越低。

信息熵计算练习：

设离散属性a有V个可能的取值{ $a^{1}$ , $a^{2}$ ,…, $a^{v}$ }
若用a来进行划分，则会产生V个分支节点
其中第v个分支节点包含了D中所有在属性a上取值为 $a^{v}$ 的样本，记为 $D^{v}$
那么可计算出属性a对样本集D进行划分所获得的“信息增益”为：
$G a i n (D, a) = H (D) - \sum_{v = 0}^{v} \frac{| D^{v} |}{| D |} H (D^{v})$
其中， $\frac{| D^{v} |}{| D |} H (D^{v})$ 也被称为条件熵

ID3决策树算法使用信息增益来构建决策树，对于所有的属性我们先选择信息增益最大的作为根节点，然后计算其他属性的信息增益再选择最大的作为子节点，一直递归调用该操作，直到信息增益很小或者没有特征为止。

ID3算法的优缺点：

信息增益比

信息增益比定义： $G a i n_r a t i o (D, a) = G_{r} (D, a) = \frac{G a i n (D, a)}{I V (a)}$

其中

I V (a) = - \sum_{V = 1}^{V} \frac{| D^{v} |}{| D |} l o g_{2} \frac{| D^{v} |}{| D |}

称为属性a的“固有值”，属性a的可能取值数目越多（即V越大），则 $I V (a)$ 的值通常就越大。

对数据信息极大的浪费

Q1：在训练时，如何在属性值缺失的情况下进行划分属性选择？
　　　
　　　Q2：在训练时，给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
　　　
　　　Q3：在预测时，若属性值缺失，如何计算？

Q1:

Q2:

若样本 $x$ 在划分属性a上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_{x}$
若样本 $x$ 在划分属性a上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a_{v}$ 对应的子结点中调整为 $\tilde{r_{v}} \times w$ (直观来看，相当于让同一个样本以不同概率划入不同的子结点中去)