决策树

决策树算法分支处理基本流程划分选择信息增益增益率

决策树算法

分类算法是利用训练样本集获得分类函数即分类模型（分类器），从而实现将数据集中的样本划分到各个类中。分类模型通过学习训练样本中的属性集与类别之间的潜在关系，并以此为依据对新样本属于哪一类进行预测。

决策树通过把数据样本分配到某个叶子结点来确定数据集中样本所属的分类决策树由结点、分支和叶子结点组成 决策结点表示在样本的一个属性上进行的划分分支表示对于决策结点进行划分的输出叶结点代表经过分支到达的类 从决策树根结点出发，自顶向下移动，在每个决策结点都会进行次划分，通过划分的结果将样本进行分类，导致不同的分支，最后到达叶子结点，这个过程就是利用决策树进行分类的过程

分支处理

往往使用启发式算法来进行决策树的构造，例如，使用贪婪算法对每个结点构造部分最优决策树对于一个决策树的构建，最重要的部分就在于其分支处理，即确定在每个决策结点处的分支属性分支属性的选取即对决策节点上选择哪一个属性来对数据集进行划分，要求每个分支中样本的类别纯度尽可能高，而且不要产生样本数量太少的分支

基本流程

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

划分选择

决策树学习的关键是，如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)

西瓜数据集，如下图所示：

信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合$D$中的第$k$类样本所占的比例为$p_k(k=1,2,...,|y|$)，则$D$的信息熵定义为$$Ent(D)=-\sum _1^{|y|}{p}_k\ast lo{g}_2{p}_k$$ $Ent(D)$的值越小，则$D$的纯度越高。

假定离散属性$a$有$V$个可能的取值$\{a^1,a^2,...,a^V\}$,若使用$a$来对样本集$D$进行划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$的样本，记为$D^v$。根据上述公式计算出$D$的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$|D^v|/|D|$，即样本数越多的分支结点的影响越大，于是可以计算出用属性$a$对样本集$D$进行划分所获得的“信息增益”(information gain) $$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$ 一般而言，信息增益越大，则意味着使用属性$a$来划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择，即在算法流程的第8行选择属性$a_{\ast }=arg{\max }_{a\in A}Gain(D,a)$。著名的ID3决策树学习算法$[Quinlan,1986]$就是以信息增益为准则来选择划分属性。

下面给出对根结点信息熵的计算ID3.py

