|NO.Z.00005|——————————|BigDataEnd|——|Arithmetic&Machine.v05|——|Machine：监督学习算法.v04|

### --- 学习算法

~~~     决策树学习本质上是从训练数据集中归纳出一组分类规则，也称为 "树归纳"。
~~~     对于给定的训练数据集，存在许多对它无错编码的树。而为了简单起见，
~~~     我们感兴趣的是从中选出 "最小" 的树，这里的树的大小用树的节点数和决策节点的复杂性度量。

~~~     从另一个角度看，决策树学习是由训练数据集估计条件概率模型。
~~~     基于特征空间划分的类的条件概率模型有无数个，
~~~     我们选择的模型应该是不仅能对训练数据有很好的拟合，而且对未知数据也有很好的预测。

~~~     树的学习算法从包含全部训练数据的根开始，每一步都选择最佳划分。
~~~     依赖于所选择的属性是数值属性还是离散属性，每次将数据划分为两个或 n 个子集，
~~~     然后使用对应的子集递归地进行划分，直到所有训练数据子集被基本正确分类，
~~~     或者没有合适的特征为止，此时，创建一个树叶节点并标记它，这就生成了一颗决策树。

~~~     综上，决策树学习算法包含特征选择、决策树的生成与决策树的剪枝。
~~~     由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。
~~~     其中决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

### --- 特征选择：香农熵和信息增益

~~~     # 香农熵的计算
~~~     决策树学习的关键在如何选择最优划分属性。一般而言，随着划分过程不断进行，
~~~     我们希望决策树的分支节点所包含的样本尽可能属于同一类别， 
~~~     即节点的 "纯度" （purity）越来越高。
~~~     在分类树中，划分的优劣用不纯度度量（impurity-measure）定量分析。
~~~     对于节点m，令Nm 为到达节点m的训练实例数，对于根节点，Nm为 N。
~~~     Nm个实例中有Nim个属Ci 类，而 。
~~~     当一个实例到达了节点m则它属于Ci类的概率估计为：

~~~     在二分类问题中，如果对于所有的，Pim为0或1。
~~~     当到达节点 时，所有实例都不属于Ci类，则Pim为 0。反之，如果所有实例都属于Ci类，
~~~     Pim则为1。如果此时划分是纯的，则我们不需要再进一步划分，
~~~     并可以添加一个叶节点，用Pim为 1 的类标记。

~~~     我们可以将任意节点的类分布记作(P0,P1)，其中P1=1-P0。
~~~     选择最佳划分的度量通常是根据划分后叶节点不纯性的程度。不纯度越低，类分布就越倾斜。
~~~     例如，类分布为{0,1)的节点具有零不纯性，而均衡分布(0.5,0.5)的的节点具有最高的不纯性。
~~~     一种度量不纯性的函数是熵函数（entropy）：

~~~     若P=0，则 Pimlog2Pim=0。
~~~     在信息论与概率统计中，熵是表示随机变量不确定性的度量。这里我们使用的熵，也叫作香农熵，
~~~     这个名字来源于信息论之父克劳德·香农。

~~~     为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值（数学期望），即上述公式。
~~~     对于二分类问题，如P1=1 而P2=0 ，则所有的实例都属于Ci类，熵为 0。如果P1=P2=0.5 ，熵为1。

import numpy as np
p=1/2
-((p*np.log2(p))+(p*np.log2(p)))

~~~     # 输出参数
1.0

~~~     但是，熵并非是唯一可能的度量。
~~~     对于二分类问题，其中P1=P，P2=1-P ，函数 是非负函数，度量划分的不纯度，如果满足如下性质：

~~~     这些都可以推广到 K>2 类，并且给定损失函数，误分类误差可以推广到最小风险。
~~~     下图显示了二元分类问题不纯性度量值得比较，p 表示属于其中一个类的记录所占的比例。
~~~     从图中可以看出，三种方法都在类分布均衡时（即当 p=0.5 时 ）达到最大值，
~~~     而当所有记录都属于同一个类时（p等于 1 或 0）达到最小值。

