心得体会：
1决策树是在 香农熵 和 信息增益 的基础上构建的
2筛选决策标签，当筛去该标签时得到香农熵最优结构时，选择该决策标签，不断筛选直到选完所有标签（或余下结果都一样）
3取余下结果中最多的结果作为该叶节点的返回结果
4数据结构是字典树
#3-1构造决策树 #计算香农熵 from math import log 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 for key in labelCounts: prob=float(labelCounts[key]/numEntries)#该种数据的占比 shannonEnt-=prob*log(prob,2)#香农熵公式 return shannonEnt #自定义数据 def createDataSet(): dataSet=[ [1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no'], ] labels=['no surfacing','flippers'] return dataSet,labels # myDat,labels=createDataSet() # print(calcShannonEnt(myDat)) #按照给定特征划分数据集 def splitDataSet(dataSet,axis,value):#选择axis位是value的数据 retDataSet=[] for featVec in dataSet: if featVec[axis]==value:#选择数据集中符合条件的数据 reducedFeatVec=featVec[:axis]#axis之前的数据 reducedFeatVec.extend(featVec[axis+1:])#axis之后的数据 retDataSet.append(reducedFeatVec)#新数据集（已经筛选过axis位） return retDataSet # myDat,labels=createDataSet() # print(myDat) # print(splitDataSet(myDat,0,1)) # print(splitDataSet(myDat,0,0)) # 选择最好的数据集划分方式 def chooseBestFeatureToSplit(dataSet): numFeatures=len(dataSet[0])-1 #最后一个数据是结果 baseEntropy=calcShannonEnt(dataSet) #计算基础香农熵 bestInfoGain=0.0 #信息增益 bestFeature=-1 #初始特征位是-1 for i in range(numFeatures): featList=[example[i] for example in dataSet] # 复制dataset uniqueVals=set(featList) # 数据去重，得到i位置的域 newEntropy=0.0 #i位置的总信息期望 for value in uniqueVals: subDataSet=splitDataSet(dataSet,i,value) #筛选i位置为value的数据 prob=len(subDataSet)/float(len(dataSet)) #这些数据的占比 newEntropy+=prob*calcShannonEnt(subDataSet) #筛选i位置为value的数据 的信息期望 inoGain=baseEntropy-newEntropy #筛选i位置后剩下的信息期望 if(inoGain>bestInfoGain):#选择筛去i后余下香农熵最小的，筛去i数据最整齐 bestInfoGain=inoGain bestFeature=i return bestFeature # myDat,labels=createDataSet() # print(chooseBestFeatureToSplit(myDat)) #递归构建决策树 import operator #返回出现次数最多的分类名称 def majorityCnt(classList): classCount={} for vote in classList: if vote not in classCount.keys(): classCount[vote]=0 classCount[vote]+=1 sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)#按字典（k，v）第一个域v排序 return sortedClassCount[0][0] #返回classList中val最大的key #创建决策树 def createTree(dataSet,labels):#输入数据和位置含义 classList=[example[-1] for example in dataSet] #返回所有结果 if classList.count(classList[0])==len(classList): #如果（第0位数据出现的次数和长度一样）剩下结果都一样 return classList[0] #返回第0位的结果，因为都一样 if len(dataSet[0])==1: #如果数据只剩下最后一位（最后一位是结果 ） return majorityCnt(classList) #返回最多的结果 bestFeat=chooseBestFeatureToSplit(dataSet) #选择最优的位置 bestFeatLabel=labels[bestFeat] #最优位置的结果 myTree={bestFeatLabel:{}} #字典树 bestFeatLabel:{}中bestFeatLabel代表该位置的问题，｛｝表示问题的选择分支 del(labels[bestFeat])#在位置表中删除最优位置 featValues=[example[bestFeat] for example in dataSet] #最优位置可能的选择 uniqueVals=set(featValues) #去重 for value in uniqueVals: subLabels=labels[:] #去掉最优位置后的数据 myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels) #创建该分支下的子树 return myTree # myDat,labels=createDataSet() # mytree=createTree(myDat,labels) # cur=mytree # while True: # if(type(cur)==dict): # label=list(cur.keys())[0] #因为字典树只有一个根节点 # print("%s ?"%label) # key=int(input("input_1/0(yes/no):"))#key要强制转换成int不然默认是string # cur=cur[label][key] #选择分支 # else: # print(cur) # break