机器学习笔记

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

第一章 绪论

1.2 基本术语

• 所有的可能的模型组合成为一个假设空间 H

• 预测分为两类任务：

  • 分类任务： 预测的结果是离散值
    • 二分类任务，其中标签为(0/1 或者 +1/-1 代表 正例/负例)
    • 多分类任务，类别数目 k > 2
  • 回归任务： 预测的结果是连续值

• 同时另一种任务是 聚类：事先不知道数据的规律，同时没有标签，属于无监督学习

• 建立模型/学习 的目的

  • 找到一个从输入空间 X -> 输出 Y的函数映射
  • 使得学习到的模型能够很好的拟合“新数据”，即具有很好的泛化能力

• 通常假设样本数据服从独立同分布（i.i.d），而服从的分布是未知的，我们需要做的就是找出这个分布规律

• 归纳偏好 可以理解为对不同特征的重视程度

• 任何一个有效的机器学习算法必有相应的归纳偏好，因为能够拟合有限数据的曲线并不唯一，因此需要设定归纳偏好，使得泛化能力得到保证

• 通常

• 奥卡姆剃刀 原则作为一般性的归纳偏好原则，但是很遗憾原则中 “简单” 的含义针对不同的模型并不唯一，需要借助其他机制才能完成判断

• NFL (No Free Lunch Theorem) 指出，必须结合具体的学习问题去讨论算法的优劣性

• 需要注意学习算法自身的偏好与问题是否匹配，不同的数据集有不同的“特点”，需要不同的“偏好”去拟合具体的数据集

第二章 模型评估与选择

2.1 经验误差与过拟合

• 误差分为两类：

  • 经验误差： 数据集上的误差
  • 泛化误差： 新样本上的误差

• 过拟合的理解：

  • 学习到了数据集中不够 general 的特性
  • 把训练集自身的某些特性当做整体的特性
  • 过拟合是无法避免的

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 模型中还会用到（抽样方法）

验证集

• 我们将数据集划分为训练集和验证集，在验证集上进行模型选择和调参

  注意！！！
  在模型选择调节完毕之后，还应将整个数据集 D 再完整训练一遍！

2.3 性能度量

• 不同的性能度量导致不同的评判结果
• 不能仅仅依赖评判结果，不同的任务需求和数据需要不同的模型和性能度量

2.3.1 错误率与精度

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

2.3.2 查准率、查全率与 F1

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

Precision 和 Recall 定义为：

$${P} = TP \over {TP + FP}$$ $${R} = TP \over {TP + FN}$$

• Precision 很高往往导致 Recall 较低，可以理解为谨小慎微，需要很大的确信度才会做决定
• Recall 很高往往导致 Precision 较低，可以理解为宁可错杀一万，也不会放过一个

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

• ROC - 受试者工作特征
• 横轴： TPR ； 纵轴： FPR

---

• AUC - 曲线下面积
• 面积的大小代表预测的准确性
• 绘制步骤
  • 对每个测试样例进行预测，得到预测值
  • 对预测值进行排序
  • 按照排序好的数据进行遍历，依次假设当前样例为正例
  • 若样例为真正例，则纵坐标加$1 \over m^+$，否则横坐标加$1 \over m^+$
  • AUC中坐标 $x$ 代表 该点之前的反例所占比，因为每遇到一个反例横坐标扩大一个百分点（$1 \over m^-$），同理，$y$ 代表 该点之前的正例所占比
  • 正常的AUC的范围是 [0.5, 1]，如果AUC的值小于0.5就应该把预测的结果尝试反过来…

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})$$

• 为了权衡不同类型的错误造成的代价
• 使用 代价矩阵($cost_{01}，cost_{10}...$)刻画不同的代价
• 使用 比值 刻画代价之间的重要程度

2.4 比较检验

• 使用假设检验的方法，进行误差的假设检验
• 后期进行二项检验、t检验的具体笔记

2.5 偏差与方差

• 针对回归问题，期望泛化误差可以分解为 偏差、方差、噪声之和
• 分解结果：

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

• 具体分解过程见书 P45页
• 偏差与方差的关系
  • 偏差与方差是 准 与 确 的关系
  • 偏差 ：刻画预测结果的 确 的程度，即算法本身的拟合能力
  • 方差 ：刻画预测结果的 准 的程度，也提现算法抗数据扰动的能力
  • 噪声 ： 刻画算法达到期望泛化误差的下界，即学习问题本身的难度
  • 学习初期， 偏差 主导泛化错误率，体现为 欠拟合
  • 学习后期，欠拟合问题逐渐解决， 方差 主导泛化错误率，体现为 过拟合 ，在学习器学习过程中，会渐渐学习到数据中的 干扰数据，从而导致学习器的抗干扰能力下降，也即方差增加

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

• Min-Max规范化和z-score规范化的区别

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

第3章 线性模型

3.1 基本形式

