【一起啃西瓜书】机器学习-期末复习

机器学习-期末复习笔记

• 第一章：绪论
• • 引言
  • 一般过程
  • 任务
  • 数据
  • 泛化能力
• 第二章：模型评估与选择
• • 错误率&误差
  • 经验误差与过拟合
  • 评估方法
  • 性能度量
  • • 错误率&精度
    • 查准率&查全率
    • P-R曲线
  • ROC&AUC
  • 偏差与方差
• 第三章：线性模型
• • 基本形式
  • 线性模型优点
  • 参数/模型估计
  • 对数线性回归
  • 对数几率回归
• 第四章：决策树
• • 基本流程
  • 划分选择
  • • 信息增益
    • 增益率
    • 基尼指数
  • 剪枝处理
  • • 预剪枝
    • 后剪枝
  • ID3,C4.5和CART算法对比
• 第五章 神经网络
• • 神经元模型
  • 感知机
  • 多层感知机
  • 多层前馈神经网络
  • 误差逆传播算法
  • 全局最小与局部极小
  • 深度学习
• 第六章：支持向量机
• • 间隔与支持向量
  • 对偶问题
  • 解的稀疏性
  • 求解方法 - SMO
  • 线性不可分
  • 核支持向量机
  • 核函数
  • 软间隔
  • 损失函数
• 第七章：贝叶斯分类器
• • 贝叶斯决策论
  • 极大似然估计
  • 朴素贝叶斯分类器
  • 拉普拉斯修正
• 第八章：集成学习
• • 个体与集成
  • Boosting
  • AdaBoost推导
  • AdaBoost注意事项
  • AdaBoost实验
  • Bagging与随机森林
  • Bagging算法特点
  • 随机森林
  • 随机森林的特点
  • 随机森林的生成
  • 袋外错误率（OOB error）
  • 随机森林的简单实例分析
• 第九章：聚类
• • 聚类任务
  • 性能度量
  • 距离计算
  • 原型聚类
  • • k均值算法
  • 层次聚类
• 总结

第一章：绪论

引言

人工智能和机器学习，深度学习的关系：

• 机器学习是人工智能的一个实现途径
• 深度学习是机器学习的一个方法发展而来

机器学习致力于研究如何通过计算的手段，利用经验来改善系统自身的性能，从而在计算机上从数据（经验）中产生“模型”，用于对新的情况给出判断（利用此模型预测未来的一种方法）。

分为三类：监督学习、无监督学习、强化学习。

一般过程

1. 数据获取
2. 特征工程
3. 模型选择
4. 模型训练
5. 模型评估
6. 超参数条件
7. 预测

更详细：

机器学习过程中,通过确定两方面的参数来找到泛化性能最好的函数:

1. 函数参数,也就是我们通常所说的w和b，这类参数可以通过各种最优化算法自动求得;
2. 模型参数,比如多项式回归中的多项式次数,规则化参数入等(即超参数)，一般在模型训练之前通过手工指定（当然也可以采用网格法等算法进行寻优)。

确定模型超参数的过程称为模型选择(从Algorithm选择Models)。

机器学习的一般过程:

1. 确定模型的一组超参数，
2. 用训练集训练该模型,找到使损失函数最小的最优函数,
3. 在验证集上对最优函数的性能进行度量，
4. 重复1、2、3步，直到搜索完指定的超参数组合，
5. 选择在验证集上误差最小的模型,并合并训练集和验证集作为整体训练模型，找到最优函数,
6. 在测试集上对最优函数的泛化性能进行度量。

任务

• 分类:离散值
• 回归:连续值
• 聚类:无标记信息

有无标记信息

• 监督学习：分类、回归
• 无监督学习：聚类
• 半监督学习：两者结合

数据

泛化能力

机器学习的目标是使得学到的模型能很好的适用于“新样本”，而不仅仅是训练集合，我们称模型适用于新样本的能力为泛化(generalization)能力。

第二章：模型评估与选择

错误率&误差

错误率

• 错误率即错分样本的占比：E = a/m

误差

• 误差即样本真实输出与预测输出之间的差异

  • 训练(经验)误差–>训练集
  • 测试误差–>测试集
  • 泛化误差–>除训练集外所有样本（对未参与训练的样本总体，测试集只是其中一小部分）

• 机器学习的目的是通过现有样本，学习到泛化误差小的预测模型；

• 由于事先并不知道新样本的特征，我们只能努力使经验误差最小化；

