一、前言

  前一节讲述了机器学习决策树的原理，以及如何选择最优特征作为分类特征。本节主要内容：

• 决策树构建
• 决策树可视化（白盒模型，神经网络是黑盒模型）
• 使用决策树进行分类预测
• 决策树存储与读取
• sklearn预测隐形眼镜类型

二、决策树构建

**决策树生成原理：**得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据，因此可以采用递归的原则处理数据集。
决策树优缺点：

• 计算复杂度不高，输出结果易于理解：以ID3为例，每次运算都是基于某一列特征，特征计算完后，下次计算不考虑该最优特征，并且通过适当剪枝可以简化复杂度；
• 对中间的缺失值不敏感；
• 可以处理不相关特征数据：是基于每一列特征来计算，不考虑特征之间的依赖关系。

决策树算法种类：

ID3
以信息增益作为树的分裂准则，该算法存在的不足：

• ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用，如果一定要运用ID3出来连续属性，那么要自己将连续特征离散化
• 对于缺失值的情况没有做考虑
• 偏向于多值属性，例如，如果存在唯一标识属性ID(每个样本的ID属性值都不相同)，则ID3会选择它作为优先分裂属性，这样显然使得划分充分纯净，但这种划分对分类几乎毫无用处

C4.5

• 以基于信息增益的增益率(gain ratio)作为树的分裂准则，解决了ID3的偏向于多值属性问题；
• 内部自己考虑了连续属性离散化过程，所以克服了ID3的偏向于多值属性问题；
• 内部考虑了缺失值的自动处理策略。

CART

• ID3和C4.5只能处理分类问题，而CART 可以处理分类和回归问题。

1 ID3算法

  ID3算法核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子节点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
  根据上一节求得结果，由于特征A3的信息增益最大，所以选择特征A3作为根结点的特征。它将训练集D划分为两个子集D1(A3取值为“是”)和D2(A3取值为“否”)。由于D1只有同一类样本点，所以它成为一个叶结点，结点的类标记为“是”。
对D2则需要从特征A1(年龄)，A4(信贷情况)中选择新的特征，计算各个特征的信息增益：

• g(D2,A1) = H(D2) - H(D2|A1) = 0.251
• g(D2,A2) = H(D2) - H(D2|A2) = 0.918
• g(D2,A4) = H(D2) - H(D2|A4) = 0.474

  根据计算，选择信息增益最大的特征A2(有工作)作为结点的特征。由于A2有两个可能取值，从这一结点引出两个子结点：一个对应“是”(有工作）的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为“是”；另一个对应“否”(无工作)的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为“否”。由此生成一颗决策树，该决策树只用了两个特征(有两个内部结点），生成的决策树如下图所示：

#！/user/bin/env python
# -*- coding:utf-8 -*-
#@Time  : 2020/3/3 10:54
#@Author: fangyuan
#@File  : 决策树构建决策树.pyfrom math import log
import operatordef calcShannonEnt(dataSet):numEntires = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntiresshannonEnt -= prob * log(prob,2)return shannonEntdef createDataSet():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,labelsdef 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 retDataSetdef chooseBestFeatureToSplit(dataSet):numFeatures = len(dataSet[0]) - 1baseEntropy = calcShannonEnt(dataSet)bestInfoGain = 0.0bestFeature = -1for i in range(numFeatures):featList = [example[i] for example in dataSet]uniqueVals = set(featList)newEntropy = 0.0for value in uniqueVals:subDataSet = splitDataSet(dataSet,i,value)prob = len(subDataSet) / float(len(dataSet))newEntropy += prob * calcShannonEnt(subDataSet)infoGain = baseEntropy - newEntropyif(infoGain > bestInfoGain):bestInfoGain = infoGainbestFeature = ireturn bestFeaturedef majorityCnt(classList):classCount = {}for vote in classList:if vote not in classCount.keys():classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)return sortedClassCount[0][0]def createTree(dataSet,labels,featLabels):classList = [example[-1] for example in dataSet]if classList.count(classList[0]) == len(classList):return classList[0]if len(dataSet[0]) == 1:return majorityCnt(classList)bestFeat = chooseBestFeatureToSplit(dataSet)bestFeatLabel = labels[bestFeat]featLabels.append(bestFeatLabel)myTree = {bestFeatLabel:{}}del(labels[bestFeat])featValues = [example[bestFeat] for example in dataSet]uniqueVals = set(featValues)for value in uniqueVals:myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),labels,featLabels)return myTreeif __name__ == '__main__':dataSet,labels = createDataSet()featLabels = []myTree = createTree(dataSet,labels,featLabels)print(myTree)

