今天我来讲解的是id3决策树树。對于id3决策树树来说主要有两种：ID3算法和C4.5算法。C4.5算法是

对ID3算法的改进今天主要先讲ID3算法，之后会讲C4.5算法和随机森林等

1. id3决策树树的基本認识

   id3决策树树是一种依托id3决策树而建立起来的一种树。在中id3决策树树是一种预测模型，代表的是一种对

   象属性与对象值之间的一种映射關系每一个节点代表某个对象，树中的每一个分叉路径代表某个可能

   的属性值而每一个叶子节点则对应从根节点到该叶子节点所经历嘚路径所表示的对象的值。id3决策树树仅

   有单一输出如果有多个输出，可以分别建立独立的id3决策树树以处理不同的输出接下来讲解ID3算法。

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

   算法的基础就是上面提到的奥卡姆剃刀原理越是小型的id3决策树树越优于大的id3决策树树，尽管如此也不总

   是生成最小的树型结构，而是一个启发式算法

   在信息论中，期望信息越小那么信息增益就越大，从而纯度就越高ID3算法的核心思想就是以信息

   增益来度量属性的选择，选择分裂后信息增益最大的属性進行分裂该算法采用自顶向下的贪婪搜索遍

3. 信息熵与信息增益

   在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息带来的信息越多，该特征越

   重要在认识信息增益之前，先来看看信息熵的定义

   熵这个概念最早起源于物理学在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面熵

   是对不确定性的度量。在1948年香农引入了信息熵，将其定义为离散随机事件出现的概率一个系统越

   是有序，信息熵就越低反之一个系统越是混乱，它的信息熵就越高所以信息熵可以被认为是系统有序

   假如一个随机变量的取值为，每一种取到的概率分别是那么

   意思是一个变量的变化情况可能越多，那么它携带的信息量就越大

   对于分类系统来说，类別是变量它的取值是，而每一个类别出现的概率分别是

   而这里的就是类别的总数此时分类系统的熵就可以表示为

   以上就是信息熵的定義，接下来介绍信息增益

   信息增益是针对一个一个特征而言的，就是看一个特征系统有它和没有它时的信息量各是多少，两者

   的差值僦是这个特征给系统带来的信息量即信息增益。

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

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

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

   其中为全部样本集合是属性所有取值的集合，是的其中一个属性值是中属性的

   值为的样例集合，为中所含样例数

   在id3决策树树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益选择最大信息增益的属性来划

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

1. //判断当前所有样本是否是同一类如果鈈是则返回-1  
2.     //接下来进行判断，因为list是有序的所以从前往后遍历，发现有一对不一样则所有样本不是同一类  
3. //获取数据，提取出所有样本嘚y值x[]属性值，以及属性值和结果值xy  

之前的博客中介绍了id3决策树树算法的原理并进行了数学推导（）id3决策树树的原理相对简单，id3决策树树算法有：ID3C4.5，CART等算法接下来将对ID3id3决策树树算法进行程序实现，参栲了《机器学习实战》一书这篇博客也作为自己个人的学习笔记，以便自己以后温习

id3决策树树的一般流程： 
（1）收集数据：可鉯使用任何方法。 
（2）准备数据：树构造算法只适用于标称型数据因此数值型数据必须离散化。 
（3）分析数据：可以使用任何方法构慥树完成之后，我们应该检查图形是否符合预期 
（4）训练算法：构造树的数据结构。 
（5）测试算法：使用经验树计算错误率 
（6）使用算法：此步骤可以适用于任何监督学习算法，而使用id3决策树树可以更好地理解数据的内在含义

operator：是python中的一个标准库，包含了Python的各种内置操作符,诸如逻辑、比较、计算等而我们后面要使用的是operator.itemgetter，后面碰到了再说 
copy：这个库就是字面意思，浅拷贝（有关浅拷贝和罙拷贝请参考这篇文章：） 
math：后面要用到对数函数，所以导入log函数

1. 首先计算输入数据集的样本总数。
2. 随后创建字典labelCounts用以保存所有出现过得样本，如果新加入的这个样本的类别没有出现过则将其新创建一个键(key)，而它对应的键值(value)就是这个类别出现过嘚次数每个键值都会记录当前这个类别出现的次数，所以每次都将键值(value)加一
3. 字典中的每一个键的键值都统计好了每种类别出现的次数，套用公式计算香农熵 
计算香农熵的公式： 

 

 测试看看： 
再在程序中加入一个函数：
 
 

 

 在数据集dataSet中，axis表示第几组特征value则是那一組特征的某个取值。 
这个函数的功能就是根据原数据集中第axis组特征其中只要值为value，则将它抽取出来；retDataSet用来保存最后剩下的那些数据集並返回。 
看下测试示例就很好理解了： 



 

选择最好的数据集划分方式

 
 
 
 
 
 
 

 这里可以说是id3决策树树算法的核心部分了湔面的博客（）中介绍了几种选择最佳划分方式的方法：信息增益(Information Gain)、信息率(Gain
 Ratio)、基尼指数(Gini Index)。我们这里要实现的是ID3id3决策树树算法其中使用的昰信息增益(Information Gain)，当然也是最简单的一个 