~~~     # 这里我们给出三种不纯性度量方法的计算实例：

~~~     从上面的例子及图中可以看出，不同的不纯性度量是一致的。根据计算，
~~~     节点 具有最低的不纯性度量值，然后依次是N2，N3 。
~~~     虽然结果是一致的，但是作为测试条件的属性选择仍然因不纯性度量的选择而异。

### --- 香农熵的代码实现

row_data = {'是否陪伴' :[0,0,0,1,1],
'是否玩游戏':[1,1,0,1,1],
'渣男' :['是','是','不是','不是','不是']}
dataSet = pd.DataFrame(row_data)
dataSet

def calEnt(dataSet):
n = dataSet.shape[0] # 数据集总行数
iset = dataSet.iloc[:,-1].value_counts() # 标签的所有类别
p = iset/n # 每一类标签所占比
ent = (-p*np.log2(p)).sum() # 计算信息熵
return ent
calEnt(dataSet)

~~~     # 输出参数
0.9709505944546686

~~~     熵越高，信息的不纯度就越高，则混合的数据就越多。
~~~     也就是说，单从判断的结果来看，如果你从这 5 人中瞎猜，
~~~     要准确判断其中一个人是不是“bad boy”，是不容易的。

### --- 信息增益

~~~     决策树最终的优化目标使得叶节点的总不纯度最低，即对应衡量不纯度的指标最低。
~~~     同时我们知道，全局最优树没有办法简单高效的获得，
~~~     因此此处我们仍然要以局部最优化方法来指导建模过程，并通过优化条件的设置，
~~~     最终在每一步都是局部最优的条件下逐步至尽可能全局最优的结果。
~~~     而在信息熵指数的指导下，决策树生成过程的局部最优条件也非常好理解：
~~~     即在选取属性测试条件（attribute test condition）对某节点（数据集）进行切分的时候，
~~~     尽可能选取使得该节点对应的子节点信息熵最小的特征进行切分。
~~~     换而言之，就是要求父节点信息熵和子节点总信息熵之差要最大。
~~~     假定离散属性a有V个可能的取值a1,a2,q3...aV,若使用来对父节点样本集D进行划分，
~~~     则会产生V个分支节点。

~~~     其中第V个分支节点包含了D中所有在属性a上的取值为aV的样本，这些样本记为Dv。
~~~     我们可以根据熵函数计算出Dv的信息熵，
~~~     考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重|DV|/D|。

~~~     为了确定测试条件的效果，
~~~     我们需要比较父节点（划分前）的不纯程度和分支节点（划分后）的不纯程度，
~~~     它们的差越大，则意味着使用属性 a 来进行划分所获得的 "不纯度提升" 越大，测试条件效果越好。

### --- 也可以用以下公式：

~~~     其中 即为 Ent(D)，是给定节点的不纯度度量，D 是父节点上的记录总数，V 表示属性的个数，
~~~     Dv是与第 v 个分支节点相关联的记录个数。
~~~     对此，我们可以用增益来确定划分效果的标准。

~~~     决策树归纳算法通常选择最大化增益的测试条件，因为对所有的测试条件来说，
~~~     Ent(D) 是一个不变的值，所以最大化增益等价于最小化分支节点的不纯性度量的加权平均值。

~~~     最后，当选择熵作为公式的不纯性度量时，熵的差就是所谓的 "信息增益" ，
~~~     即资讯获利（information gain）。 我们手动计算一下，bad boy 数据集中第 0 列的信息增益：

### --- 划分数据集

~~~     分类算法除了需要测量信息熵，还需要划分数据集。
~~~     在知道如何得到熵之后，我们就可以按照获取最大信息增益的方法来判断是否正确地划分了数据集。 
~~~     我们将对每个特征划分数据集的结果计算一次信息熵，
~~~     以便判断按照哪个特征划分数据集是最好的划分方式。

### --- 数据集最佳切分函数

