1决策树模型
1.1基本概念
决策树类似于我们玩的读心游戏，一个人问问题，另一个人只能回答yes或no。比如：
问：这是个人吗？回答：是
问：是女生吗？回答：不是
问：他戴眼镜吗？回答：是
…
一直猜出回答者的正确答案。如下图所示。
1.2 信息增益与基尼不纯度
在介绍决策树之前我们先来介绍下信息熵，信息熵是约翰·香农根据热力学第二定律，在 1948《通信的数学原理》一书中提出，主要思想是：一个问题不确定性越大，需要获取的信息就越多，信息熵就越大；一个问题不确定性越小，需要获取的信息就越少，信息熵就越小。比如“小张今天会不会在9:00之前到公司”的信息熵就比“小张今天会不会吃早饭”的信息熵要高，因为小张长久以来没有不吃早饭的习惯。
信息熵是这样定义的：假设集合D中第k类样本的比率为pk，(k=1,2,…|y|)
Ent(D)=-
在决策树中有两个概念：信息增益（Information Gain）和基尼不纯度（Gini impurity
）。
信息增益（Information Gain）：划分数据前后数据信息熵的差值。
信息增益纯度越高，纯度提升越大；信息增益纯度越低，纯度提升越小。
信息增益使用的是ID3算法（改进后为C4.5算法）。决策树在选取节点的时候，计算每个特征值划分后的信息增益，选取信息增益最大的节点。
基尼不纯度：反映从集合D中随机取两个样本后，其类别不一致性的概率。
Gini(D)=
基尼不纯度使用的是CART算法。决策树在集合中要选取基尼不纯度最小的那个节点。
1.3 Sklearn中的决策树构建
Sklearn中使用sklearn.tree.DecisionTreeClassifier构建决策树分类；from sklearn.tree import DecisionTreeRegressor构建决策树回归。
import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import ListedColormap from sklearn import tree,datasets from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import train_test_split def base_of_decision_tree(max_depth): wine = datasets.load_wine() # 仅选前两个特征 X = wine.data[:,:2] y = wine.target X_train,X_test,y_train,y_test = train_test_split(X, y) clf = DecisionTreeClassifier(max_depth=max_depth) clf.fit(X_train,y_train) #定义图像中分区的颜色和散点的颜色，允许用户使用十六进制颜色码来定义自己所需的颜色库 cmap_light = ListedColormap(['#FFAAAA','#AAFFAA','#AAAAFF']) cmap_bold = ListedColormap(['#FF0000','#00FF00','#0000FF'] #分别将样本的两个特征值创建图像的横轴和纵轴 x_min,x_max = X_train[:,0].min()-1,X_train[:,0].max()+1 y_min,y_max = X_train[:,1].min()-1,X_train[:,1].max()+1 xx, yy = np.meshgrid(np.arange(x_min, x_max, .02),np.arange(y_min, y_max, .02)) #给每个样本分配不同的颜色， predict：训练后返回预测结果，显示标签值 Z = clf.predict(np.c_[xx.ravel(),yy.ravel()]) Z = Z.reshape(xx.shape) plt.figure() # plt.pcolormesh的作用在于能够直观表现出分类边界 plt.pcolormesh(xx,yy,Z,cmap=cmap_light,shading='auto') #用散点把样本表示出来 plt.scatter(X[:,0],X[:,1],c=y,cmap=cmap_bold,s=20,edgecolors='k') plt.xlim(xx.min(),xx.max()) plt.ylim(yy.min(),yy.max()) plt.title("Classifier:(max_depth="+str(max_depth)+")") print("红酒数据训练集(max_depth="+str(max_depth)+"):{:.2f}".format(clf.score(X_train,y_train))) print("红酒数据测试集(max_depth="+str(max_depth)+"):{:.2f}".format(clf.score(X_test,y_test))) plt.show()
输出
红酒数据训练集(max_depth=1):0.68 红酒数据测试集(max_depth=1):0.69 红酒数据训练集(max_depth=3):0.88 红酒数据测试集(max_depth=3):0.76 红酒数据训练集(max_depth=5):0.90 红酒数据测试集(max_depth=5):0.84
当为max_depth（即树的深度）为1、3、5的时候，划分如下图：
通过图和输出结果，都可以看出，随着max_depth增加，划分越精确（ max_depth=1的时候完全是不正确的）。但是我们会发现所有的数据测试集都低于训练集的值，这就是决策树最致命的一点：容易过拟合。
1.4剪枝
解决过拟合的方法是剪枝，预剪枝（Pre-pruning）和后剪枝（post-pruning）。预剪枝及早停止树的增长；后剪枝先形成树，然后再剪枝。Sklearn仅采用预剪枝的策略，预剪枝可以分以下三种方法中的任意一种来解决。
限制最大深度
限制叶节点数最大数目
规定一个节点数据点的最小数目
我们以Sklearn乳腺癌数据采取限制最大深度来看一下防止过拟合的效果。
from sklearn.datasets import load_breast_cancer from sklearn.tree import DecisionTreeClassifier def decision_tree(): cancer = load_breast_cancer() x_train,x_test,y_train,y_test = train_test_split(cancer.data,cancer.target,stratify=cancer.target,random_state=42) tree = DecisionTreeClassifier(random_state=0) # 构件树，不剪枝 tree.fit(x_train,y_train) print("不剪枝，训练数据集上的精度:{:.3f}".format(tree.score(x_train,y_train))) print("不剪枝，测试数据集上的精度:{:.3f}".format(tree.score(x_test,y_test))) print("不剪枝，树的深度:{}".format(tree.get_depth())) tree = DecisionTreeClassifier(max_depth=4,random_state=0) # 构件树，剪枝 tree.fit(x_train,y_train) print("剪枝，训练数据集上的精度:{:.3f}".format(tree.score(x_train,y_train))) print("剪枝，测试数据集上的精度:{:.3f}".format(tree.score(x_test,y_test))) print("剪枝，树的深度:{}".format(tree.get_depth()))
输出
不剪枝，训练数据集上的精度:1.000 不剪枝，测试数据集上的精度:0.937 不剪枝，树的深度:7 剪枝，训练数据集上的精度:0.988 剪枝，测试数据集上的精度:0.951 剪枝，树的深度:4
可见树的深度为7的时候，测试数据集的得分<训练数据集的得分。但是当树的深度为4的时候，测试数据集的得分几乎等于训练数据集的得分。
1.5 决策树的可视化
为了看到可视化的决策树，首先需要下载并且安装一个软件Graphviz的软件，Graphviz 是一款由AT&T Research和Lucent Bell实验室开源的可视化图形工具。然后打开命令行，输入pip3 install graphviz。接下来运行下面代码。
from sklearn.tree import export_graphviz import graphviz def show_tree(): wine = datasets.load_wine() # 仅选前两个特征 X = wine.data[:,:2] y = wine.target X_train,X_test,y_train,y_test = train_test_split(X, y) clf = DecisionTreeClassifier(max_depth=3)#为了图片不太大选择max_depth=3 clf.fit(X_train,y_train) export_graphviz(clf,out_file="wine.dot",class_names=wine.target_names,feature_names=wine.feature_names[:2],impurity=False,filled=True) #打开dot文件 with open("wine.dot") as f: dot_graph = f.read() graphviz.Source(dot_graph)
在本地目录下生成wine.dot文件，用Graphviz软件打开，得到如图图片。
总结一下，决策树的优点是：容易可视化和无需对数据进行预处理；缺点是即使采取剪枝也会造成过拟合。解决这个问题最有利的方法是采用随机森林模型。