# -*- coding: utf-8 -*- # @Time : 2020/07/02 # @Author : AWAYASAWAY # @File : tree.py # @IDE : PyCharm from math import log from decimal import Decimal def calcShannonEnt(dataSet): ''' 计算给定数据集的根节点的香农熵：一般为最后一列 :param dataSet: :return:返回根结点的shannonEnt ''' # 获取数据集dataSet列表的长度 numEntries = len(dataSet) # 新建一个数据字典，用来统计每个标签出现的次数，计算概率 labelCounts = {} for featVec in dataSet: # featVec[-1]获取dataSet每行中最后一个数据，作为字典中的key（标签） currentLabel = featVec[-1] # 以currentLabel作为key加入到labelCounts # 如果当前的键值不存在，则扩展字典并将当前的键值加入字典。每个键值都记录了当前类别出现的次数。 # 键值存在则对应Value+'a',否则为'b' if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 Ent = 0.0 shannonEnt = 0.0 for key in labelCounts: # 计算正反例样本 # print('labels：', key) # 计算分类概率=标签发生的频率(labelCounts[key]) / 数据集长度 prob = float(labelCounts[key]) / numEntries # 计算香农熵，以'c'为底求对数 shannonEnt += -prob * log(prob, 2) return shannonEnt def createDataset(): ''' 创建数据：西瓜书 76 页 数据类型：不限定 :dataSet:西瓜数据集 :return:dataSet, label ''' dataSet = [ ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'], ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['青绿', '稍缩', '浊响', '清晰', '稍凹', '软粘', '是'], ['乌黑', '稍缩', '浊响', '稍糊', '稍凹', '软粘', '是'], ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '硬滑', '是'], ['乌黑', '稍缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'], ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'], ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'], ['青绿', '稍缩', '浊响', '稍糊', '凹陷', '硬滑', '否'], ['浅白', '稍缩', '沉闷', '稍糊', '凹陷', '硬滑', '否'], ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '软粘', '否'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'], ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'] ] labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜'] return dataSet, labels def splitDataSet(dataSet, axis, value): ''' 按照给定特征划分数据集 :param dataSet: :param axis: :param value: :return: ''' retDataSet = [] for featVec in dataSet: if featVec[axis] == value: # reduceFeatVec 为新生的空list reduceFeatVec = featVec[:axis] # extend只是扩展长度 reduceFeatVec.extend(featVec[axis + 1:]) # append添加列表 retDataSet.append(reduceFeatVec) return retDataSet def chooseBestFeature2Split(dataSet): ''' 选择最好的数据集划分方式 :param dataSet: :return: ''' # 提取特属性集合的长度 numFeatures = len(dataSet[0]) - 1 # 根结点的香农熵/整个数据集的原始香农熵 baseEntropy = calcShannonEnt(dataSet) print('整个数据集的原始香农熵 %.3f' % baseEntropy) # 特征 i 拥有最好的信息增益 bestInfoGain = 0.0 bestFeature = -1 featInfoGain = [] for i in range(numFeatures): # 将dataSet中的数据先按行依次放入example中，然后取得example中的example[i]元素,放入列表featList中 # 提取所有的属性值 featList = [example[i] for example in dataSet] # print(featList) # 删除重复的属性值,创建唯一的分类标签列表 uniqueVals = listDeduplication(featList) # uniqueVals = set(featList) newEntropy = 0.0 # 计算每种划分方式的信息熵 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet) / float(len(dataSet)) newEntropy += prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy infoGain = float(Decimal(infoGain).quantize(Decimal('0.000'))) featInfoGain.append((infoGain)) if infoGain > bestInfoGain: bestInfoGain = infoGain bestFeature = i return featInfoGain, bestFeature, bestInfoGain def listDeduplication(x): ''' List去重 :param x: list :return: list ''' return list(dict.fromkeys(x)) if __name__ == '__main__': dataSet, labels = createDataset() featInfoGain, bestFeature, bestInfoGain = chooseBestFeature2Split(dataSet) print('各个属性的信息增益') d = dict(zip(labels[:-1], featInfoGain)) for key, value in d.items(): print(key, '=', value) print(labels[bestFeature], '的信息增益最大= %.3f'% bestInfoGain) 整个数据集的原始香农熵 0.998 各个属性的信息增益 色泽 = 0.108 根蒂 = 0.143 敲声 = 0.141 纹理 = 0.381 脐部 = 0.289 触感 = 0.006 纹理 的信息增益最大= 0.381

增益率

但是当每个分支结点仅包含一个样本时，这些分支结点的纯度已达到最大（如，编号列）。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效的预测。

实际上，信息增益准则对可能取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的$C4.5$决策树算法$[Quinlan,1993]$不直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优的划分属性，增益率定义为: $$GainRation(D,a)=\frac{Gain(D,a)}{IV(a)}$$ 其中 $$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$ 称为$a$的“固有值”$(intrinsicvalue)[Quinlan,1993].$ 属性$a$的可能取值数目越多(即$V$越大)，则$IV(a)$的值通常会很大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，$C4.5$算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式$[Quinlan,1993]:$ 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

下面给出的计算C4.5.py