• 试图用 属性 的 线性组合 进行预测
• 基本形式：

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

• $\omega$ 代表了各属性的 重要性， 因此线性模型具有很好的 可解释性

3.2 线性回归

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

• 当属性件间在 “序” 的关系，通过对离散值进行排序，然后转换为相应大小的连续值
• 当属性间不存在 “序” 的关系，可以通过使用 OneHot 编码方法进行离散值的转换
• 无序属性进行连续化会不恰当的引入 “序” 的关系

损失函数：

• 使用 均方误差(MSE) 进行性能度量

$$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），虽然叫回归，但是其实是 分类 算法

起源

• 希望使用 线性模型 进行 分类预测任务
• 因此输出结果需要是 离散的 类别标签，二分类为例： y = {0,1}
• 但是线性模型的预测结果是连续值，因此我们需要找到一个函数将连续的结果值映射为离散的类别标签
• 因此，单位阶跃函数 是理想的映射函数，但是单位阶跃函数并不单调可微，这样就引入了 对数几率函数 作为替代函数
• 预测的结果其实是 对率几率，定义如下：

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

• 而 y 才是概率
• 去除 ln 有 几率 的定义，反映 x 作为正例的相对可能性
• 直接对 分类可能性 建模，无需实现假设数据分布，避免假设分布不准确引入的问题

3.4 线性判别分析

核心思想：

• 异类点的投影点尽可能的远离，同类点之间的协方差尽可能的小(即同类点之间尽可能的靠近)

优化目标

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

• 二维情况详细推导可以参考 https://www.cnblogs.com/engineerLF/p/5393119.html
• 其中可以用“广义瑞利商”的性质得出最优$w$ ,详细性质推导见 https://www.cnblogs.com/pinard/p/6244265.html

最大化方法

• 添加负号，变为最小化问题
• 使用拉格朗日乘子法，

求解结果

• 在一般的实践中，$S_w^{-1}$ 使用SVD进行奇异值分解，通过 $S^{-1}_w = V{\Sigma}^{-1}U^T$ 得到 ${S_w}^{-1}$

KLDA

• 在LDA中引入核函数，应对非线性可分问题，具体推导见西瓜书P137

3.5 多分类学习

• 三种拆分策略：

  • 一对一（OvO）
  • 一对其余（OvR）
  • 多对多（MvM）

• 一对一 将类别两两配对生成 $\frac {N(N-2)}{2}$ 个分类器

• 一对其余 每次将一个类别视为正例，其余视为反例，因此一共会生成 $N$ 个分类器
• 但是，一对一的 训练开销 通常小于 一对其余，因为一对一只用到了两个类的训练数据

多对多分类

• 常用纠错输出码（ECOC）
• 常见编码矩阵：二元码，三元码（加上停用类，不带入计算）
• 将类别进行随机拆分，拆分为两类：正例和反例，形成很多个二分类器
• 任意两个分类器越 ”不相同“，训练结果越好，思想类似于 Bagging，训练多个高多样性的分类器
• 最后这些分类器对同一个样本预测，将预测结果分别计算编码距离（海明距离 / 欧式距离），将编码距离最小的类作为最终结果
• 同一个分类任务， ECOC编码越长，分类器之间的相似性就会越小，因此容错能力越好
• 同等长度的编码， 任意两个类别的编码距离越大，容错能力越好

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 ，就是我们新的阈值

欠采样、过采样思想

欠采样

• 减少数据集的数目，使得所有类别的数据相同
• 代表算法： EasyEnsemble，即分割负例为不同的数据集，以供多个学习器使用，利用了集成的思想

过采样

• 增加数据集的数目，使得所有类别的数据相同
• 需要注意增加数据集的方法，单纯的 重复采样 会导致严重的 过拟合
• 代表算法： SMOTE

3.7 相关思考

• 线性回归推导中的最小二乘和极大似然的关系

  • 是因为极大似然中假设 误差服从正态分布 所以才会有推导结果与最小二乘是一样的，正态分布中刚好有二次项

  • 另一种说法是最小二乘选择使用平方的原因是推导极大似然的推导结果就是最小二乘，所以说最小二乘是极大似然估计的结果

第4章 决策树

4.1 决策树模型与学习

优点

• 模型具有可读性，分类速度快

概念