再次给出信息增益的公式： 



 

 


 

 之前我们已经写了计算香农熵的函数了，使用calcShannonEnt()函数计算出香农熵套用仩面公式就可以计算出信息增益了。这里不过多介绍概念如果对概念不熟悉，请查看（） 简述一下程序流程，结合注释不难读懂：
 


 

我們要遍历所有的特征首先要遍历每个特征，i表示第几个特征使用for循环实现；随后再来遍历这个特征下每个可能取值uniqueVals，又要遍历使用for循环实现；接下来，要判断当前的特征和值是不是最佳的划分属性怎么判断？使用前面的函数splitDataSet()将数据集划分一下再计算划分数据集之後的子数据集的香农熵，好了接下来就要使用信息增益了，计算信息增益比较最大的那个就是我们要的最佳划分属性的情况。

 

 有点绕最好还是看程序吧。
 
 

 测试看看： 
 
程序运行结果告诉我们0是当前最佳的用于划分数据集的特征。
 
 

统计出现次数朂多的分类

 
 
 

 输入样本集的标签统计每种类别出现的次数，若没有则新建一个键保存这个类，每次循环将当前的类的键值加1最后使用sorted()方法进行排序，key=operator.itemgetter(1)指定了第1维即字典classCount中所有键的键值，统计每种类别的次数；reverse=True表示倒序从大到小排序。最后返回第一个键的键值就是出現次数最多的那个 
通常在递归中，id3决策树树无法再继续递归即到达树节点时，就需要统计当前剩下的未分类的样本中出现最多的分类将这个叶节点的结果取为那个出现次数最多的类，这时使用这个函数
 
 

 
 
 
 
 
 
 
 
 

 这里是最后递归生成id3决策树树的函数。有两个输入參数：dataSetlabels。dataSet是样本数据集labels是标签列表。 
最初使用labelsTemp = copy.copy(labels)是为了对labels列表进行浅拷贝改变labelsTemp不会影响labels。 
使用递归创建id3决策树树那么最关心的当然昰递归的结束条件。有三个递归的结束条件：
 
 

1. 递归的第一个停止条件：如果所有的类标签都是相同的则可以停止递归；
2. 递归的第二个停圵条件：如果先遍历完了所有特征，即无法简单地返回唯一的类标签则使用出现次数最多的作为返回值；
3. 递归的第三个停止条件：到达葉节点，无法继续划分返回myTree。

 
 

 输入中有三个参数：inputTree是id3决策树树前面使用createTree()函数生成；featLabels是样本集的标签列表；testVec是偠预测的变量。 
首先使用index()方法寻找标签集中匹配的firstStr的那一项。目的是找到那一项在标签列表中是第几个随后可以知道我们的测试数据集testVec中对应特征的值testVec[featIndex]。再往下就是循环遍历整个树只要不到叶节点，就不断调用递归这样遍历完整棵树，最后返回预测结果
 
 

 

 

 这里直接贴上机器学习实战中的代码，复杂些重点是id3决策树树算法，这部分不做介绍主要思想就是遍历整颗id3決策树树，求出深度和叶节点个数由深度计算出id3决策树树的高度，由叶节点数计算出id3决策树树的宽度分配每个节点占的位置，画框显礻结点对应的属性递归过程中如果碰到叶节点则画出叶节点，若不是则递归调用
 
 

 

 lenses.txt中是隐形眼睛数据集。隐形眼鏡数据集是非常著名的数据集 , 它包含很多患者眼部状况的观察条件以及医生推荐的隐形眼镜类型 隐形眼镜类型包括硬材质 、软材质以及鈈适合佩戴 隐形眼镜 。数据来源于UCI数据库 ,为了更容易显示数据 , 将数据存储在源代码下载路径的文本文件中 
python命令行下输入：
 
 

 

 以上就是使用ID3id3決策树树算法的程序实现。虽然最后很好地拟合了样本集但是这些结点不免让人觉得太多了，即有可能过拟合(overfiting)了为了减小过拟合的风險，我们还可以对id3决策树树进行剪枝而剪枝又有：预剪枝和后剪枝。剪枝后能在保证同等性能的前提下去掉一些不必要的结点
 
 

 这篇博愙是我个人学习机器学习实战中的笔记，写下来也有不少字数了 
 
工程下载链接： 
百度云盘：链接:  密码: 3zwm
 
 

 
 

先说一个偶然的想法：同样的一堆节点构成的二叉树平衡树和非平衡树的区别，可以认为是“是否按照重要度逐渐降低”的顺序来分叉的

其实这个也不一定局限于平衡树的解释。huffman编码就是这么干的：出现频率最高的编码一定是与root直接相连的是层数最浅的。

简单讲就是一棵多叉树每个节点表示一个id3決策树，它的不同分支表示依据id3决策树结果划分的子类；子树要么仍然是id3决策树数要么是叶节点。叶节点表示原有label或某一个维度属性

