Python高级--决策树

一、决策树原理

1）我们经常使用决策树处理分类问题

决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

  女儿：多大年纪了？

  母亲：26。

  女儿：长的帅不帅？

  母亲：挺帅的。

  女儿：收入高不？

  母亲：不算很高，中等情况。

  女儿：是公务员不？

  母亲：是，在税务局上班呢。

  女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑:

上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色节点表示判断条件，橙色节点表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。

这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。

2）正式定义决策树

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

可以看到，决策树的决策过程非常直观，容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。

3）决策树与K-近邻值分类比较

之前介绍的K-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。

4）决策树算法分析

决策树算法能够读取数据集合，构建类似于上面的决策树。决策树很多任务都是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，机器学习算法最终将使用这些机器从数据集中创造的规则。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

二、决策树的构造

分类解决离散问题，回归解决连续问题

1）决策树构造

• 决策树：信息论
• 逻辑斯底回归、贝叶斯：概率论

2）奥卡姆剃刀原则

尽量用较少的东西做更多的事

3）分裂属性

构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况：

  1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。

  2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。

  3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。

属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。

4） ID3算法

划分数据集的大原则是：将无序的数据变得更加有序。

我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前使用信息论量化度量信息的内容。

在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

在可以评测哪种数据划分方式是最好的数据划分之前，我们必须学习如何计算信息增益。集合信息的度量方式称为香农熵或者简称为熵，这个名字来源于信息论之父克劳德•香农。

5）entropy熵

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号x的信息定义为：

其中p(x)是选择该分类的概率

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

其中n是分类的数目。

6）决策树中的信息增益

在决策树当中，设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为

其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。

现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：

而信息增益即为两者的差值：

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。

三、信息熵的简单计算

情况说明，但某人爬山爬了一半的时候发生了一下几种情况：

• 1.有0.5的几率想往上爬，有0.5的几率想下山
• 2.一定要爬到山顶
• 3.有0.999的几率想下山，有0.001的几率再向上爬

我们来简单计算一下 这三种情况的信息熵
情况一：

-(0.5*math.log2(0.5)+0.5*math.log2(0.5)) 

1

这样的熵值为1，说明情况最不稳定

情况二：

-(1*math.log2(1))

1

这样的熵值为0，说明情况最稳定的情况
情况三：

-(0.999*math.log2(0.999)+0.001*math.log2(0.001))

0.011407757737461138

这样的熵值，我们基本可以认为登山者是要下山了。

四、信息增益的简单计算

1）基于ID3算法

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

2）检测SNS社区中的僵尸账号

1、计算整个系统中信息的熵

如图我们可以观察得到：
账号真实：y 7个 p1： 7/10
账号虚假：n 3个 p2： 3/10
计算这个系统中的信息熵

inof_D = -((3/10)*math.log2(3/10)+(7/10)*math.log2(7/10))   #当前系统的信息熵

0.8812908992306927

2、求依据日志密度 判断帐号是否真实的信息熵

现在我们假设将训练元组D(帐号是否真实)按属性A(日志密度)进行划分，则A对D划分的期望信息为：

如图我们可以观察得到：
s：3个 p1： 0.3 n y n
m：4个 p2： 0.4 y y n y
l：3个 p2： 0.3 y y y
计算这个系统中的信息熵

info_L_D = -0.3*((2/3*math.log2(2/3))+1/3*math.log2(1/3)) - 0.4*(1/4*math.log2(1/4)+3/4*math.log2(3/4))-0.3*(math.log2(1))

3、日志密度这个特征带来的 信息增益

inof_D-info_L_D

0.2812908992306927

4、求 依据好友密度判断帐号是否真实的 信息熵

s - 4  p=0.4 n n y n
m - 4 p=0.4 y y y y
l - 2   p=0.2 y y

info_F_D = -0.4*((3/4)*math.log2(3/4)+(1/4)*math.log2(1/4))
info_F_D

0.32451124978365314

5、好友密度带来的信息增益

inof_D-info_F_D

0.5567796494470396

可以看出：好友密度带来的信息增益就很大了

6、求 是否适用真实头像判断帐号是否真实的 信息熵

y - 5  p=0.5  y y y y n
n - 5  p=0.5  n y n y y

info_F_D = -0.5*(1/5*math.log2(1/5)+4/5*math.log2(4/5))-0.5*(2/5*math.log2(2/5)+3/5*math.log(3/5))

0.7785973535509508

7、是否适用真实头像带来的信息增益

inof_D-info_F_D 

0.10269354567974187

可以看出：是否适用真实头像带来的信息增益很小

3）创建决策树模型

导入一些列包

import numpy as np
import pandas as pd
from pandas import Series,DataFrame
import matplotlib.pyplot as plt

from sklearn.tree import DecisionTreeClassifier
dtree = DecisionTreeClassifier() 

4）将训练数据数字化供模型训练

训练数据与数字的映射关系：

# 日志密度 s m l  0 1 2
# 好友密度 s m l  0 1 2
# 头像     n y    0 1
# 结果     n y    0 1

X_train = np.array([
    [0,0,0],
    [0,2,1],
    [2,1,1],
    [1,1,1],
    [2,1,1],
    [1,2,0],
    [1,0,0],
    [2,1,0],
    [1,0,0],
    [0,0,1],
])
y_train = np.array([0,1,1,1,1,1,0,1,1,0])