• 损失函数使用 正则化的极大似然函数
• 学习的策略是 最小化损失函数
• 使用启发式方法求解决策树，求解的结果是次优的
• 结点有两种类型：内部结点(非叶子结点）表示一个特征或属性， 叶子结点代表一个类
• 还表示给定特征条件下的概率分布

决策树的学习算法包括：

• 特征选择（划分选择）
• 决策树的生成，只考虑局部最优
• 决策树的剪枝，考虑全局最优

注意两种情况：

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

4.2 特征选择（划分选择）

基于 信息熵 进行特征选择

• 表示随机变量不确定性的度量

• 同时也可以从另一个角度理解： 表示了解一件事情所需要花费的信息代价（数学之美）

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

• 信息增益
  • 对 可取数目较多 的特征(属性)有所偏好
• 增益率
  • 对 可取数目较少 的特征(属性)有所偏好

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

• 基尼系数

4.3 决策树的生成

常用的 3 种生成算法：

• ID3， 使用 信息增益 进行特征选择
• C4.5， 使用 增益率 进行特征选择
• CART， 使用 基尼系数 进行特征选择

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

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

4.4 CART 的生成

CART回归树的生成

回归树 可以被看作是一个 函数, 将输入的特征最终映射为一个 分数(实值)

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

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

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

CART回归树的损失函数

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

CART回归树的划分

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

• 依次将当前样本的每一个 特征/属性 值，作为一个切分点$s$，而当前变量就是切分变量$j$
• 使用当前切分变量的切分点将当前划分空间$R_m$划分为两个子区域 $R_1=\lbrace{x}|\lbrace{x^{(j)}} < s\rbrace\rbrace$, $R_2=\lbrace{x}|\lbrace{x^{(j)}} > s\rbrace\rbrace$
• 然后计算 $R_1$ 和 $R_2$ 的固定输出值 $c_{1i}$, $c_{2i}$
• 计算$c_{1i}$, $c_{2i}$ 下的平方误差和 $r_{js} = r_{js1} + r_{js2}$

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

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

CART分类树的生成

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

算法停止的条件可以是：

• 结点中的样本个数少于阈值
• 结点上的基尼指数小于阈值(基本属于同一类)
• 或者没有更多特征

CART分类树的剪枝

4.5 决策树的剪枝

剪枝策略

• 预剪枝
• 后剪枝

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

预剪枝

• 在划分结点前估计，若划分结点后不能提升泛化性能，则停止划分
• 使用贪心的策略，有可能陷入局部最优
• 带来欠拟合的风险

后剪枝

• 等决策树完全生成好之后，再从下而上的进行剪枝
• 剪枝策略：
  • 将结点的子树替换为叶节点，观察泛化性能是否提升，如果提升则将子树替换为叶节点，否则不进行剪枝
  • 根据奥卡姆剃刀原则，如果泛化性能不变依然应该选择剪枝，形成更简单的决策树
• 可以较好的防止过拟合，但是时间开销很大

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

4.6 连续与缺失值

4.6.1 连续值的处理

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

• 将这 N 个不同的值进行排序
• 依次选取划分点 t，大于划分点 t 的记为 $D_t^+$, 同理，小于 t 的记为 $D_t^-$
• 这样，可以将每一个取值都作为一次划分点，然后计算 信息增益, 最后可以得到属性 A 的信息增益
• 后续就跟离散值的做法一样了

4.6.2 缺失值的处理

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

• 初始将所有样本赋予 1 的 权值
• 计算 属性a 上的三个概率（主要都是针对不含有缺失值的样本）
  • 无缺失样本所占总体数据比例
  • 无缺失样本中第$k$类所占比例
  • 属性 a 上无缺失样本中取值为$a^v$所占比例
• 利用这三个概率计算每一个属性 a 的信息增益

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

• 更新含有缺失值的样本的权值，并划入每一个结点
  • 将划入的数据权值更新为 ${r^n}_v * w_x$, 相当于将数据依概率进行划分
• 后续与普通的操作相同

注意：

• 更新权值相当于以不同的概率将样本划分进每一个结点
• 因为含有缺失值的样本可能接下来还要参加其他属性的信息增益的计算，而计算中会涉及权值，所以 权值 相当于对带有缺失值的样本的 影响力

4.7 多变量决策树

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

4.8 习题思考

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

• 由于训练集总会与模型之间存在误差，如果选择最小误差，则会很大程度的拟合为符合训练集的决策树，从而导致严重的过拟合

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

• 缺点：

  • 使用递归的方法会保存大量的参数信息，而在参数中有大量的数据信息，从而会导致内存溢出
  • 如果使用栈的结构，不能完成以MaxNode的约束，会生成畸形的决策树（只有一边），只能完成以MaxDepth的约束
  • 如果使用队列的结构，只能完成BFS即以MaxNode的约束

• 优点：

  • 使用递归的方法代码更加简洁，易读
  • 使用栈的结构有利于后剪枝
  • 使用队列的结构，由于入队之前必须进行划分，如果是用预剪枝则会很方便，因为可以比较划分与否的验证集精度，而栈则做不到

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

第5章 神经网络

后续再写

第6章 支持向量机

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

6.1 概念

• SVM是一种 二分类 模型
• 学习算法是 求解凸二次规划的最优化算法
• 模型分类三类
  • 线性可分支持向量机：当数据集线性可分（硬间隔支持向量机）
  • 线性支持向量机：当数据集近似线性可分（软间隔支持向量机）
  • 非线性支持向量机：使用核技巧
• 核函数
  • 表示将输入从输入空间映射到特征空间得到的特征向量之间的内积

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

其中几个重要的点：

• 支持向量是 ${\alpha_i}^* > 0$ 的点
• 对偶学习问题的KKT条件

• KKT的对偶互补条件

$${\alpha}^* \geq 0$$

• 实际应用中b的求解
  • 理论上使用任意一个数据$x_j$就能算出 $b$
  • 在实际应用中，采用更加鲁棒的做法:使用所有 支持向量 求解的平均值,$S$代表支持向量的集合

$$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 线性支持向量机

• 引入

  • 大部分数据并不满足完全线性可分，存在一部分数据非线性可分，因此对每一个数据引入一个松弛变量 $\xi \geq 0$,使得那些不满足线性可分的数据点加上 $\xi$ 变得线性可分

• 线性支持向量机的原始问题：

$$\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$$

• 原始问题的对偶问题

  • 同线性可分的推导相同，先求$\min_{w,b,{\xi}}$(即分别对$w,b,\xi$求导，并令导数等于零，求出相应的表达式，代回原式，得到$\min_{w,b,{\xi}}L(w,b,\xi,\alpha,\mu)$)
  • 再求出$\max_{\alpha}\min_{w,b,{\xi}}L(w,b,\xi,\alpha,\mu)$

• 原始问题满足的KKT条件

6.3.2 支持向量

• 若${\alpha_i}^* < C$, 则$\xi_i = 0$,支持向量恰好落在间隔边界上
• 若${\alpha_i}^* = C$，$0<\xi_i<1$,则此时分类正确，$x_i$ 在分类超平面与间隔边界之间
• 若${\alpha_i}^* = C$，$\xi_i = 1$，则 $x_i$ 在分离超平面上
• 若${\alpha_i}^* = C$，$\xi_i > 1$, 则 $x_i$ 位于分类错误的一侧

6.3.3 合页损失函数

• 定义

• 原始问题也等价于含有合页函数作为损失函数的目标函数
• 也即将 $\xi_i$ 换成了${[1-y_i(w*x_i+b)]}_+$

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

• 相比感知机的损失函数和0-1损失函数，合页损失函数有更高的要求

6.4 支持向量回归

• 思想
  • 不同于传统回归模型，SVR对偏差有一定的容忍，形成一个以容忍度/宽度$2\epsilon$为间隔带，误差不超过$\epsilon$的样本都认为预测正确
  • SVR也可以引入核函数
  • SVR引入了 $\epsilon-不敏感损失$

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

• 原始问题
  • SVR考虑预测模型两侧的情况，所以约束条件分为两个

$$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中的应用

• 将SVM对偶问题中的内积 $x_i*x_j$ 变换为特征空间中的内积 $\phi(x_i)*\phi(x_j)$
• 当映射函数是 非线性函数 时，学习到的核函数SVM是 非线性分类模型

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

6.6 习题思考

• 为什么高斯核会把原始维度映射到无穷多维？
  • 定义多项式核函数 $k(x,y) = {(x^Ty)}^p$
  • 然后考虑高斯核函数$k(x,y) = exp(-{\Vert{x-y}\Vert}^2)$
  • 展开后得到： $k(x,y) = exp(-{\Vert{x}\Vert}^2)exp(-{\Vert{y}\Vert}^2)exp(2xy)$
  • 由泰勒展开公式：

$$指数函数： 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!}}$$

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