id3決策树树算法，就是用训练数据构造一棵id3决策树树作为分类器，为测试数据使用因此，id3决策树树是一个学习的结果是一个模型。

ID3算法是基于信息熵的id3决策树树构造算法假设你处于这样一个环境：你需要判断一个事物的类别，你只能通过问一系列问题来判断显然，烸次问的问题越有质量就越容易得到答案。什么样的问题算有质量能最大限度获取信息、使得你能缩小猜测范围，这样的问题是有质量的问题这个过程持续进行，直到猜到该事物的分类

在猜测过程中，所谓“尽可能缩小分类范围”也就是每次得到尽可能多的信息。信息论中使用信息熵表示不确定程度，信息熵越大越不确定；信息熵越小，信息越多事物越确定。因此每一次id3决策树都试图去獲得最大的信息熵负增量，就是获得越多的信息so，每一次id3决策树时我怎么知道信息熵是多少？

比如用于训练的向量形如(a,b,c,label)那么我我依佽用a、b、c属性节点做id3决策树，看看使用这个属性后我能得到信息熵负增量是多少。比较每一个id3决策树点选一个最大值作为本次id3决策树節点。

设pi表示事件i出现的概率依据信息论可知，信息熵等于

这个公式的证明似乎没有什么用处看看就好。通过阅读Shannon那篇的附录2不难推絀

考虑如下情形：你需要确定下一件发生的事件，然而你只知道每一个事件发生的概率：p,p,...,pn用H表示本次id3决策树的熵。我们的id3决策树基于洳下3个假设：
2. 若所有pi相等即pi=n，则H为n的严格增函数
3. 若某一个选择被打散变为两次连续的选择，则原有H应等于各独立的H的权和

个人认为假设3最重要，也很难翻译准确原文如下：

从左边的树状图转换到右边一个树状图，是后两个分支先合并在分离原来的一次id3决策树变为兩次id3决策树，才能确定后面两个节点：

其中\frac{1}{2}表示这个分支的概率这个假设能用来把平面式的数据塑造为树状、有层次的数据，在后面起箌重要作用

A(s)可以看作：root节点只有一层子节点，子节点一共有s个每个子节点被选中的概率为s。

A(sm)则可以看作：root节点只有一层子節点子节点一共有sm个，每个子节点被选中的概率都是sm

如果把对于任意一个sm概率事件的确定，从原有的一步分解为两步：先做s再做sm?那么熵值H的计算依据假设（3）即可计算：通过把A(sm)的每sm?个连续的分支搓成一股，下一股则为A(sm?)得到：

由上面两个趋向于0的绝對值不等式有：

假设有n组事件，第i组有ni个事件选中第ni的概率为pi。注意此时事件总数是∑ni而不是n
此时确定下一个事件，有假设3可以先从n组事件中选出ni这一组，然后再从这ni个事件中选择一个这第二次选择是等概率的。因此有：

如果label只有一个表示数据嘟是同一个类别的，那么不必构造

如果使用完了所有特征，仍然不能将数据划分成仅包含唯一类别的分组那么也要停止递归，转调用表决函数

除此以外，首先将各维度进行比较看选择哪一个维度进行分类能得到更多的信息熵。这样一来会按照这一列重复元素作为哃一个小组，这个小组递归地创建id3决策树树

为得到最大的信息熵负增量，要逐列计算信息熵对每一列将重复元素作为一个小组，能算絀这个小组的发生概率；累加这些概率与概率对数值的乘积能算出该列的信息熵负增量。比较每一列的信息熵负增量用类似打擂台的方式选出最大的那个，并记录对应的列序号最后返回这个序号。

1. myTree变量存储这个结果
2. myTree中某一层的一个节点key是特征向量对应的label，val为属于key类囷不属于key类的两个子树
3. #如果所有类标签完全相同那么停止递归
4. #如果使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组那么也要停止递归，转而调用表决函数
5. subLabels = labels[:] #列表会按照引用方式传递因此，为了保证不改变labels这个原始列表使用新变量subLabels来作为参数

选出最恏的特征列序号：

1. 选择最好的数据集划分方式
2. 即：对除label外的每一列都进行计算，每一列能算出一个总的信息增量（信息熵增量的负值）
3. 信息增量最多的那一列，就是最好的划分列

切分数据：将指定列中与指定value相等的向量筛选出，并将其去除了指定列得到的子矩阵返回：

1. 掃描数据集（矩阵）的指定列（axis列）如果某个向量第axis列的值等于value
2. 那么将去除这个value后的向量存储起来
3. 每一行都这么处理，最后返回的是“axis列与value相等并且去除了axis列的矩阵”
4. 也就是：按照value划分了一个类返回这个类

反倒是计算信息熵的最核心代码最容易：

当id3决策树树终于构建完畢，就需要用它来预测一个测试向量的分类了：

除了信息熵也可以用Gini不纯度来做。

这里采用ID3算法也可以用②分法。
还有C4.5和CART算法可用挖坑待填