武科大领航工作室机器学习专题python机器学习爬虫

机器学习笔记

2018-07-25  本文已影响52人  danielAck

以西瓜书为主线，以其他书籍作为参考进行补充，例如《统计学习方法》，《PRML》等

第一章 绪论

1.2 基本术语

第二章 模型评估与选择

2.1 经验误差与过拟合

2.2 评估方法

因此提出不同的评估方法

测试集的划分方法

  1. 留出法

    将数据集划分为两个互斥的集合，同时保留类别比例(即进行分层抽样)

    一般采用确定分层比例后，在层的大小内进行若干次随机划分、重复进行后取平均值作为最终结果

  2. 交叉验证法

    与留出法相似，将数据集A分为 k 个互斥的集合

        for i in k:

        将 A - k_i 作为训练集
        将 k_i 作为测试集
        记录 测试误差 err_i

    return 测试误差的平均数
    • p次k折交叉验证：通常重复 p 次进行，取 p 次结果的均值
    • 目的: 为了减少样本划分不同而引入的误差

  3. 留一法

    k 折交叉验证法的特殊情况
    当 k = m , 此时称为 留一法

  4. 自助法

    在 数据集较小、很难划分 训练集/ 测试集 的时候很有效

    但是，此方法产生的数据改变了出事数据集的分布，会引入估计偏差

    具体方法：
    假设数据集 D 有 m 个样本

    1. 每次从数据集 D 中采出一个样本，放入 D‘ 中，再将样本放回 D
    2. 重复进行 m 次采样操作
    3. 用 D’ 作为训练集， D / D{`} 作为测试集

    可证明，测试集中度数据占 D 中的 1/3 ， 且均未出现过在 D‘ 中

    自助法在集成学习中的 Bagging 模型中还会用到（抽样方法）

验证集

2.3 性能度量

2.3.1 错误率与精度

分类任务中最常用的性能度量，可用于 二分类 及 多分类

2.3.2 查准率、查全率与 F1

查准率 也叫 准确率（Precision）
查全率 也叫 召回率（Recall）

Precision 和 Recall 定义为：

{P} = TP \over {TP + FP}

{R} = TP \over {TP + FN}

P-R 曲线

  1. 绘制具体步骤

    参考ROC曲线的绘制过程，将预测结果排序，依次将预测结果设置为阈值然后计算相应的 Precision 和 Recall

  2. 若分类器的 A 的 P-R 曲线完全被另一个分类器B “包住” ,则 B 的性能优于 A

  3. 平衡点（BEP）

    是当 Precision = Recall 时的取值，BEP 大的分类器更优

F1 Score

比算术平均、几何平均更加重视较小值

{F_1} = \frac {2 \times P \times R}{P + R}

Fβ Score

针对对于查准率和查全率重视程度不一样的情况
比算术平均、几何平均更加重视较小值

{F_\beta} = \frac {(1 + {\beta}^2) \times P \times R}{({\beta}^2 \times P) + R}

macro F1 Score

亦称 宏F1
直接计算，再求平均

{macro-P} = {1 \over n} \sum_{i=1}^{n}P_i

同理可得 macro-R，利用 macro-P、macro-R 和 F1 计算公式最后可得macro-F1

micro F1 Score
亦称 微F1，同理macro-F1，记为micro-F1，先对 TP、TN、FP、FN 求平均，再计利用平均值计算F1 Score

2.3.3 ROC与AUC

2.3.4 代价敏感错误率与代价曲线

敏感代价错误率

E(f;D;cost) = \frac{1}{m} (\sum_{x \in {D^+}}I(f(x_i)\not=y_i) \times cost_{01} + \sum_{x_i \in D^-}I(f(x_i)\not=y_i) \times cost_{10})

2.4 比较检验

2.5 偏差与方差

E(f;D) = bias^2(x) + var(x) + \epsilon^2

偏差与方差的经典关系图：


image
Min-Max z-score
计算量小 计算量大
易受极大/极小值影响 不易受极值影响
超出原极值范围才需要重新计算 来一个数据重新计算一次

第3章 线性模型

3.1 基本形式

f(x) = \omega^Tx + b = \omega_1x_1 + \omega_2x_2 + \cdots + \omega_dx_d + b

3.2 线性回归

回归模型的变量通常是连续值，因此当属性是离散值时，可以进行 连续化

损失函数：

MSE = \sum_{i=1}^{m}{(f(x_i) - y_i)}^2 = \sum_{i=1}^{m}{(\omega x_i + b - y_i)}^2

求解方法：

3.3 对数几率回归

也叫逻辑回归（Logistic Regression），虽然叫回归，但是其实是 分类 算法

起源

\omega x^T + b = ln \frac {y}{1-y}

3.4 线性判别分析

核心思想：

优化目标

J = \frac{w^TS_bw}{w^TS_ww}

最大化方法

求解结果

KLDA

3.5 多分类学习

多对多分类

3.6 类别不平衡问题

“再缩放” 思想

在对分类任务进行预测时，y 是代表正例的概率，通常将阈值设置为 0.5，即 y > 0.5 ,将结果判定为正例，否则判定为负例

言外之意：

若 y > 0.5， 预测为正例， 即若 \frac{y}{1-y} > 1, 预测为正例

但是，注意这样做的原因：
0.5 代表的其实是 观测几率, 即我们在数据集中能观测到正例的几率（我们 假设 两个类别的数据集是一样大的，因此观测几率是 0.5）所以当 y > 0.5 代表预测正例的概率大于观测概率，当然应该判定为正例。

而现在，不同的类别对应的数据量不同了，不再是 1 ： 1，我们的阈值就不应该设置为 0.5， 而是应该当：

若 \frac {y}{1-y} > \frac{m^+}{m^-}，预测为正例， 解出 y ，就是我们新的阈值

欠采样、过采样思想

欠采样

过采样

3.7 相关思考

第4章 决策树

4.1 决策树模型与学习

优点

概念

决策树的学习算法包括：

注意两种情况：

  1. 当属性集为空或所有样本在属性集上的取值相同，将类别标记为 D 中最多的类别，使用的是当前结点的 后验分布
  2. 当当前结点包含的样本集为空，同样将类别标记为 D 中最多的类别，但是是利用的当前结点的 先验分布

4.2 特征选择（划分选择）

基于 信息熵 进行特征选择

常用 3 种指标选择应作为划分的特征

所以通常采用一种折中的方法： 先找出高于平均水平的 信息增益， 再找出其中 信息增益率 最大的特征(属性)

4.3 决策树的生成

常用的 3 种生成算法：

ID3相当于用极大似然法进行概率模型的选择 理解

决策树模型的参数估计就是基于特征空间怎样划分使得样本出现的概率最大,而寻找怎样划分的过程即求解概率模型参数的过程

4.4 CART 的生成

CART回归树的生成

对于回归问题，CART 采用与决策树相同的思想，还是 对输入空间进行划分，每一个划分R_m对应一个固定的输出值c_i，生成的回归模型表示为：

f(x)=\sum_{m=1}^Mc_mI(x\in{R_m})

固定的输出值 c_i 为划分空间R_m中y_i的均值

CART回归树的损失函数

CART回归树采用 平方误差 \sum_{x_i\in{R_m}}(y_i-f(x_i))^2

CART回归树的划分

依次对划分空间R_m中的每一个样本进行如下的操作：

比较所有的r_{js}, 找到 最小的 r_{js}下的最优切分变量 j，最优切分点 s

再对划分好的两个子区域进行上述划分，直到满足停止条件

CART分类树的生成

CART分类树使用 基尼系数 为划分依据，剩下的生成方式与决策树的生成方式一样

算法停止的条件可以是：

CART分类树的剪枝

4.5 决策树的剪枝

剪枝策略

由 4.3 中 ID3相当于用极大似然法进行概率模型的选择 的概念， 决策树的剪枝也可以看做是正则化的极大似然估计，正则化项就是决策树的叶结点个数

预剪枝

后剪枝

这里的泛化性能评估标准可以是 精度

4.6 连续与缺失值

4.6.1 连续值的处理

假设属性 A 为连续值属性， A 属性共有 N 个不同的值

4.6.2 缺失值的处理

当计算属性 A 的信息增益时，如果发现有样本有缺失值：

Gain(D,a) = \rho \times (Ent(D^n) - \sum_{v=1}^{V}{r_v}^~Ent({D_v}^n))

注意：

4.7 多变量决策树

相当于对特征进行了一个线性的组合，之前的特征是单变量，组合之后单个结点相当于一个 线性的分类器

4.8 习题思考

1. 以“最小训练误差”作为划分选择的缺点

2. 对比使用递归、栈（非递归）、队列（非递归）三种结构生成决策树的优缺点

当数据属性相对较多，属性不同取值相对较少时，树会比较宽，此时深度优先所需内存较小，反之宽度优先较小。

第5章 神经网络

后续再写

第6章 支持向量机

支持向量机内容顺序主要根据《统计学习方法》中的章节来安排，主要内容也由《统计学习方法》展开，其中穿插入西瓜书的知识点

6.1 概念

6.2 线性可分支持向量机

支持向量机的学习是在特征空间中进行的，线性可分SVM将输入空间中的输入线性映射为特征空间中的特征向量，非线性可分SVM将输入非线性映射为特征向量

学习到的分离超平面：

w^* * x + b^* = 0

最终的分离决策函数使用符号函数

6.2.1 函数间隔和几何间隔

\hat{\gamma}_i = y_i(w*x_i+b)

其中 y_i 用来表示分类预测的正确性, w*x_i+b 用来表示分类的确信度（换言之就是点到分类超平面的距离）

定义超平面的函数间隔为数据集D中所有样本的函数间隔中的最小值，即：

\hat{\gamma} = \min_{i=1,...,N}\hat{\gamma}_i

由于成倍缩放w,b会导致函数间隔成倍缩放，所以 w 加上约束，如约束为：\Vert{w}\Vert = 1， 可以导出几何间隔

\gamma = \frac{\hat{\gamma}}{\Vert{w}\Vert}

6.2.2 间隔最大化

可以得到求解式：

\max{\frac{\hat{\gamma}}{\Vert{w}\Vert}}_{w,b}

s.t. y_i(w*x_i+b) \geq \hat{\gamma}, i = i,2,...,N

令 \hat{\gamma} = 1,得到 线性可分支持向量机的最优化问题(凸二次优化问题), 具体推导见《方法》P97：

\min_{w,b} \frac{1}{2}{\Vert{w}\Vert}^2

s.t. y_i(w*x_x+b) - 1 \geq 0, i=1,2,...,N

6.2.3 学习的对偶算法

求解 线性可分支持向量机的最优化问题 使用 拉格朗日对偶性，令原式为原始问题，通过求解对偶问题得到原始问题的最优解

推导过程见 《统计学习方法》 P103

其中几个重要的点：

image

{\alpha}^* \geq 0

b = \frac{1}{S}\sum_{s\in{S}}(\frac{1}{y_s} - \sum_{i\in{S}}\alpha_iy_ix_i^Tx_s)

6.3 线性支持向量机与软间隔最大化

6.3.1 线性支持向量机

\min_{w,b,\xi} \frac{1}{2}{\Vert{w}\Vert}^2+C\sum_{i=1}^N{\xi}_i
s.t. y_i(w*x_i+b) \geq 1 - {\xi}_i, i = 1,2,...N
{\xi}_i \geq 0, i=1,2,...N

image

6.3.2 支持向量

6.3.3 合页损失函数

image

{\sum_{i=1}^N}{[1 - y_i(w*x_i+b)]}_+ + \lambda{\Vert{w}\Vert}^2

[图片上传失败...(image-b1fd0d-1532507004505)]

6.4 支持向量回归

l_\epsilon(z) = \begin{cases} 0, & \text{if $|z| \leq \epsilon$} \\[2ex] |z| - \epsilon, & \text{otherwise} \end{cases}

f(x_i) - y_i \leq \epsilon + \xi_i, 上侧

y_i - f(x_i) \leq \epsilon + \hat{\xi_i}, 下侧

6.5 核函数

6.5.1 核技巧

非线性分类问题

求解思想

核函数定义

K(x,z) = \phi(x)*\phi(z)

其中，\phi{x} 为 映射函数

表示定理

h^*(x) = \sum_{i=1}^m\alpha_ik(x,x_i)

核函数在SVM中的应用

使用核函数的支持向量机最优化问题

6.6 习题思考

指数函数： e^x = \sum_{n=0}^\infty{\frac{x^n}{n!}}

可以得到：

k(x,y) = exp(-{\Vert{x}\Vert}^2)exp(-{\Vert{y}\Vert}^2){\sum_{n=0}^\infty}{\frac{(2x^Ty)^n}{n!}}

可以看出，高斯核其实被展开为无穷项多项式核函数的和，而这其中也包括了无限维的多项式核，因此高斯核会把原始维度映射到无穷多维

第七章 贝叶斯分类器

7.1 贝叶斯决策论

概念

二者结合形成了在样本上的 “条件风险” 函数

R(c_i|x) = \sum_{j=1}^N\lambda_{ij}P(c_j|x)

\lambda_{ij} 是将真实标记为 c_j 的标记预测为 c_i 的损失，可以为任意的损失函数

P(c_i|x) 是 可从数据中获得 样本分类为 c_i 的 后验概率

我们需要找到一个判定准则 h , 来 最小化总体风险, 即 使得预测结果类 c^* 是使得上面提到的损失最小的类 c

因此最优的判定准则为：

h(x^*) = \mathop{argmin}_{c\in{Y}}R(c|x)

现在，就我们就只需要考虑如何求得所有的 R(c|x), 当损失函数是 0-1损失 时有：

R(c|x) = 1 - P(c|x)

注意！ 上式只在 损失函数 是 0-1损失 时成立！！！

于是，我们可以得到贝叶斯最优分类器：

h^*(x) = \mathop{argmax}_{c\in{Y}}P(c|x)

后验概率的求解

现在的任务变为了求解 P(c|x), 主要有 判别式模型 和 生成式模型

P(c|x) = \frac{P(c)P(x|c)}{P(x)}

而对于所有的训练数据，P(x) 是相同的，不影响求解最优，由此，贝叶斯最优分类器的公式可以更改为：

$h^*(x) = \mathop{argmax}_{c\in{Y}}P(c)P(x|c)$$

7.2 朴素贝叶斯分类器

由于通常数据的特征/维度会有很多，同时每一个特征的取值也有很多，例如一共有K个特征，而每一个特征是一个二值特征，那么整个数据空间将会达到 2^K 的规模，因此与测试时很有可能该数据在训练样本中没有出现过，导致 P(x|c) = 0，这显然不对，没有出现过并不等价于概率为零

因此引入 朴素贝叶斯分类器

而在朴素贝叶斯方法中，学习 指的就是 P(c) 和 P(x|c) 的 估计

概念

P(c|x)=\frac{P(c)P(x|c)}{P{x}}=\frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)

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

计算

令 D_c 表示训练集 D 中第 c 类样本组成的集合

P(c) = \frac{|D_c|}{|D|}

对于离散属性,令 D_{c,x_i} 表示 D_c 上在第 i 个属性上取值为 x_i 的样本组成的集合

P(x_i|c)=\frac{|D_{c,x_i}|}{D_c}

对于连续属性，考虑概率密度函数，假设服从正态分布 N(\mu_{c,i},\sigma_{c,i}^2), 其中 \mu_{c,i}, \sigma_{c,i}^2表示第 c 类样本在第 i 个属性上取值的 均值 和 方差

p(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}exp(-\frac{(x_i - \mu_{c,i})^2}{2\sigma_{c,i}^2})

上面三个式子就是基于 极大似然估计 的结果

贝叶斯估计\平滑

贝叶斯估计就是加上 平滑 的极大似然估计

目的

为了避免某些属性值在计算时没有在训练数据中出现，导致概率为零最后导致连乘最后的结果为零，对上面离散情况的计算式子进行修正

\hat{P}(c) = \frac{|D_c| + \lambda}{|D| + \lambda{N}}

\hat{P}(x_i|c) = \frac{|D_{c,x_i}| + \lambda}{|D_c| + \lambda{N_i}}

常用 拉普拉斯修正, 即上式中 \lambda = 1

第八章 EM算法

8.1 概念

期望最⼤化算法，或者EM算法，是寻找具有 潜在变量 的概率模型的 最⼤似然 解的⼀种通⽤的⽅法（PRML）

但是当 Z 是连续变量或者离散变量与连续变量的组合时，⽅法是完全相同的，只需把求和换成适当的积分即可（PRML）

因为在求解最大化对数似然 log\sum_z{P(Y,Z|\theta)} 的过程中引入了一个 常数，而这个常数是一个已知了参数 \theta 和Y的关于隐变量 z 的概率值，因为需要提前已知参数 \theta 分布函数才是确定的，然后带入 Y 才能利用分布函数求出当前隐变量 z 的概率值

最大化的是期望，而这个期望是对数似然的期望，其中对数似然的分布函数已经是给定了的（其中分布函数是有关\theta的）

求的是 M步最大化需要用到的提前给定的 对数似然的分布函数， 利用提前给的 \theta 进行求解

8.2 算法步骤

8.3 算法是怎么来的 + 坐标上升###

EM算法是一个迭代计算的算法，思想就是每次固定一个变量

因此，EM算法可以看做利用 坐标上升 进行优化的算法

image

第九章 集成学习

Boosting方法

主要关注 降低偏差

AdaBoost

核心思想

弱分类器的线性组合

组成元素

算法步骤

另一种解释

AdaBoost 还可以看做是 前向分步加法算法 的特例，是由基本分类器组成的 加法模型， 损失函数是 指数函数

前向分步算法

提升树

以 分类树 或 回归树 为 基分类器 的提升方法

对分类问题，采用 二叉分类树，对回归问题， 采用 二叉回归树

采用 加法模型 + 前向分布算法 + 决策树为基函数 且基函数为决策树桩（最简单的决策树）

之所以采用二叉树，是因为二叉树是所谓的 决策树桩, 足够简单，同时也能避免 过拟合

提升树算法

不同问题的提升树算法区别在于： 损失函数不同

分类问题提升树

分类问题提升树与Adaboost差别不大

其中，对于二分类问题，与 AdaBoost 算法步骤相同，只不过将基分类器固定为 二叉分类树，即二分类问题的提升树算法是 AdaBoost算法的特殊情况

回归问题提升树

回归问题提升树采用 前向分步算法 + 平方损失函数，学习方法就是不断地拟合 残差

梯度提升树（Gradient Boosing Decision Tree）####

核心思想

GBDT基分类器的选择

算法步骤

大部分在提升树中的步骤不变，加入了 用损失函数的负梯度作为残差的近似值

计算负梯度的例子

对于 平方损失函数，它就是残差，对于一般损失函数，它是残差的近似值

image

logloss的推导如下：

image

不同的问题下选择的损失函数不同，后面会看到，例如多分类问题下的GBDT选择的就是logloss

GBDT的各种扩展

对于不同的问题GBDT采用不同的处理方法，而这些方法的不同之处只在于 损失函数的不同

同时，应该注意，不同的损失函数下，算法的初始化方法也不同！！！！

Adaboost 和 GBDT 的区别

而

Shrinkage

同时GDBT还使用了 shrinkage 的方法

即每一次训练出 对残差的拟合的回归树的时候，我们再乘上一个系数 \mu, 意味着每一次我们只学习残差的一小部分

在GBDT的原文中指出，每次一小步一小步的学习有足够的信心比一大步一大步的学习更容易避免过拟合

即Shrinkage仍然以残差作为学习目标，但对于残差学习出来的结果，只累加一小部分（step*残差）逐步逼近目标，step一般都比较小，如0.01~0.001（注意该step 不是 gradient的step），导致各个树的残差是渐变的而不是陡变的。直觉上这也很好理解，不像直接用残差一步修复误差，而是只修复一点点，其实就是把大步切成了很多小步。本质上，Shrinkage为每棵树设置了一个weight，累加时要乘以这个weight，但和Gradient并没有关系。这个weight就是step。就像Adaboost一样，Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。

Bagging方法

基础的 Bagging 方法

核心思想

使用 自助采样法 获得初始训练集中约 63.2% 的样本，如此重复M次采样，获得M个不同的数据集，根据这M个不同的数据集分别训练出M个不同的分类器

结合算法

由于一共有M个不同的分类器，需要将这M个分类器的结果合并为一个最终的结果

Bagging 不同于 AdaBoost，可以不加修改的应用于回归和多分类任务

Bagging 主要关注 降低方差，因此不易受到样本的扰动

随机森林

核心思想

在 Bagging方法 的基础上加上了 对特征的随机选择，每次训练时先随机选择 k 个特征作为训练的特征，推荐值： log_2d

优点

结合策略

平均法

面对个体学习器性能相差较大时，选用 加权平均法， 个体学习器性能相近时选用 简单平均法，因为加权平均法要学习的权重更多，更容易 过拟合

投票法

多样性增强

第十章 聚类

概念

聚类任务大部分是针对有未知类别(无标记)的数据（当然也可以是含有标签的数据），试图将数据划分为若干个 不相交 的子集

划分子集的过程可以看做是虚招数据内部 分布结构 的过程

聚类可以作为单独的学习任务，也可以与其他学习任务一起工作：将聚类好的子集作为数据源支撑逻辑回归预测

距离计算

在进行聚类任务的时候，经常会涉及到距离的计算，不同的算法会使用不同的距离度量方式

最常用的是 闵可夫斯基距离

dist_{mk}(x_i,x_j)=(\sum_{u=1}^n{|x_{iu}-x_{ju}|})^{\frac{1}{p}}

p=2时，就是常见的欧氏距离，p=1时，就是曼哈顿距离

对于 连续属性，有序离散属性 可以采用上面的公式计算距离，但对于 无序离散属性 采用VDM距离

VDM_P(a,b)=\sum_{i=1}^k{|\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|}^p

其中，m_{u,a} 表示属性 u 上取值为 a 的样本的个数， m_{u,a,i} 表示在第 i 个样本簇中在属性 u 上取值为 a 的样本的个数

原型聚类

算法思想

先对原型进行初始化，然后对原型进行迭代更新求解

K均值算法

需要预先指定聚类簇数 K

算法步骤

学习向量量化（LVQ）####

此时LVQ的数据是 含有标签 的数据

高斯混合聚类

具体参考 EM算法 中在高斯混合模型中的应用

密度聚类

假设样本的内部结构可以根据样本分布的 紧密程度 确定

DBSCAN

算法参数

邻域距离： \epsilon - 邻域 包含样本集中与 x_j 距离不大于 \epsilon 的样本（决定了每一步 会 划多大的圆）

邻域大小： 作为能够扩展的要求，即\epsilon-邻域内必须至少包含MinPts个样本才能成为核心对象，拥有继续扩展的权利（决定了下一步 继续扩展的要求）

层次聚类

AGNES

采用 自底向上 的思想，先将每一个样本看做是一个簇，然后 合并 距离最近的两个簇，直到达到预设的聚类个数

距离的计算有以下三种：

上一篇下一篇

猜你喜欢

热点阅读