第七章 贝叶斯分类器

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)$, 主要有 判别式模型 和 生成式模型

• 生成式模型
  • 通过直接建立模型来预测 c
  • 代表：决策树、BP神经网络、支持向量机

• 判别式模型
  • 通过对概率分布 $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）

• 为什么EM算法需要先给定一个先验的参数 $\theta$？

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

• 每次 M步 最大化的是什么？

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

• 每次 E步 求的是什么？

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

8.2 算法步骤

• 输入模型参数的初值 $\theta^{(0)}$
• E步： 利用已知的参数$\theta^i$ 计算函数 $Q(\theta,\theta^{(i)}) = \sum_zlogP(Z|Y,\theta^{(i)})P(Y,Z|\theta)$
  • 其中函数 $Q(\theta,\theta^{(i)})$ 就代表对数似然的期望
  • 需要计算的就是 $P(Z|Y,\theta^{(i)})$
  • 其中含有 M步需要最大化的参数$\theta$
• M步： 最大化E步求出的 $Q(\theta,\theta^{(i)})$ 中的参数 $\theta$
• 将 M步 求出的最大的 $\theta$ 作为E步中已知的参数$\theta^i$，迭代进行计算，直到参数 $\theta$ 收敛（变化很小）

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

• 思想

  • 最大化观测数据的对数似然函数 $logP(Y|\theta)$
  • 找到一个对数似然函数的下界函数 $Q(\theta)$
  • 找到下界函数 $Q(Z)$ 的最大值 $\theta^*$
  • 下界函数利用 Jensen不等式 得到（提示：log函数是一个凹函数）求得，其中需要引入一个使用 $\theta^{(i)}$ 的先验分布 $Q(z^{(i)})$