• 但是，一味地减小经验误差并不必然意味着泛化误差减小。很多时候虽然能在训练集上做到分类错误率为零，但多数情况下这样的学习器并不好。

经验误差与过拟合

• 过拟合（训练集误差小，测试集误差大）
  学习器把训练样本学习的“太好”，将训练样本本身的特点 当做所有样本的一般性质（不考虑数据噪声），导致泛化性能下降
• 欠拟合（训练集误差大）
  对训练样本的一般性质尚未学好

如何判断区分二者？

• 过拟合：模型过于复杂，导致训练误差低，测试误差高
• 欠拟合：模型简单，训练测试误差均高

解决：

过拟合

1. 增加训练样本数量
2. 正则化
3. 降维
4. 集成学习方法
5. 减少模型复杂度

欠拟合：

1. 添加新特性
2. 增加模型复杂度
3. 减小正则化系数

决策树:拓展分支
神经网络:增加训练轮数

• 过拟合：学习器把训练样本本身特点当做所有潜在样本都会具有的一般性质.
• 欠拟合：训练样本的一般性质尚未被学习器学好.

评估方法

现实任务中往往会对学习器的泛化性能、时间开销、存储开销、可解释性等方面的因素进行评估并做出选择。

我们假设测试集是从样本真实分布中独立采样获得，将测试集上的“测试误差”作为泛化误差的近似，所以测试集要和训练集中的样本尽量互斥。

留出法：

• 直接将数据集划分为两个互斥集合
• 训练/测试集划分要尽可能保持数据分布的一致性
• 一般若干次随机划分、重复实验取平均值
• 训练/测试样本比例通常为2:1~4:1

交叉验证法：

• 将数据集分层采样划分为k个大小相似的互斥子集，每次用k-1个子集的并集作为训练集，余下的一个子集作为测试集，最终返回k个测试结果的均值，k最常用的取值是10.

自助法：

以自助采样法为基础，对数据集D有放回采样m次得到训练集D’ , D\D’用做测试集。

• 实际模型与预期模型都使用m个训练样本

• 约有1/3的样本没在训练集中出现

• 从初始数据集中产生多个不同的训练集，对集成学习有很大的好处

• 自助法在数据集较小、难以有效划分训练/测试集时很有用；由于改变了数据集分布可能引入估计偏差，在数据量足够时，留出法和交叉验证法更常用。

性能度量

性能度量是衡量模型泛化能力的评价标准，反映了任务需求；使用不同的性能度量往往会导致不同的评判结果

回归任务最常用的性能度量是“均方误差”：

错误率&精度

对于分类任务,错误率和精度是最常用的两种性能度量：

• 错误率：分错样本占样本总数的比率
• 精度（正确率）：分对样本占样本总数的比率

查准率&查全率

信息检索、Web搜索等场景中经常需要衡量正例被预测出来的比率或者预测出来的正例中正确的比率，此时查准率和查全率比错误率和精度更适合。

统计真实标记和预测结果的组合可以得到“混淆矩阵”：

查准率：在预测结果中，预测正例对了所占所有预测正例中的比例（竖着来）

查全率：在真实情况中，预测正例对了所占所有真实情况中的比例（横着来）

在预测癌症患者时，优先考虑查全率，因为如果有一个人漏判了便很严重，所以我们更看重：真实患有癌症的情况下，模型预测正确的概率。

基于混淆矩阵，解释什么是TPR（True Positive Rate）真正利率，FPR（False Positive Rate）假正例率，查准率（P），查全率（R）？

• TPR和R相等，都是真实正例被预测正确的比例，即：TPR=R=TP/TP+FN
• FPR：真实反例被预测为正例的比率，即：FPR=FP/FP+TN
• P：预测为正例的实例中，真正正例的比例，即：P=TP/TP+FP

P-R曲线

对样本进行分类时，模型一般会存在置信度，即当判断一个样本为目标类别的最小概率。根据学习器的预测结果按正例可能性大小对样例进行排序，并逐个把样本作为正例进行预测，则可以得到查准率-查全率曲线，简称“P-R曲线”.

平衡点是曲线上“查准率=查全率”时的取值，可用来用于度量P-R曲线有交叉的分类器性能高低。

比P-R曲线平衡点更用常用的是F1度量：

比$F1$更一般的形式 F B F_B FB​：

F1是基于P和R的调和平均，FB是加权调和平均

ROC&AUC

ROC曲线：纵轴是TPR，横轴是FPR

