简单介绍

决策树是一个非常常见并且优秀的机器学习中监督学习的算法,它易于理解、可解释性强,是一种简单且广泛使用的分类器。通过数据来训练该预测模型,从而高效对未打标签的数据进行分类。因此简单来说那,决策树就是可以看做一个if-then规则的集合。我们从决策树的根结点到每一个都叶结点构建一条规则,根据数据不同的输入选择下一个结点,直到达到了最终的叶结点。

ID3算法核心

知晓了决策树实现的功能之后,假如我们构建决策树,那么应该如何选择属性特征值呢。如上图所示,怎么判断出纹理这个特征就是树的根节点,为何不是触感,而色泽又凭什么要排在根蒂结点之后。这个问题也就是决策树学习的关键。其实就是选择最优划分属性,希望划分后,分支结点的“正确性”越来越高。如何计算该特征的正确性即为区分不同决策树的关键,下面就要引入一个信息的度量概念,信息增益,而ID3决策树在构建树的过程中,就是以信息增益来判断的。

香浓理论中的信息熵是度量样本集合不确定度(纯度)的最常用的指标。而在ID3算法中,我们采取信息增益这个量来作为纯度的度量。我们选取使得信息增益最大的特征进行分裂!信息熵是代表随机变量的复杂度(不确定度),条件熵代表在某一个条件下,随机变量的复杂度(不确定度)。而我们的信息增益恰好是:信息熵-条件熵。

数据的( Ck表示集合 D 中属于第 k 类样本的样本子集 )信息熵公式为: