国庆长假已过近半，想想当初自己立下的学习计划Flag究竟有没有完成？一篇长文干货值得你收藏！
一、前言
本篇讨论决策树的原理和决策树构建的准备工作，机器学习决策树的原理，以及如何选择最优特征作为分类特征，决策树构建，决策树可视化，使用决策树进行分类预测，决策树的存储和读取以及sklearn实战之预测隐形眼睛类型。
二、决策树的基础
1、决策树是什么
决策树是什么？决策树(decisiontree)是一种基本的分类与回归方法。举个通俗易懂的例子，如下图所示的流程图就是一个决策树，长方形代表判断模块(decisionblock)，椭圆形成代表终止模块(terminatingblock)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作为分支(branch)，它可以达到另一个判断模块或者终止模块。我们还可以这样理解，分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directededge)组成。结点有两种类型：内部结点(internalnode)和叶结点(leafnode)。内部结点表示一个特征或属性，叶结点表示一个类。蒙圈没？？
如下图所示的决策树，长方形和椭圆形都是结点。长方形的结点属于内部结点，椭圆形的结点属于叶结点，从结点引出的左右箭头就是有向边。而最上面的结点就是决策树的根结点(rootnode)。这样，结点说法就与模块说法对应上了。
我们回到这个流程图，对，你没看错，这就是一个假想的相亲对象分类系统。它首先检测相亲对方是否有房。如果有房，则对于这个相亲对象可以考虑进一步接触。如果没有房，则观察相亲对象是否有上进心，如果没有，直接SayGoodbye，此时可以说：”你人很好，但是我们不合适。”如果有，同样也值得认真考虑。
不过这只是个简单的相亲对象分类系统，只是做了简单的分类。真实情况可能要复杂得多，考虑因素也可以是五花八门。脾气好吗？会做饭吗？愿意做家务吗？家里几个孩子？父母是干什么的？等等各种因素。
我们可以把决策树看成一个if-then规则的集合，将决策树转换成if-then规则的过程是这样的：由决策树的根结点(rootnode)到叶结点(leafnode)的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
使用决策树做预测需要以下过程：
2、决策树的构建的准备工作
使用决策树做预测的每一步骤都很重要，数据收集不到位，将会导致没有足够的特征让我们构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，将会导致无法构建出分类效果好的决策树模型。从算法方面看，决策树的构建是我们的核心内容。
决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和决策树的修剪。
特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的标准是信息增益(informationgain)或信息增益比，为了简单，本文使用信息增益作为选择特征的标准。那么，什么是信息增益？在讲解信息增益之前，让我们看一组实例，贷款申请样本数据表。
希望通过所给的训练数据学习一个贷款申请的决策树，用于对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。
特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。
图(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。
什么是信息增益呢？在划分数据集之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
（1）香农熵
如果看不明白什么是信息增益和熵，请不要着急，因为他们自诞生的那一天起，就注定会令世人十分费解。克劳德·香农写完信息论之后，约翰·冯·诺依曼建议使用”熵”这个术语，因为大家都不知道它是什么意思。
熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。如果待分类的事物可能划分在多个分类之中，则符号xi的信息定义为：
其中p(xi)是选择该分类的概率。有人可能会问，信息为啥这样定义啊？答曰：前辈得出的结论。这就跟1+1等于2一样，记住并且会用即可。上述式中的对数以2为底，也可以e为底(自然对数)。
通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：
其中n是分类的数目。熵越大，随机变量的不确定性就越大。
当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empiricalentropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck,=1,2,3,…,K,|Ck|为属于类Ck的样本个数，因此经验熵公式就可以写为：
根据此公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：
经过计算可知，数据集D的经验熵H(D)的值为0.971。
（2）编写代码计算经验熵
在编写代码之前，我们先对数据集进行属性标注。
确定这些之后，我们就可以创建数据集，并计算经验熵了，代码编写如下：
代码运行结果如下图所示，代码是先打印训练数据集，然后打印计算的经验熵H(D)，程序计算的结果与我们统计计算的结果是一致的，程序没有问题。
（3）信息增益
在上面，我们已经说过，如何选择特征，需要看信息增益。也就是说，信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。
在讲解信息增益定义之前，我们还需要明确一个概念，条件熵。
熵我们知道是什么，条件熵又是个什么鬼？条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditionalentropy)H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
这里，
同理，当条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的条件熵成为条件经验熵(empiricalconditionalentropy)。
明确了条件熵和经验条件熵的概念。接下来，让我们说说信息增益。前面也提到了，信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutualinformation)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
设特征A有n个不同的取值{a1,a2,···,an}，根据特征A的取值将D划分为n个子集{D1,D2，···,Dn}，|Di|为Di的样本个数。记子集Di中属于Ck的样本的集合为Dik，即Dik=Di∩Ck，|Dik|为Dik的样本个数。于是经验条件熵的公式可以些为：
说了这么多概念性的东西，没有听懂也没有关系，举几个例子，再回来看一下概念，就懂了。
以贷款申请样本数据表为例进行说明。看下年龄这一列的数据，也就是特征A1，一共有三个类别，分别是：青年、中年和老年。我们只看年龄是青年的数据，年龄是青年的数据一共有5个，所以年龄是青年的数据在训练数据集出现的概率是十五分之五，也就是三分之一。同理，年龄是中年和老年的数据在训练数据集出现的概率也都是三分之一。现在我们只看年龄是青年的数据的最终得到贷款的概率为五分之二，因为在五个数据中，只有两个数据显示拿到了最终的贷款，同理，年龄是中年和老年的数据最终得到贷款的概率分别为五分之三、五分之四。所以计算年龄的信息增益，过程如下：
同理，计算其余特征的信息增益g(D,A2)、g(D,A3)和g(D,A4)。分别为：
最后，比较特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大，所以选择A3作为最优特征。
（4）编写代码计算信息增益
我们已经学会了通过公式计算信息增益，接下来编写代码，计算信息增益。
splitDataSet函数是用来选择各个特征的子集的，比如选择年龄(第0个特征)的青年(用0代表)的自己，我们可以调用splitDataSet(dataSet,0,0)这样返回的子集就是年龄为青年的5个数据集。chooseBestFeatureToSplit是选择选择最优特征的函数。运行代码结果如下：
对比我们自己计算的结果，发现结果完全正确！最优特征的索引值为2，也就是特征A3(有自己的房子)。
决策树生成和修剪
我们已经学习了从数据集构造决策树算法所需要的子功能模块，包括经验熵的计算和最优特征的选择，其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
构建决策树的算法有很多，比如C4.5、ID3和CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。由于特征数目并不是每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定的问题。目前我们并不需要考虑这个问题，只需要在算法开始运行前计算列的数目，查看算法是否使用了所有属性即可。
决策树生成算法递归地产生决策树，直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
三、决策树构建
1、ID3算法
ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点(rootnode)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
在使用ID3构造决策树之前，我们再分析下数据。
对D2则需要从特征A1(年龄)，A2(有工作)和A4(信贷情况)中选择新的特征，计算各个特征的信息增益：
根据计算，选择信息增益最大的特征A2(有工作)作为结点的特征。由于A2有两个可能取值，从这一结点引出两个子结点：一个对应”是”(有工作)的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为”是”；另一个是对应”否”(无工作)的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为”否”。
这样就生成了一个决策树，该决策树只用了两个特征(有两个内部结点)，生成的决策树如下图所示。
这样我们就使用ID3算法构建出来了决策树，接下来，让我们看看如何进行代实现。
2、编写代码构建决策树
我们使用字典存储决策树的结构，比如上小节我们分析出来的决策树，用字典可以表示为：
{'有自己的房子':{0:{'有工作':{0:'no',1:'yes'}},1:'yes'}}
创建函数majorityCnt统计classList中出现此处最多的元素(类标签)，创建函数createTree用来递归构建决策树。编写代码如下：
递归创建决策树时，递归有两个终止条件：第一个停止条件是所有的类标签完全相同，则直接返回该类标签；第二个停止条件是使用完了所有特征，仍然不能将数据划分仅包含唯一类别的分组，即决策树构建失败，特征不够用。此时说明数据纬度不够，由于第二个停止条件无法简单地返回唯一的类标签，这里挑选出现数量最多的类别作为返回值。
运行上述代码，我们可以看到如下结果：
可见，我们的决策树已经构建完成了。这时候，有的朋友可能会说，这个决策树看着好别扭，虽然这个能看懂，但是如果多点的结点，就不好看了。能直观点吗？完全没有问题，我们可以使用强大的Matplotlib绘制决策树。
3、决策树可视化
这里代码都是关于Matplotlib的，如果对于Matplotlib不了解的，可以先学习下，Matplotlib的内容这里就不再累述。可视化需要用到的函数：
对可视化决策树的程序进行了详细的注释，直接看代码，调试查看即可。为了显示中文，需要设置FontProperties，代码编写如下：
(点击图片查看大图)
不出意外的话，我们就可以得到如下结果，可以看到决策树绘制完成。plotNode函数的工作就是绘制各个结点，比如有自己的房子、有工作、yes、no，包括内结点和叶子结点。plotMidText函数的工作就是绘制各个有向边的属性。
4、使用决策树执行分类
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子结点；最后将测试数据定义为叶子结点所属的类型。在构建决策树的代码，可以看到，有个featLabels参数。它是用来干什么的？它就是用来记录各个分类结点的，在用决策树做预测的时候，我们按顺序输入需要的分类结点的属性值即可。举个例子，比如我用上述已经训练好的决策树做分类，那么我只需要提供这个人是否有房子，是否有工作这两个信息即可，无需提供冗余的信息。
用决策树做分类的代码很简单，编写代码如下：
(点击图片，查看大图)
这里只增加了classify函数，用于决策树分类。输入测试数据[0,1]，它代表没有房子，但是有工作，分类结果如下所示：
看到这里，细心的朋友可能就会问了，每次做预测都要训练一次决策树？这也太麻烦了吧？有什么好的解决吗？
5、决策树的存储
假设我们已经得到决策树
使用pickle.dump存储决策树。
#-*-coding:UTF-8-*-importpickle"""函数说明:存储决策树Parameters:inputTree-已经生成的决策树filename-决策树的存储文件名Returns:无"""defstoreTree(inputTree,filename):withopen(filename,'wb')asfw:pickle.dump(inputTree,fw)if__name__=='__main__':myTree={'有自己的房子':{0:{'有工作':{0:'no',1:'yes'}},1:'yes'}}storeTree(myTree,'classifierStorage.txt')
运行代码，在该Python文件的相同目录下，会生成一个名为classifierStorage.txt的txt文件，这个文件二进制存储着我们的决策树。我们可以使用VScode打开看下存储结果。
看不懂？没错，因为这个是个二进制存储的文件，我们也无需看懂里面的内容，会存储，会用即可。那么问题来了。将决策树存储完这个二进制文件，然后下次使用的话，怎么用呢？
很简单使用pickle.load进行载入即可，编写代码如下：
#-*-coding:UTF-8-*-importpickle"""函数说明:读取决策树Parameters:filename-决策树的存储文件名Returns:pickle.load(fr)-决策树字典"""defgrabTree(filename):fr=open(filename,'rb')returnpickle.load(fr)if__name__=='__main__':myTree=grabTree('classifierStorage.txt')print(myTree)
如果在该Python文件的相同目录下，有一个名为classifierStorage.txt的文件，那么我们就可以运行上述代码，运行结果如下图所示：
从上述结果中，我们可以看到，我们顺利加载了存储决策树的二进制文件。
四、Sklearn之使用决策树预测隐形眼睛类型
1、实战背景
进入本文的正题：眼科医生是如何判断患者需要佩戴隐形眼镜的类型的？一旦理解了决策树的工作原理，我们甚至也可以帮助人们判断需要佩戴的镜片类型。
一共有24组数据，数据的Labels依次是age、prescript、astigmatic、tearRate、class，也就是第一列是年龄，第二列是症状，第三列是是否散光，第四列是眼泪数量，第五列是最终的分类标签。数据如下图所示：
可以使用已经写好的Python程序构建决策树，不过出于继续学习的目的，本文使用Sklearn实现。
2、使用Sklearn构建决策树
官方英文文档地址：
sklearn.tree模块提供了决策树模型，用于解决分类问题和回归问题。方法如下图所示：
本次实战内容使用的是DecisionTreeClassifier和export_graphviz，前者用于决策树构建，后者用于决策树可视化。
DecisionTreeClassifier构建决策树：
让我们先看下DecisionTreeClassifier这个函数，一共有12个参数：
参数说明如下：
除了这些参数要注意以外，其他在调参时的注意点有：
sklearn.tree.DecisionTreeClassifier()提供了一些方法供我们使用，如下图所示：
了解到这些，我们就可以编写代码了。
注意一点，由于fit()函数不能接收string类型的数据，通过打印的信息可以看到，数据都是string类型的。在使用fit()函数之前，我们需要对数据集进行编码，这里可以使用两种方法：
为了对string类型的数据序列化，需要先生成pandas数据，这样方便我们的序列化工作。这里我使用的方法是，原始数据->字典->pandas数据，编写代码如下：
importpandasaspdif__name__=='__main__':withopen('lenses.txt','r')asfr:#加载文件lenses=[inst.strip().split('\t')forinstinfr.readlines()]#处理文件lenses_target=[]#提取每组数据的类别，保存在列表里foreachinlenses:lenses_target.append(each[-1])lensesLabels=['age','prescript','astigmatic','tearRate']#特征标签lenses_list=[]#保存lenses数据的临时列表lenses_dict={}#保存lenses数据的字典，用于生成pandasforeach_labelinlensesLabels:#提取信息，生成字典foreachinlenses:lenses_list.append(each[lensesLabels.index(each_label)])lenses_dict[each_label]=lenses_listlenses_list=[]print(lenses_dict)#打印字典信息lenses_pd=pd.DataFrame(lenses_dict)#生成pandas.DataFrameprint(lenses_pd)
从运行结果可以看出，顺利生成pandas数据。
接下来，将数据序列化，编写代码如下：
#-*-coding:UTF-8-*-importpandasaspdfromsklearn.preprocessingimportLabelEncoderimportpydotplusfromsklearn.externals.siximportStringIOif__name__=='__main__':withopen('lenses.txt','r')asfr:#加载文件lenses=[inst.strip().split('\t')forinstinfr.readlines()]#处理文件lenses_target=[]#提取每组数据的类别，保存在列表里foreachinlenses:lenses_target.append(each[-1])lensesLabels=['age','prescript','astigmatic','tearRate']#特征标签lenses_list=[]#保存lenses数据的临时列表lenses_dict={}#保存lenses数据的字典，用于生成pandasforeach_labelinlensesLabels:#提取信息，生成字典foreachinlenses:lenses_list.append(each[lensesLabels.index(each_label)])lenses_dict[each_label]=lenses_listlenses_list=[]#print(lenses_dict)#打印字典信息lenses_pd=pd.DataFrame(lenses_dict)...