Internal Covariate Shift

ICS：由于网络参数变化，引起内部节点（输入）数据分布发生变化的过程

• 网络中层与层之间高度耦合，具有强关联性

  • 网络中任意层都可以视为单独网络
  • 上层输入可视为作为当前层外部输入

• 随训练进行，网络中参数不断发生改变

  • 任意层中参数变化会导致之后层输入发生改变
  • 高层需要不断适应输入分布的改变，即其输入分布性质影响 该层训练
  • 由此导致模型训练困难

负面影响

• 上层网络需要不断调整输入适应数据分布变换，降低网络学习 效率

• 输入数据量级不稳定、各维度数据量级差距不稳定

  • 降低学习效率
    • 小量级维度参数要求更小的学习率
    • 否则参数可能在最优解附近反复波动
  • 容易出现梯度消失，难以训练饱和非线性模型
    • 大量级维度训练过程中容易陷入梯度饱和区，参数更新 速度慢，减缓网络收敛速度
    • 训练过程中参数更新更有可能使得输入移向激活函数 饱和区
    • 且该效应随着网络深度加深被进一步放大
  • 参数初始化需要更复杂考虑

• 还可以使用非饱和激活函数ReLU等避免陷入梯度饱和区

Batch Normalization

Batch Normalization：规范化batch数据，使样本各维度 标准化，即均值为0、方差为1

$$\begin{align*} \y & = BN_{\gamma, \beta}(z) = \gamma \odot \hat z + \beta \\ \hat z & = \frac {z - E(z)} {\sqrt {Var(z) + \epsilon}} \end{align*}$$

• $B$：mini-batch
• $z, y$：某层输入向量、规范化后输入向量 （即以个神经元中激活前标量值$z=Wx+b$为一维）
• $\odot$：逐元素乘积
• $E(x)$：均值使用移动平均均值
• $Var(x)$：方差使用移动平均无偏估计
• $\gamma, \beta$：待学习向量，用于恢复网络的表示能力
• $\epsilon$：为数值计算稳定性添加

• BN可以视为whitening的简化

  • 简化计算过程：避免过高的运算代价、时间
  • 保留数据信息：未改变网络每层各特征之间相关性

• BN层引入可学习参数$\gamma, \beta$以恢复数据表达能力

  • Normalization操作缓解了ICS问题，使得每层输入稳定 ，也导致数据表达能力的缺失
  • 输入分布均值为0、方差为1时，经过sigmoid、tanh激活 函数时，容易陷入其线性区域
  • $\gamma = \sqrt {Var(z)}, \beta = E(z)$时为等价变换 ，并保留原始输入特征分布信息

• Whitening：白化，对输入数据变换使得各特征同均值、 同方向、不相关，可以分为PCA白化、ZCA白化

训练

• 规范化在每个神经元内部非线性激活前$z=Wu$进行，而不是 [也]在上一层输出$u$上进行，即包含BN最终为

  $$z = act(BN(Wu))$$

  • $act$：激活函数
  • 偏置$b$：可以被省略，BN中减去均值

  • $u$的分布形状可以在训练过程中改变
  • 而$u$两次正则化无必要
  • $z=Wu$分布更可能对称、稠密、类似高斯分布

• 以batch统计量作为整体训练样本均值、方差估计

  • 每层均需存储均值、方差的移动平均统计量用于测试时 归一化测试数据

• 对卷积操作，考虑卷积特性，不是只为激活函数（即卷积核） 学习$\gamma, \beta$，而是为每个feature map学习 （即每个卷积核、对每个特征图层分别学习）

预测

• 预测过程中各参数（包括均值、方差）为定值，BN仅仅对数据 做了线性变换

  • 使用训练总体的无偏统计量对测试数据归一化 （训练时存储）

    $$\begin{align*} \mu_{test} & = E(\mu_{batch}) \\ \sigma^2_{test} = \frac m {m-1} E(\sigma^2_{batch}) \end{align*}$$

  • 还可以使用样本指数加权平均统计量

用途

• BN通过规范化输入数据各维度分布减少ICS，使得网络中每层 输入数据分布相对稳定

