ID3

作者: zhouycoriginal | 来源:发表于2020-02-04 13:25 被阅读0次

决策树和随机森林
机器学习之旅—决策树(3)
决策树简记
决策树基本要点及方法对比
ID3
decision tree
JS简单实现决策树(ID3算法)
（14）监督学习-分类问题-决策树
「数据分类」14决策树分类之CART算法
day10-决策树

基于信息增益(Information Gain)的ID3算法

ID3算法的核心是在各个结点上应用信息增益准则来进行特征选择，以此递归的构建决策树，具体方法是：从根结点开始，对结点计算所有可能的信息增益，选择信息增益最大的特征作为该结点的特征，结点的信息增益根据样本的标签进行计算。

信息增益

熵

信息增益与熵(entropy)有关，在概率论中，熵是随机变量不确定性的度量，熵越大，随机变量的不确定性就越大；假设 $X$ 是取有限个值的离散随机变量，其概率分布为：
$P(X=x_i)=p_i,i=1,2,3,...,n$
则，熵的定义为：
$H(X)=-\sum_{i=1}^{n}p_i*\log{p_i}$ 一般取自然对数 $e$ 为底数
值得注意的是，熵实际上是随机变量 $X$ 的分布的泛函数，它并不依赖 $X$ 的实际取值，而仅仅依赖 $X$ 的概率分布，所以它又可以被记作：
$H(p)=-\sum_{i=1}^{n}p_i*\log{p_i}$
其中, $n$ 表示 $X$ 的 $n$ 种不同的取值, 这个值一般是离散的. $p_i$ 表示为 $X$ 取到值为 $i$ 的概率. $log$ 一般是自然底数
例子:

条件熵

多个变量的熵叫联合熵, 比如两个变量 $X,Y$ 的联合熵就表示为:
$H(X,Y)=-\sum_{i=1}^{n}p_{(x_i,y_i)}\log p_{(x_i,y_i)}$
类似于条件概率,熵同样也存在着条件熵, 条件熵描述了知道某个变量以后, 剩下的变量的不确定性, 其表达式如下:
$H(X|Y)=-\sum_{i=1}^{n}p_{(x_i,y_i)}\log p(x_i|y_i)$

信息增益

$H(X)$ 度量了 $X$ 的不确定性, $H(X|Y)$ 度量了知道 $Y$ 后, $X$ 的不确定性, 那么 $H(X)-H(X|Y)$ 度量的可以理解为:知道 $Y$ 的基础上, $X$ 不确定性减少的程度,我们记为 $I(X,Y)$ ,如图:

更多理解

假定当前样本集合 $D$ 中,第 $k$ 类样本所占比例为 $p_k(k=1,2,3...,|y|)$ , 则 $D$ 的信息熵定义为:
$Ent(D)=-\sum_{k=1}^{|y|}p_k \log p_k$
假定离散属性 $a$ 有 $V$ 个可能的取值 ${a^1,a^2...a^v}$ , 若使用 $a$ 来对样本集进行划分,则会产生 $V$ 个分支结点, 也就是说, ID3构建的决策树, 是多叉树, 那么它的信息增益就是
$Gain(D,a) = Ent(D)-\sum_{v=1}^{V} \frac{|D^v|}{|D|}Ent(D^v)$
比如: 一个二分类数据集, 包含17个样本, 其中正例为8,反例为9,那么, 数据集 $D$ 的信息熵为:
$Ent(D)=-(\frac{8}{17}\log \frac{8}{17}+\frac{9}{17}\log \frac {9}{17})$
对于变量 $a$ ,他有三个取值, 那么它可以将数据集划分为三个子集: $D^1,D^2,D^3$ , 其样本里分别为6,6,5, 这三个自数据集中, 正负样本分别为(3,3) (4,2),(1,4), 这三个分支结点的信息熵为为:
$Ent(D^1)=-(\frac{3}{6} \log \frac{3}{6}+\frac{3}{6} \log \frac{3}{6})$
$Ent(D^2)=-(\frac{4}{6} \log \frac{4}{6}+\frac{2}{6} \log \frac{2}{6})$
$Ent(D^3)=-(\frac{1}{5} \log \frac{1}{5}+\frac{4}{5} \log \frac{4}{5})$
那么变量 $a$ 的信息增益为:
$Gain(D,a)=Ent(D)-\sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v)$

ID3 步骤

ID3使用信息增益来决策当前树结点该使用那个变量来构建决策树, 显然,信息增益越大的, 就越能更有效的区分特征(变量)与预测标签之间的关系.
输入 $m$ 个样本,每个样本有 $n$ 个离散的特征,令特征集合为 $A$ ,输出决策树 $T$

判断样本是否为同一类别, 如果是, 则返回树T
判断特征是否为空, 是, 则返回树T
计算A中, 各个特征的信息增益,选择最大的信息增益特征,记为 $i$
按特征 $i$ 的不同取值, 将对应的样本分成不同类别,每个类别产生一个子结点,对应的特征值为 $i_j$
重复上述步骤直到结束

ID3算法的缺点

无法处理连续的特征
采用信息增益更大的特征优先建立决策树, 但相同的数据集下, 取值较多的特征值比取值较少的特征值信息增益更大
没有考虑缺失值
过拟合问题

决策树和随机森林
随机森林和GBDT算法的基础是决策树而建立决策树的算法由很多，ID3，C4.5,CART等， ID3：ID3算法...
机器学习之旅—决策树(3)
从 ID3 到 C4.5 ID3 定义 ID3 算法的核心是在决策树各个子节点上应用信息增益准则选择特征，递归的构...
决策树简记
具有不同划分准则的算法决策树原理剖析及实现(ID3)理解决策树算法(实例详解)-ID3算法与C4.5算法 ID3（...
决策树基本要点及方法对比
决策树的生产，基本方法有ID3、C4.5、CART。基于基础决策树学习器，可进一步构建提升树。 ID3 ID3算法...
ID3
基于信息增益(Information Gain)的ID3算法 ID3算法的核心是在各个结点上应用信息增益准则来进行...
decision tree
ID3 C4.5 CART 比较 ID3（以信息增益为准则选择信息增益最大的属性）缺点信息增益对==可取值数目...
JS简单实现决策树(ID3算法)
推荐阅读:ID3算法 wiki决策树算法及实现完整示例代码:JS简单实现决策树(ID3算法)_demo.html ...
（14）监督学习-分类问题-决策树
决策树算法分为ID3，C4.5，CART几种。其主要区别在于特征选择的方法不同。 1、 ID3 特征选择方法...
「数据分类」14决策树分类之CART算法
1.CART算法与ID3算法对比（1）CART算法解决了ID3算法的不足，既能用于分类问题，又能用于回归问题。 ...
day10-决策树
今天学了决策树的基本知识。基于信息论的决策树算法有：ID3, CART, C4.5等算法。 ID3 算法是根...

ID3

基于信息增益(Information Gain)的ID3算法

信息增益

熵

条件熵

信息增益

更多理解

ID3 步骤

ID3算法的缺点

相关文章

决策树和随机森林

机器学习之旅—决策树(3)

决策树简记

决策树基本要点及方法对比

ID3

decision tree

JS简单实现决策树(ID3算法)

（14）监督学习-分类问题-决策树

「数据分类」14决策树分类之CART算法

day10-决策树

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读