~~~     划分数据集的最大准则是选择最大信息增益，也就是信息下降最快的方向。
~~~     通过手动计算，我们知道：
~~~     第 0 列的信息增益为 0.42，第 1 列的信息增益为 0.17，0.42 > 0.17。
~~~     所以我们应该选择第 0 列进行切分数据集。

### --- 用 Python 可以通过以下代码来输出每一列的信息增益（了解即可）：

# 定义信息熵
def calEnt(dataSet):
n = dataSet.shape[0] # 数据集总行数
iset = dataSet.iloc[:,-1].value_counts() # 统计标签的所有类别
p = iset/n # 统计每一类标签所占比
ent = (-p*np.log2(p)).sum() # 计算信息熵
return ent
# 选择最优的列进行切分
def bestSplit(dataSet):
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 levels: # 对当前列的每一个取值进行循环
childSet = dataSet[dataSet.iloc[:,i]==j] # 某一个子节点的
dataframe
ent = calEnt(childSet) # 计算某一个子节点的信息熵
ents += (childSet.shape[0]/dataSet.shape[0])*ent # 计算当前列的信息熵
print('第{}列的信息熵为{}'.format(i,ents))
infoGain = baseEnt-ents # 计算当前列的信息增益
print('第{}列的信息增益为{}\n'.format(i,infoGain))
if (infoGain > bestGain):
bestGain = infoGain # 选择最大信息增益
axis = i # 最大信息增益所在列的索引
print("第{}列为最优切分列".format(axis))
return axis

### --- 接下来，我们来验证我们构造的数据集最佳切分函数返回的结果与手动计算的结果是否一致。

bestSplit(dataSet)

~~~     第 0 列的信息熵为 0.5509775004326937
~~~     第 0 列的信息增益为 0.4199730940219749
~~~     第 1 列的信息熵为 0.8
~~~     第 1 列的信息增益为 0.17095059445466854
~~~     第 0 列为最优切分列
~~~     也就是说，最大信息熵的所选的特征是分类后熵值最小的特征。
~~~     分类后熵值最小的特征恰恰是分类结果一致的特征，
~~~		而分类结果一致的特征必须是两类样本差异最大的特征。

### --- 按照给定列切分数据集

~~~     通过最佳切分函数返回最佳切分列的索引，我们就可以根据这个索引，
~~~     构建一个按照给定列切分数据集的函数。

"""
函数功能：按照给定的列划分数据集
参数说明：
dataSet：原始数据集
axis：指定的列索引
value：指定的属性值
return：redataSet：按照指定列索引和属性值切分后的数据集
"""
def mySplit(dataSet,axis,value):
col = dataSet.columns[axis]
redataSet = dataSet.loc[dataSet[col]==value,:].drop(col,axis=1)
return redataSet
#验证函数：以axis=0，value=1为例
mySplit(dataSet,0,1)

### --- 决策树的生成

~~~     # 目前我们已经学习了从数据集构造决策树算法所需要的子功能模块，其工作原理如下：
~~~     得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，
~~~     因此可能存在大于两个分支的数据集划分。
~~~     第一次划分之后，数据集被向下传递到树的分支的下一个节点。
~~~     在新的节点上，我们可以再次划分数据，因此我们可以采用递归的原则处理数据集。

### --- 递归约束的条件是：

~~~     程序遍历完所有划分数据集的属性
~~~     每个分支下的所有实例都具有相同的分类
~~~     当前节点包含的样本集合为空，不能划分

~~~     在第 2 种情形下，我们把当前节点标记为叶节点，
~~~     并将其类别设定为该节点所含样本最多的类别，任 何到达叶节点的数据必然属于叶节点的分类；
~~~     在第 3 种情形下，同样把当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。

