一天，小迪与小西想养一只宠物。
小西：小迪小迪，好想养一只宠物呀，但是不知道养那种宠物比较合适。
小迪：好呀，养只宠物会给我们的生活带来很多乐趣呢。不过养什么宠物可要考虑好，这可不能马虎。我们需要考虑一些比较重要的问题。
小西：我也考虑了好多呀，可是还是很难去选择。我想养可爱的小兔兔，可是兔兔吃得很挑剔，又想养狗狗，可是狗狗每天都需要遛它，怕自己没有时间呀。
小迪：其实我们可以绘制一个决策树，决策树是机器学习中做判断的常用模型。原理也非常简单。
小西：决策树是什么，怎么能帮助我们作出决策呢？
小迪：别着急，听我，慢慢道来~
一、概述决策树（Decision Tree）是有监督学习中的一种算法，并且是一种基本的分类与回归的方法。也就是说，决策树有两种：分类树和回归树。这里我们主要讨论分类树。
决策树算法的本质就是树形结构，只需要有一些设计好的问题，就可以对资料进行分类了。在这里，我们需要了解三个概念：
我们可以把决策树看作是一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：
由决策树的根节点到叶节点的每一条路径构建一条规则
路径上中间节点的特征对应着规则的条件，也叶节点的类标签对应着规则的结论
决策树的路径或者其对应的if-then规则集合有一个重要的性质：互斥并且完备。也就是说，每一个例项都被 有且仅有一条路径或者规则所覆盖。这里的覆盖是指例项的特征与路径上的特征一致，或例项满足规则的条件。
二、决策树的构建准备工作 使用决策树做分类的每一个步骤都很重要，首先要收集足够多的资料，如果资料收集不到位，将会导致没有足够的特征去构建错误率低的决策树。资料特征充足，但是不知道用哪些特征好，也会导致最终无法构建出分类效果好的决策树。
决策树构建过程可以概括为3个步骤：特征选择、决策树的生成和决策树的剪枝。
1.特征选择 特征选择就是决定用哪个特征来划分特征空间，其目的在于选取对训练资料具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称这个特征是没有分类能力的，经验上扔掉这些特征对决策树学习的精度影响不会很大。
那如何来选择最优的特征来划分呢？一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度（purity）越来越高。
下面三个图表示的是纯度越来越低的过程，最后一个表示的是三幅图中纯度最低的状态。
在实际使用中，我们衡量的常常是不纯度。度量不纯度的指标有很多种，比如：熵、增益率、基尼值数。
这里我们使用的是熵，也叫作夏农熵，这个名字来源于信息论之父 克劳德·夏农。
1.1 夏农熵及计算函式熵定义为资讯的期望值。在信息论与概率统计中，熵是表示随机变数不确定性的度量。
夏农熵的python程式码如下：
""" 函式功能：计算夏农熵 引数说明： dataSet：原始资料集 返回： ent:夏农熵的值 """ def calEnt(dataSet): n = dataSet.shape[0] #资料集总行数 iset = dataSet.iloc[:,-1].value_counts #标签的所有类别 p = iset/n #每一类标签所占比 ent = (-p*np.log2(p)).sum #计算资讯熵 return ent
我们以海洋生物资料为例，构建资料集，并计算其夏农熵
表1 海洋生物资料
#建立资料集 import numpy as np import pandas as pd def createDataSet: row_data = {\'no surfacing\':[1,1,1,0,0], \'flippers\':[1,1,0,1,1], \'fish\':[\'yes\',\'yes\',\'no\',\'no\',\'no\']} dataSet = pd.DataFrame(row_data) return dataSet dataSet = createDataSet dataSet calEnt(dataSet)
熵越高，资讯的不纯度就越高。也就是混合的资料就越多。
1.2 资讯增益 资讯增益（Information Gain）的计算公式其实就是父节点的资讯熵与其下所有子节点总资讯熵之差。但这里要注意的是，此时计算子节点的总资讯熵不能简单求和，而要求在求和汇总之前进行修正。
a=(3/5)*(-(2/3)*np.log2(2/3)-(1/3)*np.log2(1/3)) calEnt(dataSet)-a
用同样的方法，把第1列的资讯增益也算出来，结果为0.17
2. 资料集最佳切分函式 划分资料集的最大准则是选择最大资讯增益，也就是资讯下降最快的方向。
""" 函式功能：根据资讯增益选择出最佳资料集切分的列 引数说明： dataSet：原始资料集 返回： axis:资料集最佳切分列的索引 """ #选择最优的列进行切分 def bestSplit(dataSet): baseEnt = calEnt(dataSet) #计算原始熵 bestGain = 0 #初始化资讯增益 axis = -1 #初始化最佳切分列，标签列 for i in range(dataSet.shape[1]-1): #对特征的每一列进行循环 levels= dataSet.iloc[:,i].value_counts.index #提取出当前列的所有取值 ents = 0 #初始化子节点的资讯熵 for j in levels: #对当前列的每一个取值进行循环 childSet = dataSet[dataSet.iloc[:,i]==j] #某一个子节点的dataframe ent = calEnt(childSet) #计算某一个子节点的资讯熵 ents += (childSet.shape[0]/dataSet.shape[0])*ent #计算当前列的资讯熵 #print(f\'第{i}列的资讯熵为{ents}\') infoGain = baseEnt-ents #计算当前列的资讯增益 #print(f\'第{i}列的资讯增益为{infoGain}\') if (infoGain > bestGain): bestGain = infoGain #选择最大资讯增益 axis = i #最大资讯增益所在列的索引 return axis
通过上面手动计算，可以得出：
第0列的资讯增益为0.42，第1列的资讯增益为0.17，0.42>0.17，所以应该选择第0列进行切分资料集。
接下来，我们来验证我们构造的资料集最佳切分函式返回的结果与手动计算的结果是否一致。
bestSplit(dataSet) #返回的结果为0，即选择第0列来切分资料集
3. 按照给定列切分资料集通过最佳切分函式返回最佳切分列的索引，可以根据这个索引，构建一个按照给定列切分资料集的函式
""" 函式功能：按照给定的列划分资料集 引数说明： dataSet：原始资料集 axis：指定的列索引 value：指定的属性值 返回： redataSet：按照指定列索引和属性值切分后的资料集 """ def mySplit(dataSet,axis,value): col = dataSet.columns[axis] redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1) return redataSet
验证函式，以axis=0，value=1为例
mySplit(dataSet,0,1)
三、递回构建决策树 目前我们已经学习了从资料集构造决策树算法所需要的子功能模组，其工作原理如下：得到原始资料集，然后基于最好的属性值划分资料集，由于特征值可能多于两个，因此可能存在大于两个分支的资料集划分。第一次划分之后，资料集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分资料。因此我们可以采用递回的原则处理资料集。
决策树生成算法递回地产生决策树，直到不能继续下去未为止。这样产生的树往往对训练资料的分类很准确，但对未知的测试资料的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练资料的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化，也就是常说的剪枝处理。剪枝处理的具体讲解我会放在回归树里面。
1. ID3算法构建决策树的算法有很多，比如ID3、C4.5和CART，这里我们选择ID3算法。
ID3算法的核心是在决策树各个节点上对应资讯增益准则选择特征，递回地构建决策树。具体方法是：从根节点开始，对节点计算所有可能的特征的资讯增益，选择资讯增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递回地呼叫以上方法，构建决策树；直到所有特征的资讯增益均很小或没有特征可以选择为止。最后得到一个决策树。
递回结束的条件是：程式遍历完所有的特征列，或者每个分支下的所有例项都具有相同的分类。如果所有例项具有相同分类，则得到一个叶节点。任何到达叶节点的资料必然属于叶节点的分类，即叶节点里面必须是标签。
2. 编写程式码构建决策树""" 函式功能：基于最大资讯增益切分资料集，递回构建决策树 引数说明： dataSet：原始资料集（最后一列是标签） 返回： myTree：字典形式的树 """ def createTree(dataSet): featlist = list(dataSet.columns) #提取出资料集所有的列 classlist = dataSet.iloc[:,-1].value_counts #获取最后一列类标签 #判断最多标签数目是否等于资料集行数，或者资料集是否只有一列 if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1: return classlist.index[0] #如果是，返回类标签 axis = bestSplit(dataSet) #确定出当前最佳切分列的索引 bestfeat = featlist[axis] #获取该索引对应的特征 myTree = {bestfeat:{}} #采用字典巢状的方式储存树资讯 del featlist[axis] #删除当前特征 valuelist = set(dataSet.iloc[:,axis]) #提取最佳切分列所有属性值 for value in valuelist: #对每一个属性值递回建树 myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value)) return myTree
检视函式执行结果
myTree = createTree(dataSet) myTree
四、决策树的储存 构造决策树是很耗时的任务，即使处理很小的资料集，也要花费几秒的时间，如果资料集很大，将会耗费很多计算时间。因此为了节省时间，建好树之后立马将其储存，后续使用直接呼叫即可。
这里使用的是numpy里面的save函式，它可以直接把字典形式的资料储存为.npy档案，呼叫的时候直接使用load函式即可。
#树的储存 np.save(\'myTree.npy\',myTree) #树的读取 read_myTree = np.load(\'myTree.npy\').item read_myTree
五、使用决策树执行分类""" 函式功能：对一个测试例项进行分类 引数说明： inputTree：已经生成的决策树 labels：储存选择的最优特征标签 testVec：测试资料列表，顺序对应原资料集 返回： classLabel：分类结果 """ def classify(inputTree,labels, testVec): firstStr = next(iter(inputTree)) #获取决策树第一个节点 secondDict = inputTree[firstStr] #下一个字典 featIndex = labels.index(firstStr) #第一个节点所在列的索引 for key in secondDict.keys: if testVec[featIndex] == key: if type(secondDict[key]) == dict : classLabel = classify(secondDict[key], labels, testVec) else: classLabel = secondDict[key] return classLabel """ 函式功能：对测试集进行预测，并返回预测后的结果 引数说明： train：训练集 test：测试集 返回： test：预测好分类的测试集 """ def acc_classify(train,test): inputTree = createTree(train) #根据测试集生成一棵树 labels = list(train.columns) #资料集所有的列名称 result = for i in range(test.shape[0]): #对测试集中每一条资料进行循环 testVec = test.iloc[i,:-1] #测试集中的一个例项 classLabel = classify(inputTree,labels,testVec) #预测该例项的分类 result.append(classLabel) #将分类结果追加到result列表中 test[\'predict\']=result #将预测结果追加到测试集最后一列 acc = (test.iloc[:,-1]==test.iloc[:,-2]).mean #计算准确率 print(f\'模型预测准确率为{acc}\') return test
测试函式
train = dataSet test = dataSet.iloc[:3,:] acc_classify(train,test)
使用SKlearn中graphviz包实现决策树的绘制
#汇入相应的包 from sklearn import tree from sklearn.tree import DecisionTreeClassifier import graphviz #特征 Xtrain = dataSet.iloc[:,:-1] #标签 Ytrain = dataSet.iloc[:,-1] labels = Ytrain.unique.tolist Ytrain = Ytrain.apply(lambda x: labels.index(x)) #将本文转换为数字 #绘制树模型 clf = DecisionTreeClassifier clf = clf.fit(Xtrain, Ytrain) tree.export_graphviz(clf) dot_data = tree.export_graphviz(clf, out_file=None) graphviz.Source(dot_data) #给图形增加标签和颜色 dot_data = tree.export_graphviz(clf, out_file=None, feature_names=[\'no surfacing\', \'flippers\'], class_names=[\'fish\', \'not fish\'], filled=True, rounded=True, special_characters=True) graphviz.Source(dot_data) #利用render方法生成图形 graph = graphviz.Source(dot_data) graph.render("fish")
这样最终的树模型就画出来啦。