#！/user/bin/env python
# -*- coding:utf-8 -*-
#@Time  : 2020/3/3 15:06
#@Author: fangyuan
#@File  : 决策树测试分类.py#！/user/bin/env python
# -*- coding:utf-8 -*-
#@Time  : 2020/3/3 10:54
#@Author: fangyuan
#@File  : 决策树构建决策树.pyfrom math import log
import operatordef calcShannonEnt(dataSet):numEntires = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]if currentLabel not in labelCounts.keys():labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntiresshannonEnt -= prob * log(prob,2)return shannonEntdef createDataSet():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"""
删除第axis列，值为value的行数数据集，将数据集调整后并返回新建数据集
axis表示是第几个特征 value表示对应特征所取值
例如 axis = 0 value = 1 则返回的新数据集为(第6至第10行数据删除第一列)
[0,0,0,'no'],
[0,0,1,'no'],
[1,1,1,'yes'],
[0,1,2,'yes'],
[0,1,2,'yes']
"""
def splitDataSet(dataSet,axis,value):# 创建返回的数据集列表retDataSet = []# 按行遍历数据集for featVec in dataSet:# 如果某一行的第axis列值为valueif featVec[axis] == value:# 去掉该行的某个元素axis，如删除上述注释中第0列的1reducedFeatVec = featVec[:axis]# 将符合条件的行修改后添加到返回的数据集reducedFeatVec.extend(featVec[axis+1:])# 添加返回划分后的数据集retDataSet.append(reducedFeatVec)return retDataSetdef chooseBestFeatureToSplit(dataSet):# 特征列数为4numFeatures = len(dataSet[0]) - 1# 计算数据集香农熵baseEntropy = calcShannonEnt(dataSet)# 信息增益bestInfoGain = 0.0# 最优特征的索引值bestFeature = -1# 遍历所有特征(一列一列遍历的)for i in range(numFeatures):# 获取dataSet的第i个特征的所有取值，即第i列，从上到下依次取值featList = [example[i] for example in dataSet]# 创建set集合，元素不可重复，如特征1中，只有0，1，2代表的青年，中年，老年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 bestFeaturedef majorityCnt(classList):classCount = {}for vote in classList:if vote not in classCount.keys():classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)return sortedClassCount[0][0]"""
运用了createTree()函数的递归
递归算法中，包括两个固定步骤：递归头和递归体
递归头：什么时候不调用自己的方法，即递归的结束条件
递归体：什么时候需要调用自己的方法，即自己调用自己
优点：将问题逐渐简单化；
缺点：会占用大量的系统堆栈，内存耗用多，递归调用层数多时，比循环慢很多
"""
def createTree(dataSet,labels,featLabels):# 取分类标签即提取所有行元素最右边一个元素即为类标签(‘no’,'no','yes','yes'......)classList = [example[-1] for example in dataSet]# 如果类别完全相同则停止继续划分--第一个停止条件# list.count()统计列表中某个元素出现的次数# 例如仅仅使用有自己的房子这一特征，就能完全确定是否贷款，则其他特征无需继续执行if classList.count(classList[0]) == len(classList):return classList[0]# 遍历完所有特征时，还有若干数据时，返回出现次数最多的类标签--第二个停止条件# 若所有特征已经用完了，类别结果中，仍然有贷款或者不贷款两种情况，则使用投票表决法返回结果if len(dataSet[0]) == 1:return majorityCnt(classList)# 选择最优特征bestFeat = chooseBestFeatureToSplit(dataSet)# 最优特征的标签bestFeatLabel = labels[bestFeat]featLabels.append(bestFeatLabel)# 根据最优特征的标签生成树如{'有自己的房子':{}}myTree = {bestFeatLabel:{}}# 删除已经使用的特征标签del(labels[bestFeat])# 得到训练集中所有最优特征的属性值，当bestFeat为'有自己房子'时，即为第三列数据[0,0,0,1,0,0,0,1,1,1,1,1,0,0,0]featValues = [example[bestFeat] for example in dataSet]# 去掉重复的属性值，uniqueVal:{0,1}uniqueVals = set(featValues)# 遍历特征，创建决策树# 最优特征为'有自己房子'时，只有0，1两个分类，即以该特征为根节点，0，1为分支，将此数据集划分为两个子数据集，递归for value in uniqueVals:myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),labels,featLabels)return myTreedef classify(inputTree,featLabels,testVec):# 迭代firstStr = next(iter(inputTree))secondDict = inputTree[firstStr]# 将标签字符串转换为索引# index()方法查找当前列表中第一个匹配firstStr变量的元素featIndex = featLabels.index(firstStr)for key in secondDict.keys():if testVec[featIndex] == key:if type(secondDict[key]).__name__ == 'dict':classLabel = classify(secondDict[key],featLabels,testVec)else:classLabel = secondDict[key]return classLabelif __name__ == '__main__':dataSet,labels = createDataSet()print("最优特征索引值：" + str(chooseBestFeatureToSplit(dataSet)))featLabels = []myTree = createTree(dataSet,labels,featLabels)print(myTree)testVec = [0,1]result = classify(myTree,featLabels,testVec)if result == 'yes':print('放贷')if result == 'no':print('不放贷')

2 编写构建决策树代码

# 用字典表示决策树
{'有自己的房子':{0:{'有工作':{0:'no',1:'yes'}},1:'yes'}}

Python知识学习积累

• extend和append区别

>>> li = ['a', 'b', 'c']  
>>> li.extend(['d', 'e', 'f'])   
>>> li  
['a', 'b', 'c', 'd', 'e', 'f']  
>>> len(li)                      
6  
>>> li[-1]  
'f'  
>>> li = ['a', 'b', 'c']  
>>> li.append(['d', 'e', 'f'])   
>>> li  
['a', 'b', 'c', ['d', 'e', 'f']]  
>>> len(li)                      
4  
>>> li[-1]  
['d', 'e', 'f'] 

• next()与iter()函数
  引用链接
  引用链接