Cone

• 锥：$C \subset V, \forall x \in C, a>0 \Rightarrow ax \in C$

  • 锥总是无界的

  • $V$：向量空间

• Convex Cone 凸锥：$\forall x,y \in C, \forall a,b > 0 \Rightarrow ax + by \in C$

  • 凸锥必然是凸集
  • 非凸锥：凸锥的补集

• Norm Cone $n$ 维标准锥：$C = { (x,t)| |x|_2 \leq t, x \in R^{n-1}, t \in R }$

• Second Order Cone 二阶锥：$C = { (x,t)|Ax+b|_2 \leq c^Tx + d }$

  • 二阶锥相对于对标准锥做了仿射变换（平移变换）

Notations and Terminology

Strong Convexity

• 凸函数 $f$ 满足

  $$\forall x, y \in R, \forall \lambda \in (0,1), f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda)f(y)$$

• 强凸函数：不等式严格不等的凸函数

  • 为保证强凸性，常添加二次项保证，如：增广拉格朗日

凸集相关标记

• $C \subseteq R^N$：非空凸集
• $x \in R^N$

• 点 $x \in R^N$ 到 $C$ 的距离为

  $$D_C(x) = \min_{y \in C} \|x-y\|_2$$

• 点 $x \in R^N$ 在 $C$ 上投影为

  $$P_Cx \in C, D_C(x) = \|x - P_Cx\|_2$$
  • $C \subseteq R^N$：闭凸集