• 如何求得需要引入的先验分布 $Q(z^{(i)})$？

  • 从 Jensen不等式入手，由于Jensen 表示： $E[f(x)] \leq f[E(x)]$, 当$x$为常数c的时候，左右式相等，此时取到等号
  • 此时求得 $Q(z^{(i)}) = P(z^{(i)}|Y,\theta)$

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

• 首先固定住 $\theta$, 调整先验分布函数$Q(z^i)$取到等号
• 然后固定住先验分布函数$Q(z^{(i)})$，调整$\theta$，使先验分布函数$Q(z^{(i)})$取得最大值，得到$\theta^{new}$
• 再固定住$\theta$，此时使用刚计算出的$\theta^{new}$ ，调整先验分布函数$Q(z^i)$取到等号….
• 直到对数似然函数收敛到最大值$\theta^*$

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

第九章 集成学习

优点：

• 广泛使用，例如 GBM（Gradient Boosting Machine），随机森林(Random Forest)
• 不关心输入的缩放，所以不用考虑对输入的归一化
• 可以关注到特征的 非线性(高阶)关系
• 可扩展

Boosting方法

主要关注 降低偏差，属于串行算法

AdaBoost

核心思想

弱分类器的线性组合

组成元素

• 弱分类器 $G_m(x)$
• 弱分类器系数 $\alpha_m$
• 第 m 轮中，第 i 个样本的系数 $w_{m,i}$
• 弱分类器在 加权数据集 上的分类误差率 $e_m$，是被$G_m(x)$误分类的样本的权值之和

算法步骤

• 将样本的权值先给定为均值，在此基础上学习出基本分类器 $G_1(x)$
• 反复学习基分类器，执行以下步骤：
  • 使用当前权值分布的数据集学习得到基本分类器 $G_m(x)$
  • 计算基本分类器在当前 加权数据集 上的分类误差率 $e_m$
  • 根据 $\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}$ 调整基本分类器 $G_m(x)$ 的系数 $\alpha_m$，分类误差率 越小 的基本分类器，其系数 越大，即在最终分类器中的作用越大
  • 根据基本分类器 $G_m(x)$ 的系数 $\alpha_m$，更新下一个基本分类器 $G_{m+1}(x)$ 训练的数据集的权值分布 $w_{m+1,i}$

另一种解释

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

前向分步算法

• 学习的是 加法模型
• 从前向后，每次只学习一个基分类器及其系数

提升树

提升树是迭代 多棵回归树 来共同决策,注意是有多颗回归树，只不过是串行生成的而已，而随机森林是可以并行生成的

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

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

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

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

提升树算法

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

• 分类问题： 指数损失函数
• 回归问题：平方误差损失函数
• 一般决策问题： 一般损失函数

分类问题提升树

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

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

回归问题提升树

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

• 计算当前残差 $r_{mi} = y_i - f_{m-1}(x_i)$
• 训练一个拟合当前残差 $r_{mi}$ 的回归树 $f_{m}$
• 将学习到的回归树与之前的回归树进行加和，求得最终的回归提升树

梯度提升树（Gradient Boosing Decision Tree）

核心思想

• 在 提升树 的基础上加入了 梯度 的概念,利用 负梯度在当前模型的值 作为回归问题提升树中的残差的 近似值

GBDT基分类器的选择

• 服从 低方差和高偏差，算法框架服从 boosting框架 即可

• 由于是 拟合残差(连续值)，所以GBDT中的基分类器选择的基本都是 CART回归树

算法步骤

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

• 使用 原始数据集作为训练集, 利用 CART回归树 训练出第一个回归树 $f_0(x)$
• 计算损失函数的 负梯度 当回归树 $f_{m-1}(x)$ 下的值 $r_{mi}$, 后面有举例怎么计算
• 对 $r_{mi}$ 拟合一颗 CART回归树 $f_r(x)$, 拟合的过程参考:CART回归树的生成
• 更新 $f_m(x)$ 为 $f_{m-1}(x)$ 与 $f_r(x)$ 的和
• 重复执行以上步骤，直到达到停止条件

计算负梯度的例子

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

logloss的推导如下：

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

GBDT的各种扩展

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

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

• GBDT处理回归问题

  • 采用 平方损失函数, $L(y_i,F(x_i))=\frac{1}{2} * (y_i-F(x_i))^2$
  • 算法步骤：
  • 初始化：使用样本的均值
  • 
  • 参考：https://blog.csdn.net/qq_22238533/article/details/79185969

