0003.有监督学习之决策树
一、什么是决策树
决策树（Decision Tree）是有监督学习中的一种算法，并且是一种节本的分类与回归的方法。即决策树有两种：分类树和回归树。
那什么事决策树了？ 简单点说就是二元判定，从头到尾逐次判定其归属类型。
从上述案例，我们很容易理解：决策树算法的本质就是二元判定的属性结构，我们可以通过一些静心设计的问题，对数据进行分类。以下是关于决策树需要理解的几个概念：
| 节点 | 说明 |
| 根节点 | 没有进边，有出边 |
| 中间节点 | 既有进边也有出边，但进边有且仅有一条，出边也可以有很多条 |
| 叶节点 | 只有进边，没有出边，进边有且仅有一条。每个叶节点都是一类类别标签 |
| *父节点和子节点 | 在两个相连的节点中，更靠近根节点的是父节点，另一个则是子节点。两者是相对的 |
决策树看作是一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：
- 由决策树的根节点到叶节点的每一条路径构建一条规则
- 路径上中间节点的特征对应着规则的条件，叶节点的类标签对应着规则的结论
决策树的路径或者其对应的if-then规则集合有一个重要的性质：互斥并且完备。也就是说，每一个实例都被有且仅有一条路径或者规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。
二、决策树的构建准备工作
使用决策树做分类的每一步步骤都很重要，首先我们要手机足够多的数据，如果数据收集不到位，将会导致没有足够的特征去构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，也会导致最终无法构建出分类效果好的决策树。从算法方面来看的话，决策树的构建就是我们的核心内容。
决策树如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和决策树的剪枝。
1. 特征选择
特征选择就是决定用哪个特征来划分特征空间，其目的在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称这个特征是没有分类能力的，经验上扔掉这些特征对决策树学习的精度影响不会很大。
那如何来选择最优的特征进行划分呢？一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本仅可能属于同一类别，也就是节点的纯度（purity）越来越高。
下面是三个图表示的是纯度越来越低的过程，最后一个表示的是纯度最低的状态。
在实际使用中，我们衡量的常常是不纯度。度量不纯度的指标有很多种，如：熵、增益率、基尼指数。
这里我们使用的是熵，即香农熵，这个名字来源于信息论之父 克劳德-香农。
①香农熵及计算函数
熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。
假定当前样本集合D中一共有n类样本，第i类样本为xi，那么xi的信息定义为：l(xi) = -log2p(xi)
其中p(xi) 是选择该分类的概率。
通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有累呗所有可能值包含的信息期望值（数学期望），通过下面的公式得到：
Ent(D)的值越小，则D的不纯度就越低。
香农熵的python代码如下：
def calEnt(dataSet): """ 函数功能：计算香农熵 参数说明： dataSet：原始数据集 返回： ent：香农熵的值 """ n = dataSet.shape[0] # 数据集的总行数 iset = dataSet.iloc[:, -1].calue_counts() # 标签的所有类别 p = iset/n # 每一类标签的占比 ent = (-p*np.log2(p)).sum() # 信息熵（此函数应该要导入numpy库， from numpy as np） return ent
下面以海洋生物数据为例来构建数据集，并计算香农熵。
首先创建海洋生物数据集
import pandas as pd import numpy as np 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
带入数据集后，可以看到其熵结果97.1%。熵越高，信息的不纯度就越高。也就是混合的数据就越多。
②信息增益
信息增益（information Gain）的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。但是这里要注意的是，此时计算子节点的总信息熵不能简单求和，而要求在求和汇总之前进行修正。假设离散属性a有V个可能的取值{a1，a2，......，aV}，若使用a对样本数据集D进行划分，则会产生V个分支节点，其中第V个分支节点包含了D找那个所有在属性a上取值为au的样本，即为Du。我们可根据信息熵的计算公式计算出Du的信息熵，再考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重|Du| / |D|，这就是所谓的修正。
所以信息增益的计算公式为：
那我们手动计算一下，海洋生物数据集中第0列的信息增益：
用同样的方法，可以把第1列的信息增益也算出来，结果为0.17。
2. 数据集最佳切分函数
划分数据集的最大准则是选择最大信息增益，也就是信息下降最快的方向。
# 选择最优的列进行切分 def bestSplit(dataSet): """ 函数功能：根据信息增益选择出最佳数据集切分的列 参数说明： dataSet：原始数据集 返回： axis：数据集最佳切分列的索引 """ 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 lecvels: # 对房钱列的每一个取值进行循环 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 # 计算当前列的信息增益 if (infoGain > baseGain): bestGain = infoGain # 选择最大信息增益 axis = i # 最大信息增益所在列的索引 return axis
通过上面手动计算，我们知道：第0列的信息增益为0.42，第1列的信息增益为0.17，所以我们应该选择第0列进行切分数据集。