• Indicator Function 凸集 $C$ 的示性函数为

  $$l_C(x) = \left \{ \begin{array} 0 & if x \in C \\ +\infty & if x \notin C \end{array} \right.$$

齐次函数

齐次函数：有倍数性质的函数，若变量乘以系数 $\alpha$，则新函数为原函数乘上 $\alpha^k$ 倍

$$f(\alpha x) = \alpha^k f(x)$$

• $\alpha \neq 0 \in F, x \in X$
• $f: X \rightarrow W$：域 $F$ 内两个向量空间之间的 $k$ 次齐次函数

• 线性函数 $f: X \rightarrow W$ 是一次齐次函数
• 多线性函数 $f: x_1 x_2 \cdots * x_n \rightarrow W$ 是 $n$ 次齐次函数

基本定理

• 欧拉定理：函数 $f: R^n \rightarrow R$ 可导、$k$ 次齐次函数，则有 $x \nabla f(x) = kf(x)$

次梯度

• 次梯度：实变量凸函数 $f$ 在点 $x_0$ 的次梯度 $c$ 满足

  $$\forall x, f(x) - f(x_0) \geq c(x - x_0)$$

• 可证明凸函数 $f$ 在 $x_0$ 处所有次梯度的集合 $\partial f(x)$ 是非空凸紧集

  • $\partial f(x) = [a, b]$，其中$a, b$为单侧极限

    $$\begin{align*} a & = lim_{x \rightarrow x_0^{-}} \frac {f(x) - f_0(x)} {x - x_0} \\ b & = lim_{x \rightarrow x_0^{+}} \frac {f(x) - f_0(x)} {x - x_0} \end{align*}$$

• 凸函数均指下凸函数，梯度不减

次梯度性质

运算性质

• 数乘性质

  $$\partial(\alpha f)(x) = \alpha \partial f(x), \alpha > 0$$

• 加法性质

  $$\begin{align*} f &= f_1 + f_2 + \cdots + f_m, \\ \partial f &= \partial f_1 + \cdots + \partial f_m \end{align*}$$

• 仿射性质：$f$为凸函数

  $$\begin{align*} h(x) &= f(Ax + b) \\ \partial h(x) &= A^T \partial f(Ax + b) \end{align*}$$

最优化性质

• 凸函数 $f$ 在点 $x_0$ 可导，当且仅当次梯度仅包含一个点，即该点导数

• 点 $x_0$ 是凸函数 $f$ 最小值，当且仅当次微分中包含 0 （此性质为“可导函数极小点导数为 0 ”推广）

• 负次梯度方向不一定是下降方向

次梯度求解

• 逐点（分段）极值的函数求次梯度
• 求出该点相应极值函数
• 求出对应梯度即为次梯度

Pointwise Maximum

逐点最大函数：目标函数为

$$\begin{align*} f(x) & = max \{f_1(x), f_2(x), \cdots, f_m(x)\} \\ I(x) & = \{i | f_i(x) = f(x)\} \end{align*}$$

• $I(x)$：保存 $x$ 处取值最大的函数下标

• 弱结果：$I(x)$ 中随机抽取，以 $f_i(x)$ 在该处梯度作为次梯度

• 强结果

  $$\partial f(x) = conv \cup_{i \in I(x)} \partial f_i(x)$$
  • 先求支撑平面，再求所有支撑平面的凸包
  • 可导情况实际上是不可导的特殊情况

分段函数

• 折点处

  $$\partial f(x) = conv\{a_i, a_{i+1}\} = [a_i, a_{i+1}]$$

• 非折点处

  $$\partial f(x) = {a_i}$$

$L_1$范数

PointWise Supremum

逐点上确界：目标函数为

$$\begin{align*} f(x) &= \sup_{\alpha \in A} f_{\alpha}(x) \\ I(x) &= \{\alpha \in A | f_{\alpha}(x) = f(x)\} \end{align*}$$

• 弱结果：可行梯度为

  $$\partial (\max_{\alpha} f_{\alpha}(x)) \in partial f(x)$$

• 强结果

  $$\partial f(x) = conv \cup_{\alpha \in I(x)} \partial f_{alpha}(x) \subseteq \partial f(x)$$

最大特征值

$$\begin{align*} f(x) & = \lambda_{max}(A(x)) = \sup_{\|y\|_2 = 1} \\ A(x) & = A_0 + x_1 A_1 + \cdots + x_n A_n \end{align*}$$

• $A_n$：对称矩阵

• 对确定 $\hat {x}$，$A(x)$ 最大特征值 $\lambda_{max}$、对应特征向量 $y$，则该点此梯度为

  $$(y^T A_0 y, \cdots, y^T A_n y)$$

Pointwise Inferior

逐点下确界：目标函数为

$$f(x) = \inf_y h(x, y)$$

• $h$：凸函数

• 弱结果：给定$x = \hat x$，可行次梯度为

  $$(\partial h(x, \hat y)|_{x=\hat x}, 0) \in \partial f(x)$$

复合函数

$$f(x) = h(f_1(x), \cdots, f_n(x))$$

• $h$：凸、不降函数
• $f_i$：凸函数

• 弱结果：给定$x = \hat x$，可行次梯度为

  $$g = z_1 g_1 + \cdots + z_k g_k \in \partial f(\hat x)$$

  • $z \in \partial h(f_1(\hat x), \cdots, f_k(\hat x))$
  • $g_i \in \partial f_i(\hat x)$

  • 证明

    $$\begin{align*} f(x) & \geq h(f_1(\hat x) + g_1^T(x - \hat x), \cdots, f_k(\hat x) + g_k^T(x - \hat x) \\ & \geq h(f_1(\hat x), \cdots, f_k(\hat x)) + z^T(g_1^T(x - \hat x), \cdots, g_k^T(x - \hat x)) \\ & = f(\hat x) + g^T(x - \hat x) \end{align*}$$

次梯度法

$$\begin{align*} x^{(k+1)} & = x^{(k)} + \alpha_k g^{(k)} \\ f_{best}^{(k+1)} & = min{f_{best}^{(k)}, f(x^{(k+1)})} \end{align*}$$

• $g^{(k)}$：函数$f$在$x^{(k)}$处次梯度

• 求解凸函数最优化的问题的一种迭代方法

• 相较于较内点法、牛顿法慢

  • 应用范围更广泛：能够用于不可微目标函数，目标函数可微时，无约束问题次梯度与梯度下降法有同样搜索方向
  • 空间复杂度更小
  • 可以和分解技术结合，得到简单分配算法
  • 通常不会产生稀疏解

步长选择

• 次梯度法选取步长方法很多，以下为保证收敛步长规则

• 恒定步长：$\alpha_k = \alpha$
• 恒定间隔：$\alpha_k = \gamma / |g^{(k)}|_2$
• 步长平方可加、步长不可加：$\sum{k=1}^{\infty} \alpha_k^2 < \infty, \sum{k=1}^{\infty} \alpha_k = \infty$
• 步长不可加、但递减：$lim_{k \rightarrow \infty} \alpha_k = 0$
• 间隔不可加、但递减：$lim_{k \rightarrow \gamma_k} \gamma_k = 0$

数据说明

数据模式

• 结构化数据：行数据，可用二维表逻辑表达数据逻辑、存储在数据库中

  • 可以看作是关系型数据库中一张表
  • 行：记录、元组，表示一个样本信息
  • 列：字段、属性，有清晰定义

• 非结构化数据：相对于结构化数据而言，不方便用二维逻辑表达的数据

  • 包含信息无法用简单数值表示
    • 没有清晰列表定义
    • 每个数据大小不相同
  • 研究方向
    • 社交网络数据
    • 文本数据
    • 图像、音视频
    • 数据流
  • 针对不同类型数据、具体研究方面有不同的具体分析方法，不存在普适、可以解决所有具体数据的方法

• 半结构化数据：介于完全结构化数据、完全无结构数据之间的数据

  • 一般是自描述的，数据结构和内容混合、没有明显区分
  • 树、图（XML、HTML 文档也可以归为半结构化数据）

• 结构化数据：先有结构、再有数据
• 半结构化数据：先有数据、再有结构

数据拼接

• 利用外键拼接不同来源的数据时，注意不同数据间粒度差异
  • 外键低于问题标签粒度时，考虑对数据作聚合操作再拼接
    • 保证拼接后用于训练的记录粒度和问题一致
    • 避免维度爆炸
    • 各数据来源数据厚薄不同，会改变数据分布
  • 外键高于、等于目标粒度时，可考虑直接直接连接

数据问题

稀疏特征

• 产生原因
  • 数据缺失
  • 统计数据频繁 0 值
  • 特征工程技术，如：独热编码

缺失值

产生原因

• 信息暂时无法获取、成本高
• 信息被遗漏
• 属性不存在

缺失值影响

• 建模将丢失大量有用信息
• 模型不确定性更加显著、蕴含规则更难把握
• 包含空值可能使得建模陷入混乱，导致不可靠输出

缺失利用

• 直接使用含有缺失值特征：有些方法可以完全处理、不在意缺失值

  • 分类型变量可以将缺失值、异常值单独作为特征的一种取值
  • 数值型变量也可以离散化，类似分类变量将缺失值单独分箱

• 删除含有缺失值特征

  • 一般仅在特征缺失率比较高时才考虑采用，如缺失率达到 90%、95%

插值补全

• 非模型补全缺失值

  • 均值、中位数、众数
  • 同类/前后均值、中位数、众数
  • 固定值
  • 矩阵补全
  • 最近邻补全：寻找与样本最接近样本相应特征补全

• 手动补全：根据对所在领域理解，手动对缺失值进行插补

  • 需要对问题领域有很高认识理解
  • 缺失较多时费时、费力

• 建模预测：回归、决策树模型预测

  • 若其他特征和缺失特征无关，预测结果无意义
  • 若预测结果相当准确，缺失属性也没有必要纳入数据集

• 多重插补：认为待插补值是随机的

  • 通常估计处待插补值
  • 再加上不同噪声形成多组可选插补值
  • 依据某准则，选取最合适的插补值

• 高维映射：one-hot 编码增加维度表示某特征缺失

  • 保留所有信息、未人为增加额外信息
  • 可能会增加数据维度、增加计算量
  • 需要样本量较大时效果才较好

• 压缩感知：利用信号本身具有的稀疏性，从部分观测样本中恢复原信号

  • 感知测量阶段：对原始信号进行处理以获得稀疏样本表示
    • 傅里叶变换
    • 小波变换
    • 字典学习
    • 稀疏编码
  • 重构恢复阶段：基于稀疏性从少量观测中恢复信号

异常值

• 异常值/离群点：样本中数值明显偏离其余观测值的个别值

异常值分析：检验数据是否有录入错误、含有不合常理的数据

非模型异常值检测

• 简单统计

  • 观察数据统计型描述、散点图
  • 箱线图：利用箱线图四分位距对异常值进行检测

• $3\sigma$ 原则：取值超过均值 3 倍标准差，可以视为异常值

  • 依据小概率事件发生可能性“不存在”
  • 数据最好近似正态分布

模型异常值检测

• 基于模型预测：构建概率分布模型，计算对象符合模型的概率，将低概率对象视为异常点

  • 分类模型：异常点为不属于任何类的对象
  • 回归模型：异常点为原理预测值对象
  • 特点
    • 基于统计学理论基础，有充分数据和所用的检验类型知识时，检验可能非常有效
    • 对多元数据，可用选择少，维度较高时，检测效果不好

• 基于近邻度的离群点检测：对象离群点得分由其距离 k-NN 的距离确定

  • k 取值会影响离群点得分，取 k-NN 平均距离更稳健
  • 特点
    • 简单，但时间复杂度高 $\in O(m^2)$，不适合大数据集
    • 方法对参数 k 取值敏感
    • 使用全局阈值，无法处理具有不同密度区域的数据集

• 基于密度的离群点检测

  • 定义密度方法
    • k-NN 分类：k 个最近邻的平均距离的倒数
    • DSSCAN 聚类中密度：对象指定距离 d 内对象个数
  • 特点
    • 给出定量度量，即使数据具有不同区域也能很好处理
    • 时间复杂度 $\in O^(m^2)$，对低维数据使用特点数据结构可以达到 $\in O(mlogm)$
    • 参数难以确定，需要确定阈值

• 基于聚类的离群点检测：不属于任何类别簇的对象为离群点

  • 特点
    • （接近）线性的聚类技术检测离群点高度有效
    • 簇、离群点互为补集，可以同时探测
    • 聚类算法本身对离群点敏感，类结构不一定有效，可以考虑：对象聚类、删除离群点再聚类
    • 检测出的离群点依赖类别数量、产生簇的质量

• One-class SVM

• Isolation Forest

异常值处理

• 删除样本

  • 简单易行
  • 观测值很少时，可能导致样本量不足、改变分布

• 视为缺失值处理

  • 作为缺失值不做处理
  • 利用现有变量信息，对异常值进行填补
  • 全体/同类/前后均值、中位数、众数修正
  • 将缺失值、异常值单独作为特征的一种取值

• 很多情况下，要先分析异常值出现的可能原因，判断异常值是否为真异常值

类别不平衡问题

创造新样本

• 对数据集重采样

  • 尝试随机采样、非随机采样
  • 对各类别尝试不同采样比例，不必保持 1:1 违反现实情况
  • 同时使用过采样、欠采样

• 属性值随机采样

  • 从类中样本每个特征随机取值组成新样本
  • 基于经验对属性值随机采样
  • 类似朴素贝叶斯方法：假设各属性之间相互独立进行采样，但是无法保证属性之前的线性关系

• 对模型进行惩罚

  • 类似 AdaBoosting：对分类器小类样本数据增加权值
  • 类似 Bayesian分类：增加小类样本错分代价，如：penalized-SVM、penalized-LDA
  • 需要根据具体任务尝试不同惩罚矩阵

新角度理解问题

• 将小类样本视为异常点：问题变为异常点检测、变化趋势检测

  • 尝试不同分类算法
  • 使用 one-class 分类器

• 对问题进行分析，将问题划分为多个小问题

  • 大类压缩为小类
  • 使用集成模型训练多个分类器、组合

• 需要具体问题具体分析

模型评价

• 尝试其他评价指标：准确度在不平衡数据中不能反映实际情况
  • 混淆矩阵
  • 精确度
  • 召回率
  • F1 得分
  • ROC 曲线
  • Kappa

数据量缺少

图片数据扩充

Data Agumentation：根据先验知识，在保留特点信息的前提下，对原始数据进行适当变换以达到扩充数据集的效果

• 对原始图片做变换处理

  • 一定程度内随机旋转、平移、缩放、裁剪、填充、左右翻转，这些变换对应目标在不同角度观察效果
  • 对图像中元素添加噪声扰动：椒盐噪声、高斯白噪声
  • 颜色变换
  • 改变图像亮度、清晰度、对比度、锐度

• 先对图像进行特征提取，在特征空间进行变换，利用通用数据 扩充、上采样方法

  • SMOTE

• Fine-Tuning 微调：直接接用在大数据集上预训练好的模型，在小数据集上进行微调

  • 简单的迁移学习
  • 可以快速寻外效果不错针对目标类别的新模型

特征缩放

• 正则化：针对单个样本，将每个样本缩放到单位范数
• 归一化：针对单个属性，需要用到所有样本在该属性上值

Normalizaion

归一化/标准化：将特征/数据缩放到指定大致相同的数值区间

• 某些算法要求数据、特征数值具有零均值、单位方差
• 消除样本数据、特征之间的量纲/数量级影响
  • 量级较大属性占主导地位
  • 降低迭代收敛速度：梯度下降时，梯度方向会偏离最小值，学习率必须非常下，否则容易引起宽幅震荡
  • 依赖样本距离的算法对数据量机敏感

• 决策树模型不需要归一化，归一化不会改变信息增益（比），Gini 指数变化

Min-Max Scaling

线性函数归一化：对原始数据进行线性变换，映射到 $[0, 1]$ 范围

$$X_{norm} = \frac {X - X_{min}} {X_{max} - X_{min}}$$

• 训练集、验证集、测试集都使用训练集归一化参数

Z-Score Scaling

零均值归一化：将原始数据映射到均值为 0，标准差为 1 的分布上

$$Z = \frac {X - \mu} {\sigma}$$

其他一些变换方式

• 对数变换：$X^{‘} = lg(X)$
• 反余切函数变换：$X^{‘} = \frac {2 arctan(x)} {\pi}$
• Sigmoid 变换：$X^{‘} = \frac 1 {1 + e^{-x}}$
• 模糊向量变：$X^{‘} = \frac 1 2 + \frac 1 2 sin \frac {X - \frac{max(X) - min(X)} 2} {max(X) - min(X)} * \pi$

Regularization

正则化：将样本/特征某个范数缩放到单位 1

$$\begin{align*} \overrightarrow x_i & = ( \frac {x_i^{(1)}} {L_p(\overrightarrow x_i)}, \frac {x_i^{(2)}} {L_p(\overrightarrow x_i)}, \cdots, \frac {x_i^{(d)}} {L_p(\overrightarrow x_i)})^T \\ L_p(\overrightarrow x_i) & = (|x_i^{(1)}|^p + |x_i^{(2)}|^p + \cdots + |x_i^{(d)}|^p)^{1/p} \end{align*}$$

• $L_p$：样本的 $L_p$ 范数

• 使用内积、二次型、核方法计算样本之间相似性时，正则化很有用

综述

• 特征工程：对原始数据进行工程处理，将其提炼为特征，作为输入供算法、 模型使用

  • 本质上：表示、展示数据的过程
  • 目的：去除原始数据中的杂质、冗余，设计更高效的特征以刻画求解的 问题、预测模型之间的关系
    • 把原始数据转换为可以很好描述数据特征
    • 建立在其上的模型性能接近最优
  • 方式：利用数据领域相关知识、人为设计输入变量

• 数据、特征决定了机器学习的上限，模型、算法只是逼近上限，特征越好

  • 模型选择灵活性越高：较好特征在简单模型上也能有较好 效果，允许选择简单模型
  • 模型构建越简单：较好特征即使在超参不是最优时效果也 不错，不需要花时间寻找最优参数
  • 模型性能越好
    • 排除噪声特征
    • 避免过拟合
    • 模型训练、预测更快

• 特征工程要：小步快跑、多次迭代

  • 便于及时发现问题、定位问题，如：数据穿越

频繁项集

• 频繁项集：频繁出现项集合（无序）
• 频繁项序列：频繁出现项序列（有序）

• 相关关联规则算法：数据量大时，无法直接发现频繁项集
• 频繁项集评估标准

评估标准

• 支持度：数据关联出现概率，关联数据在数据集中出现次数占 总数据集比重

  $$Support(X, Y) = P(XY) = \frac {num(XY)} {num(All)}$$
  • 支持度高数据不一定构成频繁项集，但支持度数据肯定不能 不构成频繁项集

• 置信度：数据出现条件概率，某个数据出现、另一数据出现概率

  $$Confidence(X \Leftarrow Y) = P(X|Y) = \frac {P(XY)} {P(Y)}$$

• 提升度：数据之间关联关系，某数据出现、另一数据出现概率同 其总体出现概率之比

  $$\begin{align*} Lift(X \Leftarrow Y) & = \frac {P(X|Y)} {P(X)} \\ & = \frac {Confidence(X \Leftarrow)}{P(X)} \\ & = \frac {P(XY)} {P(X)P(Y)} \end{align*}$$
  • 提升度大于1则为有效的强关联规则，否则为无效的强关联 规则
  • 若X、Y不相关，则提升度为1

• 选择频繁数据集，一般需要自定义评估标准：自定义支持度、 自定义支持度和置信度组合

Apriori

Apriori算法

• 以支持度作为评估标准，找出数据集中最大的频繁$k$项集
  • 找到符合支持度标准的频繁$k$项集
  • 迭代直到无法找到项数更大的频繁项集

算法

• 输入：数据集合D、支持度阈值$\alpha$
• 输出：最大的频繁K项集

• 置$k=1$，扫描整个数据集，以所有出现过数据作为候选1项集
• 挖掘候选$k$项集
  • 扫描数据、计算候选$k$项集支持度
  • 去除支持度低于阈值$\alpha$的项集得到频繁$k$项集
    • 若频繁$k$项集只包含1项，直接返回
    • 若频繁$k$项集为空，返回频繁$k-1$项集
  • 基于频繁$k$项集连接、生成候选$k+1$项集
  • 置$k=k+1$

• 需要频繁扫描数据、效率低
• 频繁项集的子项集肯定也是频繁项集

FPTree/FPGrowth

FPTree：对Apriori算法改进，不在需要多次扫描数据

• FPTree引入部分数据结构以临时存储数据

  

  • 项头表：按频繁1项集出现频数降序排列的表
  • FP Tree：包含原始数据、频数的多叉树
  • 节点链表：链接项头表中频繁1项集、FPTree中相应节点 的链表

• 特点：效率高

  • 只需要扫描两次数据
  • 使用多叉树存储临时数据，利用高频频繁项集

算法

• 建立项头表

  • 扫描数据，得到所有1项集频数、剔除支持度低于阈值者， 并按支持度（频数）降序排列
  • 第二次扫描数据，剔除每条数据中非频繁1项集、 在每条数据内部按支持度降序排列

  

• 建立FPTree：逐条读取处理后排序后数据，依次插入树中

  • 每条数据中排序靠前者为祖先节点
  • 若有直系公共祖先则公共祖先节点计数+1
  • 新节点通过链表和项头表链接

  

• 挖掘FPTree：对项表头中每项，找到其条件模式基

  • 将子树中每个节点计数置为叶子节点计数和，则子树中节点 取值即为其与当前项组合出现频数/支持度
  • 删除（当前子树内）支持度/频数低于支持度阈值$\alpha$ 节点
  • 剩余节点项、当前项组合即为相应频繁$k$项集

  

  • 条件模式基：节点作为叶子节点所对应的FP子树

Prefix-Projected Pattern Growth

PrefixSpan：前缀投影模式挖掘

• 以支持度为标准，挖掘数据集中频繁序列
  • 每条数据为若干项集组成的序列，序列内项集间有序
  • 为方便，每条数据序列中项集中的项已排序

• 可以将每条数据序列整体视为串
• 频繁序列：频繁出现子序列

算法

• 输入：序列数据集$S$、支持度$\alpha$
• 所有满足阈值要求的频繁序列

• 找出所有长度1前缀（即所有项）、对应投影

  • 计数、剔除持度小于阈值$\alpha$者，得到频繁1项序列
  • 置$k=1$

• 对每个长度为$k$前缀递归挖掘

  • 若前缀对应投影为空，返回
  • 若前缀对应投影中所有项支持度均小于阈值$\alpha$，返回
  • 同满足阈值要求阈值$\alpha$要求项合并，得到新前缀
  • 置$k=k+1$

• prefix：前缀，正在处理的子序列
• projected：投影，各数据序列中位于前缀之后子串 ?串

聚类算法

聚类：按照某特定标准（如距离准则）把数据集分割成不同类、簇， 簇内数据相似性尽可能大、不同簇间数据对象差异性仅可能大

• 属于无监督学习，目标是把相似的样本聚集在一起

  • 通常只需要给定相似度的计算即可
  • 无需使用训练数据学习

• 聚类算法分类

  • 基于划分
  • Hierarchical Methods：基于层次
  • 基于密度
  • 基于网络
  • 基于模型
  • 模糊聚类
  • 基于约束
  • 基于粒度
  • 谱聚类
  • 核聚类
  • 量子聚类

衡量聚类算法优劣

• 算法的处理能力

  • 处理大数据的能力
  • 处理噪声数据能力
  • 处理任意形状数据的能力，如：有间隙的嵌套数据

• 算法是否需要预测条件

  • 聚类数目
  • 相关领域知识

• 输入数据关联性

  • 结果是否和数据输入顺序相关
  • 对数据维度敏感性（是否能处理高维数据）
  • 对数据类型要求

Hierarchical Methods

层次聚类

• 自底向上合并的层次聚类

  • 最底层开始，通过合并最相似类簇形成上层类簇
  • 全部数据点合并到同一类簇、或达到终止条件时结束

• 自顶向下分裂的层次聚类

  • 从包含全部数据点的类簇开始，递归分裂出最相异的下层 类簇
  • 每个类簇仅包含单个数据点时结束

• 优点

  • 可解释性好：如需要创建分类方法时
  • 研究表明能产生高质量聚类，可以应用在较大K的K-means 后的合并阶段
  • 可以解决非球形类簇

• 缺点

  • 时间复杂度高$O(N^2 log N)$（$N$为数据点数目）
  • 贪心算法无法取得最优解

• 距离选择参见ml_tech/#todo

AGENS

AGENS：自下向上层次聚类

• 组连接：组与组之间距离
  • single linkage
  • average linkage
  • complete linkage
• 算法复杂度：$n^2logn$

流程

• 每个数据点视为一类，计算两两直接最小距离
• 合并距离最小两个两类别为新类
• 重新计算新类、所有类之间距离
• 重复以上，直至所有类合并为一类

Divisive Analysis

DIANA：自定向下层次聚类

算法流程

• 所有数据归为一组$C_1=(p_1, p_2, dots, p_n)$
• 计算所有点之间的距离矩阵，选择到其他点平均距离最大的点， 记为$q$，取该点作为新组起始点
• $\forall p, p \notin C_1$，计算 $d_arg(p, C_1) - d_arg(p, C_2)$， 若小于零则属于$C_1$，否则属于$C_2$

Balanced Itertive Reducing and Clustering Using Hierarchies

BIRCH：利用层次方法的平衡迭代规约和聚类，利用层次方法聚类 、规约数据

• 特点
  • 利用CF树结构快速聚类
  • 只需要单遍扫描数据
  • 适合在数据类型为数值型、数据量大时使用

常见算法、改进

• A Hierarchical Clustering Algorithm Using Dynamic Modeling：使用KNN算法计算作为linkage、构建图
  • 较BIRCH好，但算法复杂度依然为$O(n^2)$
  • 可以处理比较复杂形状

Partition-Based Methods

基于划分的方法

• 基本流程

  • 确定需要聚类的数目，挑选相应数量点作为初始中心点
  • 再根据预定的启发式算法队数据点做迭代
  • 直到达到类簇内点足够近、类簇间点足够远

• 优点

  • 对大型数据集同样简单高效、时空复杂度低

• 缺点

  • 数据集越大，结果容易越容易陷入局部最优
  • 需要预先设置k值，对初始k中心点选取敏感
  • 对噪声、离群点敏感
  • 只适合数值性
  • 不适合非凸形状

• 影响结果因素

  • 原始问题是否可分
  • 分类数目K
  • 初始点选择

K-means

• 数据：$\Omega={X_1, X_2, \dots, X_N}$，分k个组

  $$C_1, C_2, \dots, C_k \\ C_1 \cup C_2 \cup \dots \cup C_k = \Omega \\$$

  每个样本点包含p个特征：$X_i = (x_1, x_2, \dots, x_p)$

• 目标：极小化每个样本点到聚类中心距离之和

  $$\arg_{C_1, C_2, \dots, C_K} \min \sum_{i=1}^K \sum_{x_j in \C_i} d(x_j, C_i)$$
  • 若定义距离为平方欧式距离，则根据组间+组内=全， 极小化目标就是中心点距离极大化

• 优化问题是NP-hard问题，需要采用近似方法

K值选择

• 经验选择
• 特殊方法：Elbow Method，肘部法则，画出距离和K的点图， 选择剧烈变化的点的K值

Lloyd’s Algorithm

• 随机选择K对象，每个对象初始地代表类簇中心
• 对剩余对象，计算与各簇中心距离，归于距离最近地类簇
• 重新计算各类簇平均值作为新簇中心
• 不断重复直至准则函数收敛

• 算法时间效率：$\in O(K * N^{\pi})$

常见算法、改进

• K-means++、Intelligent K-means、Genetic K-means：改进 K-means对初值敏感
• K-medoids、K-medians：改进K-means对噪声、离群点敏感
• K-modes：适用于分类型数据
• Kernel-Kmeans：可以解决非凸问题

Density-Based Methods

基于密度的方法

• 优点
  • 对噪声不敏感
  • 能发现任意形状聚类
• 缺点
  • 聚类结果和参数关系很大

相关概念

• 核心点：半径eps的邻域内点数量不少于阈值MinPts的点

• 直接可达：核心点半径eps的领域内被称为直接可达

  • 没有任何点是由非核心点直接可达的

• 可达：若存在$p_1, \cdots, p_n$点列中相邻点直接可达， 则$p_1, p_n$可达

  • 非对称关系，因为核心点没有直接可达点

• 连接性：若存在点$o$可达$p,q$，则$p,q$称为[密度]连接

  • 对称关系
  • 聚类内点都是相连接的
  • 若p由q可达，则p在q所属聚类中

• 局外点：不由任何点可达的点

DBSCAN

• Density-Based Spatial Clustering of Applications with Noise

算法流程

• 从任意对象点p开始
• 寻找合并核心点p对象直接密度可达对象
  • 若p是核心点，则找到聚类
  • 若p是边界，则寻找下个对象点
• 重复直到所有点被处理

说明

• DBSCAN用固定参数识别聚类，类簇稀疏程度不同时，相同判断 标准会破坏类自然结构

  • 较稀疏类簇会被划分为多个
  • 密度大距离近多个类被合并

• 参数影响

  • eps过大大多数点聚为同一簇中、过小则会导致簇分裂
  • MinPts值过大则同簇中点被标记为噪声点、过小则有大量 核心点

• 超参半径eps、最小点数量MinPts经验选取

  • 计算所有点k距离
  • 对各点k距离排序、绘制折线图
  • 观察折线图，以发现极具变化的位置对应k距离作为半径
  • k即作为最小点数量

  • k距离：距离点第k近点距离

常见算法、改进

• Ordering Points to Indentify Clustering Structure：优先 搜索高密度，然后根据高密度特点设置参数，改善DBSCAN

Grid-Based Methods

基于网络的方法

• 优点

  • 速度快，速度与数据对象个数无关，只依赖数据空间中每维 上单元数目
  • 可以和基于密度算法共同使用

• 缺点

  • 对参数敏感
  • 无法处理不规则分布的数据
  • 维数灾难
  • 聚类结果精确性低：算法效率提高的代价

流程

• 将数据空间划分为网格单元：不同算法主要区别
• 将数据对象集映射到网格单元中，计算各单元密度
• 根据预设的阈值判断每个网格单元是否为高密度单元
• 将相连的高度密度网格单元识别为类簇

常见算法、改进

• statistical information grid
• wave-cluster
• clustering-quest

Model-Based Methods

基于模型的方法：为每个类簇假定模型，寻找对给定模型的最佳拟合

• 优点
  • 对类划分以概率形式表示
  • 每类特征可以用概率表达
• 缺点
  • 执行效率不高，尤其是分布数量多、数据量少时

SOM

SOM：假设输入对象中存在一些拓扑结构、顺序，可以实现从输入 空间到输入平面的降维映射，且映射具有拓扑特征保持性质

• 网络结构

  • 输入层：高维输入向量
  • 输入层：2维网络上的有序节点

• 学习过程

  • 找到、更新与输入节点距离最短的输出层单元，即获胜单元
  • 更新邻近区域权值，保持输出节点具有输入向量拓扑特征

SOM算法流程

• 网络初始化：初始化输出层节点权重
• 随机选取输入样本作为输入向量，找到与输入向量距离最小的 权重向量
• 定义获胜单元，调整获胜单元邻近区域权重、向输入向量靠拢
• 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类 结果

常见算法

• 概率生成模型：假设数据是根据潜在概率分布生成
  • Gaussian Mixture Model
• 基于神经网络模型的方法
  • Self Organized Maps

模糊聚类

模糊聚类：样本以一定概率属于某个类

• 优点
  • 对正态分布的数据聚类效果较好
  • 算法对孤立点敏感

Fuzzy C-means(FCM)

FCM：对K-means的推广软聚类

• 算法最终输出$C$个聚类中心向量、$C*N$模糊划分矩阵

  • 表示每个样本点对每个类的隶属度
  • 根据划分矩阵、按照最大隶属原则确定样本点归属
  • 聚类中心表示类平均特征，可以作为类代表

• 特点

  • 算法性能依赖初始聚类中心，需要依赖其他算法快速确定 初始聚类中心、或多次执行算法
  • 不能确保收敛于最优解

• soft cluster：点可以属于多个类

参数选择

• 聚类数目$C$：$C$远远小于聚类样本总数目，且大于1
• 柔性参数$m$
  • $m$过大：聚类效果差
  • $m$过小：算法接近HCM聚类算法

算法流程

• 标准化数据矩阵
• 建立模糊相似矩阵，初始化隶属矩阵

• 迭代，直到目标函数收敛到极小值

  $$w_k(x_i) = \frac 1 \sum_{i=1}^k (\frac {d(x_i, \mu_k)} {d(x_i, \mu_i} )^{1/(m-2)})$$

• 根据迭代结果，由最终隶属矩阵确定数据所属类，得到聚类结果

常见算法、改进

• HCM算法

基于约束的算法

基于约束的算法：考虑聚类问题中的约束条件，利用约束知识进行 推理

• 约束

  • 对聚类参数的约束
  • 对数据点的约束

• 典型算法

  • Clustering with Obstructed Distance：用两点之间障碍 距离取代一般的欧式距离计算最小距离

量子聚类

量子聚类：用量子理论解决聚类过程中初值依赖、确定类别数目的 问题

• 典型算法
  • 基于相关点的Pott自旋、统计机理提供的量子聚类模型： 将聚类问题视为物理系统

核聚类

核聚类：增加对样本特征的优化过程，利用Mercer核把输入空间映射 至高维特征空间，在特征空间中进行聚类

• 特点

  • 方法普适
  • 性能上优于经典聚类算算法
  • 可以通过非线性映射较好分辨、提取、放大有用特征
  • 收敛速度快

• 典型算法

  • SVDD算法
  • SVC算法

谱聚类

谱聚类：建立在图论中谱图理论基础上，本质是将聚类问题转换为 图的最优划分问题

基本流程

• 根据样本数据集定义描述成对数据点的相似度亲和矩阵
• 计算矩阵特征值、特征向量
• 选择合适的特征向量聚类不同点

Emsemble Learning

• 集成学习：训练多个基模型，并将其组合起来，以达到更好的 预测能力、泛化能力、稳健性
• base learner：基模型，基于独立样本建立的、一组 具有相同形式的模型中的一个
• 组合预测模型：由基模型组合，即集成学习最终习得模型

• 源于样本均值抽样分布思路

  • $var(\bar{X}) = \sigma^2 / n$
  • 基于独立样本，建立一组具有相同形式的基模型
  • 预测由这组模型共同参与
  • 组合预测模型稳健性更高，类似于样本均值抽样分布方差 更小

• 关键在于

  • 获得多个独立样本的方法
  • 组合多个模型的方法

分类

• homogenous ensemble：同源集成，基学习器属于同一类型

  • bagging
  • boosting

• heterogenous ensemble：异源集成，基学习器不一定属于同 一类型

  • [genralization] stacking

• 以上都是指原始版本、主要用途

Boosting

提升方法：将弱可学习算法提升为强可学习算法的组合元算法

• 属于加法模型：即基函数的线性组合
• 各模型之间存在依赖关系

分类Boosting

• 依次学习多个基分类器
• 每个基分类器依之前分类结果调整权重
• 堆叠多个分类器提高分类准确率

• boosting通过组合多个误分率略好于随机猜测的分类器得到 误分率较小的分类器，因此boosting适合这两类问题

  • 个体之间难度有很大不同，boosting能够更加关注较难的 个体
  • 学习器对训练集敏感，boosting驱使学习器在趋同的、 “较难”的分布上学习，此时boosting就和bagging一样能够 使得模型更加稳健（但原理不同）

• boosting能减小预测方差、偏差、过拟合

  • 直觉上，使用在不同的样本上训练的基学习器加权组合， 本身就能减小学习器的随机变动

  • 基于同样的理由，boosting同时也能减小偏差

  • 过拟合对集成学习有些时候有正面效果，其带来多样性， 使模型泛化能力更好，前提是样本两足够大，否则小样本 仍然无法提供多样性

回归Boosting

• 依次训练多个基学习器
• 每个基学习器以之前学习器拟合残差为目标
• 堆叠多个学习器减少整体损失

• boosting组合模型整体损失（结构化风险）

  $$R_{srm} = \sum_{i=1}^N l(y_i, \hat y_i) + \sum_{t=1}^M \Omega(f_t)$$

  • $l$：损失函数
  • $f_t$：基学习器
  • $\Omega(f_t)$：单个基学习器的复杂度罚
  • $N, M$：样本数目、学习器数目

• 基学习器损失

  $$obj^{(t)} = \sum_{i=1}^N l(y_i, \hat y_i^{(t)}) + \Omega(f_t)$$

最速下降法

使用线性函数拟合$l(y_i, \hat y_i^{(t)})$

$$\begin{align*} obj^{(t)} & = \sum_i^N l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i)] + \Omega(f_t) \end{align*}$$