若某个学习器的ROC曲线被另一个学习器的曲线“包住”，则后者性能优于前者；否则如果曲线交叉，可以根据ROC曲线下面积大小进行比较，也即AUC值.

AUC衡量了样本预测的排序质量。

偏差与方差

通过实验可以估计学习算法的泛化性能，而“偏差-方差分解”可以用来帮助解释泛化性能。

期望输出与真实标记的差别称为偏差：

• 偏差度量了学习算法期望预测与真实结果的偏离程度；即刻画了学习算法本身的拟合能力；
• 方差度量了同样大小训练集的变动所导致的学习性能的变化；即刻画了数据扰动所造成的影响；
• 噪声表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界；即刻画了学习问题本身的难度。

泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的。给定学习任务为了取得好的泛化性能，需要使偏差小(充分拟合数据)而且方差较小(减少数据扰动产生的影响)。

第三章：线性模型

基本形式

线性模型一般形式：
$x$：属性描述的示例，$xi$：是$x$在第$i$个属性上的取值.

向量形式：

f ( x ) = w T x + b f(x) = w^Tx + b f(x)=wTx+b

w = ( w 1 ; w 2 ; . . . ; w d ) w = (w_1;w_2;...;w_d) w=(w1​;w2​;...;wd​)：向量表示

线性模型优点

• 形式简单、易于建模
• 可解释性
• 非线性模型的基础
  • 引入层级结构或高维映射

线性回归（linear regression）目的

• 学得一个线性模型以尽可能准确地预测实值输出标记

单一属性的线性回归目标：

• f ( x ) = w T x + b f(x) = w^Tx + b f(x)=wTx+b

参数/模型估计

参数/模型估计：最小二乘法（least square method）

最小化均方误差

分别对$w$和$b$求导，可得：

基于均方误差最小化来进行模型求解的方法为最小二乘法.

在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧式距离之和最小。

对数线性回归

输出标记的对数为线性模型逼近的目标:

对数几率回归

二分类任务

z = w T x + b z = w^Tx + b z=wTx+b

寻找函数将分类标记与线性回归模型输出联系起来:

最理想的函数——单位阶跃函数

预测值大于零就判为正例，小于零就判为反例，预测值为临界值零则可任意判别

单位阶跃函数缺点：不连续

替代函数——对数几率函数（logistic function）

• 单调可微、任意阶可导

单位阶跃函数与对数几率函数的比较：

运用对数几率函数：

对数几率（log odds）

• 样本作为正例的相对可能性的对数
  
  对数几率回归优点

• 无需事先假设数据分布

• 可得到“类别”的近似概率预测

• 可直接应用现有数值优化算法求取最优解

第四章：决策树

基本流程

决策树基于树结构来进行预测

• 决策过程中提出的每个判定问题都是对某个属性的“测试”
• 决策过程的最终结论对应了我们所希望的判定结果
• 每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内
• 从根结点到每个叶结点的路径对应了一个判定测试序列

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树

划分选择

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高

经典的属性划分方法：

• 信息增益
• 增益率
• 基尼指数

信息增益

“信息熵”是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为 p k p_k pk​，则D的信息熵定义为：

Ent(D)的值越小，则D的纯度越高。

• 计算信息熵时约定：若p=0， p ∗ l o g 2 p = 0 p*log2^p = 0 p∗log2p=0.
• Ent(D)的最小值为0，最大值 l o g 2 y log2^y log2y.

• 一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大
• ID3决策树学习算法[Quinlan, 1986]以信息增益为准则来选择划分属性

信息增益实例

存在的问题

若把“编号”也作为一个候选划分属性，则其信息增益一般远大于其他属性。显然，这样的决策树不具有泛化能力，无法对新样本进行有效预测。

信息增益对可取值数目较多的属性有所偏好

增益率

存在的问题：

• 增益率准则对可取值数目较少的属性有所偏好

C4.5 [Quinlan, 1993]使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选取增益率最高的

基尼指数

数据集D的纯度可用“基尼值”来度量：

• 反映了从D中随机抽取两个样本，其类别标记不一致的概率.

• Gini(D)：越小，数据集D的纯度越高.

CART [Breiman et al., 1984]采用“基尼指数”来选择划分属性

剪枝处理

为什么剪枝？

• “剪枝”是决策树学习算法对付“过拟合”的主要手段
• 可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合

剪枝的基本策略

• 预剪枝
• 后剪枝

判断决策树泛化性能是否提升的方法

• 留出法：预留一部分数据用作“验证集”以进行性能评估