• 实现网络层与层之间的解耦

  • 方便迁移学习
  • 加速模型学习速度：后层网络无需不断适应输入分布变化， 利于提高神经网络学习速度

• 降低模型对网络超参数、初始值敏感度，使得网络学习更加稳定

  • 简化调参过程
  • 允许使用更大的学习率提高学习效率
  $$\begin{align*} BN(Wu) & = BN((aW)u) \\ \frac {\partial BN(aWu)} {\partial u} & = \frac {\partial BN(Wu)} {\partial u} \\ \frac {BN(aWu)} {\partial aW} & = \frac 1 a \frac {\partial BN(Wu)} {\partial W} \end{align*}$$

  • $a$：假设某层权重参数变动$a$倍

  • 激活函数函数输入不受权重$W$放缩影响
  • 梯度反向传播更稳定，权重$W$的Jacobian矩阵将包含接近 1的奇异值，保持梯度稳定反向传播

• 允许网络使用饱和激活函数（sigmoid、tanh等），而不至于 停滞在饱和处，缓解梯度消失问题

  • 深度网络的复杂性容易使得网络变化积累到上层网络中， 导致模型容易进入激活函数梯度饱和区

• 有正则化作用，提高模型泛化性能，减少对Dropout的需求

  • 不同batch均值、方差有所不同，为网络学习过程增加随机 噪声
  • 与Dropout关闭神经元给网络带来噪声类似，一定程度上 有正则化效果

Layer Normalization

层归一化：假设非线性激活前的输入随机变量分布接近，可以直接 基于每层所有非线性激活前输入估计均值、方差

$$\begin{align*} \mu^l & = \frac 1 H \sum_{i=1}^H h_i^l \\ \sigma^l &= \sqrt {\frac 1 H \sum_{i=1}^H (h_i^l - \mu^l)^2} \\ h^l & = W^l x^{l-1} + b^l \\ LN(h^l) & = \frac {g^l} {\sigma^l} \odot (h^l - \mu^l) + b^l \\ x^l & = g(LN(h^l)) \end{align*}$$

• $h^l$：第$l$隐层激活前值
• $\mu^l, \sigma^l$：第$l$隐层对应LN均值、方差 （标量，是同层神经元激活前值统计量）

• 相对于BN，其适应范围更广

  • 循环神经网络中，BN无法处理长于训练序列的测试序列
  • BN无法应用到在线学习、超大分布式模型任务，此时训练 batch较小，计算的均值、方差无法有效代表训练总体

• LN假设非线性激活前输入随机变量分布接近，而CNN网络中图像 边缘对应kernel大量隐藏单元未被激活，假设不成立，所以 CNN网络中LN效果没有BN效果好

指数类

Sigmoid

将实数映射到(0, 1)区间

$$sigmoid(z) = \frac 1 {1+e^{-z}}$$

• $z= wx+b$

• 用途

  • 隐层神经元输出
  • 二分类输出

• 缺点

  • 激活函数计算量大，BP算法求误差梯度时，求导涉及除法
  • 误差反向传播时容易出现梯度消失
  • 函数收敛缓慢

Hard_Sigmoid

计算速度比sigmoid激活函数快