### --- ID3算法
~~~     ID3 算法原型见于 J.R Quinlan 的博士论文，是基础理论较为完善，
~~~     使用较为广泛的决策树模型，在此基础上 J.R Quinlan 进行优化后，
~~~     陆续推出了 C4.5 和 C5.0 决策树算法，我们先从 ID3 开始，再讨论如何从 ID3 逐渐优化至 C4.5。
~~~     ID3 算法的核心是在决策树各个节点应用信息增益准则选择特征，递归地构建决策树。

~~~     # 具体方法是：
~~~     从根节点开始，对节点计算所有可能的特征的信息增益。
~~~     选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点。
~~~     再对子节点调用以上方法，构建决策树。
~~~     直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一颗决策树。

### --- python代码实现（了解即可）

"""
函数功能：基于最大信息增益切分数据集，递归构建决策树
参数说明：
dataSet：原始数据集(最有一列是标签)
return：myTree：字典形式的树
"""
def createTree(dataSet):
featlist = list(dataSet.columns) # 提取出数据集所有的列
classlist = dataSet.iloc[:,-1].value_counts() # 获取最后一列类标签
# 判断最多标签数目是否等于数据集行数，或者数据集是否只有一列
if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
return classlist.index[0] # 如果是，返回类标签
axis = bestSplit(dataSet) # 确定出当前最佳切分列的索引
bestfeat = featlist[axis] # 获取该索引对应的特征
myTree = {bestfeat:{}} # 采用字典嵌套的方式存储树信息
del featlist[axis] # 删除当前特征
valuelist = set(dataSet.iloc[:,axis]) # 提取最佳切分列所有属性值
for value in valuelist: # 对每一个属性值递归建树
myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
return myTree
#查看运行结果
myTree = createTree(dataSet)
myTree

{'是否陪伴': {0: {'是否玩游戏': {0: '不是', 1: '是'}}, 1: '不是'}}

### --- ID3算法局限性

~~~     # ID3 算法局限主要源于局部最优化条件，即信息增益的计算方法，其局限性主要有以下几点：
~~~     分支度越高（分类水平越多）的离散变量往往子节点的总信息熵更小，
~~~     ID3 是按照某一列进行切分， 有一些列的分类可能不会对结果有足够好的指示。
~~~     极端情况下取 ID 作为切分字段，每个分类的纯度都是 100%，因此这样的分类方式是没有效益的。
~~~     不能直接处理连续型变量，若要使用 ID3 处理连续型变量，则首先需要对连续变量进行离散化。
~~~     对缺失值较为敏感，使用 ID3 之前需要提前对缺失值进行处理。
~~~     没有剪枝的设置，容易导致过拟合，即在训练集上表现很好，
~~~     测试集上表现很差对于 ID3 的诸多优化措施，最终也构成了 C4.5 算法的核心内容。

### --- C4.5 算法

~~~     C4.5 算法与 ID3 算法相似，C4.5 算法对 ID3 算法进行了改进，C4.5 在生成的过程中，
~~~     用信息增益比准则来选择特征。

### --- 修改局部最优化条件

~~~     以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。
~~~     使用信息增益比（information gain ratio）可以对这一问题进行校正。
~~~     信息增益比定义为其信息增益与训练数据集关于某一特征的值的熵之比：

~~~     称为属性 a 的 "固有值“（intrinsic value）。
~~~     属性 a 的可能取值越多（即 V 越大），则 IV(a) 的值通常会越大。
~~~     IV 值会随着叶节点上样本量的变小而逐渐变大，也就是说一个特征属性中如果标签分类太多，
~~~     每个叶子上的 IV 值就会非常大。

~~~     值得注意的是，增益率准则对可取值数目较少的属性有所偏好，
~~~     因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，
~~~     而是使用了一种启发式：先从候选划分属性中找出信息增益高于平均水平的属性， 再从中选择增益率最高的。

~~~     我们可利用 Gain_ratio 代替 Gain 重新计算数据集中第 0 列的 Gain_ratio ，
~~~     由于根据 accompany 字段切分后，2 个分支分别有 3 个和 2 个的样例数据，