• $gi = \partial{\hat y} l(y_i, \hat y^{t-1})$

• 一次函数没有极值
• 将所有样本损失视为向量（学习器权重整体施加），则负梯度 方向损失下降最快，考虑使用负梯度作为伪残差

Newton法

使用二次函数拟合$l(y_i, \hat y_i^{(t)}$

$$\begin{align*} obj^{(t)} & = \sum_i^N l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) \\ & \approx \sum_{i=1}^N [l(y_i, \hat y^{(t-1)}) + g_i f_t(x_i) + \frac 1 2 h_i f_t^2(x_i)] + \Omega(f_t) \\ \end{align*}$$

• $hi = \partial^2{\hat y} l(y_i, \hat y^{t-1})$

• 二次函数本身有极值
• 可以结合复杂度罚综合考虑，使得每个基学习器损失达到最小

Boosting&Bagging

• 基分类器足够简单时，boosting表现均显著好于bagging

  • 仅靠单次决策（单个属性、属性组合）分类

• 使用C4.5树作为基分类器时，boosting仍然具有优势，但是不够 有说服力

• 结论来自于Experiments with a New Boosting Algorithm

Boosting&Bagging

• 基分类器足够简单时，boosting表现均显著好于bagging

  • 仅靠单次决策（单个属性、属性组合）分类