$$hard_signmoid(z) = \left \{ \begin {array} {l} 0 & z < -2.5 \\ 1 & z > 2.5 \\ 0.2*z + 0.5 & -2.5 \leq z \leq 2.5 \\ \end {array} \right.$$

• $z= wx+b$

Softmax

主要用于多分类神经网络输出

$$softmax(z_i) = \frac {e^{z_i}} {\sum_{k=1}^K e^{z_k}}$$

• $z_i = w_i x + b_i$：$(w_i, b_i)$组数同分类数量，和输入 $x$维度无关

• $K$：分类数目

• 工程意义：指数底

  • 可导$max$：拉开数值之间差距
  • 特征对输出结果为乘性：即$z_i$中输入增加会导致输出 随对应权重倍数增加
  • 联合交叉熵损失避免导数溢出，提高数值稳定性

• 理论意义：概率论、最优化

  • softmax符合最大熵原理
  • 假设各标签取值符合多元伯努利分布，而softmax是其 link functiond的反函数#todo
  • 光滑间隔最大函数

• Softmax回归参数$(w_i, b_i$$冗余，可以消去一组

Softplus

$$softplus(z) = log(exp(z)+1)$$

• $z = wx + b$

Tanh

双曲正切函数

$$\begin{align*} tanh(z) & = \frac {sinhz} {coshz} \\ & = \frac {e^z - e^{-z}} {e^z + e^{-z}} \\ \end{align*}$$

• $z = wx + b$
• $\frac{\partial tanh(z)}{\partial z} = (1 - tanh(z))^2$ ：非常类似普通正切函数，可以简化梯度计算

线性类

Softsign

$$softsign(z) = \frac z {abs(z) + 1)}$$

ReLU

Rectfied Linear Units：修正线性单元

$$relu(z, max) = \left \{ \begin{array} {l} 0 & z \leq 0 \\ z & 0 < x < max \\ max & z \geq max \\ \end {array} \right.$$

LeakyReLU

Leaky ReLU：带泄露的修正线性

$$relu(z, \alpha, max) = \left \{ \begin {array} {l} \alpha z & z \leq 0 \\ z & 0 < z < max \\ max & z \geq max \\ \end {array} \right.$$

• $\alpha$：超参，建议取0.01

• 解决了$z < 0$时进入死区问题，同时保留了ReLU的非线性特性

Parametric ReLU

PReLU：参数化的修正线性

$$prelu(z) = \left \{ \begin{array} {l} \alpha z & z < 0 \\ z & z> 0 \\ \end{array} \right.$$

• $\alpha$：自学习参数（向量），初始值常设置为0.25，通过 momentum方法更新

ThreshholdReLU

带阈值的修正线性

$$threshhold_relu(z, theta)= \left \{ \begin{array} {l} z & z > theta \\ 0 & otherwise \\ \end{array} \right.$$

Linear

线性激活函数：不做任何改变

线性指数类

Exponential Linear Unit

Elu：线性指数

$$elu(z, \alpha) = \left \{ \begin{array} {l} z & z > 0 \\ \alpha (e^z - 1) & x \leqslant 0 \\ \end{array} \right.$$

• $\alpha$：超参

• $x \leq 0$时，$f(x)$随$x$变小而饱和
  • ELU对输入中存在的特性进行了表示，对缺失特性未作定量 表示

• 网络深度超超过5层时，ELU相较ReLU、LReLU学习速度更快、 泛化能力更好

Gausssion Error Liear Unit

GELU：ReLU的可导版本

Selu

可伸缩指数线性激活：可以两个连续层之间保留输入均值、方差

• 正确初始化权重：lecun_normal初始化
• 输入数量足够大：AlphaDropout
• 选择合适的$\alpha, scale$值

$$selu(z) = scale * elu(z, \alpha)$$

梯度消失

激活函数导数太小（$<1$），压缩误差（梯度）变化

Dropout

Dropout：训练时根据随机隐藏部分神经元、对应连接边避免 过拟合

固定概率丢弃

Dropout最简单方法：设置固定概率p，对每个神经元以概率p判定 是否需要保留

$$\begin{align*} y & = f(W * d(x) + b) \\ d(x) & = \left \{ \begin{array}{l} m \odot x, & 训练阶段 px, & 测试阶段 \end{array} \right. \end{align*}$$

• $d(x)$：丢弃函数
• $m \in {0, 1}^d$：丢弃掩码，通过概率为p的伯努利 分布随机生成

• $p$可以设置为0.5，对大部分网络、任务比较有效

  • 此时随机生成多的网络最具多样性

• 训练时

  • 激活神经元数量为原来的p倍
  • 每个batch分别进行drop，相当于对每个batch都有独特网络

• 测试时

  • 所有神经元都被激活，造成训练、测试时网络输出不一致， 需将每个神经元输出乘p避免
  • 也相当于把不同网络做平均

• 在预测时，类似bagging技术将多个模型组合

  • 只是类似，各个drop后的子网并不独立，在不同子网中相同 神经元的权重相同
  • 多个模型组合组合可以一定程度上抵消过拟合
  • 因为在训练时子网中部分神经元被drop，剩余部分权重相较 完全网络有$\frac 1 {1-p}$，所以在完整网络中，各部分 权重需要$ * (1-p)$

• 讲道理应该是隐藏部分神经元而不是连接，否则会使神经元偏向 某些输入，还不如隐藏部分神经元，这样可以让神经元随机降低 样本权重，理论上能减弱过拟合

丢弃方法

• 输入层神经元丢弃率更接近1，使得输入变化不会太大

  • 输入层神经元丢失时，相当于给数据增加噪声，提高网络 稳健性

• 循环神经网络丢弃

  • 不能直接丢弃隐状态，会损害循环网络在时间维度上的记忆 能力
  • 简单方法：可以考虑对非循环连接进行随机丢弃
  • 变分丢弃法：根据贝叶斯对丢弃法是对参数的采样解释， 采样参数需要每个时刻保持不变
    • 需要对参数矩阵的每个元素随机丢弃
    • 所有时刻使用相同的丢弃掩码

解释

• 集成学习解释

  • 每次丢弃，相当于从原网络采样得到子网络
  • 每次迭代，相当于训练不同的子网络，共享原始网络参数
  • 最终网络可以近似看作是集成了指数个不同网络的组合模型

• 贝叶斯学习解释

  • 对需要学习的网络$y = f(x, \theta)$，贝叶斯学习假设 参数$\theta$为随机向量

  • 设先验分布为$q(\theta)$，贝叶斯方法预测为

    $$\begin{align*} E_{q(\theta)}[y] & = \int_q f(x, \theta) q(\theta) d\theta \\ & \approx \frac 1 M \sum_{m=1}^M f(x, \theta_m) \end{align*}$$

  • $f(x, \theta_m)$：第$m$次应用丢弃方法的网络
  • $\theta_m$：对全部参数的采样

深度学习CTR

Deep Crossing

Deep Crossing：深度学习CTR模型最典型、基础性模型

• multiple residual units：残差网络

Factorization Machine based Neural Network

FNN：使用FM隐层作为embedding向量，避免完全从随机状态训练 embedding

• 输入特征为高维稀疏特征，embeddingd层与输入层连接数量大、 训练效率低、不稳定

• 提前训练embedding提高模型复杂度、不稳定性

Product-based Neural Network

PNN：在embedding层、全连接层间加入product layer，完成 针对性特征交叉

• product layer：在不同特征域间进行特征组合，定义有 inner、outer product以捕捉不同的交叉信息，提高表示能力

• 传统DNN中通过多层全连接层完成特征交叉组合，缺乏针对性

  • 没有针对不同特征域进行交叉
  • 不是直接针对交叉特征设计

Wide&Deep Network

Wide&Deep：结合深层网络、广度网络平衡记忆、泛化

• deep models：基于稠密embedding前馈神经网络
• wide models：基于稀疏特征、特征交叉、特征转换线性模型

• 基于记忆的推荐通常和用户已经执行直接相关；基于泛化的推荐 更有可能提供多样性的推荐

• memorization：记忆，学习频繁出现的物品、特征，从历史 数据中探索相关性

• generalization：泛化，基于相关性的transitivity，探索 较少出现的新特征组合

• https://arxiv.org/pdf/1606.07792.pdf

• wide&deep系模型应该都属于stacking集成

Google App Store实现

$$P(Y=1|x) = \sigma(w_{wide}^T[x, \phi(x)] + w_{deep}^T \alpha^{l_f} + b)$$

• wide部分：cross product transformation

  • 输入
    • 已安装Apps
    • impression Apps
    • 特征工程交叉特征
  • 优化器：带L1正则的FTRL

• Deep部分：左侧DNN

  • 输入
    • 类别特征embedding：32维
    • 稠密特征
    • 拼接：拼接后1200维 （多值类别应该需要将embedding向量平均、极大化）
  • 优化器：AdaGrad
  • 隐层结构
    • 激活函数relu优于tanh
    • 3层隐层效果最佳
    • 隐层使用塔式结构

DeepFM

DeepFM：用FM替代wide&deep中wide部分，提升其表达能力

• Dense Embeddings：FM中各特征隐向量，FM、DNN公用
• FM Layer：FM內积、求和层

$$\begin{align*} y_{FM} & = <w, x> + \sum_i \sum_j <v_i, v_j> x_i x_j + b \\ \hat y_{DeepFM} & = \sigma(y_{FM} + y_{DNN}) \end{align*}$$

• 特点（和Wide&Deep关键区别）

  • wide部分为FM （deep&wide中wide部分有特征交叉，但依靠特征工程实现）
  • FM、DNN部分共享embedding层

• 同时组合wide、二阶交叉、deep三部分结构，增强模型表达能力

  • FM负责一阶特征、二阶特征交叉
  • DNN负责更高阶特征交叉、非线性

实现

• DNN部分隐层

  • 激活函数relu优于tanh
  • 3层隐层效果最佳
  • 神经元数目在200-400间为宜，略少于Wide&Deep
  • 在总神经元数目固定下，constant结构最佳

• embedding层

  • 实验中维度为10

Deep&Cross Network

Deep&Cross：用cross网络替代wide&deep中wide部分，提升其 表达能力

• 特点（和WDL、DeepFM区别）

  • 使用交叉网络结构提取高阶交叉特征
    • 无需特征工程（WDL）
    • 不局限于二阶交叉特征（DeepFM）

• 交叉网络可以使用较少资源提取高阶交叉特征

https://arxiv.org/pdf/1708.05123.pdf

交叉网络

交叉网络：以有效地方式应用显式特征交叉，由多个交叉层组成

$$\begin{align*} x_{l+1} & = f(x_l, w_l, b_l) + x_l \\ & = x_0 x_l^T w_l + b_l + x_l \end{align*}$$

• $x_l$：第$l$交叉层输出
• $w_l, b_l$：第$l$交叉层参数

• 借鉴残差网络思想

  • 交叉层完成特征交叉后，会再加上其输入
  • 则映射函数$f(x_l, w_l, b_l)$即拟合残差

• 特征高阶交叉

  • 每层$x_0 x_l^T$都是特征交叉
  • 交叉特征的阶数随深度$l$增加而增加，最高阶为$l+1$

• 复杂度（资源消耗）

  • 随输入向量维度、深度、线性增加
  • 受益于$x_l^T w$为标量，由结合律无需存储中间过程矩阵

Nueral Factorization Machine

NFM：用带二阶交互池化层的DNN替换FM中二阶交叉项，提升FM的 非线性表达能力

$$\begin{align*} \hat y_{NFM}(x) & = w_0 + \sum_{i=1}^m w_i x_i + f_{DNN}(x) \\ & = w_0 + \sum_{i=1}^m + h^T f_{\sigma}(f_{BI}(\varepsilon_x)) \end{align*}$$

• $f_{DNN}(x)$：多层前馈神经网络，包括Embedding Layer、 Bi-Interaction Layer、Hidden Layer、 Prediciton Layer
• $h^T$：DNN输出层权重

模型结构

Embedding Layer

全连接网络：将每个特征映射为稠密向量表示

$$\varepsilon_x = \{x_1v_1, x_2v_2, \cdots, x_mv_m\}$$

• $v_i$：$k$维embedding向量

• 只需要考虑非0特征，得到一组特征向量
• 特征向量会乘以特征值以反映真实值特征 （一般embedding特征取0/1，等价于查表）

Bi-Interaction Layer

BI层：将一组embedding向量转换为单个向量

$$\begin{align*} f_(BI)(\varepsilon_x) & = \sum_{i=1} \sum_{j=i+1} x_i v_i \odot x_j v_j \\ & = \frac 1 2 (\|\sum_{i=1}^m x_i v_i\|_2^2 - \sum_{i=1}^m \|x_i v_i\|_2^2) \end{align*}$$

• $\odot$：逐元素乘积

• 没有引入额外参数，可在线性时间$\in O(kM_x)$内计算
• 可以捕获在低层次二阶交互影响，较拼接操作更 informative，方便学习更高阶特征交互

• 将BI层替换为拼接、同时替换隐层为塔型MLP（残差网络） 则可以得到wide&deep、DeepCross
• 拼接操作不涉及特征间交互影响，都交由后续深度网络学习 ，实际操作中比较难训练

Hidden Layer

隐层：普通多层嵌套权重、激活函数

$$f_{\sigma} = \sigma_l(\beta_l (\cdot \sigma_1(\beta_l f_{BI}(\varepsilon_X) + b_1)) + b_l)$$

• $l=0$没有隐层时，$f_{\sigma}$原样输出，取$h^T$为 全1向量，即可得FM模型

Attentional Factorization Machines

AFM：引入Attention网络替换FM中二阶交互项，学习交互特征的 重要性，剔除无效的特征组合（交互项）

$$\begin{align*} \hat y_{AFM} & = w_0 + \sum_{i=1}^m w_i x_i + f_{AFM}(\varepsilon) \\ & = w_0 + \sum_{i=1}^m w_i x_i + p^T \sum_{i=1}^m \sum_{j=i+1}^m a_{i,j} (v_i \odot v_j) x_i x_j \end{align*}$$

• $\varepsilon$：隐向量集，同上
• $p^T$：Attention网络输出权重

模型结构

Pair-Wise Interaction Layer

成对交互层：将m个embedding向量扩充为$m(m-1)/2$个交互向量

$$f_{PI}(\varepsilon) = \{(v_i \odot v_j) x_i x_j\}_{(i,j) \in R_X}$$

• $R_X = {(i,j) | i \in X, j \in X, j > i }$
• $v_i$：$k$维embedding向量

Attention-based Pooling

注意力池化层：压缩交互作用为单一表示时，给交互作用赋不同权重

$$\begin{align*} f_{Att}(f_{PI}(\varepsilon)) = \sum_{(i,j) \in R_X} a_{i,j} (v_i \odot v_j) x_i x_j \end{align*}$$

• $a{i,j}$：交互权重$w{i,j}$的注意力得分
• $\odot$：逐元素乘积

• 考虑到特征高维稀疏，注意力得分不能直接训练，使用MLP attention network参数化注意力得分

  $$\begin{align*} a_{i,j}^{'} & = h^T ReLU(W((v_i \odot v_j) x_i x_j) + b) \\ a_{i,j} & = \frac {exp(a_{i,j}^{'})} {\sum_{(i,j) \in R_X} exp(a_{i,j}^{'})} \end{align*}$$

  • $W \in R^{t*k}, b \in R^t, h \in R^T$：模型参数
  • $t$：attention network隐层大小

Deep Interest Network

DIN：融合Attention机制作用于DNN

模型结构

activation unit

激活单元

$$\begin{align*} v_U(A) & = f_{au}(v_A, e_1, e_2, \cdots, e_H) \\ & = \sum_{j=1}^H a(e_j, v_A) e_j \\ & = \sum_{j=1}^H w_j e_j \end{align*}$$

• 相较于上个结构仅多了直接拼接的用户、上下文特征

模型训练

Mini-batch Aware Regularization

• 以Batch内参数平均近似$L_2$约束

$$\begin{align*} L_2(W) & = \sum_{i=1}^M \sum_{j=1}^B \sum_{(x,y) \in B_j} \frac {I(x_i \neq 0)} {n_i} \|W_i\|_2^2 \\ & \approx \sum_{i=1}^M \sum_{j=1}^B \frac {\alpha_{j,i}} {n_i} \|W_i\|_2^2 \end{align*}$$

• $W \in R^{K * M}, W_i$：embedding字典、第$i$embedding 向量
• $K, M$：embedding向量维数、特征数量
• $B, B_j$：batch数量、第$j$个batch

• 则参数迭代

  $$W_i \leftarrow w_j - \eta[\frac 1 {|B_j|} \sum_{(x,y) \in B_j} \frac {\partial L(p(x), y)} {\partial W_j} + \lambda \frac {\alpha_{j,i}} {n_i} W_i]$$

Data Adaptive Activation Function

$$\begin{align*} f(x) & = \left \{ \begin{array}{l} x, & x > 0 \\ \alpha x, & x \leq 0 \end{array} \right. \\ & = p(x) * x + (1 - p(x)) * x \\ p(x) & = I(x > 0) \end{align*}$$

PReLU在0点处硬修正，考虑使用其他对输入自适应的函数替代，以 适应不同层的不同输入分布

$$p(x) \frac 1 {1 + exp(-\frac {x - E[x]} {\sqrt{Var[x] + \epsilon}})}$$

Deep Interest Evolution Network

DIEN：引入序列模型AUGRU模拟行为进化过程

模型结构

• Interest Extractor Layer：使用GRU单元建模历史行为依赖 关系

? 关系

Stacked Generalization

堆栈泛化：使用多种模型分别训练训练，将其结果叠加作为下层 模型的输入，最终得到预测输出

• 属于异源集成模型，可以视为

  • 复合函数

    

  • 短路网络

    

• 从某种意义上，复杂模型都是stacking

思想

• 不同模型侧重于获取数据不同方面的特征

  • 使用基学习器抽取数据特征进行表示学习，提取不同角度的 数据高维特征
  • 考虑到使用全量训练数据训练、预测作为下层模型输入会 导致过拟合，可使用K折交叉验证避免过拟合
  • 有些基学习器只使用适合其部分特征训练
    • GBDT、DNN适合低维稠密特征

• 元学习器组合多个基学习器的输出

  • 从数据高维特征学习数据模式，具有更好的泛化能力，避免 过拟合

算法

• 输入：模型$M1, M_2, \cdots, M_d$、训练特征：$X{n*m}$、 训练标签$Y_{n}$、测试特征$X^{‘}$
• 输出：stacking模型、预测标签

• 将训练数据K折划分，对第$i$轮划分

  • 使用模型$M1, M_2, \cdots, M_d$分别在相应训练集 $[X[:n_i,:], X[n{i+1}:,:]]$、 $[Y[:ni], Y[n{i+1}:]]$上训练
  • 在相应验证集$X[ni:n{i+1}, :]$上验证、并记录验证 结果
  • 将验证集验证结果叠加得到部分样本新特征 $N[ni: n{i+1}, d]$

• 将K轮划分得到的部分新特征拼接得到训练集的完整新特征 $N_{n * d}$，将新特征作为输入，训练下层模型，得到最终 stacking模型

• 将测试特征如上作为输入经过两层模型预测，得到最终预测结果

• 以上以2层stacking为例，有深层stacking

常用模型

基学习器

• 交叉项、原始特征本身也可以视为线性基学习器学习到的特征

• 具体模型参见 ml_specification/rec_system/ctr_stacking_models

GBDT

• 各树中各节点对应元学习器一维输入特征

• 适合低维稠密通用特征，对输入特征分布没有要求

• GBDT树根据熵增益（Gini系数增益）划分节点，每条路径 都代表一定区分能力

  • 以叶子节点（路径）作为特征，相当于自动进行特征 转换、组合、选择、离散化，得到高维组合特征

• GDBT相较于单棵树、或RF更适合stacking

  • 单棵树表达能力弱，无法表达多个有区分性特征组合， 集成模型可将样本映射为多个特征
  • GBDT拟合残差意味着各树对样本区分度不同，对各特征 区别对待更合理

DNN

• 适合普通稠密特征、embedding特征
• 模型表达能力强，能抽取有良好分布数据的深层次特征，提高 模型准确性、泛化能力
• 容易扩充其他类别特征，如：图片、文字

元学习器

• LR

  • 适合低维稀疏特征，可对所有特征离散化以引入非线性

• FM

  • 适合低维稀疏特征
  • LR基础上自动组合二阶交叉项

• Linear：训练模型、对训练结果线性加权

?

Matching

基于用户行为

离线协同过滤

• 根据用户行为日志，利用物品-based协同过滤生成离线的 物品2物品相似度矩阵、用户离线推荐结果

  • 基于艾宾浩斯遗忘曲线按照时间进行降权
  • 弱化热点影片的权重
  • 矩阵分解

• 基于用户的playlog接口实时获取用户的短时间内的观看历史， 通过物品2物品相似度矩阵进行CF扩散，提取出与用户短时间内 观看历史相似的topN个物品用于召回

• 用户的CF离线推荐结果直接作为线上服务的召回渠道

W2V

• 全部影片作为预料库、观看历史按时序排列视为文档，计算所有 物品的词向量

• 根据词向量计算物品2物品相似度矩阵，用于线上playlog召回 数据

LDA

• 基于概率主题模型：文档-潜在主题-词三级关系，映射/类比到 用户行为数据：用户-潜在兴趣-资源

• 通过用户历史行为记录，提取LDA中间产物、用户的潜在兴趣 向量、资源潜在主题分布向量

• 基于物品的主题向量，进行物品2物品相似度计算，用于线上 playlog召回数据

SimRank

• 将用户、物品关系视为二部图，考虑相似关系可以在图上传播 思想，使用SimRank计算物品相似队列

基于内容

基于标题

• 对影片文本简介使用doc2vector，计算资源的表示向量
• 使用资源的表示项集计算物品2物品相似度矩阵

基于Style

基于Tag

其他方向

• RNN捕捉用户在点击序列中的模式，利用点击行为发生先后顺序 调整推荐展示顺序

• Graph Embedding

Ranking

特征工程

• 低维稠密通用特征：泛化能力良好、记忆能力差

  • embedding特征
  • 统计特征

• 高维稠密特征：记忆能力较好

  • 视频ID
  • 标签
  • 主题

分类

• 按特征来源分类

  • 物品特征：资源风格、低于、类型、标签、统计特征
  • 用户特征：性别、年龄、婚姻状况、收入预测
  • context特征：网络状态、时间段、城市
  • 交叉特征

• 按特征更新频率、获取方式

  • 离线特征：变化缓慢，如：用户、物品基本特征、统计特征
  • 近在线特征：分钟级、小时级需要更新的特征，如：ctr
  • 在线特征：每次请求达到实时获取特征，如：网络状态、 请求时间

特征扩充

• 用户兴趣向量丰富用户维度上兴趣特征

  • LDA中间产物作为用户潜在兴趣向量
  • W2V词向量、用户行为历史统计出用户兴趣向量

• 资源embedding向量丰富物品维度特征

  • 用户行为数据embedding得到W2V、LDA词向量
  • 资源标题embedding得到doc2vector词向量

• 资源封面AutoEncode向量

  • 基于资源封面采用自编码器训练，提取隐层向量作为资源 特征

统计特征细化

• 特征工程时间窗口细化：按不同时间窗口分别计算资源的统计 特征

  • 丰富资源特征
  • 融入时间衰减因素

• 在线特征交叉：交叉特征增加样本特征的区分度

连续特征离散化

• 目标：避免特征为长尾分布、大部分取值集中在小范围，对样本 区分度差

• 等频离散化：等频分桶、独热编码
• 对数转化

采样策略

• 负样本采样策略调整：基本曝光时间、顺序，过滤负样本
• 不平衡样本策略调整：离线A/B测试正负样本比例，择优调整

模型

• 一般使用stacking模型堆叠集成

• 参见ml_models/model_enhancement/ensemble_stacking

基学习器

• GBDT：各树、各叶子节点对应一维特征

  • 适合低维稠密通用特征，对输入特征分布没有要求

• DNN

  • 适合普通稠密特征、embedding特征
  • 能抽取有良好分布数据的深层次特征，提高模型准确性、 泛化能力

元学习器

• LR

  • 适合低维稀疏特征，可对所有特征离散化以引入非线性

• FM

  • 适合低维稀疏特征
  • LR基础上自动组合二阶交叉项

• Linear：训练模型、对训练结果线性加权

冷启动、EE

冷启动

Matching

• 冷启动用户召回

  • 使用imbd算法计算资源得分，根据不同时间周期进行得分 融合、并ab测试，选取最优时间周期组合
  • 按照imdb得分倒排，生成热点召回数据

• 冷启动资源召回

  • 基于资源库，统计各资源点击、播放率，按一定比例召回 第点击、播放率物品

Ranking

• 通常使用强化学习算法

• Thompson Sampling
• UCB算法
• Epsilon-Greedy算法
• 朴素Bandit算法
• LinUCB算法：较UCB算法加入特征信息
• COFIBA算法：Bandit算法结合协同过滤

Exploration and Exploitation Tradeoff

Matching

• 调整不同召回渠道的配比方式保证多样性

数据说明

数据模式

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

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

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

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

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

  • 一般是自描述的，数据结构和内容混合、没有明显区分
  • 树、图（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算法

谱聚类

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

基本流程

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