~~~     因此其 IV 指标计算过程如下：
~~~     然后可进一步计算其他各字段的 Gain_ratio ，并选取 Gain_ratio 最大的字段进行切分。

### --- 连续变量处理手段

~~~     在 C4.5 中，同样还增加了针对连续变量的处理手段。如果输入特征字段是连续型变量，
~~~     则算法首先会对这一列数进行从小到大的排序，
~~~     然后选取相邻的两个数的中间数作为切分数据集的备选点，若一个连续 变量有 N 个值，
~~~     则在 C4.5 的处理过程中将产生 N-1 个备选切分点，
~~~     并且每个切分点都代表着一种二叉树的切分方案，例如：

~~~     这里需要注意的是，此时针对连续变量的处理并非是将其转化为一个拥有 N-1 个分类水平的分类变量，
~~~     而是将其转化成了 N-1 个二分方案，而在进行下一次的切分过程中，这 N-1 个方案都要单独带入考虑，
~~~     其中每一个切分方案和一个离散变量的地位均相同（一个离散变量就是一个单独的多路切分方案）。 
~~~     例如有如下数据集，数据集中只有两个字段，第一行代表年龄，是特征变量，第二行代表性别，
~~~     是目标字段，则对年龄这一连续变量的切分方案如图所示：

~~~     从上述论述能够看出，在对于包含连续变量的数据集进行树模型构建的过程中要消耗更多的运算资源。
~~~     但与此同时，我们也会发现，当连续变量的某中间点参与到决策树的二分过程中，
~~~     往往代表该点对于最终分类结果有较大影响，这也为我们连续变量的分箱压缩提供了指导性意见。 
~~~     例如上述案例，若要对Age 列进行压缩，则可考虑使用 36.5 对其进行分箱，
~~~     则分箱结果对于性别这一目标字段仍然具有较好的分类效果，
~~~     这也是决策树的最常见用途之一，也是最重要的模型指导分箱的方法。

### --- 决策树的拟合度优化

~~~     在实际操作过程中，我们判断模型是否过拟合往往是从模型训练误差和泛化误差的比较中得出，
~~~     而采用我们之前介绍的交叉验证可得到较为准确的训练误差和泛化误差，
~~~     二者结合使用就能判断模型是否存在过拟合现象。
~~~     虽然我们之前举例时并没有对数据集进行切分，
~~~     但任何有监督学习算法建模过程中都需要进行训练集和测试集的划分，
~~~     决策树也不例外，进而我们可用交叉验证计算训练误差和泛化误差，
~~~     进而判断决策树是否存在过拟合。这是一套通用地判断有监督学习算法是否过拟合的方法，
~~~     同时通用的方法中还有更高级的方法，我们将在后续进行逐步介绍。
~~~     但对于决策树而言，有一套决策树独有的防止过拟合的解决方案— —剪枝。

### --- 决策树剪枝

~~~     所谓剪枝是指在决策树中去除部分叶节点。
~~~     剪枝（Pruning）主要是用来防止过拟合，对于一般的数据集如果总是追求 ”纯的“ 叶节点，
~~~     或者观测数较小的叶节点，很容易使得树过于庞杂，尤其是存在可以反复使用的连续变量的时候，
~~~     此时就需要主动去掉一些分支来降低过拟合的风险。
~~~     常见的剪枝策略有 ”预剪枝“（Pre-Pruning）和 ”后剪枝“（Post-Pruning）。

~~~     # - 预剪枝：
~~~     在决策树生成的过程中，对每个节点在划分前先进行估计，
~~~     如果当前的节点划分不能带来决策树泛化性能（预测性能）的提升，
~~~     则停止划分并且将当前节点标记为叶节点。

~~~     # - 后剪枝：
~~~     先训练生成一颗完整的树，自底向上对非叶节点进行考察，
~~~     如果将该节点对应的子树替换为叶节点能带来决策树泛化能力的提升，则将该子树替换为叶节点。

### --- CART 算法

