机器学习与数据挖掘复习笔记

发表于 Waline： 阅读次数：

结构按照著名坑导 BJP 的 PPT 整理，不代表作者同意其中任何内容，重要部分（如 BP）以及 PPT 啥都没讲的（如 OPTICS）按我的知识而不是 PPT 整理

考试回忆

很水，感觉是拍脑袋出题。六个大题

  1. 欠拟合怎么发现怎么解决
  2. 举三个人脸识别的算法，简单描述过程
  3. KNN 优缺点？K 值过大过小怎么办
  4. 你的机器学习方法精度上不去怎么办
  5. 给一个单隐层网络，算 BP 后权重更新值的形式
  6. 给四条离散数据，求最大信息增益的属性

概述

大数据：在可接受的时间内，无法用单机系统完整处理的数据

  • 大数据处理：分治，特定场景优化，并行，异构，弹性，横向扩展，容错
  • Hadoop 离线 Map Reduce；Spark 迭代式；Storm 流式在线实时

机器学习（ML），数据挖掘（DM），知识发现（KDD）

数据挖掘基本任务：描述性（挖掘模式），预测性（给出值）

机器学习基本任务：分类，聚类，预测，联想，优化；生成一个数据空间到目标空间的映射 \(S\to Z\)

  • 分类：目标空间已知有限离散
  • 聚类：目标空间位置有限离散
  • 预测：目标空间是连续值空间
  • 联想：目标空间是数据空间，需要发现数据本身的联系
  • 优化：目标是数据空间上的函数 \(F(S)\)，需要 \(\max{d[F(S)]}\)，\(d\) 为一种度量

机器学习基本过程：收集数据，清洗数据，提取特征，训练模型，获得知识

数据和度量

概念：

  • 数据集，数据对象和属性的集合
  • 数据属性，又叫变量，字段，特征或特性；属性类型（名词，有序，区间，比值）
  • 数据对象，又叫记录，点，案例，样本，实体或事件

数据常见类型：记录数据（数据矩阵，词向量，事务数据），图数据，有序数据

归一化方法

线性（离差标准化法，最大最小法），其中 \(min\)，\(max\) 分别为数据集最小，最大值 \[ v=\frac{x-min}{max-min} \] Z-Score，其中 \(\mu\)，\(\sigma\) 为数据集均值和方差 \[ v=\frac{x-\mu}{\sigma} \] 其他从 \((-\infty,+\infty)\) 映射到 \([0,1]\) 的函数：高斯，Sigmoid

度量方法

相异性

方法 计算 特点
欧几里得 \(\sqrt{\sum_k(p_k-q_k)^2}\) 各维尺度敏感，不识别相关维
闵可夫斯基距离 \((\sum_k|p_k-q_k|^r)^{1/r}\)
马氏距离 \(\sqrt{(p-q)^T\Sigma^{-1}(p-q)}\)，其中 \(\Sigma=1/n((\boldsymbol{X}-\boldsymbol{\mu})^T(\boldsymbol{X}-\boldsymbol{\mu}))\) 为所有 \(n\) 个样本的协方差矩阵，\(\boldsymbol{X}\) 是 \(n\times m\) 的样本矩阵， \(\boldsymbol{\mu}\) 为 \(1\times m\) 样本均值 各维尺度无关，要求样本数量大于维数且满秩，要求总体一致

相似性

方法 计算
余弦相似度 \(\cos(p, q)=\dfrac{pq}{|p||q|}\)
距离倒数 \(\dfrac{1}{1+d}\)
杰卡德系数（离散集合） \(J(A,B)=\dfrac{|A\cap B|}{|A\cup B|}\)
Tanimoto 系数 \(f(A,B)=\dfrac{\sum_kA_kB_k}{|A|^2+|B|^2-\sum_kA_kB_k}\)
Dice 系数 \(S(A,B)=\dfrac{2|A\cap B|}{|A|+|B|}\)
皮尔森相关系数 \(\dfrac{\mathrm{cov}(X,Y)}{\sigma_x\sigma_y}\)
斯皮尔曼相关系数 排序重新按序赋值后的变量的皮尔森相关系数
交叉熵 \(CE(p,q)=-\sum_{i=1}^{k}p_i\log q_i\)
KL 散度 \(KL(p|q)=\sum_{i=1}^kp_i\log(p_i/q_i)\)
互信息 \(I(X,Y)=H(Y)-H(Y|X)=\sum_{x,y}p(x,y)\log(p(x,y)/p(x)/p(y))\)