• GBDT处理二分类问题

  • 采用 logloss损失函数，推导上图有
  • 算法步骤：
  • 初始化： $F_0(x) = 0.5 log(\frac{\sum_{i=1}^Ny_i}{\sum_{i=1}^N(1-y_i)})$, log中的式子表示 *正样本数目/负样本数目
  • 
  • 参考：https://blog.csdn.net/qq_22238533/article/details/79192579
  • 相比回归任务，由于二分类任务最终预测的是类别，而模型输出的是连续值，因此我们还需要将预测的分值$F_m(x)$转换为类别
  • 对于采用 logloss损失函数的情况：$P_i^+ = \frac{1}{1+e^{-F_m(x_i)}}$, 代表正样本的概率
  • 对于采用 指数损失函数 的情况： $P_i^+ = \frac{1}{1+e^{-2F_m(x_i)}}$, 代表正样本的概率

• GBDT处理多分类问题

  • 采用一对多的策略，即每个类别分开训练树
  • 必须K个类别都训练好了第一棵树，然后再继续训练第二棵树
  • 算法步骤：
  • 初始化：原文中初始化为0，sklearn中实现的是初始化为数据先验概率（就是各类别的占比）
  • 
  • 参考：https://blog.csdn.net/qq_22238533/article/details/79199605

关于GDBT较为详细的解释：
https://blog.csdn.net/molu_chase/article/details/78111148

Adaboost 和 GBDT 的区别

• AdaBoost 是通过提升错分数据点的权重来定位模型的不足，
• AdaBoost 是以指数损失函数为损失函数

而

• Gradient Boosting 是通过算梯度（gradient）来定位模型的不足

Shrinkage

同时GDBT还使用了 shrinkage 的方法

即每一次训练出 对残差的拟合的回归树的时候，我们再乘上一个系数 $\mu$, 意味着每一次我们只学习残差的一小部分，类似于随机优化中的学习率

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

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

Xgboost

主要参考陈天奇博士的slice（https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf）以及源论文

1. 先从三个角度去回顾监督学习的基本点

模型（Model）

• 可以以线性模型为基础（包括 线性/逻辑 回归）
• 预测的结果 $y_i$ 根据任务的不同会有不同的含义
  • 线性回归问题： $y_i$ 代表预测的分数
  • 逻辑回归问题： 使用 $1 / (1 + exp(-\hat{y}_i))$ 表示样例为正例的 概率
  • 其他任务，例如排序问题，$y_i$ 代表排序的分数

参数（Parameter）

由于模型是 线性模型, 所以参数就是模型的系数 $\Theta = \lbrace{w_j|j=1, … ,d}\rbrace$

目标函数（Object Function）

$$Obj(\Theta)=L(\Theta) + \omega(\Theta)$$

其中，$L(\Theta)$ 是训练误差，$\omega(\Theta)$ 是正则化项，意味着模型的复杂程度

• 损失函数的选择：

  • 平方损失： $l(y_i,\hat{y}_i)=(y_i-\hat{y}_i)^2$
  • Logistic损失： $y_iln(1+e^{-\hat{y}_i})+(1-y_i)ln(1+e^{\hat{y}_i})$

• 正则化的选择

  • L2 正则(norm)：$\lambda{\Vert{w}\Vert}^2$
  • L1 正则(norm)：$\lambda{\Vert{w}\Vert}_1$

• 岭回归（Ridge Regression）

  • 使用 线性模型 + 平方损失 + L1正则
  • $\sum_{i=1}^n{(y_i-w^Tx_i)^2 + \lambda{\Vert{w}\Vert}^2}$

• Lasso

  • 使用 线性模型 + 平方损失 + L2正则

• Logistic Regression

  • 使用 线性模型 + Logistic损失 + L2正则

目标函数使用 $L(\Theta)$ 和 $\omega(\Theta)$ 两部分的原因

• $L(\Theta)$ 使得模型至少能够很好的拟合训练数据，从而尽可能的接近基础分布(underlying distribution)
• $\omega(\Theta)$ 使得模型变得更简单，使得预测拥有 更小的方差，从而使得预测更加稳定

2. 所要学习的内容

集成的回归树

• 回归树选用CART回归树作为基分类器, 也支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）
  • 先对每一个特征寻找切分点计算信息增益，然后确定最优切分点，再来计算切分后的结果值 $f_t(x_i)=w^*=-\frac{\sum_{i \in {I_j}}g_i}{\sum_{i\in{I_j}}h_i+\lambda}$
  • 每一个叶节点包含一个分数

回归树不仅仅能做回归！！

回归树的集成方法根据你如何看待预测结果同时可以用来做分类、回归、排名(Ranking) 等等

例如，我们也可以用集成回归树来做分类，这时预测的结果\分数(Score)可以看做是样本为正例的 概率

3. 学习的方法

使用 提升(Boosting) 的思想，所以算法大部分与提升树算法相近