预剪枝

决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别

针对上述数据集，基于信息增益准则，选取属性“脐部”划分训练集。分别计算划分前（即直接将该结点作为叶结点）及划分后的验证集精度，判断是否需要划分。若划分后能提高验证集精度，则划分，对划分后的属性，执行同样判断；否则，不划分

预剪枝的优缺点

优点

• 降低过拟合风险
• 显著减少训练时间和测试时间开销

缺点

• 欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”本质禁止这些分支展开，带来了欠拟合风险

后剪枝

先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点

后剪枝的优缺点

优点

• 后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能往往优于预剪枝决策树

缺点

• 训练时间开销大：后剪枝过程是在生成完全决策树之后进行的，需要自底向上对所有非叶结点逐一考察

ID3,C4.5和CART算法对比

相同点：都采用贪心方法，以自顶向下递归的分治方式构造，随着树的构建，训练集递归地被划分为子集

不同点：

• ID3算法基于信息增益为准则来选择划分属性，依赖于特征数目多的特征，没有考虑少特征和不完整数据，抗噪性差，容易产生过拟合.
• C4.5算法基于增益率准则来选择划分属性，使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选取增益率最高的，对可取值数目较少的属性有所偏好。

第五章 神经网络

神经元模型

• 输入：来自其他n个神经元传递过来的输入信号
• 处理：输入信号通过带权重的连接进行传递, 神经元接受到总输入值将与神经元的阈值进行比较
• 输出：通过激活函数的处理以得到输出

• 理想激活函数是阶跃函数, 0表示抑制神经元而1表示激活神经元
• 阶跃函数具有不连续、不光滑等不好的性质, 常用的是 Sigmoid 函数

感知机

感知机由两层神经元组成, 输入层接受外界输入信号传递给输出层, 输出层是M-P神经元（阈值逻辑单元）

感知机能够容易地实现逻辑与、或、非运算

感知机学习

给定训练数据集, 权重$wi(i=1,2,...,n)$与阈值$\eta$可以通过学习得到.

感知机学习规则

对训练样例$(x,y)$, 若当前感知机的输出为 y h a t y^{hat} yhat, 则感知机权重调整规则为：

$\eta$ 属于(0, 1)称为学习率.

若感知机对训练样例$(x,y)$预测正确, 则感知机不发生变化；否则根据错误程度进行权重的调整.

感知机学习能力

• 若两类模式线性可分, 则感知机的学习过程一定会收敛；否感知机的学习过程将会发生震荡
• 单层感知机的学习能力非常有限, 只能解决线性可分问题
• 事实上, 与、或、非问题是线性可分的, 因此感知机学习过程能够求得适当的权值向量. 而异或问题不是线性可分的, 感知机学习不能求得合适解

对于非线性可分问题, 如何求解？

• 多层感知机

多层感知机

解决异或问题的两层感知机:

输出层与输入层之间的一层神经元, 被称之为隐层或隐含层, 隐含层和输出层神经元都是具有激活函数的功能神经元

多层前馈神经网络

定义：每层神经元与下一层神经元全互联, 神经元之间不存在同层连接也不存在跨层连接

前馈：输入层接受外界输入, 隐含层与输出层神经元对信号进行加工, 最终结果由输出层神经元输出

学习：根据训练数据来调整神经元之间的“连接权”以及每个功能神经元的“阈值”

多层网络：包含隐层的网络

误差逆传播算法

误差逆传播算法（Error BackPropagation, 简称BP）是最成功的训练多层前馈神经网络的学习算法.

此处请参考：【深度学习】梯度下降和反向传播原理

标准 BP 算法

• 每次针对单个训练样例更新权值与阈值.
• 参数更新频繁, 不同样例可能抵消, 需要多次迭代.

累计 BP 算法

• 其优化的目标是最小化整个训练集上的累计误差
• 读取整个训练集一遍才对参数进行更新, 参数更新频率较低.

实际应用

但在很多任务中, 累计误差下降到一定程度后, 进一步下降会非常缓慢, 这时标准BP算法往往会获得较好的解, 尤其当训练集非常大时效果更明显.

多层前馈网络表示能力

• 只需要一个包含足够多神经元的隐层, 多层前馈神经网络就能以任意精度逼近任意复杂度的连续函数

多层前馈网络局限

• 神经网络由于强大的表示能力, 经常遭遇过拟合. 表现为：训练误差持续降低, 但测试误差却可能上升
• 如何设置隐层神经元的个数仍然是个未决问题. 实际应用中通常使用“试错法”调整

