决策树通俗详解（附python代码）

from math import log import operator import matplotlib.pyplot as plt import pickle #计算熵：度量数据集的无序程度 def calcShannonEnt(dataSet): #dataSet包括特征和label，最后一列为label numEntries = len(dataSet) labelCounts = {} #统计各标签值的数量 for featVec in dataSet: currentLabel = featVec[–1] #取最后一列：label标签值 if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 #计算熵：-sum(pi*logpi)，每个特征值的熵求和 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key])/numEntries #计算每个特征的概率值 shannonEnt -= prob * log(prob,2) #计算每个特征的熵值 return shannonEnt #划分数据集：将符合要求的元素抽取出来 def splitDataSet(dataSet, axis, value): dataSet：待划分的数据集 axis：选定的特征名称 value：需要返回的特征的值 retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] #chop out axis used for splitting reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet #选择出能划分数据集的最好的特征 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] #提取该特征列所有数据 uniqueVals = set(featList) #set()函数创建一个无序不重复元素集，即特征都包含哪些特征值（比如是否有房这个特征，就包含是和否两个元素） #计算当前特征分类的信息熵 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 #计算信息增益：整体熵-当前特征信息熵 #选择最大的信息增益 if (infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature #返回特征索引值 #计算出现次数最多的类别 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): dataSet：数据集，包括特征和标签 labels：标签列表，算法本身是不需要这个参数的，这里是为了给出数据明确的含义 classList = [example[–1] for example in dataSet] #取最后的标签label列 #停止条件1：类别完全相同则停止划分 if classList.count(classList[0]) == len(classList): return classList[0] #停止条件2：已遍历完所有特征，返回出现次数最多的类别 if len(dataSet[0]) == 1: return majorityCnt(classList) #选择最好的特征 bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel:{}} #将选择出的特征添加进树（myTree包含了代表树结构信息的嵌套字典） labels2 = labels.copy() del(labels2[bestFeat]) #在labels中删除已经选择过的特征 featValues = [example[bestFeat] for example in dataSet] #取出选择特征的所有特征值 uniqueVals = set(featValues) #取出选择特征都包含哪些元素 for value in uniqueVals: subLabels = labels2[:] #复制所有标签，这样树就不会弄乱现有的标签 myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) return myTree #使用决策树进行分类 def classify(inputTree,featLabels,testVec): inputTree：构建好的决策树 featLabels：特征列表 testVec：待分类的测试数据 firstStr = list(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): fw = open(filename,w) pickle.dump(inputTree,fw) fw.close() #读取决策树 def grabTree(filename): fr = open(filename) return pickle.load(fr) ##############下面是绘制树形图的########### #定义文本框和箭头格式 decisionNode = dict(boxstyle=“sawtooth”, fc=“0.8”) leafNode = dict(boxstyle=“round4”, fc=“0.8”) arrow_args = dict(arrowstyle=“<-“) #获取叶节点的数目 def getNumLeafs(myTree): numLeafs = 0 firstStr = list(myTree.keys())[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]).__name__==dict: #测试节点的数据类型是都为字典，如果不是，则为叶节点 numLeafs += getNumLeafs(secondDict[key]) else: numLeafs +=1 return numLeafs #获取树的层数 def getTreeDepth(myTree): maxDepth = 0 firstStr = list(myTree.keys())[0] secondDict = myTree[firstStr] for key in secondDict.keys(): if type(secondDict[key]).__name__==dict: #测试节点的数据类型是都为字典，如果不是，则为叶节点 thisDepth = 1 + getTreeDepth(secondDict[key]) else: thisDepth = 1 if thisDepth > maxDepth: maxDepth = thisDepth return maxDepth #绘制带箭头的注解 def plotNode(nodeTxt, centerPt, parentPt, nodeType): createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords=axes fraction, xytext=centerPt, textcoords=axes fraction, va=“center”, ha=“center”, bbox=nodeType, arrowprops=arrow_args ) #在父子文本间填充文本信息 def plotMidText(cntrPt, parentPt, txtString): xMid = (parentPt[0]–cntrPt[0])/2.0 + cntrPt[0] yMid = (parentPt[1]–cntrPt[1])/2.0 + cntrPt[1] createPlot.ax1.text(xMid, yMid, txtString, va=“center”, ha=“center”, rotation=30) #绘制树 def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on myTree： parentPt： nodeTxt： #计算宽与高 numLeafs = getNumLeafs(myTree) #决定树的宽度 depth = getTreeDepth(myTree) firstStr = list(myTree.keys())[0] #此节点的文本标签 cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff) #标记子节点属性值 plotMidText(cntrPt, parentPt, nodeTxt) plotNode(firstStr, cntrPt, parentPt, decisionNode) secondDict = myTree[firstStr] plotTree.yOff = plotTree.yOff – 1.0/plotTree.totalD for key in secondDict.keys(): if type(secondDict[key]).__name__==dict: #测试节点的数据类型是都为字典，如果不是，则为叶节点 plotTree(secondDict[key],cntrPt,str(key)) #递归 else: #its a leaf node print the leaf node plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode) plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key)) plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD #绘制主函数 def createPlot(inTree): fig = plt.figure(1, facecolor=white) fig.clf() axprops = dict(xticks=[], yticks=[]) createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) #no ticks #createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses plotTree.totalW = float(getNumLeafs(inTree)) plotTree.totalD = float(getTreeDepth(inTree)) plotTree.xOff = –0.5/plotTree.totalW; plotTree.yOff = 1.0; plotTree(inTree, (0.5,1.0), ) plt.show() ############### 测试1 ############### dataSet = [[1, 1, yes], [1, 1, yes], [1, 0, no], [0, 1, no], [0, 1, no]] labels = [no surfacing,flippers] #创建树 myTree = createTree(dataSet,labels) print(“构造的决策树为：”, myTree) #分类测试 test_result1 = classify(myTree, labels, [1,0]) print(“特征[1,0]所属类别为：”, test_result1) test_result2 = classify(myTree, labels, [1,1]) print(“特征[1,1]所属类别为：”, test_result2) #绘制树形图 createPlot(myTree) ############### 测试2 ############### fr = open(lenses.txt) lenses = [inst.strip().split(\t) for inst in fr.readlines()] lensesLabels = [age, precript, astigmatic, tearRate] #创建树 lensesTree = createTree(lenses, lensesLabels) print(“构造的决策树为：”, lensesTree) #分类测试 test_result1 = classify(lensesTree, lensesLabels, [pre, hyper, no, normal]) print(“特征[pre, hyper, no, normal]所属类别为：”, test_result1) test_result2 = classify(lensesTree, lensesLabels, [young, hyper, yes, reduced]) print(“特征[young, hyper, yes, reduced]所属类别为：”, test_result2) #绘制树形图 createPlot(lensesTree)