• 加入了对树模型的控制，即对模型的复杂程度加上了 正则化，其中正则化项的内容是 树的个数T 和 叶节点的分数(即权值)
• 在对残差的拟合中使用了 二阶泰勒展开,使得拟合精度更高
• 对展开后的目标函数求导可以得到最终的最优目标函数值

$$Obj=-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{h_j+\lambda}+\gamma{T}$$

$Obj$ 的值代表了树的结构的好坏，值越小代表结构越好，因为目标函数代表整体 损失 的大小

根据最优目标函数值(整体损失值),可以定义新的 增益公式 在划分过程中使用

同时，XGBoost算法还参考了GBDT中的 Shrinkage 方法 和 随机森林中使用到的 列采样(Column Subsampling) 方法

Shrinkage 能够减小每一棵树对最终结果的大幅影响，留出足够的学习空间给之后的树来学习，已经能够证明Shrinkage确实能够 减小过拟合的风险，但是还没有清晰的证明

列采样 在源论文中提到经过使用发现比传统的 行采样(row subsamping) 能够 更好的避免过拟合，同时还能 加快分布式的并行计算，因为要计算的特征变少了

4. 划分结点的步骤

在源论文中，提出了两种算法，一种是 完全贪心算法(exact greedy algorithm)，另一种是适用于不能完全加载进内存的大数据集的情况的 近似算法(Approximate Algorithm)

完全贪心算法

• 对于每一个特征，将样本按照特征值排好序(之所以要排序的原因是之后确定最优分裂点的算法 Weighted Quantile Sketch 中需要用到排好序的数据)
• 线性扫描每一个样本，根据增益公式计算得到最优的切分点
• 用切分点将样本进行切分

近似算法

首先，算法会根据一种规则(后续会说)生成分裂的候选结点，有两种生成方式 local 和 global

global 方式

• 在构建树的初期就确定好候选划分结点，在之后的每一层划分过程中都 不再改变 候选划分结点
• 需要更多的候选划分结点(更大的划分密度)

local 方式

• 每次 划分后都会重新生成候选划分结点
• 适合较深的树结构

从实验结果可以看出，较小的密度(eps=0.3意味着只会生成 1/eps=3个切分点)，使得global的误差较大。 eps越小，切分密度越大

5. 对于离散变量的处理

事实上不需要对离散变量和连续变量分开处理，将离散变量进行 One Hot 编码之后可以当做连续值处理，但是这样会使得数据变得 稀疏(Sparse) ,而 Xgboost 能够很好的处理稀疏的数据

6. 如何处理稀疏的数据

当数据中出现：

• 缺失数据
• 大量的 0 值
• 使用类似于One Hot 编码之后(出现大量的 0 值)

数据会变得非常稀疏，算法会决定将缺失/0值通过计算选择左子树或者右子树作为默认方向划入子树中，算法思路如下：

• 如果当前特征中出现了 缺失\0值，先计算出 $G$ 和 $H$
• 用 不含有缺失\0值 的数据计算$G_L$ 和 $H_L$，因此 $G_R=G-G_L$, $H_R=H-H_L$此时默认将含有缺失值的数据划分入右子树，计算此时的信息增益
• 同理，用 不含有缺失\0值 的数据计算$G_R$ 和 $H_R$,此时默认将含有缺失值的数据划入左子树
• 比较分别划入左子树和右子树的信息增益，选择最优划分

7. 并行计算

xgBoosting工具支持并行,但并不是tree粒度上的，而是特征粒度，决策树最耗时的步骤是对特征的值排序，xgBoosting在迭代之前，先进行预排序，存为block结构，每次迭代，重复使用该结构，降低了模型的计算；block结构也为模型提供了并行可能，在进行结点的分裂时，计算每个切分点的增益，选增益最大的切分点进行下一步分裂，那么各个特征可以开多线程进行，最终选择需要划分的特征

Bagging方法

基础的 Bagging 方法

核心思想

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

结合算法

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

• 回归问题：采用简单平均法
• 分类问题：采用简单投票法

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

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

随机森林（Random Forest）

核心思想

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

优点

• 因为随机森林加入了对特征的随机选择（随机扰动） + 样本的随机扰动（自助采样法），所以 随机森林的 泛化性能 比Bagging更好
• 随机森林比Bagging训练效率更加高，因为每次训练的特征更少，需要判断最佳分类特征的时间更短

结合策略

平均法

• 简单平均法
• 加权平均法

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

投票法

• 绝对多数投票法：若某标记得票数 超过半数 则预测为该标记
• 相对多数投票法：选取得到投票数最多的类别，若多个投票数相同，随机选择一个
• 加权投票法： 与加权平均法相似，权重是分类器的权重，同时要求权重之和为1

多样性增强

• 数据样本扰动
• 输入属性扰动
• 输入表示扰动
• 算法参数扰动

第十章 聚类

概念

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

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

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

