《机器学习实战之决策树熵的概述》由会员分享，可在线阅读，更多相关《机器学习实战之决策树熵的概述（12页珍藏版）》请在金锄头文库上搜索。
1、机器学习实战之决策树熵的概述实战之决策树熵的概述一、简介决策树(tree)是一种基本的分类与回归方法。举个通俗易懂的例子，如下图所示的流程图就是一个决策树，长方形代表判断模块(decisionblock)，椭圆形成代表终止模块(terminatingblock)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作为分支(branch)，它可以达到另一个判断模块或者终止模块。我们还可以这样理解，分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directededge)组成。结点有两种类型：内部结点(internalnode)和叶结点(leafnode
2、)。内部结点表示一个特征或属性，叶结点表示一个类。如下图所示的决策树，长方形和椭圆形都是结点。长方形的结点属于内部结点，椭圆形的结点属于叶结点，从结点引出的左右箭头就是有向边。而最上面的结点就是决策树的根结点(rootnode)。这样，结点说法就与模块说法对应上了，理解就好。我们回到这个流程图，对，你没看错，这就是一个假想的相亲对象分类系统。它首先检测相亲对方是否有房。如果有房，则对于这个相亲对象可以考虑进一步接触。如果没有房，则观察相亲对象是否有上进心，如果没有，直接SayGoodbye,此时可以说：你人很好，但是我们不合适。如果有，则可以把这个相亲对象列入候选名单，好听点叫候选名单，有点瑕
3、疵地讲，那就是备胎。不过这只是个简单的相亲对象分类系统，只是做了简单的分类。真实情况可能要复杂得多，考虑因素也可以是五花八门。脾气好吗？会做饭吗？愿意做家务吗？家里几个孩子？父母是干什么的？天啊，我不想再说下去了，想想都可怕。我们可以把决策树看成一个if-then规则的集合，将决策树转换成if-then规则的过程是这样的：由决策树的根结点(rootnode)到叶结点(leafnode)的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规
4、则所覆盖，而且只被一条路径或一条规则所覆盖。这里所覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。二、决策树的一般流程(1) 收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过采访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。(2) 准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。(3) 分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。(4) 训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一
5、个决策树的数据结构。(5) 测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。(6) 使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。三、决策树构建的准备工作使用决策树做预测的每一步骤都很重要，数据收集不到位，将会导致没有足够的特征让我们构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，将会导致无法构建出分类效果好的决策树。从算法方面看，决策树的构建是我们的核心内容。总的来说构建一个合适的模型是至关重要的,如何构建就需要我们丰富的业务理解能力和对数据的敏感程度决策树要如何构建呢？通常，这一过程可以概括为3个
6、步骤：、决策树的生成和决策树的修剪。1、特征选择特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的标准是信息增益(informationgain)或信息增益比，为了简单，本文使用信息增益作为选择特征的标准。那么，什么是信息增益？在讲解信息增益之前，让我们看一组实例，贷款申请样本数据表。1D有工作有自己时雇孑信療清况类别(是否介蜡货款)1青年否2青年不否好否3青年是否好是4肯年in5青年否杏股杏6中年否_醴7中年否好否8
7、中年是好是9中年否口10中年否非常好11老年否是非常好是12老年否是好是13老年是否好是14老年F=1否非幣好是15老年否否否希望通过所给的训练数据学习一个贷款申请的决策树，用于对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。年龄图(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是：究
8、竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。什么是信息增益呢？在划分数据集之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。(1香农熵在可以评测哪个数据划分方式是最好的数据划分之前，我们必须学习如何计算信息增益。集合信息的度量方式称为香农熵或者简称为熵(entropy)，这个名字来源于信息论之父克劳德香农。如果看
9、不明白什么是信息增益和熵，请不要着急，因为他们自诞生的那一天起，就注定会令世人十分费解。克劳德香农写完信息论之后,约翰冯诺依曼建议使用熵这个术语，因为大家都不知道它是什么意思。H(D)二熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。如果待分类的事物可能划分在多个分类之中，则符号xi的信息定义为：1(雋)=-lOV(Xi)其中p(xi)是选择该分类的概率。上述式中的对数以2为底，也可以e为底(自然对数)。通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：H二-p(xj其中n是分类的数目。
10、熵越大，随机变量的不确定性就越大。当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empiricalentropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D,则训练数据集D的经验熵为H(D),|D|表示其样本容量，及样本个数。设有K个类Ck,=1,2,3,-,K,|Ck|为属于类Ck的样本个数，因此经验熵公式就可以写为|D|D|根据此公式计算经验熵
11、H(D),分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知,在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：9966H(D)=-log2-log2-=0.971经过计算可知，数据集D的经验熵H(D)的值为0.971。(创)编写代码计算经验熵在编写代码之前，我们先对数据集进行属性标注。、年龄：0代表青年，1代表中年，2代表老年；二、有工作：0代表否，1代表是；三、有自己的房子：0代表否，1代表是；四、信贷情况：0代表一般，1代表好，2代表非常好；五、类别(是否给贷款)：no代表否，yes代表是。确定这些之后
12、，我们就可以创建数据集，并计算经验熵了，代码编写如下：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758HHH函数说明:创建测试数据集Parameters:无Returns:dataSet-数据集labels-特征标签Modify:2020-06-28数据集分类属性返回数据集和分类属性defcreateDataSet():dataSet=0,0,0,0,no,0,0,0,1,no,0,1,0,1,yes,0,1,1,0,yes,0,
13、0,0,0,no,1,0,0,0,no,1,0,0,1,no,1,1,1,1,yes,1,0,1,2,yes,1,0,1,2,yes,2,0,1,2,yes,2,0,1,1,yes,2,1,0,1,yes,2,1,0,2,yes,2,0,0,0,nolabels=不放贷,放贷returndataSet,labelsfrommathimportlog函数说明:计算给定数据集的经验熵（香农熵）Parameters:dataSet-数据集Returns:shannonEnt-经验熵（香农熵）Modify:2020-06-28defcalcShannonEnt(dataSet):numEntires=
14、len(dataSet)返回数据集的行数labelCounts=保存每个标签Label)出现次数的字典forfeatVecindataSet:对每组特征向量进行统计currentLabel=featVec-1提取标签(Label)信息-1取集合最后一个数ifcurrentLabelnotinlabelCounts.keys():如果标签;Label)没有放入统计次数的字典忝加进去值为0次labelCountscurrentLabel=0labelCountscurrentLabel+=1Labe计数shannonEnt=0.0经验熵(香农熵)forkeyinlabelCounts:计算香农熵prob=float(labelCountskey)/numEntires选择该标签Label)的概率shannonEnt-=prob*log(prob,2)利用公式计算returnshannonEnt返回经验熵(香农熵)if_name_=_main_:dataSet,features=createDataSet()print(dataSet)print(calcShannonEnt(dataSet)运行结果如下:
