决策树的一些知识

tech2022-10-11  85

决策树的一些知识

决策树决策树的定义:决策树示意图,圆点——内部节点,方框——叶节点 决策树的构造:决策树的特点:信息增益:特征选择案例(统计学习方法):决策树的生成

决策树

决策树的定义:

分类决策树模型是一种描述对实例进行分类的树形结构,决策树由结点和有向边组成,结点有两种类型:内部结点和叶结点。内部节点表示一个特征或属性,叶结点表示一个类。

决策树示意图,圆点——内部节点,方框——叶节点

决策树学习的目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。

决策树学习的本质:从训练集中归纳出一组分类规则,或者说是由训练数据集估计条件概率模型。

决策树学习的损失函数:正则化的极大似然函数

决策树学习的测试:最小化损失函数

决策树学习的目标:在损失函数的意义下,选择最优决策树的问题。

决策树原理和问答猜测结果游戏相似,根据一系列数据,然后给出游戏的答案。

决策树的构造:

决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。

1) 开始:构建根节点,将所有训练数据都放在根节点,选择一个最优特征,按着这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。

2) 如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到所对应的叶节点去。

3)如果还有子集不能够被正确的分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的节点,如果递归进行,直至所有训练数据子集被基本正确的分类,或者没有合适的特征为止。

4)每个子集都被分到叶节点上,即都有了明确的类,这样就生成了一颗决策树。

决策树的特点:

优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。

缺点:可能会产生过度匹配的问题

适用数据类型:数值型和标称型

首先:确定当前数据集上的决定性特征,为了得到该决定性特征,必须评估每个特征,完成测试之后,原始数据集就被划分为几个数据子集,这些数据子集会分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一类型,则当前无序阅读的垃圾邮件已经正确的划分数据分类,无需进一步对数据集进行分割,如果不属于同一类,则要重复划分数据子集,直到所有相同类型的数据均在一个数据子集内。

信息增益:

划分数据集的大原则是:将无序数据变得更加有序,但是各种方法都有各自的优缺点,信息论是量化处理信息的分支科学,在划分数据集前后信息发生的变化称为信息增益,获得信息增益最高的特征就是最好的选择,所以必须先学习如何计算信息增益,集合信息的度量方式称为香农熵,或者简称熵。

希望通过所给的训练数据学习一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请人的特征利用决策树决定是否批准贷款申请。

特征选择就是决定用哪个特征来划分特征空间。比如,我们通过上述数据表得到两个可能的决策树,分别由两个不同特征的根结点构成。 图(a)所示的根结点的特征是年龄,有3个取值,对应于不同的取值有不同的子结点。图(b)所示的根节点的特征是工作,有2个取值,对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是:究竟选择哪个特征更好些?这就要求确定选择特征的准则。直观上,如果一个特征具有更好的分类能力,或者说,按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有最好的分类,那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

什么是信息增益呢?在划分数据集之前之后信息发生的变化成为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。

熵定义为信息的期望值,如果待分类的事物可能划分在多个类之中,则符号Xi的信息定义为: 其中,p(Xi)是选择该分类的概率。

为了计算熵,我们需要计算所有类别所有可能值所包含的信息期望值,通过下式得到: 其中,nn为分类数目,熵越大,随机变量的不确定性就越大。

当熵中的概率由数据估计(特别是最大似然估计)得到时,所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计?比如有10个数据,一共有两个类别,A类和B类。其中有7个数据属于A类,则该A类的概率即为十分之七。其中有3个数据属于B类,则该B类的概率即为十分之三。浅显的解释就是,这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D,则训练数据集D的经验熵为H(D),|D|表示其样本容量,及样本个数。设有K个类Ck,k = 1,2,3,···,K,|Ck|为属于类Ck的样本个数,这经验熵公式可以写为: 根据此公式计算经验熵H(D),分析贷款申请样本数据表中的数据。最终分类结果只有两类,即放贷和不放贷。根据表中的数据统计可知,在15个数据中,9个数据的结果为放贷,6个数据的结果为不放贷。所以数据集D的经验熵H(D)为: 经过计算可知,数据集D的经验熵H(D)的值为0.971。

在理解信息增益之前,要明确——条件熵

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y∣X)H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性,随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X),定义X给定条件下Y的条件概率分布的熵对X的数学期望: 当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的分别为经验熵和经验条件熵,此时如果有0概率,令0log0=00log0=0

信息增益:信息增益是相对于特征而言的。所以,特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:

g(D,A)=H(D)−H(D∣A)

一般地,熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益值的大小相对于训练数据集而言的,并没有绝对意义,在分类问题困难时,也就是说在训练数据集经验熵大的时候,信息增益值会偏大,反之信息增益值会偏小,使用信息增益比可以对这个问题进行校正,这是特征选择的另一个标准。

信息增益比:特征AA对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集DD的经验熵之比:

特征选择案例(统计学习方法):

如图 计算并得出最优特征: 在编写代码之前,我们先对数据集进行属性标注。

年龄:0代表青年,1代表中年,2代表老年; 有工作:0代表否,1代表是; 有自己的房子:0代表否,1代表是; 信贷情况:0代表一般,1代表好,2代表非常好; 类别(是否给贷款):no代表否,yes代表是。 创建数据集,计算经验熵的代码如下:

