日常生活中我们往往根据事物的一些特征对他们进行分类，比如饭菜的外观好不好看，咸度合不合适……那决策树也是这个原理，它会根据事物的每一个属性进行一次测试，然后分类，最后在叶子节点上就是最终分出的类。
决策树原理
类似于上面的图，决策树就是将事物的每一种属性都拿来进行一次测试分类。决策树的分类过程
- 读取数据集
- 计算数据集的信息熵
- 遍历所有属性，选择信息熵最小的属性作为最好的分类特征
- 根据上一步的属性对数据集进行分类，并且除去已经作为分类特征的属性
- 递归，直到分类结束
其中很重要的就是信息熵的概念 香农在信息论中提出熵可以作为判断数据携带信息量的大小，并且还给了熵的计算公式。最基本的是信息的定义，如果事务在多分类中，符号xix_ixi的信息为$$l(x_i)=-log_2p(x_i)$$$p(x_i)$是选择该分类的概率
熵就是所有的信息总和Entropy(S)=−∑i=1cpilog2piEntropy(S)=-\sum_{i=1}^cp_ilog_2p_iEntropy(S)=−∑i=1cpilog2pi
信息增益的定义是数据划分前后熵的变化Gain(S,A)=Entropy(S)−∑v∈Values(A)∣Sv∣SEntropy(Sv)Gain(S,A)=Entropy(S)-\sum_{v\in{Values(A)}}\frac{|S_v|}{S}Entropy(S_v)Gain(S,A)=Entropy(S)−∑v∈Values(A)S∣Sv∣Entropy(Sv)有了这些我们就可以计算信息增益从而得到最好的分类特征
知道了上面这些，我们就可以写个简单的函数来计算一下熵值
from math import log def calcshan(dataset): length=len(dataset) p={} H=0.0 for data in dataset: currentlabel=data[-1] if currentlabel not in p.keys(): p[currentlabel]=0 p[currentlabel]+=1 for key in p: px=float(p[key])/float(length) H-=px*log(px,2) return H data=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']] shannon=calcshan(data) shannon 复制代码
当然我们也还有利用基尼系数来代替信息增益作为最佳分类判断条件的算法，以及一些防止过拟合的预剪枝方法，在这里就不过多介绍了，等以后我碰到了类似的例子我再来补充。
利用sklearn的决策树写几个例子
使用决策树对iris数据集分类
from sklearn.datasets import load_iris from sklearn import tree import matplotlib.pyplot as plt import pydotplus import numpy as np from IPython.display import Image import os os.environ["PATH"] += os.pathsep + 'F:/graphviz-2.38/bin' iris=load_iris() X = iris.data[:, [0, 2]] y = iris.target clf=tree.DecisionTreeClassifier() clf=clf.fit(X,y) #分类结果及概率 result=clf.predict(iris.data[:1,[0,2]]) result_prob=clf.predict_proba(iris.data[:1,[0,2]]) print("分类结果:",result,"对应的概率:",result_prob)
#画出决策树 dot_data = tree.export_graphviz(clf, out_file=None) graph = pydotplus.graph_from_dot_data(dot_data) graph.write_png('iris.png') #保存图像 Image(graph.create_png()) 复制代码
这里补充一下：如果想绘制出决策树的图可以下载安装graphviz，导入环境变量，并且pip graphviz和pydotplus,这样就可以保存显示决策树的图片啦（当然也可以自己写决策树利用pyplot绘制，在下面我会给出例子的）
#分类结果 x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1 y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1 xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1), np.arange(y_min, y_max, 0.1)) Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])#np.c_按行连接矩阵,注意一维向量默认是列向量 Z = Z.reshape(xx.shape) plt.contourf(xx, yy, Z, alpha=0.4) plt.scatter(X[:, 0], X[:, 1], c=y, alpha=0.8) plt.show()
还有个类似的简单例子，我就直接贴图了
对西瓜书上的西瓜数据集利用决策树进行分类
import numpy as np import pandas as pd import math import copy import matplotlib.pyplot as plt import matplotlib as mpl #解决中文乱码问题 mpl.rcParams[u'font.sans-serif'] = ['simhei'] mpl.rcParams['axes.unicode_minus'] = False #输入数据 dataset = pd.read_excel('D:/python/WaterMelon_3.0.xlsx',encoding = 'gbk') # 读取数据 Attributes = dataset.columns #所有属性的名称 print("所有属性名称为:") print(Attributes,"\n") m,n = np.shape(dataset) # 得到数据集大小 dataset = np.matrix(dataset) attributeList = [] # 属性列表，每一个属性的取值，列表中元素是集合 for i in range(n): curSet = set() # 使用集合是利用了集合里面元素不可重复的特性，从而提取出了每个属性的取值 for j in range(m): curSet.add(dataset[j,i]) attributeList.append(curSet) print("每一项属性的值为:") print(attributeList,"\n") D = np.arange(0,m,1) # 表示每一个样本编号 A = list(np.ones(n)) # 表示每一个属性是否被使用，使用过了标为 -1 A[-1] = -1 # 将数据里面的标签和编号列标记为 -1 A[0] = -1 EPS = 0.00000001 #规定差异值，小于这个值则可说明属于同一类 class Node(object): # 创建一个类，用来表示节点的信息 def __init__(self,title): self.title = title # 上一级指向该节点的线上的标记文字 self.v = 1 # 节点的信息标记 self.children = [] # 节点的孩子列表 self.deep = 0 # 节点深度 self.ID = -1 # 节点编号 def isSameY(D): # 判断所有样本是否属于同一类 curY = dataset[D[0],n-1] for i in range(1,len(D)): if dataset[D[i],n-1] != curY: return False return True def isBlankA(A): # 判断 A 是否是空，是空则返回true for i in range(n): if A[i]>0: return False return True def isSameAinD(D,A): # 判断在D中，是否所有的未使用过的样本属性均相同 for i in range(n): if A[i]>0: for j in range(1,len(D)): if not isSameValue(dataset[D[0],i],dataset[D[j],i],EPS): return False return True def isSameValue(v1,v2,EPS): # 判断v1、v2 是否相等 if type(v1)==type(dataset[0,8]): return abs(v1-v2)<EPS else: return v1==v2 def mostCommonY(D): # 寻找D中样本数最多的类别 res = dataset[D[0],n-1] # D中第一个样本标签 maxC = 1 count = {} count[res] = 1 # 该标签数量记为1 for i in range(1,len(D)): curV = dataset[D[i],n-1] # 得到D中第i+1个样本的标签 if curV not in count: # 若之前不存在这个标签 count[curV] = 1 # 则该标签数量记为1 else:count[curV] += 1 # 否则 ，该标签对应的数量加一 if count[curV]>maxC: # maxC始终存贮最多标签对应的样本数量 maxC = count[curV] # res 存贮当前样本数最多的标签类型 res = curV return res # 返回的是样本数最多的标签的类型 def entropyD(D): # 参数D中所存的样本的交叉熵 types = [] # 存贮类别标签 count = {} # 存贮每个类别对应的样本数量 for i in range(len(D)): # 统计D中存在的每个类型的样本数量 curY = dataset[D[i],n-1] if curY not in count: count[curY] = 1 types.append(curY) else: count[curY] += 1 ans = 0 total = len(D) # D中样本总数量 for i in range(len(types)): # 计算交叉熵 ans -= count[types[i]]/total*math.log2(count[types[i]]/total) return ans #对于离散型属性的信息增益函数 def gain(D,p): # 属性 p 上的信息增益 if type(dataset[0,p])== type(dataset[0,8]): # 判断若是连续属性，则调用另一个函数 res,divideV = gainFloat(D,p) else: types = [] count = {} for i in range(len(D)): # 得到每一个属性取值上的样本编号 a = dataset[D[i],p] if a not in count: count[a] = [D[i]] types.append(a) else: count[a].append(D[i]) res = entropyD(D) # D的交叉熵 total = len(D) for i in range(len(types)): # 计算出每一个属性取值分支上的交叉熵，再计算出信息增益 res -= len(count[types[i]])/total*entropyD(count[types[i]]) divideV = -1000 # 这个只是随便给的一个值，没有实际意义 return res,divideV #对于连续型属性的信息增益函数 def gainFloat(D,p): # 获得在连续属性上的最大信息增益及对应的划分点 a = [] for i in range(len(D)): # 得到在该属性上的所有取值 a.append(dataset[D[i],p]) a.sort() # 排序 T = [] for i in range(len(a)-1): # 计算每一个划分点 T.append((a[i]+a[i+1])/2) res = entropyD(D) # D的交叉熵 ans = 0 divideV = T[0] for i in range(len(T)): # 循环根据每一个分割点进行划分 left = [] right = [] for j in range(len(D)): # 根据特定分割点将样本分成两部分 if (dataset[D[j],p]<=T[i]): left.append(D[j]) else:right.append(D[j]) temp = res-entropyD(left)-entropyD(right) # 计算特定分割点下的信息增益 if temp>ans: divideV = T[i] # 始终存贮产生最大信息增益的分割点 ans = temp # 存贮最大的信息增益 return ans,divideV def treeGenerate(D,A,title): node = Node(title) if isSameY(D): # D中所有样本是否属于同一类 node.v = dataset[D[0],n-1] return node # 是否所有属性全部使用过 或者 D中所有样本的未使用的属性均相同 if isBlankA(A) or isSameAinD(D,A): node.v = mostCommonY(D) # 此时类别标记为样本数最多的类别（暗含可以处理存在异常样本的情况） return node # 否则所有样本的类别应该一致 entropy = 0 floatV = 0 p = 0 for i in range(len(A)): # 循环遍历A,找可以获得最大信息增益的属性 if(A[i]>0): curEntropy,divideV = gain(D,i) if curEntropy > entropy: p = i # 存贮属性编号 entropy = curEntropy floatV = divideV if isSameValue(-1000,floatV,EPS): # 说明是离散属性 node.v = Attributes[p]+"=?" # 节点信息 curSet = attributeList[p] # 该属性的所有取值 for i in curSet: Dv = [] for j in range(len(D)): # 获得该属性取某一个值时对应的样本标号 if dataset[D[j],p]==i: Dv.append(D[j]) # 若该属性取值对应没有符合的样本，则将该分支作为叶子，类别是D中样本数最多的类别 # 其实就是处理在没有对应的样本情况下的问题。那就取最大可能性的一类。 if Dv==[]: nextNode = Node(i) nextNode.v = mostCommonY(D) node.children.append(nextNode) else: # 若存在对应的样本，则递归继续生成该节点下的子树 newA = copy.deepcopy(A) # 注意是深度复制，否则会改变A中的值 newA[p]=-1 node.children.append(treeGenerate(Dv,newA,i)) else: # 若对应的是连续的属性 Dleft = [] Dright = [] node.v = Attributes[p]+"<="+str(floatV)+"?" # 节点信息 for i in range(len(D)): # 根据划分点将样本分成左右两部分 if dataset[D[i],p]<=floatV: Dleft.append(D[i]) else: Dright.append(D[i]) node.children.append(treeGenerate(Dleft,A[:],"是")) # 左边递归生成子树，是 yes 分支 node.children.append(treeGenerate(Dright,A[:],"否")) # 同上。 注意，在此时没有将对应的A中值变成 -1 return node # 因为连续属性可以使用多次进行划分 def countLeaf(root,deep): root.deep = deep res = 0 if root.v=='好瓜' or root.v=='坏瓜': # 说明此时已经是叶子节点了，所以直接返回 res += 1 return res,deep curdeep = deep # 记录当前深度 for i in root.children: # 得到子树中的深度和叶子节点的个数 a,b = countLeaf(i,deep+1) res += a if b>curdeep: curdeep = b return res,curdeep def giveLeafID(root,ID): # 给叶子节点编号 if root.v=='好瓜' or root.v=='坏瓜': root.ID = ID ID += 1 return ID for i in root.children: ID = giveLeafID(i,ID) return ID def plotNode(nodeTxt,centerPt,parentPt,nodeType): # 绘制节点 plt.annotate(nodeTxt,xy = parentPt,xycoords='axes fraction',xytext=centerPt, textcoords='axes fraction',va="center",ha="center",bbox=nodeType, arrowprops=arrow_args) def dfsPlot(root): if root.ID==-1: # 说明根节点不是叶子节点 childrenPx = [] meanPx = 0 for i in root.children: cur = dfsPlot(i) meanPx += cur childrenPx.append(cur) meanPx = meanPx/len(root.children) c = 0 for i in root.children: nodetype = leafNode if i.ID<0: nodetype=decisionNode plotNode(i.v,(childrenPx[c],0.9-i.deep*0.8/deep),(meanPx,0.9-root.deep*0.8/deep),nodetype) plt.text((childrenPx[c]+meanPx)/2,(0.9-i.deep*0.8/deep+0.9-root.deep*0.8/deep)/2,i.title) c += 1 return meanPx else: return 0.1+root.ID*0.8/(cnt-1) myDecisionTreeRoot = treeGenerate(D,A,"root") # 生成决策树 cnt,deep = countLeaf(myDecisionTreeRoot,0) # 得到树的深度和叶子节点的个数 giveLeafID(myDecisionTreeRoot,0) print("决策树根的属性为:",myDecisionTreeRoot.v) # 绘制决策树 decisionNode = dict(boxstyle = "sawtooth",fc = "0.9",color='black') leafNode = dict(boxstyle = "round4",fc="0.9",color='red') arrow_args = dict(arrowstyle = "<-",color='green') fig = plt.figure(1,facecolor='white') rootX = dfsPlot(myDecisionTreeRoot) plotNode(myDecisionTreeRoot.v,(rootX,0.9),(rootX,0.9),decisionNode) plt.show() 复制代码
总结
决策树比较贴近日常生活所以还算是比较好理解的一种分类算法，最重要的就是找到最合适的分类特征。但是决策树也有它的缺点，容易过拟合、容易受数据波动影响、对于一些异或问题无法做出判断、对于决定性因素的偏差……所以还是那句话，对于不同的分类问题先考虑最合适的分类模型，不要盲目使用。BTW，本来之前还有个贝叶斯分类的，但是它的核心就是贝叶斯公式，这个只要理解了公式写起代码来其实并不难，所以我就偷了个懒跳过去啦，嘻嘻嘻。
