人工智能之AdaBoost算法

人工智能之机器学习主要有三大类：分类/回归/聚类。今天我们重点探讨一下ID3算法。 

Hunt、Marin、和 Stone于1966年研制了一个概念学习系统CLS， 可以学习单个概念，并用此学到的概念分类新的实例。John Ross Quinlan（悉尼大学）于1983年研制了ID3算法。

ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。

ID3算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。

ID3算法概念：
ID3（Iterative Dichotomiser 3），即迭代二叉树3代，该算法是一种贪心算法，用来构造决策树【请参加人工智能（23）】。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

ID3算法核心：
ID3算法核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

ID3算法本质：

在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法本质是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。

ID3算法步骤：
计算各属性的信息增益，找出最大者为根节点 
1）先验熵：没有接收到其他属性时的平均不确定性；
2）后验熵：接收到输出符号Vj时关于信源的不确定性 ；
3）条件熵：对后验熵在输出符号集V中求期望，接收到全部符号后对信源的不确定性 ；
4）信息增益：先验熵与条件熵的差，是信宿端所获得信息量；
5）对剩余属性重复上述步骤。

ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记，对该属性的每个值创建一个分支据此划分样本。
具体算法流程如下：

ID3优点：
1）   算法结构简单；
2）   算法清晰易懂；
3）   非常灵活方便；
4）   不存在无解的危险；

5）   可以利用全部训练例的统计性质进行决策，从而抵抗噪音。

ID3缺点：
1）    处理大型数据速度较慢，经常出现内存不足；
2）    不能处理连续型数据，只能通过离散化将连续性数据转化为离散型数据；
3）    不可以并行，不可以处理数值型数据；
4）    只适用于非增量数据集，不适用于增量数据集，可能会收敛到局部最优解而非全局最优解，最佳分离属性容易选择属性值多一些的属性；
5）    没有对决策树进行剪枝处理，很可能会出现过拟合的问题。

注： ID3（并行）和ID3（number）解决了缺点3）的2个问题。

ID3应用场景：
决策树ID3算法是一个很有实用价值的示例学习算法，它的基础理论清晰，算法比较简单，学习能力较强，适于处理大规模的学习问题，是数据挖掘和知识发现领域中的一个很好的范例，为后来各学者提出优化算法奠定了理论基础。ID3算法特别在机器学习、知识发现和数据挖掘等领域得到了极大发展。

结语：

ID3算法是基本的决策树构建算法，作为决策树经典的构建算法，具有算法结构简单、理论清晰易懂、学习能力较强和灵活方便的特点。但也存在着不能处理连续型数据，不适用于增量数据集，处理大型数据速度较慢，可能会出现过拟合等缺点。ID3算法在世界上广为流传，得到极大的关注。ID3算法特别在机器学习、知识发现和数据挖掘等领域得到了极大发展。

文章来源：OFweek人工智能网