from math import log """ 函数说明:创建测试数据集 Parameters:无 Returns: dataSet:数据集 labels:分类属性 Modify: 2018-03-12 """ def creatDataSet(): # 数据集 dataSet=[[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 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, 'no']] #分类属性 labels=['年龄','有工作','有自己的房子','信贷情况'] #返回数据集和分类属性 return dataSet,labels """ 函数说明:计算给定数据集的经验熵(香农熵) Parameters: dataSet:数据集 Returns: shannonEnt:经验熵 Modify: 2018-03-12 """ def calcShannonEnt(dataSet): #返回数据集行数 numEntries=len(dataSet) #保存每个标签(label)出现次数的字典 labelCounts={} #对每组特征向量进行统计 for featVec in dataSet: currentLabel=featVec[-1] #提取标签信息 if currentLabel not in labelCounts.keys(): #如果标签没有放入统计次数的字典,添加进去 labelCounts[currentLabel]=0 labelCounts[currentLabel]+=1 #label计数 shannonEnt=0.0 #经验熵 #计算经验熵 for key in labelCounts: prob=float(labelCounts[key])/numEntries #选择该标签的概率 shannonEnt-=prob*log(prob,2) #利用公式计算 return shannonEnt #返回经验熵 #main函数 if __name__=='__main__': dataSet,features=creatDataSet() print(dataSet) print(calcShannonEnt(dataSet))

结果如下

0个特征的增益为0.0831个特征的增益为0.3242个特征的增益为0.4203个特征的增益为0.3630个特征的增益为0.2521个特征的增益为0.9182个特征的增益为0.474 {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

计算信息增益

from math import log """ 函数说明:创建测试数据集 Parameters:无 Returns: dataSet:数据集 labels:分类属性 Modify: 2018-03-12 """ def creatDataSet(): # 数据集 dataSet=[[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 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, 'no']] #分类属性 labels=['年龄','有工作','有自己的房子','信贷情况'] #返回数据集和分类属性 return dataSet,labels """ 函数说明:计算给定数据集的经验熵(香农熵) Parameters: dataSet:数据集 Returns: shannonEnt:经验熵 Modify: 2018-03-12 """ def calcShannonEnt(dataSet): #返回数据集行数 numEntries=len(dataSet) #保存每个标签(label)出现次数的字典 labelCounts={} #对每组特征向量进行统计 for featVec in dataSet: currentLabel=featVec[-1] #提取标签信息 if currentLabel not in labelCounts.keys(): #如果标签没有放入统计次数的字典,添加进去 labelCounts[currentLabel]=0 labelCounts[currentLabel]+=1 #label计数 shannonEnt=0.0 #经验熵 #计算经验熵 for key in labelCounts: prob=float(labelCounts[key])/numEntries #选择该标签的概率 shannonEnt-=prob*log(prob,2) #利用公式计算 return shannonEnt #返回经验熵 """ 函数说明:计算给定数据集的经验熵(香农熵) Parameters: dataSet:数据集 Returns: shannonEnt:信息增益最大特征的索引值 Modify: 2018-03-12 """ def chooseBestFeatureToSplit(dataSet): #特征数量 numFeatures = len(dataSet[0]) - 1 #计数数据集的香农熵 baseEntropy = calcShannonEnt(dataSet) #信息增益 bestInfoGain = 0.0 #最优特征的索引值 bestFeature = -1 #遍历所有特征 for i in range(numFeatures): # 获取dataSet的第i个所有特征 featList = [example[i] for example in dataSet] #创建set集合{},元素不可重复 uniqueVals = set(featList) #经验条件熵 newEntropy = 0.0 #计算信息增益 for value in uniqueVals: #subDataSet划分后的子集 subDataSet = splitDataSet(dataSet, i, value) #计算子集的概率 prob = len(subDataSet) / float(len(dataSet)) #根据公式计算经验条件熵 newEntropy += prob * calcShannonEnt((subDataSet)) #信息增益 infoGain = baseEntropy - newEntropy #打印每个特征的信息增益 print("第%d个特征的增益为%.3f" % (i, infoGain)) #计算信息增益 if (infoGain > bestInfoGain): #更新信息增益,找到最大的信息增益 bestInfoGain = infoGain #记录信息增益最大的特征的索引值 bestFeature = i #返回信息增益最大特征的索引值 return bestFeature """ 函数说明:按照给定特征划分数据集 Parameters: dataSet:待划分的数据集 axis:划分数据集的特征 value:需要返回的特征的值 Returns: shannonEnt:经验熵 Modify: 2018-03-12 """ def splitDataSet(dataSet,axis,value): retDataSet=[] for featVec in dataSet: if featVec[axis]==value: reducedFeatVec=featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet #main函数 if __name__=='__main__': dataSet,features=creatDataSet() # print(dataSet) # print(calcShannonEnt(dataSet)) print("最优索引值:"+str(chooseBestFeatureToSplit(dataSet)))

结果

0个特征的增益为0.0831个特征的增益为0.3242个特征的增益为0.4203个特征的增益为0.363 最优索引值:2

也就是说最优特征是有自己的房子,因为他的信息增益g(D,A3)最大

决策树的生成

稍后再写。

最新回复(0)