• 使用C4.5树作为基分类器时，boosting仍然具有优势，但是不够 有说服力

• 结论来自于Experiments with a New Boosting Algorithm

原理

probably approximately correct：概率近似正确，在概率近似 正确学习的框架中

• strongly learnable：强可学习，一个概念（类），如果存在 一个多项式的学习算法能够学习它，并且正确率很高，那么 就称为这个概念是强可学习的

• weakly learnable：弱可学习，一个概念（类），如果存在 一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测 略好，称此概念为弱可学习的

• Schapire证明：在PAC框架下强可学习和弱可学习是等价的

具体措施

• 弱学习算法要比强学习算法更容易寻找，所以具体实施提升就是 需要解决的问题

• 改变训练数据权值、概率分布的方法

  • 提高分类错误样本权值、降低分类正确样本权值

• 将弱学习器组合成强学习器的方法

  • competeing
  • simple majority voting
  • weighted majority voting
  • confidence-based weighting

学习器组合方式

• 很多模型无法直接组合，只能组合预测结果

• simple majority voting/simple average：简单平均

  $$h = \frac 1 K \sum_{k=1}_K h_k$$

  • $h_k$：第k个预测

• weighted majority voting/weighted average：加权平均

  $$h = \frac {\sum_{k=1}^K w_k h_k} {\sum_{k=1}^K w_k}$$

  • $w_k$：第k个预测权重，对分类器可以是准确率