度量公理：非负，对称，三角不等式；Tanimoto，Dice 距离不是度量

机器学习结果评价

鲁棒性，适应性，简洁性，可解释性

测试数据分割：保留法，交叉验证法，随机法

各指标：

  • 误差 \(Error(T)=\sum_{i=1}^{|T|}P_i\|E_i-L_i\|\)
  • 正确率 \(Accuracy(T)=|T_{error<\varepsilon}|/|T|\)
  • 精度 \(TP/(TP+FP)\)
  • 召回率 \(TP/(TP+FN)\)
  • 正确率 \((TP+TN)/(TP+TN+FP++FN)\)
  • \(F_\beta=(\beta^2+1)precision\cdot recall/(\beta^2precision + recall)\)
  • 假阳率 \(FPR=1-Specificity=TNR=FP/(FP+TN)\)
  • 灵敏度 \(Sensitivity=Recall=TPR=TP/(TP+FN)\)
  • 特异度 \(Specificity=TNR=TN/(TN+FP)\)

多分类问题指标处理：宏平均（各类别平均），微平均（先平均每个类别的 \(TP\)，\(TN\)，\(FP\)，\(FN\)）

分类

小样本学习理论

参数 \(a\)，被学习函数 \(f(x,a)\)，训练器输出联合概率 \(F(x,y)\)（样本满足该分布），损失函数 \(L(y,y')\)

期望风险 \[ R(a)=\iint L(y,(f(x,a))\ \mathrm d F(x,y) \] 经验风险 \[ R_{\text{empirical}}(a)=\frac{1}{N}\sum_{i=1}^{N}L(y_i,f(x_i,a)) \] 经验风险最小化原则 ERM

VC 维：对于一个函数集 \(\{f(x,a_1,a_2,\cdots,a_n)|a_i\in A_i\}\)，如果 \(h\) 个样本能由该函数集中的不同函数分类为 \(2^h\) 种不同可能，则 \(f\) 的 VC 维为 \(h\)

  • \(n\) 维超平面的 VC 维为 \(n+1\)
  • \(R_{\text{emp}} -R(a)= \varPhi\)，其中随机变量 \(\varPhi\) 满足

\[ F_{\varPhi}\left(\sqrt{\dfrac{h\ln(2N/h)+h-\ln(\eta/4)}{N}}\right)=\eta \]

结构风险最小化原则：考虑经验风险和置信界限

过拟合：给定一个假设空间 \(H\)，一个假设 \(h\in H\)，如果存在其他的假设 \(h'\in H\)，使得在训练样例上 \(h\) 的错误率比 \(h'\) 小，但在整个实例分布上 \(h'\) 的错误率 \(h\) 比小，那么就说假设 \(h\) 过度拟合训练数据

KNN

距离输入对象最近的 \(k\) 个对象的属性投票

决策树

每次选一个最优属性作为当前节点，去掉该属性分支成两个或多个子节点，递归

ID3 算法评估属性：信息增益 \(IG(S,A)=H(S)-\sum_{v\in Values(A)}|S_v|/|S|H(S_v)\)，其中 \(S_v\) 表示 \(S\) 中属性 \(A\) 的值为 \(v\) 的样本集

样本集的熵是 \[ H(S)=\sum_{s\in Classes}-P(s\in S)\log P(s\in S) \] \(P(s\in S)\) 表示该样本在集合 \(S\) 中类别为 \(s\) 的概率，用频率计算

搜索策略：优先选择小树防过拟合，早停止法（编码树复杂性），后修剪法

剪枝：将该子树所有后继去掉，把树根变成叶，类别是本节点出现最多的类别

规则后修剪：先变成规则，再删规则

其他的最优属性标准，惩罚值多（\(D\) 大）的属性：

  • 增益属性：\(GainRatio(S,A)=Gain(S,A)/SplitInformation(S,A)\)，\(SplitInformation(S,A)=\sum_{v\in D}-|S_v|/|D|\log(|S_v|/|D|)\)；启发式：可以仅对增益过高的属性做惩罚
  • Mantaras 基于距离的度量（选择最接近理想划分的划分）：设 \(A\) 和 \(B\) 都表示数据集的划分，\(P(A_iB_j)\) 表示一个数据划分在 \(A_i\) 类和 \(B_j\) 类的概率，条件熵 \(H(B|A)=\sum_{i,j}-P(A_iB_j)\log\dfrac{P(A_iB_j)}{P(A_i)}\)，联合熵 \(H(A,B)=\sum_{i,j}-P(A_iB_j)\log P(A_iB_j)\)，距离 \(d(A,B)=H(A|B)+H(B|A)\)，归一化 \(d_N(A,B)=d(A,B)/H(A,B)\)

随机森林

使用多个基本方法（随机选数据，随机选特征，多个决策树），最后投票或加权平均

朴素贝叶斯

事件 \(D=\{A_1,A_2,\cdots,A_n\}\)，\(h\in H\) 为假设，训练数据是一组 \(\left<D_i,h_i\right>\)，\(P(h)\) 称为先验概率，\(P(D|h)\) 为似然度，\(P(h|D)\) 为后验概率

贝叶斯公式 \[ P(h|D)=\frac{P(D|h)P(h)}{P(D)} \] 极大后验假设 \(h_{\text{MAP}}=\arg\max_{h}P(D|h)P(h)\)

极大似然假设 \(h_{ML}=\arg\max_{h}P(D|h)\)

朴素贝叶斯，假设 \(P(a_1,a_2,\cdots,a_n|h)=\prod_i P(a_i|h)\)，对于事件 \(X\) 的估计： \[ h_{NB}=\arg\max_h P(h)\prod_{a\in X} P(a|h) \] 对于 \(P(h)\) 和 \(P(a|h)\) 的 \(m\)-估计方法 \[ p=\frac{n_{\text{satisfy}}+mp_{priori}}{n+m} \]

SVM

固定经验风险，最小化置信界限 \[ g(\boldsymbol x)=\boldsymbol w^T\boldsymbol x + \boldsymbol b \] 对于支持向量 \(\boldsymbol x_s\)，\(g(\boldsymbol x_s)=\pm 1\)，两个类别的间隔 \(\dfrac{2}{\|\boldsymbol w\|}\)

等价于求 \(\|\boldsymbol w\|^2\) 最大，加入松弛变量 \(\boldsymbol \xi\) \[ \begin{aligned} \min_{\boldsymbol w, \boldsymbol b} \,\,& \|\boldsymbol w\|^2+\sum_{i=1}^n \xi_i \\ \mathrm{s.t.} \,\,& y_i(\boldsymbol w^T\boldsymbol x + \boldsymbol b) > 1-\xi_i \text{ and } \xi_i \ge 0 \end{aligned} \] 拉格朗日乘子 \(\boldsymbol \alpha\)，有对偶问题 \[ \begin{aligned} \max\,\,& f(\boldsymbol \alpha)=\sum _{i=1}^{n}\alpha_{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}\alpha_{i}(\mathbf {x} _{i}^{T}\mathbf {x} _{j})y_{j}\alpha_{j} \\ \text{s.t.}\,\,& \alpha_i\ge 0\text{ and } \sum_{i=1}^ny_i\alpha_i=0 \end{aligned} \] 是二次规划，可得 \(\mathbf {w} =\sum _{i=1}^{n}\alpha_{i}y_{i}\mathbf {x} _{i}\)

非线性可分问题，找一个到高维的映射 \(\varphi(x)\)，利用核函数 \(k(x_i,x_j)=\varphi(x_i)\cdot\varphi(x_j)\) 算高维内积

Mercer 条件：\(k(x,y)\) 描述高维内积的充要条件是对任意 \(g(x)\) 满足 \(\displaystyle \int g^2(x)\ \mathrm dx\) 存在，有 \(\displaystyle \iint k(x,y)g(x)g(y)\ \mathrm dx\mathrm dy\ge0\)

多项式核函数（二次）：\(\varphi(\boldsymbol x) = \left<x_n^2,\cdots,x_1^2,\sqrt2x_nx_{x-1},\cdots,\sqrt2x_2x_1,\sqrt{2c}x_n,\cdots,\sqrt{2c}x_1,c\right>\)，\(k(\boldsymbol x,\boldsymbol y)=(\boldsymbol x^T\boldsymbol y+c)^2\)

多项式核函数 \(k(\boldsymbol x,\boldsymbol y)=(\boldsymbol x^T\boldsymbol y+c)^d\)

径向基核函数（RBF）\(k(\boldsymbol x,\boldsymbol y)=\exp(-\|\boldsymbol x-\boldsymbol y\|^2/\sigma^2)\)

Sigmoid 核函数 \(k(\boldsymbol x,\boldsymbol y)=\tanh(-\gamma\boldsymbol x^T\boldsymbol y+c)\)

Logistic 回归

线性回归：\(f(\boldsymbol x)=\boldsymbol w^T\boldsymbol x\)；Logistic 回归：\(f(x)=\sigma(\boldsymbol w^T\boldsymbol x)\)，\(\sigma(x)=1/(1+e^{-x})\)

梯度下降求解，\(\dfrac{\partial f}{\partial w_i}=(f(x_i)-y_i)x_i\)

防止过拟合：损失加正则化项 \(\lambda\|\boldsymbol w\|\)，那么每次迭代会减小参数

聚类

硬聚类：任意两类没有共享数据点；软聚类：有

使类内相似度大，类间相似度小

层次聚类

自顶向下构造（分裂聚类），自底向上构造（凝聚聚类）

  • Linkage（仅凸且可度量）：每次合并最相似的簇；单链（SLink）：两个最近点；全链：两个最远点；均链：平均距离
  • CURE（任意形状可度量）：使用簇代表点中的最短距离，代表点是互相距离远的 \(c\) 个点，向簇中心收缩 \(a\) 倍；先采样，采样点均匀分布在分区，分区分别聚类，再一起聚类，再把剩下点分给簇

CHAMELEON（任意形状）：构造 \(k\)-近邻子图，划分成大量子图，然后层次聚类子图，设 \(EC(C_i,C_j)\) 为连接类 \(C_i\)，\(C_j\) 所有边的权重，\(EC(C_i)\) 为将 \(C_i\) 划分为两个相等子类的最小割集，相对互联性函数 \[ RI(C_i,C_j)=\frac{2\sum EC(C_i,C_j)}{\sum EC(C_i)+\sum EC(C_j)} \] 相对近似性函数 \[ RC(C_i,C_j)=\frac{\overline{EC(C_i,C_j)}}{\dfrac{|C_i|}{|C_i|+|C_j|}\overline{EC(C_i)}+\dfrac{|C_j|}{|C_i|+|C_j|}\overline{EC(C_j)}} \] 聚类使用的相似性度量：\(RI(C_i,C_j)\times RC^\alpha(C_i,C_j)\)

划分聚类

  • \(k\)-means：取中心
  • \(k\)-medoids：靠近中心的代表点

随机取 \(k\) 个代表点，然后分配并重新计算代表点直到收敛，评估是各点到各自中心点距离平方和（SSE）

密度聚类

  • DBSCAN：Eps 邻域内大于 MinPts 的点是核心点，否则若在核心点邻域点则是边界点；到另一个核心点距离小于 Eps 则密度可达；互相可达的核心点和其边界点是一簇
  • OPTICS：可以分辨密度不同簇，扫的时候维护第 MinPts 远的点距离，拿优先队列加进已扫点集；Reachablility 排序反应簇结构
  • DENCLUE：推导密度函数，拿局部极值点，各点往梯度方向合并

子空间聚类

自底向上 CLIQUE（维增长子空间聚类方法）：维数从低到高处理，对每个属性等分，则成超立方网格，网格内大于某个阈值的单元称为稠密单元，由 \(k-1\) 维稠密单元产生 \(k\) 维候选稠密单元，最后通过单元发现簇

自顶向下 PROCLUS（维规约子空间聚类方法）：初始化，采样出一个潜在中心点集合；迭代，用新点替代，距离是各子空间的平均；改进，对各中心确定特征子集

ANN 聚类

SOM 网络（Self Organizing Map）：输入层，竞争层。输入层与竞争层全连接，竞争层内部连接，对临近节点激活，远离节点抑制。每次寻找一个获胜节点激活。会把输入映射到一个空间（二维）空间上不同的区域表示不同类别。

神经网络

感知机 \(y=f(\boldsymbol w^T\boldsymbol x-\theta)\)，\(f\) 可以是阶跃函数也可以是 \(\mathrm {sgn}\)，单隐层感知机能表示凸区域，双隐层能表示任意形状

分类使用 softmax 将输出映射到概率 \(\text{softmax}(x_i)=\exp(x_i)/\sum_i\exp(x_i)\)

常用激活函数

\(\tanh(x)=\dfrac{\exp(x)-\exp(-x)}{\exp(x)+\exp(-x)}\)

\(\text{sigmoid}(x)=\dfrac{1}{1+\exp(-x)}\)

\(\text{ReLU}(x)=\max(0,x)\)

Backpropagation

假设总层数 \(L\)，代价 \(C\)，第 \(l\) 层输入 \(x^l\)，对应 \(\delta^l=\dfrac{\partial C}{\partial x^l}\)，算子输出 \(z^l\)，激活输出 \(x^{l+1}=\sigma(z^l)\)

最后一层 \(\delta^L=\Delta C\cdot \sigma'(z^L)\)

线性层 \(z^l=wx^l+b^l\) \[ \begin{cases} \delta^l=(w^{l})^T\delta^{l+1}\cdot\sigma'(z^l) \\ \dfrac{\partial C}{\partial b^l}=\delta^{l+1} \\ \dfrac{\partial C}{\partial w^l}=x^l\delta^{l+1} \end{cases} \] 卷积层 \(z^l=x^l\otimes h^l\) \[ \begin{cases} \delta^l=\delta^{l+1}\otimes \text{ROT}_{180}(h^l)\cdot\sigma'(z^l) \\ \dfrac{\partial C}{\partial h^l}=\delta^{l+1}\otimes x^l \end{cases} \]

CNN

LeNet and AlexNet：

Comparison_image_neural_networks

AlexNet 可多 GPU，不增 Channels 的卷积可以并行

Inception

来自 GoogleLeNet，拿不同的层卷，然后叠起来

Inception

Residule

残差网络

BasicBlock 两个 \(3\times3\) 卷积

Bottoleneck \(1\times1\times2^n;3\times3\times2^n;1\times1\times2^{n+1}\)

两种单元都计算残差

RNN

每层输入 \(x^L_t\)，输出 \(x^{L+1}_t=\sigma(z^L_t)\)，权重 \(w^L\)，循环权重 \(u^L\) \[ z^L_t=w^Lx^L_t+u^L\sigma(z^L_{t-1}) \] BP Through Time：反向传播，沿着时间倒序给自己传播

BiRNN：双向 RNN，实际上是两个反向 RNN 拼起来

LSTM

LSTM_Cell.svg

输入门 \[ \begin{cases} i_t=\sigma(W_i[h_{t-1},x_t]+b_i)\\ c_t=f_{t}c_{t-1}+i_t\tanh(W_C[h_{t-1},x_t]+b_C) \end{cases} \] 输出门 \[ \begin{cases} o_t=\sigma(W_o[h_{t-1},x_t]+b_o)\\ h_t=o_t\tanh(c_t) \end{cases} \] 遗忘门 \[ f_t=\sigma(W_f[h_{t-1},x_t]+b_f) \]

NLP

词向量表示

  • One-Hot：词典中的位置
  • 共现矩阵：把相邻的词所在词典中的位置也加一
  • SVD：对共现矩阵奇异值分解
  • 分布式表示：将词映射到低维空间，此时距离产生意义
  • NNLM：权重矩阵将 One-Hot 映射到低维向量后拼接 \(n\) 个
  • Word2Vec，上下文 \(2m\) 窗口：
    • CBOW，上下文预测当前值，输入词向量序列由一个周围词矩阵乘再平均，softmax 输出每个词的概率
    • Skip-gram，当前值预测上下文
  • Attention：计算 query 和 key 的相似性，归一化后对 values 加权求和

智能优化方法

遗传算法（GA）：选择，交叉，变异

蚁群算法，\(p\) 蚂蚁 \(k\) 在 \(t\) 时刻从位置 \(i\) 移动到位置 \(j\) 的概率，\(\tau\) 是信息素， \(\eta\) 是启发式（能见度），各自有权重 \[ p_{ij}^k(t)=\frac{\tau_{ij}^\alpha(t)+\eta_{ij}^\beta(t)}{\sum_{s\in Reachable(j)}\tau_{is}^\alpha(t)+\eta_{is}^\beta(t)} \] 信息素更新 \[ \tau_{ij}(t+1)=\rho\tau_{ij}(t)+\sum_k \frac{Q}{\eta_k(t)} \] 粒子群算法（PSO）：每步更新速度和位移，速度向自己曾经到过的最优位置和整个群体到过的最优位置迭代；惯性可以逐步减少避免震荡

自适应协方差矩阵进化（CMAES）：进化的目标是找到一个分布 \(P_\theta(X)\)，\(\theta\) 是参数，使 \(f(x)\) 较优。将 \(P_\theta\) 建模为多维高斯。每步调整均值（最优子群加权平均）、协方差矩阵、全局步长