一、决策树（ID3）算法

概念：采用西瓜书上的描述来说，决策树是一类常见的机器学习方法，以二分类为例，我们希望从给定的训练数据集学得一个模型用以对新示例进行分类，把这个样本分类的任务，可看作对“当前样本属于正类吗？”这个问题的“决策” 或“判定”过程。顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。

例如：判断一个西瓜是否好瓜可以通过如下决策树

现在则给出个问题，为什么最开始会先看 “色泽” 而不是先看 “根蒂” 或者 “敲声”？那么按照生活习惯的理解可以认为色泽属性在某种程度上对于是不是好瓜这个结果的影响最大，所以看一个瓜是不是好瓜我们一般先从色泽上面开始观察，即属性优先级上 “色泽” 要优于其他属性，所以构建决策树的关键问题出来了！那就是：

决策树的关键问题 ：如何从属性集中选择最优划分属性出来！！

那么现在假设我们需要训练一个用来对西瓜进行分类的决策树：首先需要使用一部分既有的数据集来作训练数据集，则若给定如下数据

总共提供17个西瓜给我们做训练数据集，每个瓜有6个属性即{“色泽”，“根蒂”，“敲声”，“纹理”，“脐部”，“触感”}，有两个分类{“是好瓜”，“不是好瓜”}

那么怎么判断哪个属性是最优划分属性？

引入一个 “信息熵” 的概念：

D是样本集，|y| 是数据的类别数，这儿 |y| = 2。pk是指当前样本集合D中第K类样本所占的比例。

当然光凭信息熵还不能够，还要引入一个 “信息增益” 的概念

在这儿根节点的信息熵为：Ent (D) = - (8/17 * log 8/17 + 9/17 * log 9/17) = 0.998