• competing voting/largest：使用效果最优者

• confidence based weighted：基于置信度加权

  $$\begin{align*} h = \arg\max_{y \in Y} \sum_{k=1}^K ln(\frac {1 - e_k} {e_k}) h_k \end{align*}$$

  • $e_k$：第k个模型损失

Meta Learning

元学习：自动学习关于关于机器学习的元数据的机器学习子领域

• 元学习主要目标：使用学习到元数据解释，自动学习如何 flexible的解决学习问题，借此提升现有学习算法性能、 学习新的学习算法，即学习学习

• 学习算法灵活性即可迁移性，非常重要

  • 学习算法往往基于某个具体、假象的数据集，有偏
  • 学习问题、学习算法有效性之间的关系没有完全明白，对 学习算法的应用有极大限制

要素

• 元学习系统必须包含子学习系统
• 学习经验通过提取元知识获得经验，元知识可以在先前单个 数据集，或不同的领域中获得
• 学习bias（影响用于模型选择的前提）必须动态选择
  • declarative bias：声明性偏见，确定假设空间的形式 ，影响搜索空间的大小
    • 如：只允许线性模型
  • procedural bias：过程性偏见，确定模型的优先级
    • 如：简单模型更好

Recurrent Neural networks

RNN：self-referential RNN理论上可以通过反向传播学习到， 和反向传播完全不同的权值调整算法

