数据挖掘决策树——ID3
经典的ID3算法
一、ID3的介绍
ID3算法最初由J. Ross Quinlan于1975年在悉尼大学开发出来作为一种分类预测方法。该算法的核心在于'信息熵'这一概念，在数据分析中用于衡量数据集的不确定性。该方法通过基于计算每个属性的信息增益来识别最优分割标准，在每次迭代中选择信息增益最大的属性来进行划分操作。经过反复循环这一过程后，则会最终生成一个能够准确分类训练样例的决策树结构。
ID3算法采用贪心策略来生成决策树结构。该算法源自概念学习系统（CLS），基于信息熵的下降速度作为选择依据
在决策树构建过程中，在每个节点上选取未被选中用于分割的最大信息增益特征作为划分依据，并依次进行。
直到生成的决策树能完美分类训练样例。
ID3算法是一种用于对数据进行分类的方法，并旨在实现预测目标；它通过构建一棵层次结构来体现数据集合中的分类规则。该算法由一系列决策节点和叶节点构成
该结构由节点及其分支组成，在决策树中位于顶端的是根节点，在其下方分布着多个子节点及分支。每个叶子节点对应着一种分类结果的可能性。如图所示：
二、关于IDE3的基本理论知识
1、信息信息熵、信息增益
不确定性度量在相关领域中被定义为熵。香农提出了信息熵概念，并将其定义为离散随机事件的概率。
当系统的有序程度提升时（即随着系统的顺序性增强），其信息熵会降低到一定程度；相反地，在系统的混乱程度增加时（即当系统的无序性增强时），其信息熵也随之提高）。这一指标也被视为衡量系统有序化程度的重要参数。
的一个度量。
若假设存在n个等概率的消息，则每个消息的概率即为1/n。在此情况下，该消息所携带的信息量可表示为-log₂(1/n)。
假设一个随机变量X的取值为x₁, x₂, …, xₙ，并且每个取值对应的概率分别为p₁, p₂,…, pₙ，则称X的信息熵H(X)定义为：
意思一个变量的取值变化越多，那么它带的信息量就越大。
在分类系统中, 变量C的取值为具体取值包括C_1, C_2, ..., C_n; 各类别出现的概率分别为.
各个类别C的概率分别为P(C₁)、P(C₂)、…、P(Cₙ)；其中n代表类别变量C的不同取值数量；而该系统的熵则可表示为以下公式。
以上就是信息熵的定义，下面介绍信息增益。
信息增益是基于某个特定特征进行计算的一个指标。具体而言，则是指在系统存在该特征T以及不存在该特征T的情况下分别计算各自的信息量，并进行比较分析。
两者的差异即是特征T向系统所释放的信息量,这被称为信息增益.详细通过公式来展示这种关系会显得较为复杂,因此下面直接举例进行说明.
2，举个经典的例子来说明
下表是一个关于天气的表，目标是play或not play
| 天气数据与是否打网球 | ||||
|---|---|---|---|---|
| Outlook | Temperature | Humidity | Windy | Target |
| sunny | hot | high | FALSE | no |
| sunny | hot | high | TRUE | no |
| overcast | hot | high | FALSE | yes |
| rainy | mild | high | FALSE | yes |
| rainy | cool | normal | FALSE | yes |
| rainy | cool | normal | TRUE | no |
| overcast | cool | normal | TRUE | yes |
| sunny | mild | high | FALSE | no |
| sunny | cool | normal | FALSE | yes |
| rainy | mild | normal | FALSE | yes |
| sunny | mild | normal | TRUE | yes |
| overcast | mild | high | TRUE | yes |
| overcast | hot | normal | FALSE | yes |
| rainy | mild | high | TRUE | no |
在表格中列出的共有14个实例中包含有5例属于no类型以及9例属于play类型的情况。我们采用该天气系统的熵值（亦称信息量）进行计算公式推导的具体步骤将在后续部分进行详细阐述
为了更好地理解特征信息增益的概念，在解决决策树分类问题的过程中，其信息增益的意义在于区分数据集基于当前特征的分裂情况与基于最优分割标准的分裂情况之间的差异。
信息差值。假设以Outlook特征来划分。
基于Outlook的属性体系存在三个核心要素；因此对应设置了三条分枝路线。从图表中可以看出，在分枝节点sunny处，“否”状态呈现出三次出现的情况，“是”的情况则出现了两次。
在overcast类别中有四个样本标记为yes，在rainy类别中有三个样本标记为yes和两个标记为no。划分后得到三类分支，请参考下文查看各子类别的信息熵计算过程
划分后的系统信息熵计算如下：
每个分支都承担着传递信息量的责任。其中的Entropy(S|T)表示在给定特征条件下计算出的条件熵值；在这里我们定义的特征变量T即为Outlook。那么对应的特征变量T即为
系统带来的信息增益为
IG(T)=Entropy(S)-Entropy(S|T)=0.24675
信息增益的计算公式如下：
其中S代表所有样本构成的集合；value(T)表示属性T的所有可能取值。设v为属性T的一个具体取值。则称满足条件的所有样本组成的子集\mathbb{S}_v即为对应于v的部分。其基数（即元素个数）记作\lvert\mathbb{S}_v\rvert
在构建决策树的过程中，在每个非终端节点之前进行预剪裁操作时（即提前剪枝），首先要评估每个候选特征的信息增益值，并在此基础上选取具有最高信息增益值的那个特征来进行分割操作。这种做法背后的逻辑是基于这样一个直观认识：当样本间差异度越大时（即分类能力越强），所选择的分割标准就越有代表性（即区分度越高）。因此可以说，在这一阶段我们实际上是在遵循着一种典型的自顶而下贪心算法的原则来进行模型构建
该算法属于经典的分类方法，在现有技术中已知实现过的多种算法其核心思路与多数现有技术相似。对于刚开始学习数据分析的人来说ID3是一个值得深入研究的基础模型
这里有一个Java实现的算法实例，感兴趣的朋友可以去看看。