决策树介绍

1.介绍

决策树算法是一种监督学习算法，英文是Decision tree。决策树思想类似于if-else这样的逻辑判断，这其中的if表示的是条件，if之后的then就是一种选择或决策。程序设计中的条件分支结构就是if-then结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法。

• 决策树是一种树形结构
• 树中每个内部节点表示一个特征上的判断，
• 每个分支代表一个判断结果的输出
• 最后每个叶节点代表一种分类结果
• 是非参数学习算法
• 可以解决分类（多分类）问题
• 可以解决回归问题：落在叶子节点的数据的平均值作为回归的结果

决策树API：

• from sklearn.tree import DecisionTreeClassifier
• from sklearn.tree import plot_tree

构建决策树的三个步骤

• 特征选择：选取有较强分类能力的特征
  问题: 如何判断特征的重要性？

  • 1. 信息增益(ID3)
  • 2. 信息增益率(C4.5)
  • 3. 基尼指数(CART分类树）
  • 4. 平方损失(CART回归树）

• 决策树生成：典型的算法有ID3和C4.5，它们生成决策树过程相似，ID3是采用信息增益作为特征选择度量，而C4.5采用信息增益比率 ， CART决策树则使用基尼指数

• 决策树剪枝：剪枝原因是决策树生成算法生成的树对训练数据的预测很准确，但是对于未知数据分类很差，这就产生了过拟合的现象。

决策树的优缺点

• 优点：可读性好，具有描述性，有助于人工分析；效率高，决策树只需要一次性构建反复使用，每一次预测的最大计算次数不超过决策树的深度
• 缺点：容易过拟合；不稳定，当数据发生微小变化时，模型差别可能会很大

通过sklearn实现决策树分类并进一步认识决策树

基于鸢尾花数据绘制图像

import numpy as np
import matplotlib.pyplot as pltfrom sklearn import datasetsiris = datasets.load_iris()
X = iris.data[:,2:]
y = iris.target
# 画出数据分布的散点图
plt.scatter(X[y==0,0],X[y==0,1])
plt.scatter(X[y==1,0],X[y==1,1])
plt.scatter(X[y==2,0],X[y==2,1])plt.show()

训练决策树模型

from sklearn.tree import DecisionTreeClassifiertree = DecisionTreeClassifier(max_depth=2,criterion="entropy")
tree.fit(X,y)

依据模型绘制决策树的决策边界

#找到模型的决策边界，并绘制图像
def plot_decision_boundary(model,axis):x0,x1 = np.meshgrid(np.linspace(axis[0],axis[1],int((axis[1]-axis[0])*100)).reshape(-1,1),np.linspace(axis[2],axis[3],int((axis[3]-axis[2])*100)).reshape(-1,1))X_new = np.c_[x0.ravel(),x1.ravel()]y_predict = model.predict(X_new)zz = y_predict.reshape(x0.shape)from matplotlib.colors import ListedColormapcustom_map = ListedColormap(["#EF9A9A","#FFF59D","#90CAF9"])plt.contourf(x0,x1,zz,linewidth=5,cmap=custom_map)plot_decision_boundary(tree,axis=[0.5,7.5,0,3])
plt.scatter(X[y==0,0],X[y==0,1])
plt.scatter(X[y==1,0],X[y==1,1])
plt.scatter(X[y==2,0],X[y==2,1])
plt.show()

树模型可视化

from sklearn.tree import plot_tree
import matplotlib.pyplot as pltplot_tree(tree,filled=True)
plt.show()

从上面的可视化图形中看出

• X[1] <=0.8 作为第一次分割的依据，满足条件的所有样本均为统一类别
• X[1]>0.8的，依据 X[1]<=0.75 为划分依据
• 由于设置了树的最大深度为2，第二层的两个叶子节点没有完全区分开，绿色的里面有5个应该是紫色的类型，紫色的里面有1个绿色类型的

2. ID3 决策树

ID3 树是基于信息增益构建的决策树，采用划分后样本集的不确定性作为衡量划分样本子集的好坏程度，用信息增益度量不确定性----信息增益越大，不确定性越小

1. 信息熵

• 定义----熵在信息论中代表随机变量不确定度的度量。

  • 熵越大，该变量包含的信息量就大，数据的不确定性度越高
  • 熵越小，数据的不确定性越低

• 公式
  $$H=-\sum _{i=1}^k{p}_i\log (p_i)$$

例子1：假如有三个类别，分别占比为：{1/3,1/3,1/3}，信息熵计算结果为：

$H=-\frac{1}{3}\log (\frac{1}{3})-\frac{1}{3}\log (\frac{1}{3})-\frac{1}{3}\log (\frac{1}{3})=1.0986$

例子2：假如有三个类别，分别占比为：{1/10,2/10,7/10}，信息熵计算结果为：

$H=-\frac{1}{10}\log (\frac{1}{10})-\frac{2}{10}\log (\frac{2}{10})-\frac{7}{10}\log (\frac{7}{10})=0.8018$

熵越大，表示整个系统不确定性越大，越随机，反之确定性越强。

• 公式的转换 ------ 当数据类别只有两类的情况下，公式可以做如下转换
  $$\begin{array}{rl}H& =-\sum _{i=1}^k{p}_i\log (p_i)\\ H& =-x\log (x)-(1-x)\log (1-x)\end{array}\text{\hspace{1em}(1)(2)}$$

• 代码角度理解信息熵的概念

import numpy as np
import matplotlib.pyplot as pltdef entropy(p):return -p*np.log(p)-(1-p)*np.log(1-p)x = np.linspace(0.01,0.99,200)
plt.plot(x,entropy(x))
plt.show()

观察上图可以得出，当我们的系统每一个类别是等概率的时候，系统的信息熵最高，当系统偏向于某一列，相当于系统有了一定程度的确定性，直到系统整体百分之百的都到某一类中，此时信息熵就达到了最低值，即为0。上述结论也可以拓展到多类别的情况。

2. 信息增益

定义：

特征$A$对训练数据集D的信息增益$g(D,A)$，定义为集合$D$的经验熵$H(D)$与特征A给定条件下D的经验熵$H(D|A)$之差。即

$$g(D,A)=H(D)-H(D|A)$$

根据信息增益选择特征方法是：

• 对训练数据集D，计算其每个特征的信息增益，
• 比较信息增益的大小，并选择信息增益最大的特征进行划分。表示由于特征$A$而使得对数据D的分类不确定性减少的程度。

算法：

设训练数据集为D，$\mid D\mid$表示其样本个数。
设有$K$个类$C_k$，$k=1,2,\cdots ,K$，$\mid C_k\mid$为属于类$C_k$的样本个数，$\sum _{k=1}^K=\mid D\mid$。
设特征A有$n$个不同取值 { a 1 , a 2 , ⋯   , a n } \{a_1, a_2, \cdots,a_n\} {a1​,a2​,⋯,a