Meta Reinforcement Learning

MetaRL：RL智能体目标是最大化奖励，其通过不断提升自己的学习 算法来加速获取奖励，这也涉及到自我指涉

Additional Model

加法模型：将模型视为多个基模型加和而来

$$f(x) = \sum_{m=1}^M \beta_m b(x;\theta_m)$$

• $b(x;\theta_m)$：基函数
• $\theta_m$：基函数的参数
• $\beta_m$：基函数的系数

• 则相应风险极小化策略

  $$\arg\min_{\beta_m, \theta_m} \sum_{i=1}^N L(y_i, \sum_{m=1}^M \beta_m b(x_i;\theta_m))$$

  • $L(y, f(x))$：损失函数

Forward Stagewise Algorithm

前向分步算法：从前往后，每步只学习加法模型中一个基函数 及其系数，逐步逼近优化目标函数，简化优化复杂度

• 即每步只求解优化

  $$\arg\min_{\beta, \theta} \sum_{i=1}^N L(y_i, \hat f_m(x_i) + \beta b(x_i;\theta))$$

  • $\hat f_m$：前m轮基函数预测值加和

步骤

• 输入：训练数据集$T={(x_1,y_1), \cdots, (x_N,y_N)}$，损失 函数$L(y,f(x))$，基函数集${b(x;\theta)}$
• 输出：加法模型$f(x)$

• 初始化$f_0(x)=0$

