机器学习之决策树(四)

1 决策树概述

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

之前介绍的K-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。
决策树算法能够读取数据集合，构建类似于上面的决策树。决策树很多任务都是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，机器学习算法最终将使用这些机器从数据集中创造的规则。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌具有几十年工作经验的人类专家

2 决策树分类

分类树

分类树用于分类标签值，如晴天/阴天、用户性别、网页是否是垃圾页面,分类的值是定性的

回归树

回 归树用于预测实数值，如明天的温度、用户的年龄、网页的相关程度,回归树的值是定量的

3 构造决策树

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

分裂属性分为三种不同的情况：

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

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

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

构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。
属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。即不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解.

4 ID3算法

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

划分原则: 将无序的数据变得更加有序.

熵: 用于度量无序程度

一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

信息增益

组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。

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

(1) 计算公式: p(x)是选择该分类的概率 %e6%98%af%e9%80%89%e6%8b%a9%e8%af%a5%e5%88%86%e7%b1%bb%e7%9a%84%e6%a6%82%e7%8e%87.png)

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

n是分类的数目

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

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

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

则信息增益为两者的差值:

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。我们假设训练集合包含10个元素：

import numpy as np
import pandas as pd
from pandas import Series,DataFrame
import math
# no  p = 3/10  0.3
# yes p = 0.7

# 按照类别对训练数据进行的划分
# 数据样本原始的熵
info_D = -0.3*math.log2(0.3) -0.7*math.log2(0.7)
info_D
#输出  0.8812908992306927

按照日志密度划分信息增益

# s  0.3  no yes no    -- no 2/3  yes 1/3
# l  0.3  yes yes yes  -- no 0    yes 1
# m  0.4  yes yes no yes -- no 1/4 yes 3/4

info_L_D = 0.3*(-2/3*math.log2(2/3)-1/3*math.log2(1/3)) + 0.3*(-1*math.log2(1)) + 0.4*(-1/4*math.log2(1/4)-3/4*math.log2(3/4))
info_L_D
#输出  0.6
info_D - info_L_D
#输出  0.2812908992306927

计算按照好友密度划分的信息熵

# 计算按照好友密度划分的信息熵
# s 0.4  no no yes no   --- no 3/4 yes 1/4
# l 0.2  yes yes        --- no 0   yes 1
# m 0.4  yes yes yes yes -- no 0   yes 1
info_F_D = 0.4*(-3/4*math.log2(3/4)-1/4*math.log2(1/4))
info_F_D
#输出  0.32451124978365314
info_D - info_F_D
#输出  0.5567796494470396

按照是否使用真实头像的熵

# no  0.5  no yes no yes yes   ---  no 2/5  yes 3/5
# yes 0.5  yes yes yes yes no  ---  no 1/5  yes 4/5
info_H_D = 0.5*(-2/5*math.log2(2/5)-3/5*math.log2(3/5)) + 0.5*(-1/5*math.log2(1/5)-4/5*math.log2(4/5))
info_H_D
#输出 0.8464393446710154
info_D - info_H_D
#输出 0.034851554559677256

实战

1 比较KNN 逻辑斯蒂 决策树进行分类

from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LogisticRegression

#导入IRIS数据集,加载IRIS的数据集
iris = datasets.load_iris()
X = iris.data
y = iris.target

#max_depth 设置决策树的最大深度
reg1 = DecisionTreeClassifier(max_depth=5)
reg1.fit(X,y).score(X,y)  #输出  1.0
#KNN
reg2 = KNeighborsClassifier()
reg2.fit(X,y).score(X,y)  #输出0.967
#逻辑斯蒂
reg3 = LogisticRegression()
reg3.fit(X,y).score(X,y)  #输出0.96

从结果可知，决策树得分最高，预测最准确.

2 预测一个椭圆

#导包
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor

# 创建X与y
rng = np.random.RandomState(1) #伪随机数 == np.random.seed(1) 可预知的随机数

#随机生成-100 到100的数字,这些数字就是角度
X = np.sort(200 * rng.rand(100,1) - 100,axis = 0)
#根据角度生成正弦值和余弦值，这些值就是圆上面的点
y = np.array([np.pi * np.sin(X).ravel(),np.pi * np.cos(X).ravel()]).transpose()
#添加噪声
y[::5,:] += (0.5 -rng.rand(20,2))

#参数max_depth越大，越容易过拟合
# 第1步：训练
regr1 = DecisionTreeRegressor(max_depth=2)
regr2 = DecisionTreeRegressor(max_depth=5)
regr3 = DecisionTreeRegressor(max_depth=8)

regr1.fit(X,y)
regr2.fit(X,y)
regr3.fit(X,y)

# 第2步：预测
X_test = np.arange(-100.0,100.0,0.01)[:,np.newaxis]
y_1 = regr1.predict(X_test)
y_2 = regr2.predict(X_test)
y_3 = regr3.predict(X_test)

根据数据绘制椭圆图

# 显示图像
plt.figure(figsize=(12,8))
s = 50

plt.subplot(221)
plt.scatter(y[:,0],y[:,1],c='navy',s=s,label='data')
plt.legend()

plt.subplot(222)
plt.scatter(y_1[:,0],y_1[:,1],c='b',s=s,label='data')
plt.legend()

plt.subplot(223)
plt.scatter(y_2[:,0],y_2[:,1],c='r',s=s,label='data')
plt.legend()

plt.subplot(224)
plt.scatter(y_3[:,0],y_3[:,1],c='g',s=s,label='data')
plt.legend()

plt.show()

3 下面我们对鸢尾花的案例再次进行分析

from sklearn.tree import DecisionTreeClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LogisticRegression
#导包加载数据
from sklearn.datasets import load_iris
iris = load_iris()
data = iris.data
target = iris.target

# 特征选择？？ 方差选择
data.std(axis=0)
# array([0.82530129, 0.43214658, 1.75852918, 0.76061262])
train = data[:,[0,3]]
import matplotlib.pyplot as plt
%matplotlib inline
plt.scatter(train[:,0],train[:,1],c=target)

# 获取预测集（屏幕中所有的点）
xmin,xmax = train[:,0].min(),train[:,0].max()
ymin,ymax = train[:,1].min(),train[:,1].max()
x = np.linspace(xmin,xmax,300)
y = np.linspace(ymin,ymax,300)
#meshgrid函数用两个坐标轴上的点在平面上画格。
xx,yy = np.meshgrid(x,y)
X_test = np.c_[xx.ravel(),yy.ravel()]

使用决策树算法

# max_depth 决策树深度，一般设置的值不要超过特征数量
# max_depth 值越大，拟合度越高
tree = DecisionTreeClassifier(max_depth=1)
tree.fit(train,target)

使用KNN算法

knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(train,target)

使用逻辑斯蒂回归算法

logistic = LogisticRegression()
logistic.fit(train,target)

预测数据

results = [tree.predict(X_test),knn.predict(X_test),logistic.predict(X_test)]

图形绘制

from matplotlib.colors import ListedColormap
cmap = ListedColormap(['#00aaff','#ff00aa','#aaff00'])

titles = ['DecisonTree','Knn','Logistic']
plt.figure(figsize=(12,3))
for i,y_ in enumerate(results):
    axes = plt.subplot(1,3,i+1)
    axes.scatter(X_test[:,0],X_test[:,1],c=y_,cmap=cmap)
    axes.set_title(titles[i])
    axes.scatter(train[:,0],train[:,1],c=target)