~~~     # CART：分类回归树（Classification and Regression Tree）
~~~     分裂过程是一个二叉递归划分过程
~~~     CART 预测变量 x 的类型既可以是连续型变量也可以是分类型变量
~~~     数据应以其原始形式处理，不需要离散化
~~~     用于数值型预测时，并没有使用回归，而是基于到达叶节点的案例的平均值做出预测

### --- 分裂准则

~~~     # 二叉递归划分：条件成立向左，反之向右
~~~     对于连续变量：条件是属性小于等于最优分裂点
~~~     对于分类变量：条件是属性属于若干类

### --- 二叉分裂的优点

~~~     # 相比多路分裂导致数据碎片化的速度慢，允许在一个属性上重复分裂，
~~~     # 即可以在一个属性上产生足够多的分裂。两
~~~     # 路分裂带来的树预测性能提升足以弥补其相应的树易读性损失。
~~~     对于属性不同的被预测变量 y 分裂准则不同：
~~~     分类树：Gini 准则。与之前的信息增益很类似，Gini 系数度量一个节点的不纯度。
~~~     回归树：一种常见的分割标准是标准偏差减少（Standard Deviation Reduction, SDR），
~~~     类似于最小均方误差 LS（least squares，预测错误的平方和）准则。

### --- 利用测试集进行剪枝

~~~     简单讨论 CART 算法剪枝过程，该过程也是测试集用于修正模型的最佳体现。
~~~     例如，有如下在训练集中训练得到的树模型，黑色数字表示训练集上的分类情况，
~~~     红色数字表示模型作用于验证集上的分类情况。

~~~     # 则 CART 算法利用验证集剪枝的过程如下：

~~~     判断每个叶节点在验证集上的错误率：
~~~     节点 4 的错误率e(4)=1/3
~~~     节点 5 的错误率e(5)=1
~~~     节点 6 的错误率e(6)=1
~~~     节点 7 的错误率为e(7)=4/9
~~~     计算子节点总加权平均错误率并和父节点进行比较，
~~~     加权方法就是乘以该节点样本量占父节点样本总量的百分比（测试集）：

~~~     如节点 2 的错误率为e(2)=1/4 ，而节点 4 和节点 5 的加权平均错误率为
~~~     e(4)*3/4+e(5)*1/4=2/4，因此子节点错误率更高，考虑剪枝;
~~~     节点 3 的错误率e(3)=4/10 ，e(6)*1/10+e(7)*9/10=1/10而 ，因此考虑剪枝；
~~~     节点 2 和节点 3 的加权平均错误率为e(2)*4/14+e(3)*10/14=5/14 ，
~~~     比父节点（节点 1）的错误率e(1)=7/14要小，因此保留该节点，停止剪枝。
~~~     可以看出，CART 算法剪枝过程更易于理解也更便于操作，
~~~     同时我们也能看到对于建立模型的算法而言，测试集不仅能够对模型准确率进行评估，
~~~     同时还能起到修正优化模型的作用。

### --- 测试集和验证集

~~~     对于大多数模型而言，测试集实际上的作用就是用来修正模型，为了提高修正的准确率，
~~~     我们也可采用交叉验证的方法，反复判别模型修改条件（如是否要剪枝），
~~~     并设置模型修改触发条件（如多数验证情况需要修改则对其进行修改），从而提高模型优化的可靠性。
~~~     而除了训练集和测试集之外，我们还常常会划分一个验证集，
~~~     验证集数据不参与建模也不参与模型修改和优化，只用于测试最终优化后模型效力。

~~~     而训练集、测试集和验证集的划分通常遵照 6:2:2 的比例进行划分，
~~~     当然也可根据实际需求适当调整划分比例，但无论如何，
~~~     测试集和验证集数据数量都不宜过多也不宜过少，该二者数据集数据均不参与建模， 
~~~     若占比太多，则会对模型构建过程造成较大影响（欠拟合），而若划分数据过少，
~~~     训练集数据量较大， 则又有可能造成过拟合，数据集的划分也是影响拟合度的重要因素。