缓解过拟合的策略

• 早停：在训练过程中, 若训练误差降低, 但验证误差升高, 则停止训练
• 正则化：在误差目标函数中增加一项描述网络复杂程度的部分, 例如连接权值与阈值的平方和

全局最小与局部极小

• 显然参数空间梯度为零的点, 只要是误差函数值小于邻点的误差函数值, 就是局部极小点
• 可能存在多个局部极小值, 但却只会有一个全局极最小值

“跳出”局部最小的策略

基于梯度的搜索是使用最为广泛的参数寻优方法. 如果误差函数仅有一个局部极小, 那么此时找到的局部极小就是全局最小;

然而,如果误差函数具有多个局部极小, 则不能保证找到的解是全局最小. 在现实任务中, 通常采用以下策略“跳出”局部极小, 从而进一步达到全局最小.

• 多组不同的初始参数优化神经网络, 选取误差最小的解作为最终参数.
• 模拟退火技术 [Aarts and Korst, 1989]. 每一步都以一定的概率接受比当前解更差的结果, 从而有助于跳出局部极小.
• 随机梯度下降. 与标准梯度下降法精确计算梯度不同, 随机梯度下降法在计算梯度时加入了随机因素.
• 遗传算法 [Goldberg, 1989]. 遗传算法也常用来训练神经网络以更好地逼近全局极小.

深度学习

典型的深度学习模型就是很深层的神经网络.

模型复杂度

• 增加隐层神经元的数目 (模型宽度)
• 增加隐层数目（模型深度）
• 从增加模型复杂度的角度看, 增加隐层的数目比增加隐层神经元的数目更有效. 这是因为增加隐层数不仅增加额拥有激活函数的神经元数目, 还增加了激活函数嵌套的层数.

复杂模型难点

• 多隐层网络难以直接用经典算法（例如标准BP算法）进行训练, 因为误差在多隐层内逆传播时, 往往会”发散”而不能收敛到稳定状态.

复杂模型训练方法

• 预训练:监督逐层训练是多隐层网络训练的有效手段, 每次训练一层隐层结点, 训练时将上一层隐层结点的输出作为输入, 而本层隐结点的输出作为下一层隐结点的输入, 这称为”预训练”.
• 微调：在预训练全部完成后, 再对整个网络进行微调训练. 微调一般使用BP算法.

预训练+微调 的做法可以视为将大量参数分组, 对每组先找到局部看起来比较好的设置, 然后再基于这些局部较优的结果联合起来进行全局寻优.

复杂模型训练方法

权共享

• 一组神经元使用相同的连接权值.
• 权共享策略在卷积神经网络(CNN)[LeCun and Bengio, 1995; LeCun et al. , 1998]中发挥了重要作用.

卷积神经网络

• 结构：CNN复合多个卷积层和采样层对输入信号进行加工, 然后在连接层实现与输出目标之间的映射.

• 卷积层：每个卷积层包含多个特征映射, 每个特征映射是一个由多个神经元构成的“平面”, 通过一种卷积滤波器提取的一种特征

• 采样层：亦称“汇合层”, 其作用是基于局部相关性原理进行亚采样, 从而在减少数据量的同时保留有用信息

• 连接层：每个神经元被全连接到上一层每个神经元, 本质就是传统的神经网络, 其目的是通过连接层和输出层的连接完成识别任务

卷积神经网络激活函数

• 在CNN中通常将 sigmoid 激活函数替换为修正线性函数ReLU

卷积神经网络训练

• CNN 可以用BP进行训练, 但在训练中, 无论是卷积层还是采样层, 每一组神经元都是用相同的连接权, 从而大幅减少了需要训练的参数数目

理解深度学习：

“特征工程” VS“特征学习”或者 “表示学习”

• 特征工程由人类专家根据现实任务来设计, 特征提取与识别是单独的两个阶段；
  
• 特征学习通过深度学习技术自动产生有益于分类的特征, 是一个端到端的学习框架.
  

第六章：支持向量机

间隔与支持向量

向量方向


向量加减

点到向量距离

线性模型：在样本空间中寻找一个超平面, 将不同类别的样本分开.

• Q:将训练样本分开的超平面可能有很多, 哪一个好呢?

• A:应选择”正中间”, 容忍性好, 鲁棒性高, 泛化能力最强.

距离超平面最近的这几个训练样本点使等式成立，成为支持向量，两个异类支持向量到超平面的距离之和为:


显然为了最大化间隔，仅需最小化 ∣ ∣ w ∣ ∣ 2 ||w||^2 ∣∣w∣∣2，这就是SVM的基本型.

对偶问题

解的稀疏性

支持向量机解的稀疏性: 训练完成后, 大部分的训练样本都不需保留, 最终模型仅与支持向量有关.

求解方法 - SMO

SMO（Sequential minimal optimization）

基本思路：不断执行如下两个步骤直至收敛.


用一个变量表示另一个变量, 回代入对偶问题可得一个单变量的二次规划, 该问题具有闭式解.

偏移项b：通过支持向量来确定.

线性不可分

• Q:若不存在一个能正确划分两类样本的超平面, 怎么办?
• A:将样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分.

核支持向量机

核函数

基本想法：不显式地设计核映射, 而是设计核函数.

Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定, 则它就能作为核函数来使用.

常用核函数：

软间隔

• Q:现实中, 很难确定合适的核函数使得训练样本在特征空间中线性可分; 同时一个线性可分的结果也很难断定是否是有过拟合造成的.
• A:引入”软间隔”的概念, 允许支持向量机在一些样本上不满足约束.

0/1损失函数

基本想法：最大化间隔的同时, 让不满足约束的样本应尽可能少.

存在的问题：0/1损失函数非凸、非连续, 不易优化！

软间隔支持向量机

根据KKT条件可推得最终模型仅与支持向量有关, 也即hinge损失函数依然保持了支持向量机解的稀疏性.

支持向量回归

特点: 允许模型输出和实际输出间存在2e的偏差.

损失函数

落入中间2e间隔带的样本不计算损失, 从而使得模型获得稀疏性.

第七章：贝叶斯分类器

贝叶斯决策论

贝叶斯决策论（Bayesian decision theory）是在概率框架下实施决策的基本方法。

• 在分类问题情况下，在所有相关概率都已知的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记。

极大似然估计

估计类条件概率的常用策略：先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布参数估计。

求均值与方差

需注意的是，这种参数化的方法虽能使类条件概率估计变得相对简单，但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布。

朴素贝叶斯分类器

估计后验概率$P(c|x)$主要困难：类条件概率$P(x|c)$是所有属性上的联合概率难以从有限的训练样本估计获得。

朴素贝叶斯分类器(Naïve Bayes Classifier)采用了“属性条件独立性假设”(attribute conditional independence assumption)：每个属性独立地对分类结果发生影响。

基于属性条件独立性假设，(7.8)可重写为：

其中$d$为属性数目， x i x_i xi​为x在第i个属性上的取值。

由于对所有类别来说$P(x)$ 相同，因此基于上式的贝叶斯判定准则有:

这就是朴素贝叶斯分类起的表达式子

拉普拉斯修正

若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题.

比如“敲声=清脆”测试例，训练集中没有该样例，因此连乘式计算的概率值为0，无论其他属性上明显像好瓜，分类结果都是“好瓜=否”，这显然不合理。

为了避免其他属性携带的信息被训练集中未出现的属性值“抹去”，在估计概率值时通常要进行“拉普拉斯修正”（Laplacian correction）

令N表示训练集D中可能的类别数， N i N_i Ni​表示第$i$个属性可能的取值数，则式和分别修正为:

第八章：集成学习

个体与集成

集成学习(ensemble learning)通过构建并结合多个学习器来提升性能

考虑一个简单的例子，在二分类问题中，假定3个分类器在三个样本中的表现如下图所示，其中√ 表示分类正确，X 号表示分类错误，集成的结果通过投票产生。

集成个体应：好而不同

简单分析

考虑二分类问题，假设基分类器的错误率为：

假设集成通过简单投票法结合T个分类器，若有超过半数的基分类器正确则分类就正确

假设基分类器的错误率相互独立，则由Hoeffding不等式可得集成的错误率为：

上式显示，在一定条件下，随着集成分类器数目的增加，集成的错误率将指数级下降，最终趋向于0

• 上面的分析有一个关键假设：基学习器的误差相互独立
• 现实任务中，个体学习器是为解决同一个问题训练出来的，显然不可能互相独立
• 事实上，个体学习器的“准确性”和“多样性”本身就存在冲突
• 如何产生“好而不同”的个体学习器是集成学习研究的核心
• 集成学习大致可分为两大类
  • Boosting
    • Adaboost

Boosting