距离计算

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

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

$$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

算法步骤

• 需要预先从数据集中选择 K 个样本作为初始均值向量进行初始化
• 对每一个样本对每一个初始均值向量计算距离，将样本划入 最近 的均值向量代表的簇中
• 划分完毕后重新计算均值向量，重复以上步骤，直到数据所属类别不再变化

学习向量量化（LVQ）

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

高斯混合聚类

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

密度聚类

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

DBSCAN

算法参数

• 邻域距离： $\epsilon$
• 邻域大小： $MinPts$

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

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

层次聚类

AGNES

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

距离的计算有以下三种：

• 最小距离：两个簇中的样本间的最近的距离
• 最大距离：两个簇中的样本间的最远的距离
• 平均距离：两个样本的距离的均值

零碎知识点

1. 为什么L1稀疏，L2平滑

参考 https://vimsky.com/article/969.html

https://www.jianshu.com/p/c9bb6f89cfcc (引入拉普拉斯分布和高斯分布)

有时间回来总结

1. 为什么基于 tree-ensemble 的机器学习方法，在实际的 kaggle 比赛中效果非常好？

作者：马超
链接：https://www.zhihu.com/question/51818176/answer/127637712
来源：知乎

只截取了一部分内容，原文如下：

这是一个非常好，也非常值得思考的问题。
换一个方式来问这个问题：为什么基于 tree-ensemble 的机器学习方法，在实际的 kaggle 比赛中效果非常好？

通常，解释一个机器学习模型的表现是一件很复杂事情，而这篇文章尽可能用最直观的方式来解释这一问题。

1. 理论模型 （站在 vc-dimension 的角度）

2. 实际数据

3. 系统的实现 （主要基于 xgboost）

通常决定一个机器学习模型能不能取得好的效果，以上三个方面的因素缺一不可。

（1）站在理论模型的角度统计

机器学习里经典的 vc-dimension 理论告诉我们：一个机器学习模型想要取得好的效果，这个模型需要满足以下两个条件：

1. 模型在我们的训练数据上的表现要不错，也就是 trainning error 要足够小。
2. 模型的 vc-dimension 要低。换句话说，就是模型的自由度不能太大，以防overfit.

当然，这是我用大白话描述出来的，真正的 vc-dimension 理论需要经过复杂的数学推导，推出 vc-bound.

vc-dimension 理论其实是从另一个角度刻画了一个我们所熟知的概念，那就是 bias variance trade-off.

好，现在开始让我们想象一个机器学习任务。对于这个任务，一定会有一个 “上帝函数” 可以完美的拟合所有数据（包括训练数据，以及未知的测试数据）。很可惜，这个函数我们肯定是不知道的 （不然就不需要机器学习了）。

我们只可能选择一个 “假想函数” 来 逼近 这个 “上帝函数”，我们通常把这个 “假想函数” 叫做 hypothesis.

在这些 hypothesis 里，我们可以选择 svm, 也可以选择 logistic regression. 可以选择单棵决策树，也可以选择 tree-ensemble (gbdt, random forest).

现在的问题就是，为什么 tree-ensemble 在实际中的效果很好呢？区别就在于 “模型的可控性”。

先说结论，tree-ensemble 这样的模型的可控性是好的，而像 LR 这样的模型的可控性是不够好的（或者说，可控性是没有 tree-ensemble 好的）。为什么会这样？别急，听我慢慢道来。

我们之前说，当我们选择一个 hypothsis 后，就需要在训练数据上进行训练，从而逼近我们的 “上帝函数”。我们都知道，对于 LR 这样的模型。如果 underfit，我们可以通过加 feature，或者通过高次的特征转换来使得我们的模型在训练数据上取得足够高的正确率。而对于 tree-enseble 来说，我们解决这一问题的方法是通过训练更多的 “弱弱” 的 tree. 所以，这两类模型都可以把 training error 做的足够低，也就是说模型的表达能力都是足够的。

但是这样就完事了吗？没有，我们还需要让我们的模型的 vc-dimension 低一些。

而这里，重点来了。在 tree-ensemble 模型中，通过加 tree 的方式，对于模型的 vc-dimension 的改变是比较小的。而在 LR 中，初始的维数设定，或者说特征的高次转换对于 vc-dimension 的影响都是更大的。换句话说，tree-ensemble 总是用一些 “弱弱” 的树联合起来去逼近 “上帝函数”，一次一小步，总能拟合的比较好。而对于 LR 这样的模型，我们很难去猜到这个“上帝函数”到底长什么样子（到底是2次函数还是3次函数？上帝函数如果是介于2次和3次之间怎么办呢？）。

所以，一不小心我们设定的多项式维数高了，模型就 “刹不住车了”。俗话说的好，步子大了，总会扯着蛋。这也就是我们之前说的，tree-ensemble 模型的可控性更好，也即更不容易 overfit.