#-*- coding: utf-8 -*- # @Time : 2020/7/2 16:24 # @Author : AWAYASAWAY # @File : C4.5.py # @IDE : PyCharm from math import log from decimal import Decimal def calcShannonEnt(dataSet): ''' 计算给定数据集的根节点的香农熵：一般为最后一列 :param dataSet: :return:返回根结点的shannonEnt ''' # 获取数据集dataSet列表的长度 numEntries = len(dataSet) # 新建一个数据字典，用来统计每个标签出现的次数，计算概率 labelCounts = {} for featVec in dataSet: # featVec[-1]获取dataSet每行中最后一个数据，作为字典中的key（标签） currentLabel = featVec[-1] # 以currentLabel作为key加入到labelCounts # 如果当前的键值不存在，则扩展字典并将当前的键值加入字典。每个键值都记录了当前类别出现的次数。 # 键值存在则对应Value+'a',否则为'b' if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 Ent = 0.0 shannonEnt = 0.0 for key in labelCounts: # 计算正反例样本 # print('labels：', key) # 计算分类概率=标签发生的频率(labelCounts[key]) / 数据集长度 prob = float(labelCounts[key]) / numEntries # 计算香农熵 shannonEnt += -prob * log(prob, 2) return shannonEnt def createDataset(): ''' 创建数据：西瓜书 76 页 数据类型：不限定 :dataSet:西瓜数据集 :return:dataSet, label ''' dataSet = [ ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'], ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'], ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'], ['青绿', '稍缩', '浊响', '清晰', '稍凹', '软粘', '是'], ['乌黑', '稍缩', '浊响', '稍糊', '稍凹', '软粘', '是'], ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '硬滑', '是'], ['乌黑', '稍缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'], ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'], ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'], ['青绿', '稍缩', '浊响', '稍糊', '凹陷', '硬滑', '否'], ['浅白', '稍缩', '沉闷', '稍糊', '凹陷', '硬滑', '否'], ['乌黑', '稍缩', '浊响', '清晰', '稍凹', '软粘', '否'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'], ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'] ] labels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '好瓜'] return dataSet, labels def splitDataSet(dataSet, axis, value): ''' 按照给定特征划分数据集 :param dataSet: :param axis: :param value: :return: ''' retDataSet = [] for featVec in dataSet: if featVec[axis] == value: # reduceFeatVec 为新生的空list reduceFeatVec = featVec[:axis] # extend只是扩展长度 reduceFeatVec.extend(featVec[axis + 1:]) # append添加列表 retDataSet.append(reduceFeatVec) return retDataSet def chooseBestFeature2Split(dataSet): ''' 选择最好的数据集划分方式 :param dataSet: :return: ''' # 提取特属性集合的长度 numFeatures = len(dataSet[0]) - 1 # 根结点的香农熵/整个数据集的原始香农熵 baseEntropy = calcShannonEnt(dataSet) print('整个数据集的原始香农熵 %.3f' % baseEntropy) # 特征 i 拥有最好的信息增益 bestInfoGain = 0.0 bestGainRatio = 0.0 bestFeature = -1 featInfoGain = [] featGainRatio = [] for i in range(numFeatures): # 将dataSet中的数据先按行依次放入example中，然后取得example中的example[i]元素,放入列表featList中 # 提取所有的属性值 featList = [example[i] for example in dataSet] # print(featList) # 删除重复的属性值,创建唯一的分类标签列表 #uniqueVals = listDeduplication(featList) uniqueVals = set(featList) newEntropy = 0.0 intrinsicValue = 0.0 # 计算每种划分方式的信息熵 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet) / float(len(dataSet)) intrinsicValue += -prob * log(prob, 2) newEntropy += prob * calcShannonEnt(subDataSet) # 计算每个属性的信息增益，添加到列表featInfoGain print('固有值：IV(a)=%.3f' % intrinsicValue) infoGain = baseEntropy - newEntropy infoGain = float(Decimal(infoGain).quantize(Decimal('0.000'))) featInfoGain.append((infoGain)) # 计算每个属性的信息增益率，添加到列表featGainRatio gainRatio = infoGain / intrinsicValue gainRatio = float(Decimal(gainRatio).quantize(Decimal('0.000'))) featGainRatio.append(gainRatio) if gainRatio > bestGainRatio: bestGainRatio = gainRatio bestFeature = i return featInfoGain, featGainRatio, bestFeature, bestInfoGain, bestGainRatio, newEntropy def listDeduplication(x): ''' set函数就可以 :param x: list :return: list ''' return list(dict.fromkeys(x)) if __name__ == '__main__': dataSet, labels = createDataset() # 输出 featInfoGain, \ featGainRatio, \ bestFeature,\ bestInfoGain,\ bestGainRatio,\ newEntropy = chooseBestFeature2Split(dataSet) print('各个属性的信息增益') d = dict(zip(labels[:-1], featInfoGain)) for key, value in d.items(): print(key, '=', value) print('各个属性的信息增益率') c = dict(zip(labels[:-1], featGainRatio)) for key, value in c.items(): print(key, '=', value) print(labels[bestFeature], '的信息增益率最大= %.3f'% bestGainRatio)

计算结果如下：

整个数据集的原始香农熵 0.998 固有值：IV(a)=1.580 固有值：IV(a)=1.402 固有值：IV(a)=1.333 固有值：IV(a)=1.447 固有值：IV(a)=1.549 固有值：IV(a)=0.874 各个属性的信息增益 色泽 = 0.108 根蒂 = 0.143 敲声 = 0.141 纹理 = 0.381 脐部 = 0.289 触感 = 0.006 各个属性的信息增益率 色泽 = 0.068 根蒂 = 0.102 敲声 = 0.106 纹理 = 0.263 脐部 = 0.187 触感 = 0.007 纹理 的信息增益率最大= 0.263 ):