ID3算法
决策树是如何工作的
一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应一个属性测试；每个结点包含的样本根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的每个叶结点的路径对应一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，也就是能够处理未见实例的决策树。
ID3算法介绍
ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法，即Iterative Dichotomiser 3，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法。
在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
信息熵与信息增益
在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。在认识信息增益之前，先来看看信息熵的定义
熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。
假如一个随机变量$X$的取值为$X={x_1,x_2,…,x_n} $，每一种取到的概率分别为${p_1,p_2,…,p_n}$，那么$X$的熵定义为
意思是一个变量的变化情况可能越多，那么它携带的信息量就越大。
对于分类系统来说，类别$C$是变量，它的取值是${C_1,C_2,…,C_n}$，而每一个类别出现的概率分别是
而这里的$n$就是类别的总数，此时分类系统的熵就可以表示为
以上就是信息熵的定义，接下来介绍信息增益。
信息增益是针对一个一个特征而言的，就是看一个特征$t$，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即信息增益。在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。
假设当前信息的熵为$Entropy(S)$，划分后的信息熵为$Entropy(S|T)$，代表在特征属性$T$的条件下样本的条件熵。那么最终得到特征属性$T$带来的信息增益为
信息增益的计算公式如下
其中$S$为全部样本集合，$value(T)$是属性$T$的所有取值的集合，$v$是$T$的其中一个属性值，$S_v$是$S$中属性$T$的值为$v$的样例集合，$|S_v|$为$S_v$中所含样例数。
在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。以上就是ID3算法的核心思想。
决策树停止的条件
- 该群数据的每一个数据已经归类到每一类数据中，即数据已经不能继续再分
- 该群数据已经找不到新的属性进行节点分割
- 该群数据没有任何未处理的数据
ID3算法实现
阅读$sklearn$官方文档可知，$sklearn$的决策树仅仅是实现了$cart$树而已，
当信息计算方式为$Gini$，$Entropy$，就用来分类。注意，$sklearn$并没有实现$ID3$，但是$cart$中使用$entropy$的效果，等效于“二叉树的$ID3$”，因为$ID3$可以是“二叉决策树”，也可以是“多叉决策树”，所以$sklearn$使用决策树+$entropy$方式时，无法实现“基于$ID3$算法的多叉决策树”。
https://scikit-learn.org/stable/modules/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart
参考文章：
