机器学习1：决策树

机器学习

人工智能

发布日期: 2022-07-12

文章字数: 1.2k

一、决策树的描述

决策树（decision tree）

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

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

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

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

信息熵计算练习：

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

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

ID3算法的优缺点：

信息增益比

信息增益比定义：$Gain_ratio(D,a)=G_r(D,a)=\frac{Gain(D,a)}{IV(a)}$

其中

$IV(a)=-\sum\limits_{V=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$

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

　　　对数据信息极大的浪费

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

Q1:

Q2:

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

Q3: