《机器学习实战》中关于决策树构建算法完全解析（一）

算法完全解析（一）"/>

《机器学习实战》中关于决策树构建算法完全解析（一）

#第三章决策树代码
from math import log
import operator#理解：香农熵是在计算事件可能性的离散度，越离散越难预测，不确定性越高
#计算给定数据集的香农熵
def calcShannonEnt(dataSet):                          #熵被定义为信息的期望值numEntries=len(dataSet)                           #数据集长度labelCounts={}                                    #字典for featVec in dataSet:                           #遍历数据集，为所有可能分类创建字典currentLabel=featVec[-1]                      #取得数据集每行的最后一个标识if currentLabel not in labelCounts.keys():    #字典中不存在则创建labelCounts[currentLabel]=0               #初始化新键值对     labelCounts[currentLabel]+=1                  #标识值出现的次数  shannonEnt=0.0                                    #初始化香农熵为0.0for key in labelCounts:                           #遍历字典取得每个键出现的次数 prob=float(labelCounts[key])/numEntries       #prob为选择该分类的概率，即键值对的值除以总量shannonEnt-=prob*log(prob,2)                  #log(x,a):a为底数，x为真数return shannonEnt                                 #返回香农熵，即所有类别所有可能只包含的信息的信息期望值#简单标识分类
def createDataSet():dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,0,'no']]labels=['no surfacing','flippers']return dataSet,labelsdef splitDataSet(dataSet,axis,value):                 #参数意义：待划分的数据集、划分数据集的特征、需要返回的特征的值retDataSet=[]                                     #创建新的list对象for featVec in dataSet:                           #遍历数据集的每一行if featVec[axis]==value:                      #判断数据集中取得的特征是否与需要的特征的值相等reducedFeatVec=featVec[:axis]             #如果相等则与下面一行剔除掉axis特征值的数据reducedFeatVec.extend(featVec[axis+1:])   retDataSet.append(reducedFeatVec)         #将得到的符合要求的一行放在retDataSet（列表）中return retDataSet                                 #返回所有符合要求的值的列表
'''
#extend和append的区别：extend是将两个列表合并，比如:list3=list1.extend(list2),list3元素个数为两个列表之和；而list3=list1.append(list2)是将list2作为整体添加到list1后面,list3中有len(list1)+1个元素
'''#递归构建决策树
#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):numFeatures=len(dataSet[0])-1                     #数据集第一行长度减一，获得所有特征值的数量，最后一个值是标签值（类别标签）baseEntropy=calcShannonEnt(dataSet)               #得到该数据集香农熵bestInfoGain=0.0;bestFeature=-1                   #一行中要写好多独立语句就得用号分隔,这里给for i in range(numFeatures):featList=[example[i] for example in dataSet]  #列表推导（列表解析），将数据集的每一行遍历完以后取每个元素的第i个值构成featList列表uniqueVals=set(featList)                      #创建一个集合，其中的元素是独一无二的（提取了所出现的特征值类型）newEntropy=0.0                                #初始化新的香农熵for value in uniqueVals:                      #对每一个特征值类型进行遍历提取subDataSet=splitDataSet(dataSet,i,value)  #整个数据集中剔掉特征值value以后得到的新数据集prob=len(subDataSet)/float(len(dataSet))  #计算每种特征值的香农熵，其中len(subDataSet)是符合要求的列表长度（即元素个数）newEntropy+=prob*calcShannonEnt(subDataSet)infoGain=baseEntropy-newEntropy               #计算了旧香农熵与新香农熵的差值，信息增益是熵的减少或者数据无序度的减少if(infoGain>bestInfoGain):                    #挑选最大差值为信息增益最多的指标，差值越大证明对影响越大，越重要（这里其实也可以计算比值得到结果）bestInfoGain=infoGainbestFeature=ireturn bestFeature                                #返回最好特征划分的索引值#对数据集中的类标签出现的频率做统计并返回频率最高的项
def majorityCnt(classList):classCount={}for vote in classList:if vote not in classCount.key():classCount[vote]=0classCount[vote]+=1sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)#operator.itemgetter(1)是获得字典每个键的值，即类标签值出现的次数return sortedClassCount[0][0]#创建树的函数代码
def createTree(dataSet,labels):                       #参数的意义：数据集和标签类表，标签列表包含了数据集中所有特征的标签classList=[example[-1] for example in dataSet]    #提取数据集的所有类标签if classList.count(classList[0])==len(classList):             #.count(sub,start,end)：检查从start开始到end有多少个sub元素return classList[0]                                       #类别完全相同则停止继续划分if len(dataSet[0])==1:                                        #如果dataSet中所有的特征值全用完了，则返回出现次数最多的类别return majorityCnt(classList)bestFeat=chooseBestFeatureToSplit(dataSet)        #最好特征值的索引值bestFeatLabel=labels[bestFeat]                    #得到最好特征值myTree={bestFeatLabel:{}}                         #创建字典用于存储树的所有信息，对绘制树图形非常重要del(labels[bestFeat])                             #删除标签列表的一个元素（这里是删除最好的特征）featValues=[example[bestFeat] for example in dataSet]#得到最好特征所在列的所有值uniqueVals=set(featValues)                        #得到所有出现过的特征类型for value in uniqueVals:subLabels=labels[:]                           #把去除最好特征的列表赋值给subLabelsmyTree[bestFeatLabel][value]=createTree(splitDataSet\(dataSet,bestFeat,value),subLabels)return myTree                                     #myTree是一个嵌套字典
'''
思路描述：
先提取所有类标签
边界：第一个if:所有的类标签都相同，分类结束，返回标签名称第二个if:所有的特征值都被遍历完
选择最好的特征下标
根据下标在类标签列表中找到对应的特征
创建用于存储树的字典（同时给出根节点）
删除类标签中对应的最好的特征
得到数据集中所有样本最好特征的值
得到该最好特征出现的所有值（作为继续分类的依据）
遍历出现的所有值：类标签列表刷新（被剔除了最好特征）以最好特征为结点分裂出uniqueVals个分支每个分支继续创建字典 
以上程序返回的myTree:{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}'''#使用决策树的分类函数
def classify(inputTree,featLabels,testVec):    #testVec中对应值的顺序和featLabels中的相同firstStr=list(inputTree.keys())[0]         #获得根节点secondDict=inputTree[firstStr]             #获得字典的值featIndex=featLabels.index(firstStr)       #获取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 classLabel         #返回标签值#使用pickle模块存储决策树
def storeTree(inputTree,filename):import picklefw=open(filename,'wb')pickle.dump(inputTree,fw)fw.close()def grabTree(filename):import picklefr=open(filename,'rb')return pickle.load(fr)