• 对$m=1,2,\cdots,M$，加法模型中M个基函数

  • 极小化损失函数得到参数$\beta_m, \theta_m$

    $$(\beta_m, \theta_m) = \arg\min_{\beta, \theta} \sum_{i=1}^N L(y_i, f_{m-1}(x_1) + \beta b(x_i; \theta))$$

  • 更新

    $$f_m(x) = f_{m-1}(x) + \beta_m b(x;y_M)$$

• 得到加法模型

  $$f(x) = f_M(x) = \sum_{i=1}^M \beta_m b(x;\theta_m)$$

AdaBoost&前向分步算法

AdaBoost（基分类器loss使用分类误差率）是前向分步算法的特例， 是由基本分类器组成的加法模型，损失函数是指数函数

• 基函数为基本分类器时加法模型等价于AdaBoost的最终分类器 $f(x) = \sum_{m=1}^M \alpha_m G_m(x)$

• 前向分步算法的损失函数为指数函数$L(y,f(x))=exp(-yf(x))$ 时，学习的具体操作等价于AdaBoost算法具体操作

  • 假设经过m-1轮迭代，前向分步算法已经得到

    $$\begin{align*} f_{m-1}(x) & = f_{m-2}(x) + \alpha_{m-1}G_{m-1}(x) \\ & = \alpha_1G_1(x) + \cdots + \alpha_{m-1}G_{m-1}(x) \end{align*}$$

  • 经过第m迭代得到$\alpha_m, G_m(x), f_m(x)$，其中

    $$\begin{align*} (\alpha_m, G_m(x)) & = \arg\min_{\alpha, G} \sum_{i=1}^N exp(-y_i(f_{m-1}(x_i) + \alpha G(x_i))) \\ & = \arg\min_{\alpha, G} \sum_{i=1}^N \bar w_{m,i} exp(-y_i \alpha G(x_i)) \end{align*}$$

    • $\bar w{m,i}=exp(-y_i f{m-1}(x_i))$：不依赖 $\alpha, G$

  • $\forall \alpha > 0$，使得损失最小应该有 （提出$\alpha$）

    $$\begin{align*} G_m^{*}(x) & = \arg\min_G \sum_{i=1}^N \bar w_{m,i} exp(-y_i f_{m-1}(x_i)) \\ & = \arg\min_G \sum_{i=1}^N \bar w_{m,i} I(y_i \neq G(x_i)) \end{align*}$$

    此分类器$G_m^{*}$即为使得第m轮加权训练误差最小分类器 ，即AdaBoost算法的基本分类器

  • 又根据

    $$\begin{align*} \sum_{i=1}^N \bar w_{m,i} exp(-y_i \alpha G(x_i)) & = \sum_{y_i = G_m(x_i)} \bar w_{m,i} e^{-\alpha} + \sum_{y_i \neq G_m(x_i)} \bar w_{m,i} e^\alpha \\ & = (e^\alpha - e^{-\alpha}) \sum_{i=1}^N (\bar w_{m,i} I(y_i \neq G(x_i))) + e^{-\alpha} \sum_{i=1}^N \bar w_{m,i} \end{align*}$$

    带入$G_m^{*}$，对$\alpha$求导置0，求得极小值为

    $$\begin{align*} \alpha_m^{*} & = \frac 1 2 log \frac {1-e_m} {e_m} \\ e_m & = \frac {\sum_{i=1}^N (\bar w_{m,i} I(y_i \neq G_m(x_i)))} {\sum_{i=1}^N \bar w_{m,i}} \\ & = \frac {\sum_{i=1}^N (\bar w_{m,i} I(y_i \neq G_m(x_i)))} {Z_m} \\ & = \sum_{i=1}^N w_{m,i} I(y_i \neq G_m(x_i)) \end{align*}$$

    • $w_{m,i}, Z_M$同AdaBoost中

    即为AdaBoost中$\alpha_m$

  • 对权值更新有

    $$\bar w_{m+1,i} = \bar w_{m,i} exp(-y_i \alpha_m G_m(x))$$

    与AdaBoost权值更新只相差规范化因子$Z_M$

AdaBoost

通过改变训练样本权重，学习多个分类器，并将分类器进行线性 组合，提高分类性能

• 对离群点、奇异点敏感
• 对过拟合不敏感

Boosting实现

• 改变训练数据权值或概率分布：提高分类错误样本权值、降低 分类正确样本权值

• 弱分类器组合：加权多数表决，即加大分类误差率小的弱分类器 权值，使其在表决中起更大作用；减小分类误差率大的弱分类器 权值，使其在表决中起更小作用

步骤

• 输入：训练数据集$T={(x_1, y_1), \cdots, (x_N, y_N)}$， 弱分类器算法$G(x)$

  • $x_i \in \mathcal{X \subset R^n}$
  • $y_i \in \mathcal{Y} = {-1, +1 }$

• 输出：最终分类器$G(x)$

• 初始化训练数据权值分布： $D1=(w{11}, \cdots, w{1N}), w{1i}=\frac 1 N$