import pandas as pd import numpy as np import matplotlib.pyplot as plt from sklearn.model_selection import train_test_split from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import cross_val_score from sklearn.metrics import accuracy_score,classification_report, confusion_matrix # from utilities import visualize_classifier from io import StringIO import pydotplus from sklearn.tree import export_graphviz import pylab as pl pd.set_option(precision,4) dataset = pd.read_csv(“dtree_data.csv”, header=None,names=[0,1,2]) print(dataset.head()) print(dataset.tail()) X = dataset.iloc[:, :–1] y = dataset.iloc[:, –1] # 划分训练集、测试集 X_train, X_test, y_train, y_test =train_test_split(X, y, test_size=0.20, random_state=5) # 创建分类器 clf = DecisionTreeClassifier(criterion=gini, random_state=0) # 训练模型 clf.fit(X_train, y_train) # 预测 y_pred = clf.predict(X_test) # 评价模型 accuracy = np.round(accuracy_score(y_test, y_pred),3) print(“Accuracy of the new classifier =”, accuracy) print(confusion_matrix(y_test, y_pred)) print(classification_report(y_test, y_pred)) # decision boundary plt.figure() X=np.array(X_test) y=np.array(y_pred) x_min, x_max = X[:,0].min() – 0.1, X[:,0].max() + 0.1 y_min, y_max = X[:,1].min() – 0.1, X[:,1].max() + 0.1 h = 0.02 # step size in the mesh xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h)) Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]) Z = Z.reshape(xx.shape) pl.set_cmap(pl.cm.Paired) pl.pcolormesh(xx, yy, Z) # Plot the training points for i in range(len(X)): if y[i] == 0: _ = pl.scatter(X[i,0], X[i,1], c=red, marker=o) elif y[i] == 1: _ = pl.scatter(X[i,0], X[i,1], c=blue, marker=x) elif y[i] == 2: _ = pl.scatter(X[i,0], X[i,1], c=green, marker=+) else: _ = pl.scatter(X[i,0], X[i,1], c=magenta, marker=v) pl.xlabel(Petal length) pl.ylabel(Petal width) pl.xlim(x_min,x_max) pl.ylim(y_min, y_max) pl.show()