数据挖掘算法——ID3（决策树）
决策树模型：用于对数据进行分类从而实现对数据的预测目标。该决策树方法基于训练集的数据构建初始决策树模型，在模型性能无法满足要求时，则通过识别训练集中存在的分类错误并引入新的异常样本重新训练模型直至达到预期效果。该决策系统由一系列关键组件共同构成包括核心决策节点、分支路径以及最终结果类别等要素。在该系统中根节点位于顶端代表问题核心或初始判断标准；后续分支则代表不同判断结果导向；而末端叶节点则对应最终分类结果或稳定判断结论。整个系统中每个核心判断节点都对应着一个特定的问题变量或评估标准通常与待分类对象的关键属性相关联；每条分支则对应着针对单一变量的不同取值结果导向；最终每片叶子都代表着一种明确的分类归属或稳定判断依据。
Ross Quinlan 开发的 ID3（Iterative Dichotomiser 3）是一种分类预测算法；它主要用于从数据集中构建决策树。该算法遵循信息论的基本原理，并采用 信息熵 和 信息增益 作为评估依据。从而实现了对数据进行归纳分类的能力。
Ross Quinlan 开发的 ID3（Iterative Dichotomiser 3）是一种分类预测算法；它主要用于从数据集中构建决策树。该算法遵循信息论的基本原理，并采用 信息熵 和 信息增益 作为评估依据。从而实现了对数据进行归纳分类的能力。
预备知识
- 信息的定量描述：衡量信息多少的物理量称为** 信息量** 。
- 若消息发生的概率较大，则此消息所携带的信息量相对较小；
- 若某事件发生的可能性很低，则此事件所传达的信息量相对较高。
信息量的概念：当消息x发生的概率是 p 时，则该消息所携带的信息量可表示为：I= -\log_{b} p 其中，默认情况下假定所采用对数的基础值大于1。特别地，在使用二进制系统时，默认采用以2为底的对数，并将单位命名为比特（bit），即 binary unit, 符号表示位
比如抛一枚均匀的硬币想知道抛硬币后得到正面或反面所携带的信息量是多少吗？由于出现正面和反面的概率都是0.5因此我们可以计算得到I(正) = -\log_2 \frac{1}{2} = 1 \text{b}同样地I(反) = -\log_2 \frac{1}{2} = 1 \text{b}
信源所携带的信息量定义为其消息集合的期望值。香农将其命名为信息熵(entropy)。即各属性平均携带的信息量。对于m个属性构成的集合其平均信息量为：
H(X) = \sum_{i=1}^mp(x_i)I(x_i) = -\sum_{i=1}^mp(x_i)\log_2p(x_i)
一次公平硬币抛掷的信息熵等于多少？
当 H(x)=0 时，则表示数据集 X 被完美地区分（即所有样本仅属一个类）。ID3算法会对每个特征进行信息熵的计算，在本次迭代中选择 最低信息熵 的特征来进行数据划分。
-
self-information under conditions:
当事件y_j发生时，在给定条件下随机事件x_i的概率表示为p(x_i | y_j)；其被定义为其对数值取负：
I(x_i|y_j) = -\log_2 p(x_i|y_j) -
条件熵
衡量一个特征t固定不变时系统所具有的信息具体数值是多少。这一特定数值也被称为"条件熵"
通过计算n个可能状态并取其平均值得到条件熵的具体数值。这个平均值是基于每个状态出现概率计算得出的。
在给定条件下（i=1…n），每个可能状态的自信息量为I(x_i| y_j) ，而整个系统的条件熵H(X|y_j)则定义为：
H(X|y_j)=\sum_i^np(x_i|y_j)I(x_i|y_j)
在给定属性Y（即所有可能的Yj）的情况下，系统的总条件熵H(X|Y)可表示为：
H(X|Y)=\sum_{y_j \in Y}p(y_j)H(X|y_j)
这一指标用于描述已知属性条件下系统的不确定性。
IG(Y)是表示属性分类前后的数据集不确定性的度量差值。具体而言，在已知某个属性的情况下，
数据集的不确定性相比未知该属性时减少了多大的程度。
这一度量反映了固定该属性后对数据集划分的优化效果。
IG(Y,X) = H(X) - H(X|Y) = H(X) - \sum_{y_j \in Y} p(y_j)H(X|y_j)
其中，
ID3算法会对每个候选特征计算其对应的条件熵值，
并选择具有最大信息增益 的特征来进行数据划分。
需要注意的是，
这一方法的主要缺陷在于仅衡量特征对整体系统的贡献，
而无法实现统一的数据分割策略，
因此在某些复杂任务中表现略显不足。
关于这一概念的具体探讨，
可参考相关文献以获取更深入的理解。
算法示例
下面我们以是否打球这个例子看一下ID3算法的计算过程：
根据图形信息图可知：活动是否进行的概率分别为9/14和5/14，并分别用p(进行)和p(取消)表示这两种情况发生的概率；类似地有：
其发生概率分别为：
p(\text{进行}) = \frac{9}{14}, \quad p(\text{取消}) = \frac{5}{14}
同样地：
p(\text{晴}) = \frac{5}{14}, \quad p(\text{阴}) = \frac{4}{14}, \quad p(\text{雨}) = \frac{9}{14}
| 天气\活动（概率） | 进行 | 取消 |
|---|---|---|
| 晴 | \frac{2}{5} | \frac{3}{5} |
| 阴 | 1 | 0 |
| 雨 |
该活动具有两个操作属性；由此可得该活动的熵计算式如下所示：
H(活动)=-\frac{9}{14}\cdot \log_2{\frac{9}{14}}-\frac{5}{14}\cdot \log_2{\frac{5}{14}}=0.94
天气有三个属性指标：晴天、阴天和雨天；在已观察到天气的情况下，
各天气状况对应的户外活动的条件熵分别为：
H(活动|晴)=-\frac{2}{5}\cdot \log_2\frac{2}{5}-\frac{3}{5}\cdot \log_2\frac{3}{5}=0.971
H(活动|阴)=-1^4\times \log_2 1=0
H(活动|雨)=-\frac{3}{5}\cdot \log_2\frac{3}{5}-\frac{2}{5}\cdot \log_2\frac{2}{5}=0.971
由此可得，在已知天气状况下进行活动的条件熵值为：
H(活动|天气)=P(晴天)*H(活动|晴天)+P(阴天)*H(活动|阴天)+P(雨天)*H(活动|雨天)=\frac{5}{14}*0.971+\frac{4}{14}*0+\frac{5}{14}*0.971≈0.693
从而得到天气的信息增益：IG(活动，天气)=H(活动)-H(活动|天气)=0.94-0.693=0.246
同理可得到：IG(活动，温度)=0.029，IG(活动，湿度)=0.151，IG(活动，风速)=0.048
取最大的信息增益来划分，即天气，得到如下决策树：
ID3算法的缺点：
（1）该算法倾向于选择取值范围较大的属性，在某些情况下这些属性并非最为关键。例如：在银行客户分析中，“姓名”这一属性具有较多取值却无法从中获取任何有用信息。
（2）该算法无法处理具有连续值的属性以及缺失数据的情况。
（3）以信息增益作为选择标准的前提条件是：训练子集中的正反例比例应与实际领域一致；然而一般情况下很难满足这一假设条件，这会导致信息增益计算出现偏差。
（4）由于每次划分决策树仅使用单个属性进行分隔，在一定程度上限制了各节点间的关联性；尽管节点间通过父子关系连接在一起但这种连接往往显得松散而不紧密。
（5）尽管ID3算法理论基础清晰但其计算过程较为复杂在处理大规模训练数据时会对机器内存造成较大压力并消耗更多资源。
（6）当增加训练数据量时决策树结构也会随之发生变化。
计算过程
ID3（A：条件属性集合；d：决策属性；U：训练集）将返回一棵决策树。
伪代码如下所示：
当数据集U为空时，
返回一个带有失败标记的单节点。（这种情况通常不会发生）
否则，
如果所有记录的决策属性值相同，
返回一个带有该值的单节点。（此分支至此结束）
否则，
从条件属性集合中选择信息增益最大的属性a；
将a赋给\{a_j | j = 1,2,…,m\}；
根据a_j将训练集分别划分为m个子集\{u_j | j = 1,2,…,m\}；
构建一棵树，
根标记为当前选择的属性a
树干上的边标记为a_1, a_2,…,a_m
分别对每个子集构建子树：
ID3（A - a；d；u_j），其中j=1,2,…,m
参考