• 对$m=1,2,\cdots,M$（即训练M个弱分类器）

  • 使用具有权值分布$D_m$的训练数据学习，得到基本 分类器

    $$G_m(x):\mathcal{X} \rightarrow \{-1, +1\}$$

  • 计算$G_m(x)$在训练数据集上的分类误差率

    $$\begin{align*} e_m & = P(G_m(x_i)) \neq y_i) \\ & = \sum_{i=1}^N w_{mi}I(G_m(x_i) \neq y_i) \\ & = \sum_{G_m(x_i) \neq y_i} w_{mi} \end{align*}$$

  • 计算$G_m(x)$组合为最终分类器时权重

    $$\alpha = \frac 1 2 log \frac {1-e_m} {e_m}$$

    • $\alpha_m$表示就简单分类器$G_m(x)$在最终分类器中 的重要性，随$e_m$减小而增加 （弱分类器保证$e_m \leq 1/2$）

  • 更新训练集权值分布

    $$\begin{align*} D_{m+1} & = (w_{m+1,1}, \cdots, w_{m+1,N}) \\ w_{m+1,i} & = \frac {w_{mi}} {Z_m} exp(-\alpha y_i G_m(x_i)) = \left \{ \begin{array}{l} \frac {w_mi} {Z_m} e^{-\alpha_m}, & G_m(x_i) = y_i \\ \frac {w_mi} {Z_m} e^{\alpha_m}, & G_m(x_i) \neq y_i \\ \end{array} \right. \\ Z_m & = \sum_{i=1}^N w_{mi} exp(-\alpha_m y_i G_m(x_i)) \end{align*}$$

    • $Zm$：规范化因子，是第m轮调整后的权值之和，其 使得$D{m+1}$成为概率分布
    • 误分类样本权值相当于被放大 $e^{2\alpha_m} = \frac {e_m} {1 - e_m}$倍

• 构建基本分类器线性组合

  $$f(x) = \sum_{m=1}^M \alpha_m G_m(x)$$

  得到最终分类器

  $$G(x) = sign(f(x)) = sign(\sum_{m=1}^M \alpha_m G_m(x))$$

  • 这里$\alpha_m$没有规范化，和不为1，规范化没有必要
  • $f(x)$符号决定分类预测结果，绝对值大小表示分类确信度

• AdaBoost中分类器学习和之后的分类误差率“无关”，基分类器 学习算法中的loss不是分类误差率，可以是其他loss，只是需要 考虑训练数据的权值分布

  • 好像基学习器的loss就要是和集成部分调权的loss一致

    todo

  • 按权值分布有放回的抽样，在抽样集上进行训练
  • 各样本loss按权重加权，类似分类误差率中加权

训练误差边界

AdaBoost算法最终分类器的训练误差边界为

$$\frac 1 N \sum_{i=1}^N I(G(x_i) \neq y_i) \leq \frac 1 N \sum_i exp(-y_if(x_i)) = \prod_m Z_m$$

• $G(x_i) \neq y_i$时，$y_if(x_i)<0$，所以 $exp(-y_i f(x_i)) \geq 1$，则不等式部分可证

• $$\begin{align*} \frac 1 N \sum_i exp(-y_i f(x_i)) & = \frac 1 N \sum_i exp(-\sum_{m=1}^M \alpha_m y_i G_m(x_i)) \\ & = \sum_i (w_{1,i} \prod_{m=1}^M exp(-\alpha_m y_i G_m(x_i))) \\ & = \sum_i (Z_1 w_{2,i} \prod_{m=2}^M exp(-\alpha_m y_i G_m(x_i))) \\ & = \prod_{m=1}^M Z_i \sum_i w_{M+1,i} \\ & = \prod_{m=1}^M Z_i \end{align*}$$

• AdaBoost训练误差边界性质的关键：权重调整与基本分类器权重 调整共系数（形式不完全一样）
• 这也是AdaBoost权重调整设计的依据，方便给出误差上界

二分类训练误差边界

$$\prod_{m=1}^M Z_m = \prod_{m=1}^M (2\sqrt{e_m(1-e_m)}) = \prod_{m=1}^M \sqrt{(1-4\gamma_m^2)} \leq exp(-2\sum_{m=1}^M \gamma_m^2)$$

• $\gamma_m = \frac 1 2 - e_m$

• $$\begin{align*} Z_m & = \sum_{i=1}^N w_{m,i} exp(-\alpha y_i G_m(x_i)) \\ & = \sum_{y_i = G_m(x_i)} w_{m,i}e^{-\alpha_m} + \sum_{y_i \neq G_m(x_i)} w_{m,i}e^{\alpha_m} \\ & = (1-e_m)e^{-\alpha_m} + e_m e^{\alpha_m} \\ & = 2\sqrt{e_m(1-e_m)} \\ & = \sqrt{1-4\gamma^2} \end{align*}$$

• 由$\forall x \in [0, 0.5], e^{-x} > \sqrt{1-2x}$可得， $\sqrt{1-4\gamma_m^2} \leq exp(-2\gamma_m^2)$

• 二分类AdaBoost误差边界性质的关键：$\alpha$的取值，也是 前向分步算法（损失函数）要求
• 若存$\gamma > 0$，对所有m有$\gamma_m \geq \gamma$，则 $$\frac 1 N \sum_{i=1}^N I(G(x_i) \neq y_i) \neq exp(-2M\gamma^2)$$ 即AdaBoost的训练误差是指数下降的
• 分类器下界$\gamma$可以未知，AdaBoost能适应弱分类器各自 训练误差率，所以称为adptive

Adaboost.M1

Adaboost.M1是原版AdaBoost的多分类升级版，基本思想同Adaboost

Boosting实现

• 基分类器组合方式

  • 仍然是加权投票，且投票权重同Adaboost
  • 出于多分类考虑，没有使用sign符号函数

• 改变训练数据权值或概率分布：和Adaboost形式稍有不同，但 相对的错误分类样本提升比率完全相同

  • 被上个分类器错误分类样本，权值保持不变
  • 被上个分类器正确分类样本，权值缩小比例是Adaboost平方

步骤

• 输入

  • 训练集：$T={x_i, y_i}, i=1,\cdots,N; y_i \in C, C={c_1, \cdots, c_m}$
  • 训练轮数：T
  • 弱学习器：I

• 输出：提升分类器

  $$H(x) = \arg\max_{y \in C} \sum_{m=1}^M ln(\frac 1 {\beta_m}) [h_m(x) = y]$$

  • $h_t, h_t(x) \in C$：分类器
  • $\beta_t$：分类器权重

误分率上界

• 对弱学习算法产生的伪损失$\epsilon1,\cdots,\epsilon_t$， 记$\gamma_t = 1/2 \epsilon_t$，最终分类器$h{fin}$误分率 上界有 $$\frac 1 N |\{i: h_{fin}(x_i) \neq y_i \}| \leq \prod_{t-1}^T \sqrt {1-4\gamma^2} \leq exp(-2 \sum_{t-1}^T \gamma^2)$$

特点

Adaboost.M1和Adaboost基本上没有区别

• 类别数目为2的Adaboost.M1就是Adaboost
• 同样无法处理对误分率高于0.5的情况，甚至在多分类场合， 误分率小于0.5更加难以满足
• 理论误分率上界和Adaboost相同

Adaboost.M2

AdaboostM2是AdaboostM1的进阶版，更多的利用了基分类器信息

• 要求基学习器能够输出更多信息：输出对样本分别属于各类别 的置信度向量，而不仅仅是最终标签
• 要求基分类器更加精细衡量错误：使用伪损失代替误分率 作为损失函数

Psuedo-Loss

$$\begin{align*} L & = \frac 1 2 \sum_{(i,y) \in B} D_{i,y} (1 - h(x_i, y_i) + h(x_i, y)) \\ & = \frac 1 2 \sum_{i=1}^N D_i (1 - h(x_i, y_i) + \sum_{y \neq y_i} (w_{i,y} h(x_i, y))) \end{align*}$$

• $D$：权重分布（行和为1，但不满足列和为1）

  • $D_{i,y}$：个体$x_i$中错误标签$y$的权重，代表从个体 $x_i$中识别出错误标签$y$的重要性

• $B = {(i, y)|y \neq y_i, i=1,2,\cdots,N }$
• $w$：个体各错误标签权重边际分布
• $h(x, y)$：模型$h$预测样本$x$为$y$的置信度

  • $h(x_i,y_i)$：预测正确的置信度
  • $h(x_i,y), y \neq y_i$：预测$x_i$为错误分类$y$置信度

• 伪损失函数同时考虑了样本和标签的权重分布
• 通过改变此分布，能够更明确的关注难以预测的个体标签， 而不仅仅个体

Boosting实现

• 改变数据权值或者概率分布

  • 使用psuedo-loss替代误分率，以此为导向改变权值
  • 对多分类每个错误分类概率分别计算错误占比，在此基础上 分别计算

• 基分类器组合方式：同Adaboost.M1

步骤

训练误差上界

• 对弱学习算法产生的伪损失$\epsilon1,\cdots,\epsilon_t$， 记$\gamma_t = 1/2 \epsilon_t$，最终分类器$h{fin}$误分率 上界有

$$\frac 1 N |\{i: h_{fn}(x_i) \neq y_i \}| \leq (M-1) \prod_{t-1}^T \sqrt {1-4\gamma^2} \leq (M-1) exp(-2 \sum_{t-1}^T \gamma^2)$$

特点

• 基于伪损失的Adaboost.M2能够提升稍微好于随机预测的分类器

• Adaboosting.M2能够较好的解决基分类器对噪声的敏感性，但是 仍然距离理论最优Bayes Error有较大差距，额外误差主要 来自于

  • 训练数据
  • 过拟合
  • 泛化能力

• 控制权值可以有效的提升算法，减小最小训练误差、过拟合 、泛化能力

  • 如对权值使用原始样本比例作为先验加权

• 其分类结果不差于AdaBoost.M1（在某些基分类器、数据集下）