5）将训练数据传入模型训练

dtree.fit(X_train,y_train)

6）用训练好的模型来预测

dtree.predict([
    [0,0,0],    # 日志密度低 好友密度低 头像是假的
    [0,1,0],   # 日志密度低 好友密度中等 头像是假的  好友密度这个条件还可以 其他条件都不好
    [2,0,1]    # 其他条件都很好 就是好友密度不好
])

array([0, 1, 0])

从结果可以看出 优先以信息增益大的条件去决定分类

五、决策树、K-近邻值、逻辑回归比较

1）导入模型

# 导入 数据集 和 模型 knn lgc dtree 
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LogisticRegression  # 虽然名字里有回归 但是是用来分类的
from sklearn.tree import DecisionTreeClassifier

2）获取数据集

from sklearn.datasets import load_iris

iris = load_iris()
#获取前两个特征，画图观察各个模型的区别
data = iris.data[:,:2]  # 特征
target = iris.target  # 目标值

3）绘出原始数据的图形

plt.scatter(data[:,0],data[:,1],c=target)

4）使用决策树算法（max_depth）

1、获取模型并训练

dtree = DecisionTreeClassifier()
dtree.fit(data,target)

2、将整个画布作为测试数据查看分类效果

构建测试数据

xmin = data[:,0].min() - 0.5
xmax = data[:,0].max() + 0.5
ymin = data[:,1].min() - 0.5
ymax = data[:,1].max() + 0.5

# 取遍范围
x = np.linspace(xmin,xmax,100)
y = np.linspace(ymin,ymax,100)
# 网格化处理x和y 让他们做交叉
xx,yy = np.meshgrid(x,y)
X_test = np.c_[xx.flatten(),yy.flatten()]  # 得到画布上的每一个点

3、使用X_test去预测

y_ = dtree.predict(X_test)

4、绘图

导入cmap制定显示颜色

from matplotlib.colors import ListedColormap
cmap1 = ListedColormap(['r','g','b'])

plt.scatter(X_test[:,0],X_test[:,1],c=y_)
plt.scatter(data[:,0],data[:,1],c=target,cmap=cmap1)  # 先画背景 后画点

max_depth 默认情况下的效果

5、调整max_depth最大深度查看显示效果

max_depth：决策树 决策的次数

dtree = DecisionTreeClassifier(max_depth=1) 

深度太小 容易欠拟合

dtree = DecisionTreeClassifier(max_depth=6) 

深度太大 容易过拟合

5）使用KNN算法

knn容易过拟合

1、获取模型并训练

knn = KNeighborsClassifier()
knn.fit(data,target)

2、模型预测并绘图

y_ = knn.predict(X_test)

plt.scatter(X_test[:,0],X_test[:,1],c=y_)
plt.scatter(data[:,0],data[:,1],c=target,cmap=cmap1)

6）逻辑斯蒂回归算法

* 逻辑回归容易欠拟合*

1、获取模型并训练

lgc = LogisticRegression()
lgc.fit(data,target)

2、模型预测并绘图

y_ = lgc.predict(X_test)
plt.scatter(X_test[:,0],X_test[:,1],c=y_)
plt.scatter(data[:,0],data[:,1],c=target,cmap=cmap1)   

7）三种分类模型总结

处理分类问题
有明确的业务逻辑（反映到图上 是 很规整的散点） 这个时候适合用决策树
knn(容易过拟合)和lgc（容易欠拟合）
能不用knn 尽量不用knn 速度太慢 内存消耗太大

六、决策树处理回归问题

回归很少用决策树
使用回归预测一个椭圆

在-np.pi到np.pi的范围 中 产生200个点

生成正弦值和余弦值

然后根据正弦值和余弦值产生目标值

1）导入模型

from sklearn.tree import DecisionTreeRegressor

2）获取数据

数据集：从-π 到π 取200个值

X_train = np.linspace(-np.pi,np.pi,200)
X_train

结果集：从s里取出第一个，再从c中取出一个，两个一起生成一个点的位置。

s = np.sin(X_train)
c = np.cos(X_train)
target = np.c_[s,c]

3）将所有的点画到画布上

plt.figure(figsize=(5,5))
plt.scatter(target[:,0],target[:,1])

4）撒盐操作

让圆上的40个点不规则的显示在圆的周围

noise = np.random.randn(40,2)/10  # 40行2列
target[::5] += noise   #每隔5个加一个噪声

将撒盐后的图形

plt.figure(figsize=(5,5))
plt.scatter(target[:,0],target[:,1])

5）创建决策树回归模型并训练

dtree = DecisionTreeRegressor()
dtree.fit(X_train.reshape(-1,1),target)

6）产生测试数据

X_test = np.linspace(-np.pi,np.pi,180)

7）对测试数据预测

y_ = dtree.predict(X_test.reshape(-1,1))

8）绘制预测后的值的图形

plt.figure(figsize=(5,5))
plt.scatter(y_[:,0],y_[:,1])

9）比较不同深度的拟合情况

深度小 欠拟合 深度大 过拟合

dtree = DecisionTreeRegressor(max_depth=7)  # 深度小 欠拟合  深度大 过拟合
dtree.fit(X_train.reshape(-1,1),target)
y_ = dtree.predict(X_test.reshape(-1,1))
plt.figure(figsize=(5,5))
plt.scatter(y_[:,0],y_[:,1])  # 回归很少用决策树