决策树的一些知识

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

决策树

决策树的定义：

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

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

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

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

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

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

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

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

决策树的构造：

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

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.083 第1个特征的增益为0.324 第2个特征的增益为0.420 第3个特征的增益为0.363 第0个特征的增益为0.252 第1个特征的增益为0.918 第2个特征的增益为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.083 第1个特征的增益为0.324 第2个特征的增益为0.420 第3个特征的增益为0.363 最优索引值：2

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

决策树的生成

稍后再写。