• 个体学习器存在强依赖关系，
• 串行生成
• 每次调整训练数据的样本分布

Boosting族算法最著名的代表是AdaBoost

Boosting – AdaBoost算法

AdaBoost(Adaptive Boosting, 自适应增强)调整分布的方法:

• 提高上一轮被错误分类的样本的权值，降低被正确分类的样本的权值；
• 线性加权求和。误差率小的基学习器拥有较大的权值，误差率- 大的基学习器拥有较小的权值。

AdaBoost推导

小的不会…

AdaBoost注意事项

数据分布的学习

• 重赋权法
• 重采样法

重启动，避免训练过程过早停止

AdaBoost实验

从偏差-方差的角度：降低偏差，可对泛化性能相当弱的学习器构造出很强的集成

Bagging与随机森林

• 个体学习器不存在强依赖关系
• 并行化生成
• 自助采样法

Bagging算法特点

• 时间复杂度低
  • 假定基学习器的计算复杂度为O(m)，采样与投票/平均过程的
  • 复杂度为O(s)，则bagging的复杂度大致为T(O(m)+O(s))
  • 由于O(s)很小且T是一个不大的常数
  • 因此训练一个bagging集成与直接使用基学习器的复杂度同阶
• 可使用OOB估计

从偏差-方差的角度：降低方差，在不剪枝的决策树、神经网络等易受样本影响的学习器上效果更好

随机森林

• 随机森林(Random Forest，简称RF)是bagging的一个扩展变种

• 采样的随机性

• 属性选择的随机性

什么是随机森林？

随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支——集成学习方法。

随机森林的名称中有两个关键词，一个是“随机”，一个就是“森林”。“森林”很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，其实这也是随机森林的主要思想–集成思想的体现。“随机”的包括随机选取训练样本集和随机选取分裂属性集。（具体含义在随机森林的生成部分会解释）

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高

经典的属性划分方法：

其实从直观角度来解释，每棵决策树都是一个分类器（假设现在针对的是分类问题），那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出。

随机森林的特点

随机森林的特点：

优点：

1. 两个随机性的引入，使得随机森林不容易陷入过拟合；
2. 两个随机性的引入，使得随机森林具有很好的抗噪声能力；
3. 对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化且能够有效地运行在大数据集上；
4. 能够处理具有高维特征的输入样本，而且不需要降维；
5. 在生成过程中，能够获取到内部生成误差的一种无偏估计；
6. 对于缺省值问题也能够获得很好得结果。

缺点：

1. 在某些噪音较大的分类或回归问题上会过拟合；
2. 对于有不同级别的属性的数据，级别划分较多的属性会对随机森 林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的。

随机森林的生成

• 随机森林中有许多的分类树。如果要将一个输入样本进行分类，需要将输入样本输入到每棵树中进行分类。
• 将若干个弱分类器的分类结果进行投票选择，从而组成一个强分类器，这就是随机森林bagging的思想。

每棵树的按照如下规则生成：

1. 给定一个训练样本集，数量为N，使用有放回采样到N个样本，构成一个新的训练集。注意这里是有放回的采样，所以会采样到重复的样本。

2. 从总量为M的特征向量中，随机选择m个特征（m$sqrt(M)$，然后计算m个特征的信息增益，选择最优特征（属性）。注意，这里的随机选择特征是无放回的选择。（在整个森林的生长过程中， m的值一般维持不变）

3. 有了上面随机产生的样本集，就可以使用一般决策树的构建方法，得到一棵分类（或者预测）的决策树。需要注意的是，在计算节点最优分类特征的时候，要使用b中的随机选择特征方法。

4. 通过以上三步，可以得到一棵决策树，重复这样的过程H次，就得到了H棵决策树。然后来了一个测试样本，就可以用每一棵决策树都对它分类一遍，得到了H个分类结果。这时，使用简单的投票机制，获得该测试样本的最终分类结果来判别该样本的所属类别。

一开始提到的随机森林中的“随机”就是指的a和b中的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

为什么要随机抽样训练集？

如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有集成的必要；

为什么要有放回地抽样？

如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是"有偏的"，都是"片面的"，也就是说每棵树训练出来都是有很大的差异的；

而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的。

随机森林分类效果（错误率）与两个因素有关：

1. 森林中任意两棵树的相关性：相关性越大，错误率越大；
2. 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。

袋外错误率（OOB error）

构建随机森林的关键问题就是如何选择最优的m，要解决这个问题主要依据计算袋外错误率。

随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。

