机器学习（三）决策树算法ID3的实现

    上一篇机器学习的博客我详细说了机器学习中决策树算法的原理，这篇博客我就以一个小例子来说明机器学习中决策树算法的实现。用Python实现机器学习中的决策树算法需要用到机器学习的库，sklearn，我的博客有详细讲解怎么安装机器学习中用到的sklearn库，如果我们安装的可以照着这篇博客去安装----Python2.7中安装sklearn。

        补充和总结一下上一篇博客决策树中的算法：

        ID3（Iterative Dichotomiser 3）是由罗斯奎因兰（Ros Quinlan）于1986年开发的。该算法创建一个多路树，找到每个节点（即以贪婪的方式）分类特征，这将产生分类目标的最大信息增益。树生长到最大尺寸，然后通常应用修剪步骤，以提高树的概括性来看待数据的能力。
       C4.5是ID3的后继者，并且通过动态定义将连续属性值分割成离散的一组间隔的离散属性（基于数值变量）来去除特征必须是分类的限制。C4.5将训练好的树（即ID3算法的输出）转换成if-then规则的集合。然后评估每个规则的这些准确性以确定应用它们的顺序。如果规则的准确性没有改善，则通过删除规则的前提条件来完成修剪。
       C5.0是Quinlan根据专有许可证发布的最新版本。它使用更少的内存，并建立比C4.5更小的规则集，同时更准确。
        CART（分类和回归树）与C4.5非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。CART使用在每个节点产生最大信息增益的特征和阈值构造二叉树。

       决策树的优点：
            简单的理解和解释。树木可视化。
            需要很少的数据准备。其他技术通常需要数据归一化，需要创建虚拟变量，并删除空值。但请注意，此模块不支持缺少值。
            使用树的成本（即，预测数据）在用于训练树的数据点的数量上是对数的。
            能够处理数字和分类数据。其他技术通常专门用于分析只有一种变量类型的数据集。见算法，以获取更多信息。
            能够处理多输出问题。
            使用白盒子模型。如果给定的情况在模型中可以观察到，那么条件的解释很容易用布尔逻辑来解释。相比之下，在黑箱模型（例如，在人工神经网络中）中，结果可能更难以解释。
            可以使用统计测试验证模型。这使得可以考虑模型的可靠性。
            即使其假设被数据生成的真实模型有些违反，表现良好。
     决策树的缺点：
            决策树学习者可以创建不能很好地推广数据的过于复杂的树。这被称为过拟合。修剪（目前不支持）的机制，设置叶节点所需的最小样本数或设置树的最大深度是避免此问题的必要条件。
          决策树可能不稳定，因为数据的小变化可能会导致完全不同的树被生成。通过使用合奏中的决策树来减轻这个问题。
          学习最佳决策树的问题被认为是在最优性的几个方面的NP完全，甚至对于简单的概念。因此，实际的决策树学习算法基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这可以通过在综合学习者中训练多个树来缓解，其中特征和样本随机抽样取代。
          有一些难以学习的概念，因为决策树不能很容易地表达它们，例如XOR，奇偶校验或复用器问题。
          如果某些类占主导地位，决策树学习者会创造有偏见的树木。因此，建议在拟合决策树之前平衡数据集。

      例子：关于人们买电脑，试着用决策树去分析，哪类人群符合什么条件可以买电脑。

上面的图片详细记录了14个人买电脑他们的年龄、收入、是否为学生、信用等级、以及结果是否买了电脑（Class Label）。

        根据ID3算法原理用伪代码语言简述是否买电脑与否的决策树算法核心：

        1：首先根据Class:buy_computer中的YES  OR  NO计算信息熵。

        2：然后根据属性age、income、student、credit_rating中的一个去算出各个属性与Class:Buy_Computer的YES  OR  NO去算出期望

        3：然后根据各个属性算出的期望值去与信息熵相减，绝对值大的作为根节点，画出第一层分叉树。

        4：根据划分出来的决策树，再在每个分支中继续重复上面的一二三的步骤。直到决策树的纯度达到自己的要求停止。详细的算法在上一篇博客中讲过了，这里只是再重复一边。

用python代码实现上面的ID3算法：

输出结果：