机器学习 python实例完成―决策树

# -*- coding: cp936 -*- from numpy import * import operator from math import log import operator 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 def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} # a dictionary for feature for featVec in dataSet: currentLabel = featVec[⑴] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: #print(key) #print(labelCounts[key]) prob = float(labelCounts[key])/numEntries #print(prob) shannonEnt -= prob * log(prob,2) return shannonEnt #依照给定的特点划分数据集 #根据axis等于value的特点将数据提出 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 #选取特点，划分数据集，计算得出最好的划分数据集的特点 def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 #剩下的是特点的个数 baseEntropy = calcShannonEnt(dataSet)#计算数据集的熵，放到baseEntropy中 bestInfoGain = 0.0;bestFeature = ⑴ #初始化熵增益 for i in range(numFeatures): featList = [example[i] for example in dataSet] #featList存储对应特点所有可能得取值 uniqueVals = set(featList) newEntropy = 0.0 for value in uniqueVals:#下面是计算每种划分方式的信息熵,特点i个，每一个特点value个值 subDataSet = splitDataSet(dataSet, i ,value) prob = len(subDataSet)/float(len(dataSet)) #特点样本在总样本中的权重 newEntropy = prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy #计算i个特点的信息熵 #print(i) #print(infoGain) if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature #如上面是决策树所有的功能模块 #得到原始数据集以后基于最好的属性值进行划分，每次划分以后传递到树分支的下1个节点 #递归结束的条件是程序遍历完成所有的数据集属性，或是每个分支下的所有实例都具有相同的分类 #如果所有实例具有相同的分类，则得到1个叶子节点或终止快 #如果所有属性都已被处理，但是类标签仍然不是肯定的，那末采取多数投票的方式 #返回出现次数最多的分类名称 def majorityCnt(classList): classCount = {} for vote in classList: if vote not in classCount.keys():classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] #创建决策树 def createTree(dataSet,labels): classList = [example[⑴] for example in dataSet]#将最后1行的数据放到classList中，所有的种别的值 if classList.count(classList[0]) == len(classList): #种别完全相同不需要再划分 return classList[0] if len(dataSet[0]) == 1:#这里为何是1呢？就是说特点数为1的时候 return majorityCnt(classList)#就返回这个特点就好了，由于就这1个特点 bestFeat = chooseBestFeatureToSplit(dataSet) print('the bestFeatue in creating is :') print(bestFeat) bestFeatLabel = labels[bestFeat]#运行结果'no surfacing' myTree = {bestFeatLabel:{}}#嵌套字典,目前value是1个空字典 del(labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet]#第0个特点对应的取值 uniqueVals = set(featValues) for value in uniqueVals: #根据当前特点值的取值进行下1级的划分 subLabels = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels) return myTree #对上面简单的数据进行小测试 def testTree1(): myDat,labels=createDataSet() val = calcShannonEnt(myDat) print 'The classify accuracy is: %.2f%%' % val retDataSet1 = splitDataSet(myDat,0,1) print (myDat) print(retDataSet1) retDataSet0 = splitDataSet(myDat,0,0) print (myDat) print(retDataSet0) bestfeature = chooseBestFeatureToSplit(myDat) print('the bestFeatue is :') print(bestfeature) tree = createTree(myDat,labels) print(tree)

>>> import TREE >>> TREE.testTree1() The classify accuracy is: 0.97% [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] [[1, 'yes'], [1, 'yes'], [0, 'no']] [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] [[1, 'no'], [1, 'no']] the bestFeatue is : 0 the bestFeatue in creating is : 0 the bestFeatue in creating is : 0 {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

def classify(inputTree,featLabels,testVec): firstStr = inputTree.keys()[0] secondDict = inputTree[firstStr] featIndex = featLabels.index(firstStr) key = testVec[featIndex] valueOfFeat = secondDict[key] if isinstance(valueOfFeat, dict): classLabel = classify(valueOfFeat, featLabels, testVec) else: classLabel = valueOfFeat return classLabel def storeTree(inputTree,filename): import pickle fw = open(filename,'w') pickle.dump(inputTree,fw) fw.close() def grabTree(filename): import pickle fr = open(filename) return pickle.load(fr)