《机器学习实战》笔记之三——决策树ID3算法_请利用id3算法构建决策树,a的取值范围(对数以2为底)(25分)

1.决策树

K近邻可以完成很多分类任务，但其无法给出数据的内在含义。
构造决策树的基本思想是随着树深度的增加，熵也随着下降。怎么使熵下降的迅速，还能保证树的高度不高。
本节将通过算法一步步地构造决策树，并会涉及很多有趣的细节。首先我们讨论数学上如何使用信息论划分数据集（本节使用ID3算法划分数据集），然后编写代码将理论应用到具体的数据集上，最后编写代码构建决策树。
怎么找到决定性的特征，划分最好的结果。

2.信息增益

划分数据集的大原则是 ：将无序的数据变得有序。
组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。
在划分数据集之前之后的信息发生的变化称之为信息增益，知道如何计算信息增益，我们就可以计算每个特征的值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
集合信息的度量方式称之为 香农熵。
熵是信息论中的概念，用来表示集合的无序程度，熵越大表示集合越混乱，反之则表示集合越有序。熵的计算公式为：

E = -P * log2P

熵定义为信息的期望值。那什么是信息呢？如果待分类的事务可能划分在多个分类之中，符号xi的信息定义为：

其中，p(xi)是选择分类的概率。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过以下公式得到：

其中 n 是分类的数目。

3.初识ID3

回顾决策树的基本知识，其构建过程主要有下述三个重要的问题：
（1）数据是怎么分裂的
（2）如何选择分类的属性
（3）什么时候停止分裂
从上述三个问题出发，以实际的例子对ID3算法进行阐述。

3.1 ID3算法可以归纳为以下几点：

• 使用所有没有使用的属性并计算与之相关的样本熵值
• 选取其中熵值最小的属性
• 生成包含该属性的节点

下面，引用一个网上的关于ID3思想的总结：

1. 自顶向下的贪婪搜索遍历可能的决策树空间构造决策树(此方法是ID3算法和C4.5算法的基础)；
2. 从“哪一个属性将在树的根节点被测试”开始；
3. 使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。
4. 然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。
5. 重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。

3.2 例子

通过当天的天气、温度、湿度和季节预测明天的天气

1.数据分割
对于离散型数据，直接按照离散数据的取值进行分裂，每一个取值对应一个子节点，以“当前天气”为例对数据进行分割，如图1所示。

对于连续型数据，ID3原本是没有处理能力的，只有通过离散化将连续性数据转化成离散型数据再进行处理。

连续数据离散化是另外一个课题，本文不深入阐述，这里直接采用等距离数据划分的李算话方法。该方法先对数据进行排序，然后将连续型数据划分为多个区间，并使每一个区间的数据量基本相同，以温度为例对数据进行分割，如图2所示。

2. 选择最优分裂属性
ID3采用信息增益作为选择最优的分裂属性的方法，选择熵作为衡量节点纯度的标准，信息增益的计算公式如下：

其中， Entropy表示父节点的熵； 表示节点i的熵，熵越大，节点的信息量越多，越不纯； 表示子节点i的数据量与父节点数据量之比。 越大，表示分裂后的熵越小，子节点变得越纯，分类的效果越好，因此选择 最大的属性作为分裂属性。

对上述的例子的跟节点进行分裂，分别计算每一个属性的信息增益，选择信息增益最大的属性进行分裂。

天气属性：（数据分割如上图1所示）

温度：（数据分割如上图2所示）

湿度：


季节：


由于最大，所以选择属性“季节”作为根节点的分裂属性。
3.停止分裂的条件
停止分裂的条件已经在决策树中阐述，这里不再进行阐述。

（1）最小节点数

当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
（2）熵或者基尼值小于阀值。

由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度时，节点停止分裂。

（3）决策树的深度达到指定的条件

节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。

（4）所有特征已经使用完毕，不能继续进行分裂。

被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。

3.3 例子（天气预报玩耍）