在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的袋外样本数据。

通俗的来讲就是：

• 对每颗树，利用未被该树选中的训练样本点，统计该树的误分率；将所有树的误分率取平均得到随机森林的袋外错误率。

袋外错误率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。

随机森林的简单实例分析

描述：

根据已有的训练集已经生成了对应的随机森林，随机森林如何利用某一个人的 年龄（Age）、性别（Gender）、教育情况（Highest Educational Qualification）、工作领域（Industry）以及住宅地（Residence） 共5个字段来预测他的收入层次。

收入层次：

• Band 1 : Below $40,000
• Band 2: $40,000 – 150,000
• Band 3: More than $150,000

随机森林中每一棵树都可以看做是一棵CART（分类回归树），这里假设森林中有5棵CART树，总特征个数N=5，取m=1（m为建立决策树时，随机选取的特征个数，这里假设每个CART树对应一个不同的特征）。（表格中的百分数指的是在不同条件下的数据样本占对应类别的比例）

假如要预测的某个人的信息如下：

1. Age : 35 years ;
2. Gender : Male ;
3. Highest Educational Qualification : Diploma holder;
4. Industry : Manufacturing;
5. Residence : Metro.

根据这五棵CART树的分类结果，可以针对此人的信息建立收入层次的分布情况：

对所有预测树结果求平均

最后，我们得出结论，这个人的收入层次70%是一等，大约24%为二等，6%为三等，所以最终认定该人属于一等收入层次（小于$40,000）。

第九章：聚类

聚类任务

• 在“无监督学习”任务中研究最多、应用最广.
• 聚类目标：将数据集中的样本划分为若干个通常不相交的子集（“簇”，cluster）.
• 聚类既可以作为一个单独过程（用于找寻数据内在的分布结构），也可作为分类等其他学习任务的前驱过程.

性能度量

• 聚类性能度量，亦称为聚类“有效性指标”（validity index）

直观来讲：

• 我们希望“物以类聚”，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇内相似度”（intra-cluster similarity）高，且“簇间相似度”（inter-cluster similarity）低，这样的聚类效果较好.

聚类性能度量：

• 外部指标 (external index)
  将聚类结果与某个“参考模型”(reference model)进行比较。
• 内部指标 (internal index)
  直接考察聚类结果而不用任何参考模型。

将聚类结果与真实结果进行对照，统计出来SameSame、SameDifferece…的数量.

外部指标

内部指标

距离计算

属性介绍

• 连续属性 (continuous attribute)
  在定义域上有无穷多个可能的取值
• 离散属性 (categorical attribute)
  在定义域上是有限个可能的取值
• 有序属性 (ordinal attribute)
  例如定义域为{1,2,3}的离散属性，“1”与“2”比较接近、与“3”比较远，称为“有序属性”。
• 无序属性 (non-ordinal attribute)
  例如定义域为{飞机，火车，轮船}这样的离散属性，不能直接在属性值上进行计算，称为“无序属性”。

原型聚类

也称为“基于原型的聚类” (prototype-based clustering)，此类算法假设聚类结构能通过一组原型刻画。

算法过程：

通常情况下，算法先对原型进行初始化，再对原型进行迭代更新求解。

几种著名的原型聚类算法：

• k均值算法、学习向量量化算法、高斯混合聚类算法。

k均值算法

对每一个簇进行求方差的计算。

算法流程（迭代优化）：

初始化每个簇的均值向量
repeat1. （更新）簇划分；2.  计算每个簇的均值向量
until 当前均值向量均未更新

k均值算法实例

聚类结果：

层次聚类

层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集划分既可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。

总结

• 一刷西瓜书，上课没认真听过，可能听了也听不懂（共鸣），课下跟着B站视频快速简单过了一遍，目前为止仍有$80\%$空白知识。

• 总结内容来自西瓜书课件，仅作为我的考前对这本书的整体把握，并非掌握全部知识。

• 接着就要对考试有针对的复习（毕竟老师也不想你挂科.淦就完了）考试重点笔记整理后序更新。

• 从暑假刚接触机器学习/深度学习，到现在为止，感觉确实有些东西在从无到有的发生转变，可能理解了皮毛，当然许多难的数学公式，仍有待研究学习。

• 考研后，极大可能二刷西瓜书，到时候一定要把B站吴恩达视频看了，结合着南瓜书，李航统计学方法三剑客来系统学习。

• 最后对自己说句：任重道远，加油！

---

加油!

感谢!

努力!

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！