接下来以天气预报的例子来说明。下面是描述天气数据表，学习目标是play或者not play。

可以看出，一共14个样例，包括9个正例和5个负例。那么当前信息的熵计算如下

在决策树分类问题中，信息增益就是决策树在进行属性选择划分前和划分后信息的差值。假设利用

属性Outlook来分类，那么如下图

划分后，数据被分为三部分了，那么各个分支的信息熵计算如下

那么划分后的信息熵为

代表在特征属性的条件下样本的条件熵。那么最终得到特征属性带来的信息增益为

信息增益的计算公式如下

其中为全部样本集合，是属性所有取值的集合，是的其中一个属性值，是中属性的值为的样例集合，为中所含样例数。
在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划

分，因为信息增益越大，区分样本的能力就越强，越具有代表性，很显然这是一种自顶向下的贪心策略。以上

就是ID3算法的核心思想。

有可能你不会计算举个例子，你就懂啦。

问题描述：根据以上表中的信息，得到一棵预测顾客是否会购买电脑的决策树。

步骤：
1、计算Info(buy_computer)；

buy_computer是离散的（这个例子中所有的属性都是离散的，如果是连续的，可以对其进行离散化）

表中可以看出，类no对应5个元组，类yes对应9个元组。

故得：

2、计算其余每个属性的期望信息需求。

age的熵：

age的信息增益：

显然，age在属性中具有最高的信息增益，所以它被选作分裂属性。

得到：

接下来，我们要做的事情就是递归下去。也就是把问题分为了3个子问题进行求解。

4. 决策树的思想
   =========
   注：首先是采用ID3的算法用熵和信息增益的值来衡量用哪一个特征来区别类别分类。

4.1 实施构建决策树算法

1>首先用calcShannonEnt(dataSet)函数计算给定数据集的信息熵
（标签分几种，每一种在所有分类的比例且求出熵值（S））,
2>划分数据集，用splitDataSet(dataSet, axis, value)，如何符合此特征值 则存储，存储划分后的数据集时 不需要存储选为划分的特征。
3>

• 对连续型特征进行处理 ,i代表第i个特征,featList是每次选取一个特征之后这个特征的所有样本对应的数据
  1

• 对所有特征属性进行整理，用set()方法去重复，得出总共几类特征

• 得到的去重的某一类的特征集合，根据每个特征划分数据集

• 算出每个特征拥有几条数据集，并得出占所有特征的数据集的比例

• 根据条件熵的定义

4>得到用那一列的特征区别类别最好的index值。

4.2 例子及思想

信息增益的公式，如下图1所示：

（比如天气预报的例子有outLook、温度、湿度、是否有风和标签【这里有个for循环】。
1》先算出每个类别的信息熵
2》先抽取其中outLook下的所有的特征，用set()去重后的特征。根据其中一个特征【这里有个for循环】，划分属于这一特征的数据集存储，○1算出这些数据集（晴天）占总的数据集的比例就是Sv/S, ○2算出这些筛选出来的数据集所在的类别占这些筛选出的数据集总数的比例。其实○1○2得出的结果在一个循环中【一个outLook中有下雨天、晴天、阴天，每个类别得出条件熵乘以○1，三个类别的结果相累加】
3》用上图1的公式，1》减去2》的结果得到信息增益
4》在上述的结果中，在第一个for循环中i作为特征所在的索引值；为了得出这个值，给定一个全局变量判断信息增益，取最大的的增益值且特征的所在列表的索引。
5》根据选取最好的特征值后，构建树，去除这一项特征后的数据集再去构建树，递归构建树。
递归函数停止的条件：
○1所有类别都相同的时候停止
○2递归所有的特征
6》构建树后，根据传输三个数据集【构建好字典树、类标签、测试列表】，判别属于哪一类（不是字典的时候就到叶子结点啦，打印出value就是类别标签）。

5.代码
暂时没贴

参考链接：
决策树、熵与最大熵
链接内容
链接内容
链接内容